multipath_test.go raw

   1  package cayley
   2  
   3  import (
   4  	"math/rand"
   5  	"testing"
   6  )
   7  
   8  // MultiPathSig signs a target using k parallel paths. The signer has a
   9  // trapdoor (generative basis). Splits target into k factors: first k-1
  10  // are random trapdoor paths (short), last factor uses Euclidean+conversion.
  11  func MultiPathSign(target Mat2, gb *GenerativeBasis, k int, rng *rand.Rand) [][]int8 {
  12  	P := gb.GS.P
  13  	gs := gb.GS
  14  	paths := make([][]int8, k)
  15  
  16  	// k-1 trapdoor paths (random short walks).
  17  	product := ID()
  18  	for i := 0; i < k-1; i++ {
  19  		depth := int(3 + rng.Intn(5)) // random depth 3-7
  20  		p := randomWalk(gs, depth, rng)
  21  		paths[i] = p
  22  		product = gs.Walk(product, p)
  23  	}
  24  
  25  	// Last factor: residual = (product)^{-1} · target.
  26  	residual := product.Inv(P).Mul(target, P)
  27  	euc, err := EuclideanDecomposition(residual, P)
  28  	if err != nil {
  29  		return nil
  30  	}
  31  	converted := gb.Sign(euc)
  32  	if converted == nil {
  33  		return nil
  34  	}
  35  	paths[k-1] = converted
  36  
  37  	return paths
  38  }
  39  
  40  // MultiPathVerify checks k paths whose product equals target.
  41  func MultiPathVerify(gs *GeneratorSet, paths [][]int8, target Mat2) bool {
  42  	v := ID()
  43  	for _, p := range paths {
  44  		v = gs.Walk(v, p)
  45  	}
  46  	return v.Eq(target)
  47  }
  48  
  49  // TestMultiPathSign measures the blowup factor for k=1,2,3.
  50  func TestMultiPathSign(t *testing.T) {
  51  	P := int64(31)
  52  	rng := rand.New(rand.NewSource(42))
  53  	gs := randomGens(P, 4, rng)
  54  	gb := BuildGenerativeBasis(gs)
  55  	if gb == nil {
  56  		t.Fatal("standard gens not reachable")
  57  	}
  58  	pf := gb.GPF
  59  
  60  	for _, k := range []int{1, 2, 3, 5, 10} {
  61  		nSamples := 50
  62  		var totalSteps int
  63  		var totalTrap int
  64  		var totalEuc int
  65  		n := 0
  66  
  67  		for i := 0; i < nSamples; i++ {
  68  			target := randomSL2Fast(P, rng)
  69  
  70  			paths := MultiPathSign(target, gb, k, rng)
  71  			if paths == nil { continue }
  72  
  73  			if !MultiPathVerify(gs, paths, target) {
  74  				t.Logf("k=%d: verification failed", k)
  75  				continue
  76  			}
  77  
  78  		steps := 0
  79  		for _, p := range paths {
  80  			steps += len(p)
  81  		}
  82  
  83  		totalSteps += steps
  84  			totalTrap += len(paths[0]) // first is trapdoor
  85  			if k > 1 {
  86  				totalEuc += len(paths[k-1]) // last is Euclidean-converted
  87  			}
  88  			n++
  89  		}
  90  
  91  		if n == 0 { t.Logf("k=%d: no samples", k); continue }
  92  		mean := float64(totalSteps) / float64(n)
  93  		trapMean := float64(totalTrap) / float64(n)
  94  		eucMean := float64(totalEuc) / float64(n)
  95  
  96  		t.Logf("k=%d n=%d: sig=%.0f steps (trap=%.0f euc=%.0f) opt~=%.0f",
  97  			k, n, mean, trapMean, eucMean, float64(pf.DistStatsMean()))
  98  	}
  99  }
 100  
 101  // TestMultiPathSecurity reports the MIM cost for k-path signatures.
 102  func TestMultiPathSecurity(t *testing.T) {
 103  	t.Log("=== MULTI-PATH SECURITY ===")
 104  	t.Log("")
 105  	t.Log("For k paths of length D each (b generators):")
 106  	t.Log("  Total path encoding: k·D·log₂(b) bits")
 107  	t.Log("  MIM cost: b^{kD/2} (product of k forward/backward half-sets)")
 108  	t.Log("")
 109  
 110  	for _, k := range []int{1, 2, 3, 4, 5} {
 111  		// Solve for D such that b^{kD/2} = 2^{128}
 112  		// kD/2 × log₂(b) = 128
 113  		// kD = 256 / log₂(b) = 256/3 ≈ 85.3
 114  		// D = 85.3/k
 115  		D := 85.3 / float64(k)
 116  		totalBits := float64(k) * D * 3.0
 117  		totalBytes := totalBits / 8.0
 118  		t.Logf("  k=%d: D=%.0f steps/path, total=%d steps, %.0f bytes (path) + 43B (target+salt) = %.0f bytes",
 119  			k, D, int(k*int(D)), totalBytes, totalBytes+43)
 120  	}
 121  
 122  	t.Log("")
 123  	t.Log("The security is fixed by kD = constant. Multi-path changes")
 124  	t.Log("the number of paths but NOT the total encoding length.")
 125  	t.Log("The lock analogy benefit: eliminates local-search attacks.")
 126  	t.Log("MIM complexity unchanged for fixed security parameter.")
 127  }
 128