1 package cayley
2 3 import (
4 "math"
5 "math/rand"
6 "testing"
7 )
8 9 // TrapdoorTable stores precomputed paths from root to M vertices.
10 // The public key is the generator set. The trapdoor is the path table.
11 type TrapdoorTable struct {
12 GS *GeneratorSet
13 Paths map[Mat2][]int8 // vertex → path from ID
14 M int // precomputed table size
15 }
16 17 // BuildTrapdoor precomputes paths to M random vertices using BFS from root.
18 func BuildTrapdoor(gs *GeneratorSet, M int) *TrapdoorTable {
19 pf := gs.BFS(-1) // BFS to find optimal paths to ALL vertices (one-time cost)
20 21 // Randomly select M vertices to keep in the table.
22 rng := rand.New(rand.NewSource(42))
23 allKeys := make([]Mat2, 0, len(pf.Dist))
24 for k := range pf.Dist {
25 allKeys = append(allKeys, k)
26 }
27 rng.Shuffle(len(allKeys), func(i, j int) {
28 allKeys[i], allKeys[j] = allKeys[j], allKeys[i]
29 })
30 31 tt := &TrapdoorTable{
32 GS: gs,
33 Paths: make(map[Mat2][]int8, M),
34 M: M,
35 }
36 for i := 0; i < M && i < len(allKeys); i++ {
37 path, ok := pf.PathTo(allKeys[i])
38 if ok {
39 tt.Paths[allKeys[i]] = path
40 }
41 }
42 return tt
43 }
44 45 // Sign attempts to sign a target vertex using the trapdoor table.
46 // Returns (path, found) where found indicates whether the target was in the table.
47 func (tt *TrapdoorTable) Sign(target Mat2) ([]int8, bool) {
48 path, ok := tt.Paths[target]
49 return path, ok
50 }
51 52 // Coverage returns the fraction of |G| covered by the table.
53 func (tt *TrapdoorTable) Coverage() float64 {
54 gs := tt.GS
55 volume := gs.P * (gs.P*gs.P - 1)
56 return float64(tt.M) / float64(volume)
57 }
58 59 func TestTrapdoorHitRate(t *testing.T) {
60 primes := []int64{31, 101}
61 rng := rand.New(rand.NewSource(77))
62 63 for _, P := range primes {
64 gs := randomGens(P, 4, rng)
65 volume := P * (P*P - 1)
66 67 // Vary table size M.
68 for _, M := range []int{100, 500, 1000, 5000, 10000} {
69 if M > int(volume)*9/10 {
70 continue
71 }
72 tt := BuildTrapdoor(gs, M)
73 coverage := float64(M) / float64(volume) * 100
74 75 // Measure hit rate: generate random targets, count table matches.
76 hits := 0
77 trials := 5000
78 if M < 1000 {
79 trials = 1000
80 }
81 for i := 0; i < trials; i++ {
82 target := randomSL2Fast(P, rng)
83 if _, ok := tt.Sign(target); ok {
84 hits++
85 }
86 }
87 hitRate := float64(hits) / float64(trials) * 100
88 89 if M <= 1000 || M == 10000 || (P == 31 && M == 5000) {
90 t.Logf("P=%d M=%d/%d (%.2f%%): hit rate=%.2f%% (%d/%d)",
91 P, M, volume, coverage, hitRate, hits, trials)
92 }
93 }
94 }
95 }
96 97 // TestTrapdoorSigningCost measures the path length of trapdoor signatures
98 // vs BFS optimal. When the target is in the table, the trapdoor path IS
99 // the BFS optimal path — no degradation.
100 func TestTrapdoorSigningCost(t *testing.T) {
101 P := int64(101)
102 rng := rand.New(rand.NewSource(99))
103 gs := randomGens(P, 4, rng)
104 pf := gs.BFS(-1) // optimal reference
105 106 M := 10000
107 tt := BuildTrapdoor(gs, M)
108 109 // Measure 100 random targets: BFS optimal length vs trapdoor length.
110 var optTotal, trapTotal int
111 n := 0
112 for i := 0; i < 100; i++ {
113 target := randomSL2Fast(P, rng)
114 optPath, _ := pf.PathTo(target)
115 trapPath, found := tt.Sign(target)
116 117 if !found {
118 continue // not in table → can't sign (measurement: hit rate is coverage × |G|)
119 }
120 optTotal += len(optPath)
121 trapTotal += len(trapPath)
122 n++
123 }
124 125 if n > 0 {
126 optMean := float64(optTotal) / float64(n)
127 trapMean := float64(trapTotal) / float64(n)
128 t.Logf("P=%d M=%d n=%d:", P, M, n)
129 t.Logf(" BFS optimal mean: %.1f steps", optMean)
130 t.Logf(" Trapdoor mean: %.1f steps", trapMean)
131 t.Logf(" Ratio: %.2f (trapdoor = optimal when target in table)", trapMean/optMean)
132 }
133 }
134 135 // TestTrapdoorKeygenCost measures the one-time cost of building the trapdoor.
136 func TestTrapdoorKeygenCost(t *testing.T) {
137 primes := []int64{31, 101}
138 139 for _, P := range primes {
140 volume := P * (P*P - 1)
141 142 // Keygen cost: BFS over the ENTIRE Cayley graph.
143 // This is O(|G|) — one-time at keygen. The trapdoor is a subset of the BFS results.
144 t.Logf("P=%d |G|=%d: BFS to build path table (one-time keygen cost)...", P, volume)
145 // BFS already done in BuildTrapdoor — time is captured by the BFS enumeration test.
146 }
147 }
148 149 // TestTrapdoorScaling estimates production parameters by extrapolation.
150 func TestTrapdoorScaling(t *testing.T) {
151 t.Log("=== TRAPDOOR PATH TABLE SCALING ===")
152 t.Log("")
153 t.Log("The trapdoor is a precomputed path table. Keygen runs BFS to find")
154 t.Log("optimal paths to all vertices, then keeps M entries.")
155 t.Log("")
156 t.Log("At production scale (P~2^216):")
157 t.Log(" |SL(2,Z_P)| = P^3 ≈ 2^648 — BFS infeasible (exponential)")
158 t.Log(" Keygen must use a DIFFERENT method:")
159 t.Log(" - Signer samples M random walks of length D from root")
160 t.Log(" - Records endpoints and paths")
161 t.Log(" - Table size M determines hit rate")
162 t.Log("")
163 t.Log(" For b=8 generators, diameter ≈ 1.3×log_b(|G|) ≈ 281 steps")
164 t.Log(" Each random walk of length D covers 1 vertex")
165 t.Log(" To cover 0.1% of |G|: M = 0.001×2^648 ≈ 2^638 — infeasible")
166 t.Log("")
167 t.Log(" The naive path table is NOT a viable trapdoor at production scale.")
168 t.Log(" The trapdoor must give the signer a way to reach MANY vertices")
169 t.Log(" from FEW precomputed paths — not a 1:1 table.")
170 t.Log("")
171 172 // Demonstrate the combinatorial explosion.
173 b := 8
174 t.Logf("With b=%d generators, each table entry enables reaching ALL vertices", b)
175 t.Logf("reachable via PRODUCTS of that entry with other entries.")
176 t.Logf("")
177 178 // How many unique vertices can be reached by products of k table entries?
179 for k := 1; k <= 6; k++ {
180 products := math.Pow(float64(b), float64(k))
181 t.Logf(" k=%d: b^k = %.0f unique products", k, products)
182 }
183 t.Logf("")
184 t.Logf("With M=1000 table entries, the signer can reach b^D vertices precisely")
185 t.Logf("(all walks of length D). The table is a BASIS of SHORT PATHS, not a")
186 t.Logf("lookup of endpoints. The signer decomposes the target into combinations")
187 t.Logf("of basis paths. This IS tree-SIS but with precomputed short walks.")
188 t.Logf("")
189 t.Logf("The trapdoor reduces tree-SIS to a CLOSER-TO-TARGET decomposition:")
190 t.Logf(" 1. Given target T, find the closest table entry e_i (by graph distance)")
191 t.Logf(" 2. Compose: signature = path_to(e_i) + short_correction_jump(e_i, T)")
192 t.Logf(" 3. The correction jump is short because e_i is close to T")
193 t.Logf("")
194 t.Logf("At production scale: the table entries are carefully chosen ANCHOR")
195 t.Logf("points that cover the Cayley graph uniformly. The signer's advantage")
196 t.Logf("comes from knowing these anchor positions and their shortest paths.")
197 t.Logf("The attacker must discover them from scratch.")
198 }
199