sigma_test.go raw
1 package ring
2
3 import (
4 "crypto/rand"
5 "testing"
6 )
7
8 // ─── vwidth.go tests ─────────────────────────────────────────────────────────
9
10 func TestSerializeBoundedUnsigned(t *testing.T) {
11 p := SmallGPVParams().Ring
12 orig := New(p)
13 for i := range orig.Coeffs {
14 orig.Coeffs[i] = uint32(i % 16)
15 }
16
17 data := SerializeBounded(orig, 4, false)
18 if len(data) != (p.N*4+7)/8 {
19 t.Fatalf("expected %d bytes, got %d", (p.N*4+7)/8, len(data))
20 }
21
22 restored := DeserializeBounded(p, data, 4, false)
23 if !Equal(orig, restored) {
24 t.Fatal("round-trip failed for unsigned bounded serialization")
25 }
26 }
27
28 func TestSerializeBoundedSigned(t *testing.T) {
29 p := SmallGPVParams().Ring
30 half := p.Q / 2
31 orig := New(p)
32 for i := range orig.Coeffs {
33 // Alternate positive and negative (centered form).
34 if i%2 == 0 {
35 orig.Coeffs[i] = uint32(i % 100)
36 } else {
37 orig.Coeffs[i] = p.Q - uint32(i%100) // centered negative
38 }
39 }
40
41 // Need enough bits for values up to 100.
42 data := SerializeBounded(orig, 8, true)
43 restored := DeserializeBounded(p, data, 8, true)
44 if !Equal(orig, restored) {
45 t.Fatal("round-trip failed for signed bounded serialization")
46 }
47
48 // Check the centered values are preserved.
49 for i := range orig.Coeffs {
50 var origCentered uint32
51 if orig.Coeffs[i] > half {
52 origCentered = p.Q - orig.Coeffs[i]
53 } else {
54 origCentered = orig.Coeffs[i]
55 }
56 var restoredCentered uint32
57 if restored.Coeffs[i] > half {
58 restoredCentered = p.Q - restored.Coeffs[i]
59 } else {
60 restoredCentered = restored.Coeffs[i]
61 }
62 if origCentered != restoredCentered {
63 t.Fatalf("coefficient %d: centered value %d vs %d", i, origCentered, restoredCentered)
64 }
65 }
66 }
67
68 // ─── gpv_gadget.go tests ──────────────────────────────────────────────────────
69
70 func TestGPVGadgetSignVerify(t *testing.T) {
71 gp := SmallGPVParams()
72 pk, sk := GPVGadgetKeyGen(gp)
73
74 msg := []byte("hello gadget world")
75 sig := GPVGadgetSign(sk, msg)
76
77 if !GPVGadgetVerify(pk, msg, sig) {
78 t.Fatal("valid gadget signature rejected")
79 }
80 }
81
82 func TestGPVGadgetWrongMessage(t *testing.T) {
83 gp := SmallGPVParams()
84 pk, sk := GPVGadgetKeyGen(gp)
85
86 msg := []byte("correct message")
87 sig := GPVGadgetSign(sk, msg)
88
89 if GPVGadgetVerify(pk, []byte("wrong message"), sig) {
90 t.Fatal("gadget signature verified for wrong message")
91 }
92 }
93
94 func TestGPVGadgetWrongKey(t *testing.T) {
95 gp := SmallGPVParams()
96 _, sk1 := GPVGadgetKeyGen(gp)
97 pk2, _ := GPVGadgetKeyGen(gp)
98
99 msg := []byte("test message")
100 sig := GPVGadgetSign(sk1, msg)
101
102 if GPVGadgetVerify(pk2, msg, sig) {
103 t.Fatal("gadget signature verified with wrong public key")
104 }
105 }
106
107 func TestGPVGadgetMultipleMessages(t *testing.T) {
108 gp := SmallGPVParams()
109 pk, sk := GPVGadgetKeyGen(gp)
110
111 messages := []string{
112 "",
113 "a",
114 "hello gadget",
115 "lattice-based cryptography with MP12 trapdoor",
116 }
117
118 for _, msg := range messages {
119 sig := GPVGadgetSign(sk, []byte(msg))
120 if !GPVGadgetVerify(pk, []byte(msg), sig) {
121 t.Fatalf("gadget verification failed for message %q", msg)
122 }
123 }
124 }
125
126 func TestGPVGadgetDeterminism(t *testing.T) {
127 gp := SmallGPVParams()
128 pk, sk := GPVGadgetKeyGen(gp)
129
130 msg := []byte("same message twice")
131 sig1 := GPVGadgetSign(sk, msg)
132 sig2 := GPVGadgetSign(sk, msg)
133
134 if !GPVGadgetVerify(pk, msg, sig1) || !GPVGadgetVerify(pk, msg, sig2) {
135 t.Fatal("valid gadget signatures rejected")
136 }
137
138 // Gadget signatures should produce the same E2 (deterministic decomposition)
139 // but different E1 (due to fresh perturbation).
140 e1Equal := true
141 for i := range sig1.E1.Coeffs {
142 if sig1.E1.Coeffs[i] != sig2.E1.Coeffs[i] {
143 e1Equal = false
144 break
145 }
146 }
147 if e1Equal {
148 t.Fatal("two gadget signatures have identical E1 — perturbation missing")
149 }
150 }
151
152 // ─── sigma.go: Phase 2 — interactive sigma protocol ───────────────────────────
153
154 func TestSigmaInteractive(t *testing.T) {
155 gp := SmallGPVParams()
156 pk, sk := GPVKeyGen(gp)
157
158 rng := rand.Reader
159
160 // Retry loop for rejection sampling (can fail ~1-5% of the time).
161 var z *Poly
162 var ok bool
163 for attempt := 0; attempt < 20; attempt++ {
164 w, y := Commit(pk, rng)
165 c := Challenge(pk.P.Ring, rng)
166 z, ok = Respond(sk, y, c)
167 if ok {
168 if !VerifyInteractive(pk, w, c, z) {
169 t.Fatal("valid interactive sigma proof rejected")
170 }
171 return
172 }
173 }
174 t.Fatal("rejection sampling failed after 20 attempts")
175 }
176
177 func TestSigmaInteractiveWrongKey(t *testing.T) {
178 gp := SmallGPVParams()
179 pk1, sk1 := GPVKeyGen(gp)
180 pk2, _ := GPVKeyGen(gp)
181 _ = pk2
182
183 rng := rand.Reader
184
185 w, y := Commit(pk1, rng)
186 c := Challenge(pk1.P.Ring, rng)
187 z, ok := Respond(sk1, y, c)
188 if !ok {
189 t.Fatal("rejection sampling failed")
190 }
191
192 // Verify with wrong key — should fail because BPoly doesn't match.
193 if VerifyInteractive(pk2, w, c, z) {
194 t.Fatal("interactive proof verified with wrong key")
195 }
196 }
197
198 // ─── sigma.go: Phase 3 — non-interactive (Fiat-Shamir) proof ─────────────────
199
200 func TestSigmaNonInteractive(t *testing.T) {
201 gp := SmallGPVParams()
202 pk, sk := GPVKeyGen(gp)
203
204 proof := Prove(sk, nil)
205
206 if !VerifySigma(pk, nil, proof) {
207 t.Fatal("valid non-interactive sigma proof rejected")
208 }
209 }
210
211 func TestSigmaNonInteractiveWithContext(t *testing.T) {
212 gp := SmallGPVParams()
213 pk, sk := GPVKeyGen(gp)
214
215 context := []byte("session-12345")
216 proof := Prove(sk, context)
217
218 if !VerifySigma(pk, context, proof) {
219 t.Fatal("valid context-bound sigma proof rejected")
220 }
221
222 // Wrong context should fail.
223 if VerifySigma(pk, []byte("wrong-context"), proof) {
224 t.Fatal("proof verified with wrong context")
225 }
226 }
227
228 func TestSigmaNonInteractiveWrongKey(t *testing.T) {
229 gp := SmallGPVParams()
230 _, sk := GPVKeyGen(gp)
231 pk2, _ := GPVKeyGen(gp)
232
233 proof := Prove(sk, nil)
234
235 if VerifySigma(pk2, nil, proof) {
236 t.Fatal("proof verified with wrong key")
237 }
238 }
239
240 func TestSigmaProofMarshal(t *testing.T) {
241 gp := SmallGPVParams()
242 p := gp.Ring
243 _, sk := GPVKeyGen(gp)
244
245 proof := Prove(sk, nil)
246
247 data := MarshalSigmaProof(proof)
248 restored := UnmarshalSigmaProof(p, data)
249
250 if restored == nil {
251 t.Fatal("unmarshal returned nil")
252 }
253
254 if !Equal(proof.Z, restored.Z) {
255 t.Fatal("Z not preserved after marshal round-trip")
256 }
257 if !Equal(proof.C, restored.C) {
258 t.Fatal("C not preserved after marshal round-trip")
259 }
260 }
261
262 // ─── sigma.go: Phase 4 — randomized GPV signature proof ──────────────────────
263
264 func TestRandomizeGPVSignatureRoundTrip(t *testing.T) {
265 gp := SmallGPVParams()
266 pk, sk := GPVKeyGen(gp)
267
268 msg := []byte("age>=18")
269 sig := GPVSign(sk, msg)
270 if !GPVVerify(pk, msg, sig) {
271 t.Fatal("base GPV signature must verify")
272 }
273
274 rng := rand.Reader
275 proof := RandomizeGPVSignature(pk, sig, msg, rng)
276
277 if !VerifyRandomizedGPVSignature(pk, msg, proof) {
278 t.Fatal("valid randomized signature rejected")
279 }
280 }
281
282 func TestRandomizeGPVSignatureWrongMessage(t *testing.T) {
283 gp := SmallGPVParams()
284 pk, sk := GPVKeyGen(gp)
285
286 msg := []byte("real-claim")
287 sig := GPVSign(sk, msg)
288
289 rng := rand.Reader
290 proof := RandomizeGPVSignature(pk, sig, msg, rng)
291
292 if VerifyRandomizedGPVSignature(pk, []byte("wrong-claim"), proof) {
293 t.Fatal("randomized signature verified with wrong message")
294 }
295 }
296
297 func TestRandomizeGPVSignatureWrongKey(t *testing.T) {
298 gp := SmallGPVParams()
299 pk1, sk1 := GPVKeyGen(gp)
300 pk2, _ := GPVKeyGen(gp)
301
302 msg := []byte("test-message")
303 sig := GPVSign(sk1, msg)
304
305 rng := rand.Reader
306 proof := RandomizeGPVSignature(pk1, sig, msg, rng)
307
308 // Verify with pk2 should fail.
309 if VerifyRandomizedGPVSignature(pk2, msg, proof) {
310 t.Fatal("randomized signature verified with wrong public key")
311 }
312 }
313
314 func TestRandomizeGPVSignatureMultipleMessages(t *testing.T) {
315 gp := SmallGPVParams()
316 pk, sk := GPVKeyGen(gp)
317
318 messages := []string{
319 "age>=18",
320 "country=US",
321 "membership-level=gold",
322 }
323
324 rng := rand.Reader
325 for _, msg := range messages {
326 msgBytes := []byte(msg)
327 sig := GPVSign(sk, msgBytes)
328 proof := RandomizeGPVSignature(pk, sig, msgBytes, rng)
329 if !VerifyRandomizedGPVSignature(pk, msgBytes, proof) {
330 t.Fatalf("proof failed for message %q", msg)
331 }
332 }
333 }
334
335 func TestRandomizeGPVSignatureEmptyMessage(t *testing.T) {
336 gp := SmallGPVParams()
337 pk, sk := GPVKeyGen(gp)
338
339 msg := []byte("")
340 sig := GPVSign(sk, msg)
341 rng := rand.Reader
342 proof := RandomizeGPVSignature(pk, sig, msg, rng)
343
344 if !VerifyRandomizedGPVSignature(pk, msg, proof) {
345 t.Fatal("randomized signature failed for empty message")
346 }
347 }
348
349 func TestRandomizeGPVSignatureNotLinkable(t *testing.T) {
350 gp := SmallGPVParams()
351 pk, sk := GPVKeyGen(gp)
352
353 msg := []byte("same-message")
354 sig := GPVSign(sk, msg)
355 if !GPVVerify(pk, msg, sig) {
356 t.Fatal("base sig must verify")
357 }
358
359 rng := rand.Reader
360
361 // Two independent randomizations of the same signature.
362 proof1 := RandomizeGPVSignature(pk, sig, msg, rng)
363 proof2 := RandomizeGPVSignature(pk, sig, msg, rng)
364
365 // Both must verify.
366 if !VerifyRandomizedGPVSignature(pk, msg, proof1) {
367 t.Fatal("first randomization rejected")
368 }
369 if !VerifyRandomizedGPVSignature(pk, msg, proof2) {
370 t.Fatal("second randomization rejected")
371 }
372
373 // The randomized z' must be different (prevents linkability).
374 equal := true
375 for i := range proof1.ZPrime.Coeffs {
376 if proof1.ZPrime.Coeffs[i] != proof2.ZPrime.Coeffs[i] {
377 equal = false
378 break
379 }
380 }
381 if equal {
382 t.Fatal("two randomizations produced identical z' — not randomized")
383 }
384 }
385
386 func TestRandomizeGPVSignatureFalcon512(t *testing.T) {
387 gp := DefaultGPVParams()
388 pk, sk := GPVKeyGen(gp)
389
390 msg := []byte("age>=18")
391 sig := GPVSign(sk, msg)
392 if !GPVVerify(pk, msg, sig) {
393 t.Fatal("Falcon-512 base signature must verify")
394 }
395
396 rng := rand.Reader
397 proof := RandomizeGPVSignature(pk, sig, msg, rng)
398
399 if !VerifyRandomizedGPVSignature(pk, msg, proof) {
400 t.Fatal("Falcon-512 randomized signature rejected")
401 }
402 }
403
404 // ─── Benchmarks ───────────────────────────────────────────────────────────────
405
406 func BenchmarkGPVGadgetKeyGen(b *testing.B) {
407 gp := SmallGPVParams()
408 for range b.N {
409 GPVGadgetKeyGen(gp)
410 }
411 }
412
413 func BenchmarkGPVGadgetSign(b *testing.B) {
414 gp := SmallGPVParams()
415 _, sk := GPVGadgetKeyGen(gp)
416 msg := []byte("benchmark")
417 b.ResetTimer()
418 for range b.N {
419 GPVGadgetSign(sk, msg)
420 }
421 }
422
423 func BenchmarkGPVGadgetVerify(b *testing.B) {
424 gp := SmallGPVParams()
425 pk, sk := GPVGadgetKeyGen(gp)
426 msg := []byte("benchmark")
427 sig := GPVGadgetSign(sk, msg)
428 b.ResetTimer()
429 for range b.N {
430 GPVGadgetVerify(pk, msg, sig)
431 }
432 }
433
434 func BenchmarkSigmaProve(b *testing.B) {
435 gp := SmallGPVParams()
436 _, sk := GPVKeyGen(gp)
437 b.ResetTimer()
438 for range b.N {
439 Prove(sk, nil)
440 }
441 }
442
443 func BenchmarkSigmaVerify(b *testing.B) {
444 gp := SmallGPVParams()
445 pk, sk := GPVKeyGen(gp)
446 proof := Prove(sk, nil)
447 b.ResetTimer()
448 for range b.N {
449 VerifySigma(pk, nil, proof)
450 }
451 }
452