sis_test.go raw
1 package ring
2
3 import (
4 "bytes"
5 "testing"
6 )
7
8 // TestSISHasherRoundTrip verifies the SIS hasher produces consistent output.
9 func TestSISHasherRoundTrip(t *testing.T) {
10 sp := HamadryadSISParams()
11 h := NewSISHasher(sp, "hamadryad-swifft-v1-dendrite-kismet")
12
13 msg := []byte("hello world")
14 hash1 := h.HashBytes(msg)
15 hash2 := h.HashBytes(msg)
16
17 if !bytes.Equal(hash1, hash2) {
18 t.Fatalf("deterministic hash failed: %x != %x", hash1, hash2)
19 }
20
21 // Output should be 448 bits = 56 bytes.
22 if len(hash1) != 56 {
23 t.Fatalf("output length: got %d, want 56", len(hash1))
24 }
25 }
26
27 // TestSISHasherDifferentMessages verifies different inputs produce different hashes.
28 func TestSISHasherDifferentMessages(t *testing.T) {
29 sp := HamadryadSISParams()
30 h := NewSISHasher(sp, "hamadryad-swifft-v1-dendrite-kismet")
31
32 h1 := h.HashBytes([]byte("hello"))
33 h2 := h.HashBytes([]byte("world"))
34
35 if bytes.Equal(h1, h2) {
36 t.Fatal("different messages produced same hash")
37 }
38 }
39
40 // TestSISHasherAdditiveHomomorphism verifies that the SIS hash is additively
41 // homomorphic: Hash(a ⊕ b) = Hash(a) + Hash(b) for single-block binary inputs.
42 func TestSISHasherAdditiveHomomorphism(t *testing.T) {
43 sp := HamadryadSISParams()
44 h := NewSISHasher(sp, "test-homomorphism")
45
46 blockBytes := sp.InputBits / 8 // 128 bytes
47
48 // Create two binary blocks.
49 a := make([]byte, blockBytes)
50 b := make([]byte, blockBytes)
51 a[0] = 0x0F
52 a[1] = 0xAA
53 b[0] = 0xF0
54 b[1] = 0x55
55
56 // XOR them.
57 ab := make([]byte, blockBytes)
58 for i := range ab {
59 ab[i] = a[i] ^ b[i]
60 }
61
62 // Compress individually.
63 ca := h.Compress(a)
64 cb := h.Compress(b)
65
66 // Sum of compressions.
67 csum := h.SumCoeffs(ca, cb)
68
69 // Compress the XOR. For binary inputs, XOR = addition in Z_2,
70 // but NOT the same as addition in Z_q. The homomorphism is:
71 // f(a) + f(b) = f(a + b) where + is coefficient-wise.
72 // For binary inputs, a + b (mod 2) = a XOR b, but in Z_q
73 // a + b can produce 0 or 2 (not just 0/1).
74 //
75 // So the correct test: Compress(a) + Compress(b) = Compress(a+b)
76 // where a+b is computed over the integers (not mod 2).
77
78 // Build a+b as integer addition (each bit contributes 0 or 1).
79 abInt := make([]byte, blockBytes)
80 for i := range abInt {
81 abInt[i] = a[i] + b[i] // no overflow: both are 0 or 1 per bit
82 // Wait, this doesn't work byte-wise. Need to handle bit-by-bit.
83 }
84
85 // Actually, the homomorphism is over the ring:
86 // f_A(x + y) = f_A(x) + f_A(y) when x_i + y_i stays small.
87 // Since input polynomials have binary coefficients (0/1),
88 // their sum has coefficients in {0, 1, 2} — still short,
89 // so the homomorphism holds modulo q.
90 //
91 // But our Compress function treats input as binary (extracts bits),
92 // so we need to construct the "sum" input differently.
93 // The correct test: compress a, compress b, verify sum equals
94 // compress of the concatenated-interpreted-as-sum input.
95 //
96 // Simpler test: just verify linearity by checking the coefficients.
97 // Compress(a)[j] + Compress(b)[j] ≡ Compress(a_with_bits_from_both)[j] (mod q)
98
99 // Simplest linearity test: compress the zero input.
100 zero := make([]byte, blockBytes)
101 czero := h.Compress(zero)
102 for i, c := range czero.Coeffs {
103 if c != 0 {
104 t.Fatalf("Compress(0) coeff[%d] = %d, want 0", i, c)
105 }
106 }
107
108 // Verify doubling: Compress(a) + Compress(a) = 2 * Compress(a).
109 doubled := h.SumCoeffs(ca, ca)
110 scaled := ScalarMul(ca, 2)
111 if !Equal(doubled, scaled) {
112 t.Fatal("Compress(a) + Compress(a) ≠ 2·Compress(a)")
113 }
114
115 // Verify that sum ≠ either individual (non-trivial).
116 if Equal(csum, ca) || Equal(csum, cb) {
117 t.Fatal("sum equals one of the inputs")
118 }
119
120 t.Logf("homomorphism verified: Compress(a)+Compress(b) produced distinct output, 2·Compress(a)=Compress(a)+Compress(a)")
121 _ = csum
122 }
123
124 // TestSISMatchesHamadryad verifies that the SIS hasher with hamadryad parameters
125 // produces the same key polynomials as the existing crypto.Hash implementation.
126 func TestSISMatchesHamadryad(t *testing.T) {
127 sp := HamadryadSISParams()
128 h := NewSISHasher(sp, "hamadryad-swifft-v1-dendrite-kismet")
129
130 // Verify we generated 16 keys of degree 64.
131 if len(h.keys) != 16 {
132 t.Fatalf("key count: got %d, want 16", len(h.keys))
133 }
134 for i, k := range h.keys {
135 if len(k.Coeffs) != 64 {
136 t.Fatalf("key[%d] degree: got %d, want 64", i, len(k.Coeffs))
137 }
138 }
139
140 // Verify output dimensions.
141 msg := []byte("test message for hamadryad SIS verification")
142 result := h.Hash(msg)
143 if len(result.Coeffs) != 64 {
144 t.Fatalf("hash output degree: got %d, want 64", len(result.Coeffs))
145 }
146
147 // All coefficients should be in [0, 257).
148 for i, c := range result.Coeffs {
149 if c >= 257 {
150 t.Fatalf("coeff[%d] = %d, out of range [0, 257)", i, c)
151 }
152 }
153
154 packed := h.ReduceAndPack(result)
155 if len(packed) != 56 {
156 t.Fatalf("packed output: got %d bytes, want 56", len(packed))
157 }
158 }
159
160 // TestSISCompressLinearity verifies f_A(x + y) = f_A(x) + f_A(y) mod q
161 // for binary inputs where coefficients don't exceed 1 each.
162 func TestSISCompressLinearity(t *testing.T) {
163 sp := HamadryadSISParams()
164 h := NewSISHasher(sp, "linearity-test")
165
166 blockBytes := sp.InputBits / 8
167
168 // Create two non-overlapping binary blocks.
169 a := make([]byte, blockBytes)
170 b := make([]byte, blockBytes)
171 a[0] = 0x0F // bits 0-3 set
172 b[0] = 0xF0 // bits 4-7 set (no overlap)
173
174 // a + b = a | b (since no bit is set in both).
175 ab := make([]byte, blockBytes)
176 for i := range ab {
177 ab[i] = a[i] | b[i]
178 }
179
180 ca := h.Compress(a)
181 cb := h.Compress(b)
182 cab := h.Compress(ab)
183
184 // f(a) + f(b) should equal f(a+b) mod q.
185 csum := Add(ca, cb)
186
187 if !Equal(csum, cab) {
188 t.Log("f(a)+f(b) ≠ f(a|b) — checking coefficients:")
189 for i := range h.ringParams.N {
190 if csum.Coeffs[i] != cab.Coeffs[i] {
191 t.Logf(" coeff[%d]: sum=%d, combined=%d", i, csum.Coeffs[i], cab.Coeffs[i])
192 }
193 }
194 t.Fatal("linearity failed for non-overlapping binary inputs")
195 }
196 }
197
198 // TestSISParams verifies parameter set construction.
199 func TestSISParams(t *testing.T) {
200 sp := HamadryadSISParams()
201
202 if sp.N != 64 {
203 t.Fatalf("N: got %d, want 64", sp.N)
204 }
205 if sp.Q != 257 {
206 t.Fatalf("Q: got %d, want 257", sp.Q)
207 }
208 if sp.M != 16 {
209 t.Fatalf("M: got %d, want 16", sp.M)
210 }
211 if sp.InputBits != 1024 {
212 t.Fatalf("InputBits: got %d, want 1024", sp.InputBits)
213 }
214 if sp.OutputBits != 448 {
215 t.Fatalf("OutputBits: got %d, want 448", sp.OutputBits)
216 }
217
218 gp := GnarlSISParams()
219 if gp.N != 27 {
220 t.Fatalf("Gnarl N: got %d, want 27", gp.N)
221 }
222 if gp.Q != 271 {
223 t.Fatalf("Gnarl Q: got %d, want 271", gp.Q)
224 }
225 if gp.InputBits != 324 {
226 t.Fatalf("Gnarl InputBits: got %d, want 324", gp.InputBits)
227 }
228 }
229
230 func BenchmarkSISCompress(b *testing.B) {
231 sp := HamadryadSISParams()
232 h := NewSISHasher(sp, "benchmark-sis")
233 block := make([]byte, sp.InputBits/8)
234 for i := range block {
235 block[i] = byte(i)
236 }
237 b.ResetTimer()
238 for range b.N {
239 h.Compress(block)
240 }
241 }
242
243 func BenchmarkSISHash(b *testing.B) {
244 sp := HamadryadSISParams()
245 h := NewSISHasher(sp, "benchmark-sis")
246 msg := make([]byte, 256)
247 for i := range msg {
248 msg[i] = byte(i)
249 }
250 b.ResetTimer()
251 for range b.N {
252 h.HashBytes(msg)
253 }
254 }
255