sigma.go raw
1 // Sigma protocol layer for lattice-based zero-knowledge proofs.
2 //
3 // Builds on the existing GPV signature infrastructure to provide:
4 //
5 // - Phase 2: Interactive sigma protocol for knowledge of a GPV secret key
6 // - Phase 3: Non-interactive (Fiat-Shamir) proof of key knowledge
7 // - Phase 4: Proof of knowledge of a valid GPV signature on a committed message
8 // (uses ring-inversion approach — requires large modulus)
9 //
10 // All proofs use the verification equation a·e1 + b·e2 = H(m) from the existing
11 // GPV key structure (single polynomial B = -A·R). The gadget key
12 // (GPVGadgetPublicKey with vector B) is NOT supported — its Σ B[i]·E2[i]
13 // verification is algebraically different and would require a separate protocol.
14 //
15 // Security: all proofs are HVZK (honest-verifier zero knowledge) via the standard
16 // sigma protocol paradigm. The Fiat-Shamir transform gives non-interactive proofs
17 // in the random oracle model.
18
19 package ring
20
21 import (
22 "crypto/rand"
23 "encoding/binary"
24 "io"
25
26 "golang.org/x/crypto/sha3"
27 )
28
29 // ─── Phase 2: Interactive sigma protocol ─────────────────────────────────────
30
31 // Commit generates the commitment w = a·y for random Gaussian y.
32 // Returns (w, y). The prover sends w to the verifier and keeps y secret.
33 func Commit(pk *GPVPublicKey, rng io.Reader) (*Poly, *Poly) {
34 p := pk.P.Ring
35 sigma := pk.P.Sigma
36 gs := NewGaussianSamplerFrom(sigma, rng)
37
38 y := gs.SamplePoly(p)
39 yNTT := y.Clone()
40 NTT(yNTT)
41
42 w := MulPointwise(pk.A, yNTT)
43 INTT(w)
44
45 return w, y
46 }
47
48 // Challenge generates a random short challenge polynomial.
49 // The challenge has τ=40 non-zero coefficients, each ±1.
50 func Challenge(p Params, rng io.Reader) *Poly {
51 c := New(p)
52 tau := 40
53 if tau > p.N {
54 tau = p.N / 2
55 }
56
57 positions := make([]int, p.N)
58 for i := range positions {
59 positions[i] = i
60 }
61
62 var buf [2]byte
63 for i := range tau {
64 io.ReadFull(rng, buf[:])
65 j := i + int(binary.LittleEndian.Uint16(buf[:]))%(p.N-i)
66 positions[i], positions[j] = positions[j], positions[i]
67
68 io.ReadFull(rng, buf[:1])
69 if buf[0]&1 == 0 {
70 c.Coeffs[positions[i]] = 1
71 } else {
72 c.Coeffs[positions[i]] = p.Q - 1
73 }
74 }
75 return c
76 }
77
78 // Respond computes the response z = y + r·c with rejection sampling.
79 // Returns (z, ok). If ok is false, the prover must retry with a fresh commitment.
80 func Respond(sk *GPVSecretKey, y, c *Poly) (*Poly, bool) {
81 sigma := sk.PK.P.Sigma
82
83 cNTT := c.Clone()
84 NTT(cNTT)
85
86 rNTT := sk.R.Clone()
87 NTT(rNTT)
88
89 rc := MulPointwise(rNTT, cNTT)
90 INTT(rc)
91
92 z := Add(y, rc)
93
94 zNorm := Norm(z)
95 bound := uint32(sigma * 1.5)
96 if zNorm > bound {
97 return z, false
98 }
99 return z, true
100 }
101
102 // VerifyInteractive checks a sigma protocol proof:
103 //
104 // 1. ||z||_∞ ≤ bound
105 // 2. a·z + b·c = w (mod q)
106 func VerifyInteractive(pk *GPVPublicKey, w, c, z *Poly) bool {
107 sigma := pk.P.Sigma
108
109 zNorm := Norm(z)
110 bound := uint32(sigma * 1.5)
111 if zNorm > bound {
112 return false
113 }
114
115 zNTT := z.Clone()
116 NTT(zNTT)
117 cNTT := c.Clone()
118 NTT(cNTT)
119
120 az := MulPointwise(pk.A, zNTT)
121 bc := MulPointwise(pk.B, cNTT)
122 wComputed := Add(az, bc)
123 INTT(wComputed)
124
125 return Equal(w, wComputed)
126 }
127
128 // ─── Phase 3: Non-interactive (Fiat-Shamir) proof of key knowledge ────────────
129
130 // SigmaProof is a non-interactive proof of GPV secret key knowledge.
131 type SigmaProof struct {
132 Z *Poly // response (short, rejection-sampled)
133 C *Poly // challenge (sparse, τ=40 ±1)
134 }
135
136 // hashChallenge computes c = H(transcript) using SHAKE256.
137 // Domain separated from hashToChallenge and hashMessageToTarget.
138 func hashChallenge(p Params, components [][]byte) *Poly {
139 h := sha3.NewShake256()
140 h.Write([]byte("gpv-sigma-proof-v1"))
141 for _, comp := range components {
142 h.Write(comp)
143 }
144
145 tau := 40
146 if tau > p.N {
147 tau = p.N / 2
148 }
149
150 c := New(p)
151 var buf [2]byte
152 positions := make([]int, p.N)
153 for i := range positions {
154 positions[i] = i
155 }
156
157 for i := range tau {
158 h.Read(buf[:])
159 j := i + int(binary.LittleEndian.Uint16(buf[:]))%(p.N-i)
160 positions[i], positions[j] = positions[j], positions[i]
161
162 h.Read(buf[:1])
163 if buf[0]&1 == 0 {
164 c.Coeffs[positions[i]] = 1
165 } else {
166 c.Coeffs[positions[i]] = p.Q - 1
167 }
168 }
169 return c
170 }
171
172 // Prove generates a non-interactive proof of GPV secret key knowledge.
173 // Uses Fiat-Shamir: c = H(w, context).
174 func Prove(sk *GPVSecretKey, context []byte) *SigmaProof {
175 return ProveFrom(sk, context, rand.Reader)
176 }
177
178 // ProveFrom generates a proof with the given randomness source.
179 func ProveFrom(sk *GPVSecretKey, context []byte, rng io.Reader) *SigmaProof {
180 p := sk.PK.P.Ring
181
182 for {
183 w, y := Commit(sk.PK, rng)
184
185 wSerialized := Serialize(w)
186 var components [][]byte
187 if len(context) > 0 {
188 components = [][]byte{wSerialized, context}
189 } else {
190 components = [][]byte{wSerialized}
191 }
192 c := hashChallenge(p, components)
193
194 z, ok := Respond(sk, y, c)
195 if ok {
196 return &SigmaProof{Z: z, C: c}
197 }
198 }
199 }
200
201 // VerifySigma checks a non-interactive proof of key knowledge.
202 func VerifySigma(pk *GPVPublicKey, context []byte, proof *SigmaProof) bool {
203 p := pk.P.Ring
204 z := proof.Z
205 c := proof.C
206
207 zNTT := z.Clone()
208 NTT(zNTT)
209 cNTT := c.Clone()
210 NTT(cNTT)
211
212 az := MulPointwise(pk.A, zNTT)
213 bc := MulPointwise(pk.B, cNTT)
214 w := Add(az, bc)
215 INTT(w)
216
217 wSerialized := Serialize(w)
218 var components [][]byte
219 if len(context) > 0 {
220 components = [][]byte{wSerialized, context}
221 } else {
222 components = [][]byte{wSerialized}
223 }
224 cExpected := hashChallenge(p, components)
225
226 if !Equal(c, cExpected) {
227 return false
228 }
229
230 sigma := pk.P.Sigma
231 bound := uint32(sigma * 1.5)
232 if Norm(z) > bound {
233 return false
234 }
235
236 return true
237 }
238
239 // MarshalSigmaProof serializes a SigmaProof to bytes.
240 // Challenge c is compressed as (position, sign) pairs.
241 // Response z is compressed via SerializeBounded at 12 bits/coeff.
242 func MarshalSigmaProof(proof *SigmaProof) []byte {
243 q := proof.C.params.Q
244 half := q / 2
245
246 cPairs := make([]byte, 0, 80)
247 for i, coeff := range proof.C.Coeffs {
248 if coeff != 0 {
249 absV := coeff
250 sign := byte(0)
251 if absV > half {
252 sign = 1
253 }
254 cPairs = append(cPairs, byte(i&0xFF), byte(i>>8), sign)
255 }
256 }
257
258 cData := cPairs
259 zData := SerializeBounded(proof.Z, 12, true)
260
261 out := make([]byte, 8+len(cData)+len(zData))
262 binary.LittleEndian.PutUint32(out[0:4], uint32(len(cData)))
263 copy(out[4:], cData)
264 binary.LittleEndian.PutUint32(out[4+len(cData):4+len(cData)+4], uint32(len(zData)))
265 copy(out[8+len(cData):], zData)
266 return out
267 }
268
269 // UnmarshalSigmaProof deserializes a SigmaProof from bytes.
270 func UnmarshalSigmaProof(p Params, data []byte) *SigmaProof {
271 if len(data) < 8 {
272 return nil
273 }
274 cLen := int(binary.LittleEndian.Uint32(data[0:4]))
275 if len(data) < 8+cLen {
276 return nil
277 }
278
279 cData := data[4 : 4+cLen]
280 zLen := int(binary.LittleEndian.Uint32(data[4+cLen : 4+cLen+4]))
281 if len(data) < 8+cLen+zLen {
282 return nil
283 }
284 zData := data[8+cLen : 8+cLen+zLen]
285
286 c := New(p)
287 for i := 0; i+2 < len(cData); i += 3 {
288 pos := uint16(cData[i]) | uint16(cData[i+1])<<8
289 sign := cData[i+2]
290 if pos < uint16(p.N) {
291 if sign == 0 {
292 c.Coeffs[pos] = 1
293 } else {
294 c.Coeffs[pos] = p.Q - 1
295 }
296 }
297 }
298
299 z := DeserializeBounded(p, zData, 12, true)
300
301 return &SigmaProof{Z: z, C: c}
302 }
303
304 // ─── Phase 4: Randomized GPV signature (signature-hiding, message-revealing) ──
305 //
306 // Randomizes the GPV signature response z by adding a Gaussian perturbation,
307 // and sends a commitment to the perturbation. This is coefficient-wise addition
308 // (not ring convolution), so no modulus wrapping occurs for any ring.
309 //
310 // Protocol:
311 //
312 // Prover has GPV signature (z, c) valid on m:
313 // w = A·z + B·c (GPV commitment)
314 // c = H(w, m) (Fiat-Shamir challenge)
315 //
316 // 1. Sample r_m ← D_σ (additive Gaussian randomizer)
317 // 2. Compute z' = z + r_m (randomized response)
318 // 3. Compute C = A·r_m (commitment to randomizer)
319 // 4. Proof: (z', c, C, m)
320 //
321 // Verifier:
322 // 1. w' = A·z' + B·c - C = A·(z+r_m) + B·c - A·r_m = A·z + B·c = w
323 // 2. c == H(w', m) ← original Fiat-Shamir binds proof to m
324 // 3. Norm(z') ≤ bound' ← increased bound accounts for r_m
325
326 // RandomizedSigProof is a randomized GPV signature.
327 // Hides (z) but reveals (c, m) to the verifier.
328 type RandomizedSigProof struct {
329 ZPrime *Poly // randomized z' = z + r_m
330 Chal *Poly // original challenge c (binds to m via Fiat-Shamir)
331 Commit *Poly // commitment C = A·r_m
332 }
333
334 // RandomizeGPVSignature randomizes a GPV signature to produce a hiding proof.
335 // The message m is required for the Fiat-Shamir challenge check.
336 func RandomizeGPVSignature(pk *GPVPublicKey, sig *GPVSignature, message []byte, rng io.Reader) *RandomizedSigProof {
337 p := pk.P.Ring
338 sigma := pk.P.Sigma
339 gs := NewGaussianSamplerFrom(sigma, rng)
340
341 z := sig.E1
342 c := sig.E2
343
344 rM := gs.SamplePoly(p)
345 zPrime := Add(z, rM)
346
347 rMNTT := rM.Clone()
348 NTT(rMNTT)
349 CNTT := MulPointwise(pk.A, rMNTT)
350 INTT(CNTT)
351
352 return &RandomizedSigProof{
353 ZPrime: zPrime,
354 Chal: c,
355 Commit: CNTT,
356 }
357 }
358
359 // VerifyRandomizedGPVSignature verifies a randomized GPV signature.
360 //
361 // Checks:
362 // 1. Norm(z') ≤ σ·1.5 + 13·σ (accounts for r_m)
363 // 2. w' = A·z' + B·c - C
364 // 3. c == H(w', m) (original Fiat-Shamir, binds to m)
365 func VerifyRandomizedGPVSignature(pk *GPVPublicKey, message []byte, proof *RandomizedSigProof) bool {
366 sigma := pk.P.Sigma
367 zPrime := proof.ZPrime
368 c := proof.Chal
369 commit := proof.Commit
370
371 // Norm check: ||z'|| ≤ ||z|| + ||r_m|| ≤ σ·1.5 + 13·σ.
372 bound := uint32(sigma*1.5 + 13*sigma)
373 if Norm(zPrime) > bound {
374 return false
375 }
376
377 // w' = A·z' + B·c - C.
378 zNTT := zPrime.Clone()
379 NTT(zNTT)
380 cNTT := c.Clone()
381 NTT(cNTT)
382 commitNTT := commit.Clone()
383 NTT(commitNTT)
384
385 az := MulPointwise(pk.A, zNTT)
386 bc := MulPointwise(pk.B, cNTT)
387 wNTT := Add(az, bc)
388 wNTT = Sub(wNTT, commitNTT)
389 INTT(wNTT)
390
391 // c must equal H(w', m).
392 cExpected := hashToChallenge(pk.P.Ring, wNTT, message)
393
394 return Equal(c, cExpected)
395 }
396