gpv_gadget.go raw
1 // MP12 gadget-trapdoor GPV signatures (Micciancio-Peikert 2012).
2 //
3 // This is a proper hash-then-sign lattice signature — fundamentally different
4 // from the Lyubashevsky Fiat-Shamir with Aborts in gpv.go (which is a sigma
5 // protocol turned into a signature via rejection sampling).
6 //
7 // The MP12 gadget replaces the simple `b = -a·r` key with a ℓ-component
8 // vector key where each B[i] embeds a gadget base power:
9 //
10 // Public key: (a, B[0], B[1], ..., B[ℓ-1])
11 // where B[i] = -a·R[i] + base^i (mod q)
12 // Secret key: R[0], ..., R[ℓ-1] (short ternary trapdoor components)
13 //
14 // Verification: a·E1 + Σ B[i]·E2[i] = H(m) (mod q)
15 //
16 // The signing algorithm uses a Gaussian perturbation to statistically hide
17 // the trapdoor, then decomposes the (target - perturbation) into base-b digits:
18 //
19 // 1. t = H(m)
20 // 2. p ← D_σ (zero-centered Gaussian perturbation)
21 // 3. t' = t - a·p (coset shift — prevents trapdoor leakage)
22 // 4. E2 = GadgetDecompose(t', base) — ℓ digit polynomials
23 // 5. E1 = p + Σ R[i]·E2[i]
24 //
25 // NOTE: The public key contains ℓ+1 polynomials. For Falcon-512 with base=2,
26 // ℓ = 14, making the public key ~13 KB. This is acceptable for enterprise/
27 // government deployments (10-100 counterparties) but impractical for
28 // consumer-scale use. The compact production target is the Falcon NTRU
29 // trapdoor (~700 B keys, ~700 B signatures), which is tracked as separate work.
30
31 package ring
32
33 import (
34 "crypto/rand"
35 "encoding/binary"
36 "io"
37
38 "golang.org/x/crypto/sha3"
39 )
40
41 // GPVGadgetPublicKey is an ℓ-component MP12 gadget public key.
42 // Verification: A·E1 + Σ B[i]·E2[i] = H(m) (mod q).
43 type GPVGadgetPublicKey struct {
44 A *Poly // uniform ring element (NTT form)
45 B []*Poly // B[i] = -A·R[i] + base^i (mod q), NTT form
46 P GPVParams
47 }
48
49 // GPVGadgetSecretKey is the ℓ-component trapdoor for the gadget public key.
50 type GPVGadgetSecretKey struct {
51 R []*Poly // ℓ short ternary polynomials
52 PK *GPVGadgetPublicKey
53 }
54
55 // GPVGadgetSignature is a gadget-based lattice signature: short (E1, E2)
56 // satisfying A·E1 + Σ B[i]·E2[i] = H(m).
57 type GPVGadgetSignature struct {
58 E1 *Poly // short response polynomial
59 E2 []*Poly // ℓ gadget-digit polynomials, each with short coefficients
60 }
61
62 // GPVGadgetKeyGen generates an MP12 gadget key pair.
63 func GPVGadgetKeyGen(gp GPVParams) (*GPVGadgetPublicKey, *GPVGadgetSecretKey) {
64 return GPVGadgetKeyGenFrom(gp, rand.Reader)
65 }
66
67 // GPVGadgetKeyGenFrom generates a key pair from the given randomness source.
68 func GPVGadgetKeyGenFrom(gp GPVParams, rng io.Reader) (*GPVGadgetPublicKey, *GPVGadgetSecretKey) {
69 p := gp.Ring
70 ℓ := gp.GadgetLevels
71 base := gp.GadgetBase
72
73 a := UniformPolyFrom(p, rng)
74 NTT(a)
75
76 r := make([]*Poly, ℓ)
77 b := make([]*Poly, ℓ)
78
79 for i := 0; i < ℓ; i++ {
80 r[i] = TernaryPolyFrom(p, rng)
81
82 rNTT := r[i].Clone()
83 NTT(rNTT)
84 ar := MulPointwise(a, rNTT)
85 INTT(ar)
86
87 b[i] = Neg(ar)
88 gadget := uint32(1)
89 for k := 0; k < i; k++ {
90 gadget = mulMod(gadget, base, p.Q)
91 }
92 // base^i is a constant polynomial: only coefficient 0 is non-zero.
93 b[i].Coeffs[0] = addMod(b[i].Coeffs[0], gadget, p.Q)
94 NTT(b[i])
95 }
96
97 pk := &GPVGadgetPublicKey{A: a, B: b, P: gp}
98 sk := &GPVGadgetSecretKey{R: r, PK: pk}
99 return pk, sk
100 }
101
102 // GadgetDecompose splits a polynomial into ℓ digit polynomials.
103 // Each coefficient v is decomposed as v = Σ_{i=0}^{ℓ-1} digit_i · base^i,
104 // where each digit_i ∈ [0, base). Uses unsigned decomposition.
105 func GadgetDecompose(a *Poly, base uint32) []*Poly {
106 p := a.params
107 q := p.Q
108
109 var levels int
110 for tmp := q; tmp > 0; tmp /= base {
111 levels++
112 }
113
114 digits := make([]*Poly, levels)
115 for i := range digits {
116 digits[i] = New(p)
117 }
118
119 for ci, coeff := range a.Coeffs {
120 val := coeff
121 for li := 0; li < levels; li++ {
122 digits[li].Coeffs[ci] = val % base
123 val /= base
124 }
125 }
126 return digits
127 }
128
129 // hashMessageToTarget hashes a message to a sparse polynomial in R_q.
130 // The target has τ=40 non-zero coefficients, each ±1.
131 // Domain-separated from hashToChallenge (no commitment polynomial).
132 func hashMessageToTarget(p Params, message []byte) *Poly {
133 h := sha3.NewShake256()
134 h.Write([]byte("gpv-target-v1"))
135 h.Write(message)
136
137 tau := 40
138 if tau > p.N {
139 tau = p.N / 2
140 }
141
142 c := New(p)
143 var buf [2]byte
144 positions := make([]int, p.N)
145 for i := range positions {
146 positions[i] = i
147 }
148
149 for i := range tau {
150 h.Read(buf[:])
151 j := i + int(binary.LittleEndian.Uint16(buf[:]))%(p.N-i)
152 positions[i], positions[j] = positions[j], positions[i]
153
154 h.Read(buf[:1])
155 if buf[0]&1 == 0 {
156 c.Coeffs[positions[i]] = 1
157 } else {
158 c.Coeffs[positions[i]] = p.Q - 1
159 }
160 }
161 return c
162 }
163
164 // GPVGadgetSign signs via MP12 hash-then-sign with perturbation.
165 //
166 // Algorithm:
167 // 1. t = H(m) — sparse polynomial via hashMessageToTarget
168 // 2. p ← D_σ (zero-centered Gaussian perturbation)
169 // 3. t' = t - a·p (coset shift — critical for trapdoor hiding)
170 // 4. E2 = GadgetDecompose(t', base) — ℓ digit polys, short coefficients
171 // 5. E1 = p + Σ R[i]·E2[i]
172 //
173 // (E1, E2) satisfy A·E1 + Σ B[i]·E2[i] = t.
174 func GPVGadgetSign(sk *GPVGadgetSecretKey, message []byte) *GPVGadgetSignature {
175 return GPVGadgetSignFrom(sk, message, rand.Reader)
176 }
177
178 // GPVGadgetSignFrom signs with the given randomness source.
179 func GPVGadgetSignFrom(sk *GPVGadgetSecretKey, message []byte, rng io.Reader) *GPVGadgetSignature {
180 pk := sk.PK
181 gp := pk.P
182 p := gp.Ring
183 base := gp.GadgetBase
184 sigma := gp.Sigma
185 gs := NewGaussianSamplerFrom(sigma, rng)
186
187 t := hashMessageToTarget(p, message)
188
189 perturb := gs.SamplePoly(p)
190 perturbNTT := perturb.Clone()
191 NTT(perturbNTT)
192
193 aNTT := pk.A
194 ap := MulPointwise(aNTT, perturbNTT)
195 INTT(ap)
196 tPrime := Sub(t, ap)
197
198 e2 := GadgetDecompose(tPrime, base)
199
200 e1 := perturb.Clone()
201 for i := range e2 {
202 rNTT := sk.R[i].Clone()
203 NTT(rNTT)
204 e2NTT := e2[i].Clone()
205 NTT(e2NTT)
206 prod := MulPointwise(rNTT, e2NTT)
207 INTT(prod)
208 e1 = Add(e1, prod)
209 }
210
211 return &GPVGadgetSignature{
212 E1: e1,
213 E2: e2,
214 }
215 }
216
217 // GPVGadgetVerify verifies a gadget-based GPV signature.
218 //
219 // Checks:
220 // 1. A·E1 + Σ B[i]·E2[i] = H(m) (mod q) — algebraic correctness
221 // 2. ||E2[i]||_∞ < base — each digit is a valid gadget digit
222 // 3. ||E1||_∞ ≤ bound — response is short enough for security
223 func GPVGadgetVerify(pk *GPVGadgetPublicKey, message []byte, sig *GPVGadgetSignature) bool {
224 gp := pk.P
225 p := gp.Ring
226 base := gp.GadgetBase
227 sigma := gp.Sigma
228
229 e1 := sig.E1
230 e2 := sig.E2
231
232 if len(e2) != len(pk.B) {
233 return false
234 }
235
236 for i := range e2 {
237 for _, c := range e2[i].Coeffs {
238 if c >= base {
239 return false
240 }
241 }
242 }
243
244 ℓ := len(e2)
245 tail := uint32(13 * sigma)
246 conv := uint32(float64(p.N) * float64(base-1) / 3.0)
247 e1Bound := tail + uint32(ℓ)*conv
248 half := p.Q / 2
249 if e1Bound > half {
250 e1Bound = half
251 }
252 if Norm(e1) > e1Bound {
253 return false
254 }
255
256 t := hashMessageToTarget(p, message)
257
258 // Compute via coefficient-form Mul to avoid NTT pipeline issues.
259 aCoeff := pk.A.Clone()
260 INTT(aCoeff)
261 ae1 := Mul(aCoeff, e1)
262
263 lhs := ae1
264 for i := range e2 {
265 bCoeff := pk.B[i].Clone()
266 INTT(bCoeff)
267 term := Mul(bCoeff, e2[i])
268 lhs = Add(lhs, term)
269 }
270
271 return Equal(lhs, t)
272 }
273