sis.mx raw
1 // Ring-SIS lattice hash interface (SWIFFT construction).
2 package ring
3
4 import (
5 "crypto/rand"
6 "io"
7 )
8
9 type SISParams struct {
10 N int32
11 Q uint32
12 M int32
13 ReductionMod uint32
14 BitsPerCoeff int32
15 InputBits int32
16 OutputBits int32
17 }
18
19 func HamadryadSISParams() (sp SISParams) {
20 return SISParams{
21 N: 64,
22 Q: 257,
23 M: 16,
24 ReductionMod: 128,
25 BitsPerCoeff: 7,
26 InputBits: 16 * 64,
27 OutputBits: 64 * 7,
28 }
29 }
30
31 func GnarlSISParams() (sp SISParams) {
32 return SISParams{
33 N: 27,
34 Q: 271,
35 M: 12,
36 ReductionMod: 271,
37 BitsPerCoeff: 9,
38 InputBits: 12 * 27,
39 OutputBits: 27 * 9,
40 }
41 }
42
43 type SISHasher struct {
44 params SISParams
45 keys []*Poly
46 ringParams Params
47 }
48
49 func NewSISHasher(sp SISParams, seed string) (h *SISHasher) {
50 rp := Params{
51 N: sp.N,
52 Q: sp.Q,
53 }
54
55 switch {
56 case sp.N == 64 && sp.Q == 257:
57 rp.RootOfUnity = 9
58 rp.MontR = 1 << 16
59 rp.QInv = qinv(257, 16)
60 case sp.N == 27 && sp.Q == 271:
61 rp.RootOfUnity = 0
62 default:
63 rp.RootOfUnity = findPrimRoot(sp.Q, uint32(2*sp.N))
64 if sp.Q < (1 << 16) {
65 rp.MontR = 1 << 16
66 rp.QInv = qinv(sp.Q, 16)
67 } else {
68 rp.MontR = 1 << 32
69 rp.QInv = qinv(sp.Q, 32)
70 }
71 }
72
73 h = &SISHasher{
74 params: sp,
75 ringParams: rp,
76 }
77
78 h.keys = h.genKeys(seed)
79 return h
80 }
81
82 func (h *SISHasher) genKeys(seed string) (keys []*Poly) {
83 state := uint64(0)
84 seedBytes := []byte(seed)
85 for i := int32(0); i < int32(len(seedBytes)); i++ {
86 state ^= uint64(seedBytes[i]) << ((uint32(i) * 7) % 64)
87 }
88
89 xorshift := func() (v uint64) {
90 state ^= state << 13
91 state ^= state >> 7
92 state ^= state << 17
93 return state
94 }
95
96 keys = []*Poly{:h.params.M}
97 for i := int32(0); i < h.params.M; i++ {
98 poly := New(h.ringParams)
99 for j := int32(0); j < int32(len(poly.Coeffs)); j++ {
100 poly.Coeffs[j] = uint32(xorshift() % uint64(h.params.Q))
101 }
102 if h.ringParams.RootOfUnity != 0 {
103 NTT(poly)
104 }
105 keys[i] = poly
106 }
107 return keys
108 }
109
110 func (h *SISHasher) Compress(block []byte) (acc *Poly) {
111 sp := h.params
112 acc = New(h.ringParams)
113
114 for i := int32(0); i < sp.M; i++ {
115 poly := New(h.ringParams)
116 bitBase := i * sp.N
117 for j := int32(0); j < sp.N; j++ {
118 bitIdx := bitBase + j
119 byteIdx := bitIdx / 8
120 bitOff := uint32(bitIdx % 8)
121 if byteIdx < int32(len(block)) && block[byteIdx]&(1<<bitOff) != 0 {
122 poly.Coeffs[j] = 1
123 }
124 }
125
126 NTT(poly)
127 MulAdd(acc, poly, h.keys[i])
128 }
129
130 acc.isNTT = true
131 INTT(acc)
132 return acc
133 }
134
135 func (h *SISHasher) Hash(msg []byte) (chain *Poly) {
136 sp := h.params
137 blockBytes := sp.InputBits / 8
138 if sp.InputBits%8 != 0 {
139 blockBytes++
140 }
141
142 padded := []byte{:int32(len(msg))}
143 copy(padded, msg)
144 padded = append(padded, 0x80)
145
146 for (int32(len(padded))+8)%blockBytes != 0 {
147 padded = append(padded, 0)
148 }
149
150 var lenBuf [8]byte
151 putLeU64(lenBuf[:], uint64(len(msg))*8)
152 padded = append(padded, lenBuf[:]...)
153
154 for off := int32(0); off < int32(len(padded)); off += blockBytes {
155 result := h.Compress(padded[off : off+blockBytes])
156
157 if chain == nil {
158 chain = result
159 } else {
160 chain = Add(chain, result)
161 }
162 }
163
164 if chain == nil {
165 chain = New(h.ringParams)
166 }
167 return chain
168 }
169
170 func (h *SISHasher) ReduceAndPack(coeffs *Poly) (out []byte) {
171 sp := h.params
172 totalBits := sp.N * sp.BitsPerCoeff
173 out = []byte{:(totalBits + 7) / 8}
174
175 bitPos := int32(0)
176 for i := int32(0); i < sp.N; i++ {
177 v := coeffs.Coeffs[i] % sp.ReductionMod
178 for b := int32(0); b < sp.BitsPerCoeff; b++ {
179 if v&(1<<uint32(b)) != 0 {
180 out[bitPos/8] |= 1 << uint32(bitPos%8)
181 }
182 bitPos++
183 }
184 }
185 return out
186 }
187
188 func (h *SISHasher) HashBytes(msg []byte) (out []byte) {
189 coeffs := h.Hash(msg)
190 return h.ReduceAndPack(coeffs)
191 }
192
193 func (h *SISHasher) SumCoeffs(a, b *Poly) (c *Poly) {
194 return Add(a, b)
195 }
196
197 func (h *SISHasher) SISParams() (sp SISParams) {
198 return h.params
199 }
200
201 func (h *SISHasher) RingParams() (rp Params) {
202 return h.ringParams
203 }
204
205 func (h *SISHasher) Keys() (keys []*Poly) {
206 return h.keys
207 }
208
209 func findPrimRoot(q, k uint32) (root uint32) {
210 if (q-1)%k != 0 {
211 return 0
212 }
213
214 for g := uint32(2); g < q; g++ {
215 if powModU32(g, (q-1)/2, q) == 1 {
216 continue
217 }
218 root = powModU32(g, (q-1)/k, q)
219 if root != 1 {
220 return root
221 }
222 }
223 return 0
224 }
225
226 func powModU32(base, exp, m uint32) (result uint32) {
227 r := uint64(1)
228 b := uint64(base) % uint64(m)
229 for e := exp; e > 0; e >>= 1 {
230 if e&1 == 1 {
231 r = (r * b) % uint64(m)
232 }
233 b = (b * b) % uint64(m)
234 }
235 return uint32(r)
236 }
237
238 func NewSISHasherRandom(sp SISParams) (h *SISHasher) {
239 return NewSISHasherRandomFrom(sp, rand.Reader)
240 }
241
242 func NewSISHasherRandomFrom(sp SISParams, rng io.Reader) (h *SISHasher) {
243 rp := Params{
244 N: sp.N,
245 Q: sp.Q,
246 }
247
248 switch {
249 case sp.N == 64 && sp.Q == 257:
250 rp.RootOfUnity = 9
251 rp.MontR = 1 << 16
252 rp.QInv = qinv(257, 16)
253 default:
254 rp.RootOfUnity = findPrimRoot(sp.Q, uint32(2*sp.N))
255 if sp.Q < (1 << 16) {
256 rp.MontR = 1 << 16
257 rp.QInv = qinv(sp.Q, 16)
258 } else {
259 rp.MontR = 1 << 32
260 rp.QInv = qinv(sp.Q, 32)
261 }
262 }
263
264 h = &SISHasher{
265 params: sp,
266 ringParams: rp,
267 }
268
269 keys := []*Poly{:sp.M}
270 for i := int32(0); i < sp.M; i++ {
271 keys[i] = UniformPolyFrom(rp, rng)
272 NTT(keys[i])
273 }
274 h.keys = keys
275
276 return h
277 }
278