const (
// Q is the parameter q ≡ 3329 = 2¹¹ + 2¹⁰ + 2⁸ + 1.
Q = params.Q
// N is the parameter N: the length of the polynomials
N = params.N
// PolySize is the size of a packed polynomial.
PolySize = params.PolySize
// PlaintextSize is the size of the plaintext
PlaintextSize = params.PlaintextSize
// Eta2 is the parameter η₂
Eta2 = params.Eta2
)
DeriveX4Available indicates whether the system supports the quick fourway sampling variants like PolyDeriveUniformX4.
var DeriveX4Available = keccakf1600.IsEnabledX4()
InvNTTReductions keeps track of which coefficients to apply Barrett reduction to in Poly.InvNTT().
Generated in a lazily: once a butterfly is computed which is about to overflow the int16, the largest coefficient is reduced. If that is not enough, the other coefficient is reduced as well.
This is actually optimal, as proven in https://eprint.iacr.org/2020/1377.pdf
var InvNTTReductions = [...]int{ -1, -1, 16, 17, 48, 49, 80, 81, 112, 113, 144, 145, 176, 177, 208, 209, 240, 241, -1, 0, 1, 32, 33, 34, 35, 64, 65, 96, 97, 98, 99, 128, 129, 160, 161, 162, 163, 192, 193, 224, 225, 226, 227, -1, 2, 3, 66, 67, 68, 69, 70, 71, 130, 131, 194, 195, 196, 197, 198, 199, -1, 4, 5, 6, 7, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, -1, -1, }
Zetas lists precomputed powers of the primitive root of unity in Montgomery representation used for the NTT:
Zetas[i] = ζᵇʳᵛ⁽ⁱ⁾ R mod q
where ζ = 17, brv(i) is the bitreversal of a 7-bit number and R=2¹⁶ mod q.
The following Python code generates the Zetas arrays:
q = 13*2**8 + 1; zeta = 17
R = 2**16 % q # Montgomery const.
def brv(x): return int(''.join(reversed(bin(x)[2:].zfill(7))),2)
print([(pow(zeta, brv(i), q)*R)%q for i in range(128)])
var Zetas = [128]int16{ 2285, 2571, 2970, 1812, 1493, 1422, 287, 202, 3158, 622, 1577, 182, 962, 2127, 1855, 1468, 573, 2004, 264, 383, 2500, 1458, 1727, 3199, 2648, 1017, 732, 608, 1787, 411, 3124, 1758, 1223, 652, 2777, 1015, 2036, 1491, 3047, 1785, 516, 3321, 3009, 2663, 1711, 2167, 126, 1469, 2476, 3239, 3058, 830, 107, 1908, 3082, 2378, 2931, 961, 1821, 2604, 448, 2264, 677, 2054, 2226, 430, 555, 843, 2078, 871, 1550, 105, 422, 587, 177, 3094, 3038, 2869, 1574, 1653, 3083, 778, 1159, 3182, 2552, 1483, 2727, 1119, 1739, 644, 2457, 349, 418, 329, 3173, 3254, 817, 1097, 603, 610, 1322, 2044, 1864, 384, 2114, 3193, 1218, 1994, 2455, 220, 2142, 1670, 2144, 1799, 2051, 794, 1819, 2475, 2459, 478, 3221, 3021, 996, 991, 958, 1869, 1522, 1628, }
ZetasAVX2 contains all ζ used in NTT (like the Zetas array), but also the values int16(zeta * 62209) for each zeta, which is used in Montgomery reduction. There is some duplication and reordering as compared to Zetas to make it more convenient for use with AVX2.
var ZetasAVX2 = [...]int16{ 31499, 2571, 14746, 2970, 788, 1812, 13525, 1493, -12402, 1422, 28191, 287, -16694, 202, 0, 0, -20906, -20906, -20906, -20906, -20906, -20906, -20906, -20906, 27758, 27758, 27758, 27758, 27758, 27758, 27758, 27758, 3158, 3158, 3158, 3158, 3158, 3158, 3158, 3158, 622, 622, 622, 622, 622, 622, 622, 622, -3799, -3799, -3799, -3799, -3799, -3799, -3799, -3799, -15690, -15690, -15690, -15690, -15690, -15690, -15690, -15690, 1577, 1577, 1577, 1577, 1577, 1577, 1577, 1577, 182, 182, 182, 182, 182, 182, 182, 182, 10690, 10690, 10690, 10690, 10690, 10690, 10690, 10690, 1359, 1359, 1359, 1359, 1359, 1359, 1359, 1359, 962, 962, 962, 962, 962, 962, 962, 962, 2127, 2127, 2127, 2127, 2127, 2127, 2127, 2127, -11201, -11201, -11201, -11201, -11201, -11201, -11201, -11201, 31164, 31164, 31164, 31164, 31164, 31164, 31164, 31164, 1855, 1855, 1855, 1855, 1855, 1855, 1855, 1855, 1468, 1468, 1468, 1468, 1468, 1468, 1468, 1468, -5827, -5827, -5827, -5827, 17364, 17364, 17364, 17364, -26360, -26360, -26360, -26360, -29057, -29057, -29057, -29057, 573, 573, 573, 573, 2004, 2004, 2004, 2004, 264, 264, 264, 264, 383, 383, 383, 383, 5572, 5572, 5572, 5572, -1102, -1102, -1102, -1102, 21439, 21439, 21439, 21439, -26241, -26241, -26241, -26241, 2500, 2500, 2500, 2500, 1458, 1458, 1458, 1458, 1727, 1727, 1727, 1727, 3199, 3199, 3199, 3199, -28072, -28072, -28072, -28072, 24313, 24313, 24313, 24313, -10532, -10532, -10532, -10532, 8800, 8800, 8800, 8800, 2648, 2648, 2648, 2648, 1017, 1017, 1017, 1017, 732, 732, 732, 732, 608, 608, 608, 608, 18427, 18427, 18427, 18427, 8859, 8859, 8859, 8859, 26676, 26676, 26676, 26676, -16162, -16162, -16162, -16162, 1787, 1787, 1787, 1787, 411, 411, 411, 411, 3124, 3124, 3124, 3124, 1758, 1758, 1758, 1758, -5689, -5689, -6516, -6516, 1497, 1497, 30967, 30967, -23564, -23564, 20179, 20179, 20711, 20711, 25081, 25081, 1223, 1223, 652, 652, 2777, 2777, 1015, 1015, 2036, 2036, 1491, 1491, 3047, 3047, 1785, 1785, -12796, -12796, 26617, 26617, 16065, 16065, -12441, -12441, 9135, 9135, -649, -649, -25986, -25986, 27837, 27837, 516, 516, 3321, 3321, 3009, 3009, 2663, 2663, 1711, 1711, 2167, 2167, 126, 126, 1469, 1469, 19884, 19884, -28249, -28249, -15886, -15886, -8898, -8898, -28309, -28309, 9076, 9076, -30198, -30198, 18250, 18250, 2476, 2476, 3239, 3239, 3058, 3058, 830, 830, 107, 107, 1908, 1908, 3082, 3082, 2378, 2378, 13427, 13427, 14017, 14017, -29155, -29155, -12756, -12756, 16832, 16832, 4312, 4312, -24155, -24155, -17914, -17914, 2931, 2931, 961, 961, 1821, 1821, 2604, 2604, 448, 448, 2264, 2264, 677, 677, 2054, 2054, -334, 11182, -11477, 13387, -32226, -14233, 20494, -21655, -27738, 13131, 945, -4586, -14882, 23093, 6182, 5493, 2226, 430, 555, 843, 2078, 871, 1550, 105, 422, 587, 177, 3094, 3038, 2869, 1574, 1653, 32011, -32502, 10631, 30318, 29176, -18741, -28761, 12639, -18485, 20100, 17561, 18525, -14430, 19529, -5275, -12618, 3083, 778, 1159, 3182, 2552, 1483, 2727, 1119, 1739, 644, 2457, 349, 418, 329, 3173, 3254, -31183, 20297, 25435, 2146, -7382, 15356, 24392, -32384, -20926, -6279, 10946, -14902, 24215, -11044, 16990, 14470, 817, 1097, 603, 610, 1322, 2044, 1864, 384, 2114, 3193, 1218, 1994, 2455, 220, 2142, 1670, 10336, -21497, -7933, -20198, -22501, 23211, 10907, -17442, 31637, -23859, 28644, -20257, 23998, 7757, -17422, 23132, 2144, 1799, 2051, 794, 1819, 2475, 2459, 478, 3221, 3021, 996, 991, 958, 1869, 1522, 1628, 23132, -17422, 7757, 23998, -20257, 28644, -23859, 31637, -17442, 10907, 23211, -22501, -20198, -7933, -21497, 10336, 1628, 1522, 1869, 958, 991, 996, 3021, 3221, 478, 2459, 2475, 1819, 794, 2051, 1799, 2144, 14470, 16990, -11044, 24215, -14902, 10946, -6279, -20926, -32384, 24392, 15356, -7382, 2146, 25435, 20297, -31183, 1670, 2142, 220, 2455, 1994, 1218, 3193, 2114, 384, 1864, 2044, 1322, 610, 603, 1097, 817, -12618, -5275, 19529, -14430, 18525, 17561, 20100, -18485, 12639, -28761, -18741, 29176, 30318, 10631, -32502, 32011, 3254, 3173, 329, 418, 349, 2457, 644, 1739, 1119, 2727, 1483, 2552, 3182, 1159, 778, 3083, 5493, 6182, 23093, -14882, -4586, 945, 13131, -27738, -21655, 20494, -14233, -32226, 13387, -11477, 11182, -334, 1653, 1574, 2869, 3038, 3094, 177, 587, 422, 105, 1550, 871, 2078, 843, 555, 430, 2226, -17914, -17914, -24155, -24155, 4312, 4312, 16832, 16832, -12756, -12756, -29155, -29155, 14017, 14017, 13427, 13427, 2054, 2054, 677, 677, 2264, 2264, 448, 448, 2604, 2604, 1821, 1821, 961, 961, 2931, 2931, 18250, 18250, -30198, -30198, 9076, 9076, -28309, -28309, -8898, -8898, -15886, -15886, -28249, -28249, 19884, 19884, 2378, 2378, 3082, 3082, 1908, 1908, 107, 107, 830, 830, 3058, 3058, 3239, 3239, 2476, 2476, 27837, 27837, -25986, -25986, -649, -649, 9135, 9135, -12441, -12441, 16065, 16065, 26617, 26617, -12796, -12796, 1469, 1469, 126, 126, 2167, 2167, 1711, 1711, 2663, 2663, 3009, 3009, 3321, 3321, 516, 516, 25081, 25081, 20711, 20711, 20179, 20179, -23564, -23564, 30967, 30967, 1497, 1497, -6516, -6516, -5689, -5689, 1785, 1785, 3047, 3047, 1491, 1491, 2036, 2036, 1015, 1015, 2777, 2777, 652, 652, 1223, 1223, -16162, -16162, -16162, -16162, 26676, 26676, 26676, 26676, 8859, 8859, 8859, 8859, 18427, 18427, 18427, 18427, 1758, 1758, 1758, 1758, 3124, 3124, 3124, 3124, 411, 411, 411, 411, 1787, 1787, 1787, 1787, 8800, 8800, 8800, 8800, -10532, -10532, -10532, -10532, 24313, 24313, 24313, 24313, -28072, -28072, -28072, -28072, 608, 608, 608, 608, 732, 732, 732, 732, 1017, 1017, 1017, 1017, 2648, 2648, 2648, 2648, -26241, -26241, -26241, -26241, 21439, 21439, 21439, 21439, -1102, -1102, -1102, -1102, 5572, 5572, 5572, 5572, 3199, 3199, 3199, 3199, 1727, 1727, 1727, 1727, 1458, 1458, 1458, 1458, 2500, 2500, 2500, 2500, -29057, -29057, -29057, -29057, -26360, -26360, -26360, -26360, 17364, 17364, 17364, 17364, -5827, -5827, -5827, -5827, 383, 383, 383, 383, 264, 264, 264, 264, 2004, 2004, 2004, 2004, 573, 573, 573, 573, 31164, 31164, 31164, 31164, 31164, 31164, 31164, 31164, -11201, -11201, -11201, -11201, -11201, -11201, -11201, -11201, 1468, 1468, 1468, 1468, 1468, 1468, 1468, 1468, 1855, 1855, 1855, 1855, 1855, 1855, 1855, 1855, 1359, 1359, 1359, 1359, 1359, 1359, 1359, 1359, 10690, 10690, 10690, 10690, 10690, 10690, 10690, 10690, 2127, 2127, 2127, 2127, 2127, 2127, 2127, 2127, 962, 962, 962, 962, 962, 962, 962, 962, -15690, -15690, -15690, -15690, -15690, -15690, -15690, -15690, -3799, -3799, -3799, -3799, -3799, -3799, -3799, -3799, 182, 182, 182, 182, 182, 182, 182, 182, 1577, 1577, 1577, 1577, 1577, 1577, 1577, 1577, 27758, 27758, 27758, 27758, 27758, 27758, 27758, 27758, -20906, -20906, -20906, -20906, -20906, -20906, -20906, -20906, 622, 622, 622, 622, 622, 622, 622, 622, 3158, 3158, 3158, 3158, 3158, 3158, 3158, 3158, -16694, 202, 28191, 287, -12402, 1422, 13525, 1493, 788, 1812, 14746, 2970, 31499, 2571, }
func PolyDeriveUniformX4(ps [4]*Poly, seed *[32]byte, xs, ys [4]uint8)
For each i, sample ps[i] uniformly from the given seed for coordinates xs[i] and ys[i]. ps[i] may be nil and is ignored in that case.
Can only be called when DeriveX4Available is true.
An element of our base ring R which are polynomials over ℤ_q modulo the equation Xᴺ = -1, where q=3329 and N=256.
This type is also used to store NTT-transformed polynomials, see Poly.NTT().
Coefficients aren't always reduced. See Normalize().
type Poly [N]int16
func (p *Poly) Add(a, b *Poly)
Sets p to a + b. Does not normalize coefficients.
func (p *Poly) BarrettReduce()
Almost normalizes coefficients.
Ensures each coefficient is in {0, …, q}.
func (p *Poly) CompressMessageTo(m []byte)
Writes Compress_q(p, 1) to m.
Assumes p is normalized. m has to be of length at least PlaintextSize.
func (p *Poly) CompressTo(m []byte, d int)
Writes Compress_q(p, d) to m.
Assumes p is normalized and d is in {4, 5, 10, 11}.
func (p *Poly) Decompress(m []byte, d int)
Set p to Decompress_q(m, 1).
Assumes d is in {4, 5, 10, 11}. p will be normalized.
func (p *Poly) DecompressMessage(m []byte)
Set p to Decompress_q(m, 1).
p will be normalized. m has to be of PlaintextSize.
func (p *Poly) DeriveNoise(seed []byte, nonce uint8, eta int)
Samples p from a centered binomial distribution with given η.
Essentially CBD_η(PRF(seed, nonce)) from the specification.
func (p *Poly) DeriveNoise2(seed []byte, nonce uint8)
Sample p from a centered binomial distribution with n=4 and p=½ - that is: coefficients are in {-2, -1, 0, 1, 2} with probabilities {1/16, 1/4, 3/8, 1/4, 1/16}.
func (p *Poly) DeriveNoise3(seed []byte, nonce uint8)
Sample p from a centered binomial distribution with n=6 and p=½ - that is: coefficients are in {-3, -2, -1, 0, 1, 2, 3} with probabilities {1/64, 3/32, 15/64, 5/16, 16/64, 3/32, 1/64}.
func (p *Poly) DeriveUniform(seed *[32]byte, x, y uint8)
Sample p uniformly from the given seed and x and y coordinates.
Coefficients are reduced and will be in "tangled" order. See Tangle().
func (p *Poly) Detangle()
Puts p back into standard form.
func (p *Poly) InvNTT()
Executes an in-place inverse "NTT" on p and multiply by the Montgomery factor R.
Requires coefficients to be in "tangled" order, see Tangle(). Assumes the coefficients are in absolute value ≤q. The resulting coefficients are in absolute value ≤q. If the input is in Montgomery form, then the result is in Montgomery form and so (by linearity) if the input is in regular form, then the result is also in regular form.
func (p *Poly) MulHat(a, b *Poly)
Sets p to the "pointwise" multiplication of a and b.
That is: InvNTT(p) = InvNTT(a) * InvNTT(b). Assumes a and b are in Montgomery form. Products between coefficients of a and b must be strictly bounded in absolute value by 2¹⁵q. p will be in Montgomery form and bounded in absolute value by 2q.
Requires a and b to be in "tangled" order, see Tangle(). p will be in tangled order as well.
func (p *Poly) NTT()
Executes an in-place forward "NTT" on p.
Assumes the coefficients are in absolute value ≤q. The resulting coefficients are in absolute value ≤7q. If the input is in Montgomery form, then the result is in Montgomery form and so (by linearity of the NTT) if the input is in regular form, then the result is also in regular form. The order of coefficients will be "tangled". These can be put back into their proper order by calling Detangle().
func (p *Poly) Normalize()
Normalizes coefficients.
Ensures each coefficient is in {0, …, q-1}.
func (p *Poly) Pack(buf []byte)
Packs p into buf. buf should be of length PolySize.
Assumes p is normalized (and not just Barrett reduced) and "tangled", see Tangle().
func (p *Poly) Sub(a, b *Poly)
Sets p to a - b. Does not normalize coefficients.
func (p *Poly) Tangle()
Puts p into the right form to be used with (among others) InvNTT().
func (p *Poly) ToMont()
Multiplies p in-place by the Montgomery factor 2¹⁶.
Coefficients of p can be arbitrary. Resulting coefficients are bounded in absolute value by q.
func (p *Poly) Unpack(buf []byte)
Unpacks p from buf.
buf should be of length PolySize. p will be "tangled", see Detangle().
p will not be normalized; instead 0 ≤ p[i] < 4096.
| Name | Synopsis |
|---|---|
| .. | |