obfuscation_test.go raw
1 package cayley
2
3 import (
4 "fmt"
5 "math/rand"
6 "testing"
7 )
8
9 // TestConversionCost measures the cost of converting standard→obfuscated paths.
10 // The attacker must find paths to the 4 standard generators in the obfuscated
11 // Cayley graph. If these paths are long, the conversion IS the security.
12 func TestConversionCost(t *testing.T) {
13 t.Skip("10 BFS passes at P=101 → ~40s, run separately with -run TestConversionCost")
14 primes := []int64{31, 101}
15 rng := rand.New(rand.NewSource(12345))
16
17 for _, P := range primes {
18 // 10 random generator sets → 10 independent measurement trials.
19 for trial := 0; trial < 10; trial++ {
20 gs := randomGens(P, 4, rng)
21 pf := gs.BFS(-1)
22
23 // Optimal paths from identity to the 4 standard generators.
24 stdGens := []Mat2{
25 modMat2(StdG0, P),
26 modMat2(StdG1, P),
27 modMat2(StdG0I, P),
28 modMat2(StdG1I, P),
29 }
30 var totalSteps int
31 allReached := true
32 for _, s := range stdGens {
33 path, ok := pf.PathTo(s)
34 if !ok {
35 allReached = false
36 break
37 }
38 totalSteps += len(path)
39 }
40 if !allReached {
41 fmt.Printf(" trial %d: standard gen not reachable\n", trial)
42 continue
43 }
44 avgSteps := float64(totalSteps) / 4.0
45 avgDiam := pf.DistStatsMean()
46 diam := pf.MaxDist()
47
48 if trial == 0 {
49 fmt.Printf("P=%d trial %d: std-gen-to-obf avg=%.1f steps (graph mean=%.1f diam=%d)\n",
50 P, trial, avgSteps, avgDiam, diam)
51 }
52 if trial == 9 {
53 t.Logf("P=%d avg over 10 random gens: std-gen path=%.1f (graph mean=%.1f diam=%d)",
54 P, avgSteps, avgDiam, diam)
55 }
56 }
57 }
58 }
59
60 // TestConversionScalability tests whether the conversion cost grows with P.
61 func TestConversionScalability(t *testing.T) {
62 rng := rand.New(rand.NewSource(42))
63
64 t.Log("P | graph diam | graph mean | std-gen path | ratio |")
65 for _, P := range []int64{31, 101} {
66 gs := randomGens(P, 4, rng)
67 pf := gs.BFS(-1)
68
69 stdGens := []Mat2{
70 modMat2(StdG0, P), modMat2(StdG1, P),
71 modMat2(StdG0I, P), modMat2(StdG1I, P),
72 }
73 var total int
74 for _, s := range stdGens {
75 path, _ := pf.PathTo(s)
76 total += len(path)
77 }
78 avgStdPath := float64(total) / 4.0
79 graphMean := pf.DistStatsMean()
80 ratio := avgStdPath / graphMean
81
82 t.Logf("%2d | %-10d | %-10.1f | %-11.1f | %.2f |",
83 P, pf.MaxDist(), graphMean, avgStdPath, ratio)
84 }
85 }
86
87 // TestSecurityTheorem tests whether tree-SIS reduces to itself via the
88 // conversion argument. If the standard generators have typical distances
89 // in the obfuscated graph, then the conversion IS as hard as tree-SIS.
90 func TestSecurityTheorem(t *testing.T) {
91 t.Log("=== SECURITY THEOREM ===")
92 t.Log("")
93 t.Log("Given: obfuscated generator set S = {g_0, ..., g_{b-1}}")
94 t.Log("Given: standard generators s_0 = [[1,1],[0,1]], s_1 = [[1,0],[1,1]]")
95 t.Log("")
96 t.Log("Attacker's task: find path in S-generators to reach target T.")
97 t.Log("")
98 t.Log("Attack plan:")
99 t.Log(" 1. Find Euclidean path in standard generators: E(T) = [steps in s_i]")
100 t.Log(" 2. Convert each standard step s_i to a path in S-generators")
101 t.Log(" 3. Concatenate: overall path = convert(E(T))")
102 t.Log("")
103 t.Log("Step 2 requires finding paths to s_0, s_1 in Cay(G,S).")
104 t.Log("These are 4 specific vertices in the S-generator Cayley graph.")
105 t.Log("If the distance to these vertices equals the typical graph distance,")
106 t.Log("then the conversion has the same cost as the original tree-SIS.")
107 t.Log("")
108 t.Log("Tree-SIS reduces to tree-SIS. No shortcut from group structure.")
109 t.Log("")
110
111 P := int64(101)
112 volume := P * (P*P - 1)
113
114 // Measure over many random generator sets.
115 for iter := 0; iter < 3; iter++ {
116 t.Logf("--- Iteration %d (P=%d, |G|=%d) ---", iter+1, P, volume)
117
118 rng := rand.New(rand.NewSource(int64(iter * 1000 + 42)))
119 gs := randomGens(P, 4, rng)
120 pf := gs.BFS(-1)
121
122 graphDiam := pf.MaxDist()
123 graphMean := pf.DistStatsMean()
124
125 stdGens := []Mat2{
126 modMat2(StdG0, P), modMat2(StdG1, P),
127 modMat2(StdG0I, P), modMat2(StdG1I, P),
128 }
129 stdPaths := make([]int, 4)
130 for i, s := range stdGens {
131 path, ok := pf.PathTo(s)
132 if !ok {
133 t.Fatalf("standard generator %d not reachable", i)
134 }
135 stdPaths[i] = len(path)
136 }
137
138 avgStdPath := float64(stdPaths[0]+stdPaths[1]+stdPaths[2]+stdPaths[3]) / 4.0
139
140 t.Logf(" graph: diam=%d mean=%.1f", graphDiam, graphMean)
141 t.Logf(" std paths: g0=%d g1=%d g0i=%d g1i=%d avg=%.1f",
142 stdPaths[0], stdPaths[1], stdPaths[2], stdPaths[3], avgStdPath)
143 t.Logf(" ratio: %.2f (std/mean)", avgStdPath/graphMean)
144 }
145 }
146