gpv.mx raw
1 // GPV lattice signatures with Lyubashevsky Fiat-Shamir with Aborts.
2 package ring
3
4 import (
5 "crypto/rand"
6 "io"
7
8 "crypto/sha3"
9 )
10
11 type GPVParams struct {
12 Ring Params
13 Sigma float64
14 GadgetBase uint32
15 GadgetLevels int32
16 }
17
18 type GPVPublicKey struct {
19 A *Poly
20 B *Poly
21 P GPVParams
22 }
23
24 type GPVSecretKey struct {
25 R *Poly
26 PK *GPVPublicKey
27 }
28
29 type GPVSignature struct {
30 E1 *Poly
31 E2 *Poly
32 }
33
34 func DefaultGPVParams() (gp GPVParams) {
35 p := Falcon512()
36 base := uint32(2)
37 levels := int32(0)
38 for v := p.Q; v > 0; v /= base {
39 levels++
40 }
41 return GPVParams{
42 Ring: p,
43 Sigma: RingGaussianSigma(p.N),
44 GadgetBase: base,
45 GadgetLevels: levels,
46 }
47 }
48
49 func SmallGPVParams() (gp GPVParams) {
50 p := Params{
51 N: 64,
52 Q: 257,
53 RootOfUnity: 9,
54 MontR: 1 << 16,
55 QInv: qinv(257, 16),
56 }
57 base := uint32(2)
58 levels := int32(0)
59 for v := p.Q; v > 0; v /= base {
60 levels++
61 }
62 return GPVParams{
63 Ring: p,
64 Sigma: RingGaussianSigma(p.N),
65 GadgetBase: base,
66 GadgetLevels: levels,
67 }
68 }
69
70 func GPVKeyGen(gp GPVParams) (pk *GPVPublicKey, sk *GPVSecretKey) {
71 return GPVKeyGenFrom(gp, rand.Reader)
72 }
73
74 func GPVKeyGenFrom(gp GPVParams, rng io.Reader) (pk *GPVPublicKey, sk *GPVSecretKey) {
75 p := gp.Ring
76
77 a := UniformPolyFrom(p, rng)
78 NTT(a)
79
80 r := TernaryPolyFrom(p, rng)
81
82 rNTT := r.Clone()
83 NTT(rNTT)
84
85 ar := MulPointwise(a, rNTT)
86 b := Neg(ar)
87 INTT(b)
88 bNTT := b.Clone()
89 NTT(bNTT)
90
91 pk = &GPVPublicKey{A: a, B: bNTT, P: gp}
92 sk = &GPVSecretKey{R: r, PK: pk}
93 return pk, sk
94 }
95
96 func GPVSign(sk *GPVSecretKey, message []byte) (sig *GPVSignature) {
97 return GPVSignFrom(sk, message, rand.Reader)
98 }
99
100 func GPVSignFrom(sk *GPVSecretKey, message []byte, rng io.Reader) (sig *GPVSignature) {
101 p := sk.PK.P.Ring
102 sigma := sk.PK.P.Sigma
103 gs := NewGaussianSamplerFrom(sigma, rng)
104
105 rNTT := sk.R.Clone()
106 NTT(rNTT)
107
108 for {
109 y := gs.SamplePoly(p)
110 yNTT := y.Clone()
111 NTT(yNTT)
112
113 w := MulPointwise(sk.PK.A, yNTT)
114 INTT(w)
115
116 c := hashToChallenge(p, w, message)
117 cNTT := c.Clone()
118 NTT(cNTT)
119
120 rc := MulPointwise(rNTT, cNTT)
121 INTT(rc)
122 z := Add(y, rc)
123
124 zNorm := Norm(z)
125 bound := uint32(sigma * 1.5)
126 if zNorm > bound {
127 continue
128 }
129
130 return &GPVSignature{
131 E1: z,
132 E2: c,
133 }
134 }
135 }
136
137 func GPVVerify(pk *GPVPublicKey, message []byte, sig *GPVSignature) (ok bool) {
138 p := pk.P.Ring
139 sigma := pk.P.Sigma
140
141 z := sig.E1
142 c := sig.E2
143
144 zNorm := Norm(z)
145 bound := uint32(sigma * 1.5)
146 if zNorm > bound {
147 return false
148 }
149
150 zNTT := z.Clone()
151 NTT(zNTT)
152 cNTT := c.Clone()
153 NTT(cNTT)
154
155 az := MulPointwise(pk.A, zNTT)
156 bc := MulPointwise(pk.B, cNTT)
157 wNTT := Add(az, bc)
158 w := wNTT.Clone()
159 INTT(w)
160
161 cPrime := hashToChallenge(p, w, message)
162 return Equal(c, cPrime)
163 }
164
165 func hashToChallenge(p Params, w *Poly, message []byte) (c *Poly) {
166 h := sha3.NewSHAKE256()
167 h.Write([]byte("gpv-challenge-v1"))
168
169 wBytes := Serialize(w)
170 h.Write(wBytes)
171 h.Write(message)
172
173 tau := int32(40)
174 if tau > p.N {
175 tau = p.N / 2
176 }
177
178 c = New(p)
179
180 var buf [2]byte
181 positions := []int32{:p.N}
182 for i := int32(0); i < p.N; i++ {
183 positions[i] = i
184 }
185
186 for i := int32(0); i < tau; i++ {
187 h.Read(buf[:])
188 j := i + int32(leU16(buf[:]))%(p.N-i)
189 positions[i], positions[j] = positions[j], positions[i]
190
191 h.Read(buf[:1])
192 if buf[0]&1 == 0 {
193 c.Coeffs[positions[i]] = 1
194 } else {
195 c.Coeffs[positions[i]] = p.Q - 1
196 }
197 }
198
199 return c
200 }
201