sample.go raw
1 package common
2
3 import (
4 "encoding/binary"
5
6 "github.com/cloudflare/circl/internal/sha3"
7 "github.com/cloudflare/circl/simd/keccakf1600"
8 )
9
10 // DeriveX4Available indicates whether the system supports the quick fourway
11 // sampling variants like PolyDeriveUniformX4.
12 var DeriveX4Available = keccakf1600.IsEnabledX4()
13
14 // Samples p from a centered binomial distribution with given η.
15 //
16 // Essentially CBD_η(PRF(seed, nonce)) from the specification.
17 func (p *Poly) DeriveNoise(seed []byte, nonce uint8, eta int) {
18 switch eta {
19 case 2:
20 p.DeriveNoise2(seed, nonce)
21 case 3:
22 p.DeriveNoise3(seed, nonce)
23 default:
24 panic("unsupported eta")
25 }
26 }
27
28 // Sample p from a centered binomial distribution with n=6 and p=½ - that is:
29 // coefficients are in {-3, -2, -1, 0, 1, 2, 3} with probabilities {1/64, 3/32,
30 // 15/64, 5/16, 16/64, 3/32, 1/64}.
31 func (p *Poly) DeriveNoise3(seed []byte, nonce uint8) {
32 keySuffix := [1]byte{nonce}
33 h := sha3.NewShake256()
34 _, _ = h.Write(seed[:])
35 _, _ = h.Write(keySuffix[:])
36
37 // The distribution at hand is exactly the same as that
38 // of (a₁ + a₂ + a₃) - (b₁ + b₂+b₃) where a_i,b_i~U(1). Thus we need
39 // 6 bits per coefficients, thus 192 bytes of input entropy.
40
41 // We add two extra zero bytes in the buffer to be able to read 8 bytes
42 // at the same time (while using only 6.)
43 var buf [192 + 2]byte
44 _, _ = h.Read(buf[:192])
45
46 for i := 0; i < 32; i++ {
47 // t is interpreted as a₁ + 2a₂ + 4a₃ + 8b₁ + 16b₂ + ….
48 t := binary.LittleEndian.Uint64(buf[6*i:])
49
50 d := t & 0x249249249249 // a₁ + 8b₁ + …
51 d += (t >> 1) & 0x249249249249 // a₁ + a₂ + 8(b₁ + b₂) + …
52 d += (t >> 2) & 0x249249249249 // a₁ + a₂ + a₃ + 4(b₁ + b₂ + b₃) + …
53
54 for j := 0; j < 8; j++ {
55 a := int16(d) & 0x7 // a₁ + a₂ + a₃
56 d >>= 3
57 b := int16(d) & 0x7 // b₁ + b₂ + b₃
58 d >>= 3
59 p[8*i+j] = a - b
60 }
61 }
62 }
63
64 // Sample p from a centered binomial distribution with n=4 and p=½ - that is:
65 // coefficients are in {-2, -1, 0, 1, 2} with probabilities {1/16, 1/4,
66 // 3/8, 1/4, 1/16}.
67 func (p *Poly) DeriveNoise2(seed []byte, nonce uint8) {
68 keySuffix := [1]byte{nonce}
69 h := sha3.NewShake256()
70 _, _ = h.Write(seed[:])
71 _, _ = h.Write(keySuffix[:])
72
73 // The distribution at hand is exactly the same as that
74 // of (a + a') - (b + b') where a,a',b,b'~U(1). Thus we need 4 bits per
75 // coefficients, thus 128 bytes of input entropy.
76
77 var buf [128]byte
78 _, _ = h.Read(buf[:])
79
80 for i := 0; i < 16; i++ {
81 // t is interpreted as a + 2a' + 4b + 8b' + ….
82 t := binary.LittleEndian.Uint64(buf[8*i:])
83
84 d := t & 0x5555555555555555 // a + 4b + …
85 d += (t >> 1) & 0x5555555555555555 // a+a' + 4(b + b') + …
86
87 for j := 0; j < 16; j++ {
88 a := int16(d) & 0x3
89 d >>= 2
90 b := int16(d) & 0x3
91 d >>= 2
92 p[16*i+j] = a - b
93 }
94 }
95 }
96
97 // For each i, sample ps[i] uniformly from the given seed for coordinates
98 // xs[i] and ys[i]. ps[i] may be nil and is ignored in that case.
99 //
100 // Can only be called when DeriveX4Available is true.
101 func PolyDeriveUniformX4(ps [4]*Poly, seed *[32]byte, xs, ys [4]uint8) {
102 var perm keccakf1600.StateX4
103 state := perm.Initialize(false)
104
105 // Absorb the seed in the four states
106 for i := 0; i < 4; i++ {
107 v := binary.LittleEndian.Uint64(seed[8*i : 8*(i+1)])
108 for j := 0; j < 4; j++ {
109 state[i*4+j] = v
110 }
111 }
112
113 // Absorb the coordinates, the SHAKE128 domain separator (0b1111), the
114 // start of the padding (0b…001) and the end of the padding 0b100….
115 // Recall that the rate of SHAKE128 is 168; ie. 21 uint64s.
116 for j := 0; j < 4; j++ {
117 state[4*4+j] = uint64(xs[j]) | (uint64(ys[j]) << 8) | (0x1f << 16)
118 state[20*4+j] = 0x80 << 56
119 }
120
121 var idx [4]int // indices into ps
122 for j := 0; j < 4; j++ {
123 if ps[j] == nil {
124 idx[j] = N // mark nil polynomials as completed
125 }
126 }
127
128 done := false
129 for !done {
130 // Applies KeccaK-f[1600] to state to get the next 21 uint64s of each of
131 // the four SHAKE128 streams.
132 perm.Permute()
133
134 done = true
135
136 PolyLoop:
137 for j := 0; j < 4; j++ {
138 if idx[j] == N {
139 continue
140 }
141 for i := 0; i < 7; i++ {
142 var t [16]uint16
143
144 v1 := state[i*3*4+j]
145 v2 := state[(i*3+1)*4+j]
146 v3 := state[(i*3+2)*4+j]
147
148 t[0] = uint16(v1) & 0xfff
149 t[1] = uint16(v1>>12) & 0xfff
150 t[2] = uint16(v1>>24) & 0xfff
151 t[3] = uint16(v1>>36) & 0xfff
152 t[4] = uint16(v1>>48) & 0xfff
153 t[5] = uint16((v1>>60)|(v2<<4)) & 0xfff
154
155 t[6] = uint16(v2>>8) & 0xfff
156 t[7] = uint16(v2>>20) & 0xfff
157 t[8] = uint16(v2>>32) & 0xfff
158 t[9] = uint16(v2>>44) & 0xfff
159 t[10] = uint16((v2>>56)|(v3<<8)) & 0xfff
160
161 t[11] = uint16(v3>>4) & 0xfff
162 t[12] = uint16(v3>>16) & 0xfff
163 t[13] = uint16(v3>>28) & 0xfff
164 t[14] = uint16(v3>>40) & 0xfff
165 t[15] = uint16(v3>>52) & 0xfff
166
167 for k := 0; k < 16; k++ {
168 if t[k] < uint16(Q) {
169 ps[j][idx[j]] = int16(t[k])
170 idx[j]++
171 if idx[j] == N {
172 continue PolyLoop
173 }
174 }
175 }
176 }
177
178 done = false
179 }
180 }
181
182 for i := 0; i < 4; i++ {
183 if ps[i] != nil {
184 ps[i].Tangle()
185 }
186 }
187 }
188
189 // Sample p uniformly from the given seed and x and y coordinates.
190 //
191 // Coefficients are reduced and will be in "tangled" order. See Tangle().
192 func (p *Poly) DeriveUniform(seed *[32]byte, x, y uint8) {
193 var seedSuffix [2]byte
194 var buf [168]byte // rate of SHAKE-128
195
196 seedSuffix[0] = x
197 seedSuffix[1] = y
198
199 h := sha3.NewShake128()
200 _, _ = h.Write(seed[:])
201 _, _ = h.Write(seedSuffix[:])
202
203 i := 0
204 for {
205 _, _ = h.Read(buf[:])
206
207 for j := 0; j < 168; j += 3 {
208 t1 := (uint16(buf[j]) | (uint16(buf[j+1]) << 8)) & 0xfff
209 t2 := (uint16(buf[j+1]>>4) | (uint16(buf[j+2]) << 4)) & 0xfff
210
211 if t1 < uint16(Q) {
212 p[i] = int16(t1)
213 i++
214
215 if i == N {
216 break
217 }
218 }
219
220 if t2 < uint16(Q) {
221 p[i] = int16(t2)
222 i++
223
224 if i == N {
225 break
226 }
227 }
228 }
229
230 if i == N {
231 break
232 }
233 }
234
235 p.Tangle()
236 }
237