sis.go raw
1 // Ring-SIS lattice hash interface.
2 //
3 // The Short Integer Solution (SIS) problem over polynomial rings:
4 // given random a_1, ..., a_m ∈ R_q = Z_q[x]/(x^n + 1), find short
5 // x_1, ..., x_m ∈ R_q such that Σ a_i · x_i = 0 (mod q).
6 //
7 // This is provably hard, reducing to worst-case SVP on ideal lattices.
8 //
9 // A SWIFFT-family hash is the compression function:
10 // f_A(x) = Σ a_i · x_i (NTT-accelerated)
11 //
12 // where x_i have binary (0/1) or short integer coefficients.
13 //
14 // Properties:
15 // - Collision resistance: finding x ≠ x' with f(x) = f(x') ↔ solving Ring-SIS
16 // - Additive homomorphism: f(x + y) = f(x) + f(y) when x+y stays short
17 // - Universal hashing: for random A, uniform over the output ring
18 //
19 // This package provides SISParams and SISHasher to formalize the pattern
20 // used by both hamadryad (n=64, p=257) and gnarl (n=27, p=271).
21
22 package ring
23
24 import (
25 "crypto/rand"
26 "encoding/binary"
27 "io"
28 )
29
30 // SISParams defines a Ring-SIS hash family instance.
31 type SISParams struct {
32 // Ring dimension and modulus.
33 N int // polynomial degree (power of 2 for hamadryad, power of 3 for gnarl)
34 Q uint32 // coefficient modulus (prime, q ≡ 1 mod 2n for NTT)
35
36 // M is the number of key polynomials (input components).
37 // Input is M binary polynomials of degree N, so input size = M·N bits.
38 M int
39
40 // ReductionMod is the output reduction modulus.
41 // Each coefficient is reduced mod ReductionMod for the final hash.
42 // For hamadryad: 128 (7 bits). For gnarl: 271/243/3 depending on tier.
43 ReductionMod uint32
44
45 // BitsPerCoeff is the number of bits per output coefficient.
46 BitsPerCoeff int
47
48 // InputBits is the total input size (M * N).
49 InputBits int
50
51 // OutputBits is the total output size (N * BitsPerCoeff).
52 OutputBits int
53 }
54
55 // HamadryadSISParams returns the SIS parameters for the hamadryad hash.
56 //
57 // n=64, p=257, m=16, output reduced mod 128 (7 bits/coeff) = 448 bits.
58 func HamadryadSISParams() SISParams {
59 return SISParams{
60 N: 64,
61 Q: 257,
62 M: 16,
63 ReductionMod: 128,
64 BitsPerCoeff: 7,
65 InputBits: 16 * 64, // 1024
66 OutputBits: 64 * 7, // 448
67 }
68 }
69
70 // GnarlSISParams returns the SIS parameters for the gnarl hash (full tier).
71 //
72 // n=27, p=271, m=12, output unreduced (9 bits/coeff) = 243 bits.
73 func GnarlSISParams() SISParams {
74 return SISParams{
75 N: 27,
76 Q: 271,
77 M: 12,
78 ReductionMod: 271, // full range
79 BitsPerCoeff: 9,
80 InputBits: 12 * 27, // 324
81 OutputBits: 27 * 9, // 243
82 }
83 }
84
85 // SISHasher computes Ring-SIS hashes using the SWIFFT construction.
86 // Thread-safe after initialization (all key material is read-only).
87 type SISHasher struct {
88 params SISParams
89 keys []*Poly // M key polynomials in NTT form
90
91 // nttFwd and nttInv are NTT functions for the specific ring.
92 // For standard power-of-2 dimensions, these use the ring package NTT.
93 // For non-power-of-2 (gnarl's n=27), these would need the specialized NTT.
94 ringParams Params
95 }
96
97 // NewSISHasher creates a SIS hasher with deterministic key generation.
98 // The seed string determines the key polynomials.
99 // For interoperability with existing hamadryad, use "hamadryad-swifft-v1-dendrite-kismet".
100 func NewSISHasher(sp SISParams, seed string) *SISHasher {
101 // Compute ring params. For SIS, we need NTT support,
102 // which requires q ≡ 1 (mod 2n) and a primitive root.
103 rp := Params{
104 N: sp.N,
105 Q: sp.Q,
106 }
107
108 // Find a primitive 2N-th root of unity for the NTT.
109 // For known parameter sets, use precomputed values.
110 switch {
111 case sp.N == 64 && sp.Q == 257:
112 rp.RootOfUnity = 9 // psi=9, primitive 128th root of unity mod 257
113 rp.MontR = 1 << 16
114 rp.QInv = qinv(257, 16)
115 case sp.N == 27 && sp.Q == 271:
116 // Gnarl uses a specialized 27-point NTT (not power-of-2).
117 // The ring package NTT won't work directly for this.
118 // For now, mark as needing external NTT.
119 rp.RootOfUnity = 0 // signal: needs external NTT
120 default:
121 // For other parameter sets, try to find a root.
122 rp.RootOfUnity = findPrimRoot(sp.Q, uint32(2*sp.N))
123 if sp.Q < (1 << 16) {
124 rp.MontR = 1 << 16
125 rp.QInv = qinv(sp.Q, 16)
126 } else {
127 rp.MontR = 1 << 32
128 rp.QInv = qinv(sp.Q, 32)
129 }
130 }
131
132 h := &SISHasher{
133 params: sp,
134 ringParams: rp,
135 }
136
137 // Generate key polynomials deterministically from seed.
138 h.keys = h.genKeys(seed)
139
140 return h
141 }
142
143 // genKeys generates M key polynomials from a deterministic seed.
144 // Uses the same xorshift PRNG as the existing hamadryad implementation.
145 func (h *SISHasher) genKeys(seed string) []*Poly {
146 // Derive PRNG state from seed string.
147 state := uint64(0)
148 for i, b := range []byte(seed) {
149 state ^= uint64(b) << ((uint(i) * 7) % 64)
150 }
151
152 xorshift := func() uint64 {
153 state ^= state << 13
154 state ^= state >> 7
155 state ^= state << 17
156 return state
157 }
158
159 keys := make([]*Poly, h.params.M)
160 for i := range keys {
161 poly := New(h.ringParams)
162 for j := range poly.Coeffs {
163 poly.Coeffs[j] = uint32(xorshift() % uint64(h.params.Q))
164 }
165 // Store in NTT form for fast multiplication.
166 if h.ringParams.RootOfUnity != 0 {
167 NTT(poly)
168 }
169 keys[i] = poly
170 }
171 return keys
172 }
173
174 // Compress computes one SWIFFT compression: M·N bits → N coefficients in Z_q.
175 // The input block must be exactly InputBits/8 bytes.
176 // Returns the raw coefficients (before output reduction).
177 func (h *SISHasher) Compress(block []byte) *Poly {
178 sp := h.params
179 acc := New(h.ringParams)
180
181 for i := range sp.M {
182 // Extract N binary coefficients for component i.
183 poly := New(h.ringParams)
184 bitBase := i * sp.N
185 for j := range sp.N {
186 bitIdx := bitBase + j
187 byteIdx := bitIdx / 8
188 bitOff := uint(bitIdx % 8)
189 if byteIdx < len(block) && block[byteIdx]&(1<<bitOff) != 0 {
190 poly.Coeffs[j] = 1
191 }
192 }
193
194 // NTT → pointwise multiply with key → accumulate.
195 NTT(poly)
196 MulAdd(acc, poly, h.keys[i])
197 }
198
199 acc.isNTT = true
200
201 // Inverse NTT to get coefficients.
202 INTT(acc)
203
204 return acc
205 }
206
207 // Hash computes the Ring-SIS hash of an arbitrary-length message.
208 // Uses Merkle-Damgård chaining: each block is compressed, and the
209 // result is added (coefficient-wise mod q) to the chain.
210 func (h *SISHasher) Hash(msg []byte) *Poly {
211 sp := h.params
212 blockBytes := sp.InputBits / 8
213 if sp.InputBits%8 != 0 {
214 blockBytes++
215 }
216
217 var chain *Poly
218
219 // Pad message: 0x80 || zeros || 8-byte LE length.
220 padded := make([]byte, len(msg))
221 copy(padded, msg)
222 padded = append(padded, 0x80)
223
224 for (len(padded)+8)%blockBytes != 0 {
225 padded = append(padded, 0)
226 }
227
228 var lenBuf [8]byte
229 binary.LittleEndian.PutUint64(lenBuf[:], uint64(len(msg))*8)
230 padded = append(padded, lenBuf[:]...)
231
232 // Process blocks.
233 for off := 0; off < len(padded); off += blockBytes {
234 result := h.Compress(padded[off : off+blockBytes])
235
236 if chain == nil {
237 chain = result
238 } else {
239 chain = Add(chain, result)
240 }
241 }
242
243 if chain == nil {
244 chain = New(h.ringParams)
245 }
246
247 return chain
248 }
249
250 // ReduceAndPack reduces coefficients mod ReductionMod and packs them
251 // into a byte slice at BitsPerCoeff bits each.
252 func (h *SISHasher) ReduceAndPack(coeffs *Poly) []byte {
253 sp := h.params
254 totalBits := sp.N * sp.BitsPerCoeff
255 out := make([]byte, (totalBits+7)/8)
256
257 bitPos := 0
258 for i := 0; i < sp.N; i++ {
259 v := coeffs.Coeffs[i] % sp.ReductionMod
260 for b := 0; b < sp.BitsPerCoeff; b++ {
261 if v&(1<<uint(b)) != 0 {
262 out[bitPos/8] |= 1 << uint(bitPos%8)
263 }
264 bitPos++
265 }
266 }
267 return out
268 }
269
270 // HashBytes computes the full hash (compress + reduce + pack) of a message.
271 func (h *SISHasher) HashBytes(msg []byte) []byte {
272 coeffs := h.Hash(msg)
273 return h.ReduceAndPack(coeffs)
274 }
275
276 // SumCoeffs computes the coefficient-wise sum of two hash outputs (mod q).
277 // This is the additive homomorphism: Hash(a ⊕ b) = Hash(a) + Hash(b)
278 // when the combined input stays short.
279 func (h *SISHasher) SumCoeffs(a, b *Poly) *Poly {
280 return Add(a, b)
281 }
282
283 // Params returns the SIS parameters.
284 func (h *SISHasher) Params() SISParams {
285 return h.params
286 }
287
288 // RingParams returns the underlying ring parameters.
289 func (h *SISHasher) RingParams() Params {
290 return h.ringParams
291 }
292
293 // Keys returns the key polynomials (in NTT form).
294 func (h *SISHasher) Keys() []*Poly {
295 return h.keys
296 }
297
298 // findPrimRoot finds a primitive k-th root of unity mod q.
299 // Returns 0 if none exists (i.e., k does not divide q-1).
300 func findPrimRoot(q, k uint32) uint32 {
301 if (q-1)%k != 0 {
302 return 0
303 }
304
305 // Find a generator of Z_q* by trial.
306 // For small primes, just try candidates.
307 for g := uint32(2); g < q; g++ {
308 // Check if g is a primitive root mod q.
309 if powModU32(g, (q-1)/2, q) == 1 {
310 continue // not a generator
311 }
312 // g^((q-1)/k) is a primitive k-th root.
313 root := powModU32(g, (q-1)/k, q)
314 if root != 1 {
315 return root
316 }
317 }
318 return 0
319 }
320
321 // powModU32 computes base^exp mod m.
322 func powModU32(base, exp, m uint32) uint32 {
323 result := uint64(1)
324 b := uint64(base) % uint64(m)
325 for e := exp; e > 0; e >>= 1 {
326 if e&1 == 1 {
327 result = (result * b) % uint64(m)
328 }
329 b = (b * b) % uint64(m)
330 }
331 return uint32(result)
332 }
333
334 // NewSISHasherRandom creates a SIS hasher with randomly generated keys.
335 // Used when you don't need interoperability with a fixed key set.
336 func NewSISHasherRandom(sp SISParams) *SISHasher {
337 return NewSISHasherRandomFrom(sp, rand.Reader)
338 }
339
340 // NewSISHasherRandomFrom creates a SIS hasher with keys from the given source.
341 func NewSISHasherRandomFrom(sp SISParams, rng io.Reader) *SISHasher {
342 rp := Params{
343 N: sp.N,
344 Q: sp.Q,
345 }
346
347 switch {
348 case sp.N == 64 && sp.Q == 257:
349 rp.RootOfUnity = 9
350 rp.MontR = 1 << 16
351 rp.QInv = qinv(257, 16)
352 default:
353 rp.RootOfUnity = findPrimRoot(sp.Q, uint32(2*sp.N))
354 if sp.Q < (1 << 16) {
355 rp.MontR = 1 << 16
356 rp.QInv = qinv(sp.Q, 16)
357 } else {
358 rp.MontR = 1 << 32
359 rp.QInv = qinv(sp.Q, 32)
360 }
361 }
362
363 h := &SISHasher{
364 params: sp,
365 ringParams: rp,
366 }
367
368 keys := make([]*Poly, sp.M)
369 for i := range keys {
370 keys[i] = UniformPolyFrom(rp, rng)
371 NTT(keys[i])
372 }
373 h.keys = keys
374
375 return h
376 }
377