Documentation
¶
Index ¶
- Constants
- Variables
- func PolyDeriveUniformX4(ps [4]*Poly, seed *[32]byte, xs, ys [4]uint8)
- type Poly
- func (p *Poly) Add(a, b *Poly)
- func (p *Poly) BarrettReduce()
- func (p *Poly) CompressMessageTo(m []byte)
- func (p *Poly) CompressTo(m []byte, d int)
- func (p *Poly) Decompress(m []byte, d int)
- func (p *Poly) DecompressMessage(m []byte)
- func (p *Poly) DeriveNoise(seed []byte, nonce uint8, eta int)
- func (p *Poly) DeriveNoise2(seed []byte, nonce uint8)
- func (p *Poly) DeriveNoise3(seed []byte, nonce uint8)
- func (p *Poly) DeriveUniform(seed *[32]byte, x, y uint8)
- func (p *Poly) Detangle()
- func (p *Poly) InvNTT()
- func (p *Poly) MulHat(a, b *Poly)
- func (p *Poly) NTT()
- func (p *Poly) Normalize()
- func (p *Poly) Pack(buf []byte)
- func (p *Poly) Sub(a, b *Poly)
- func (p *Poly) Tangle()
- func (p *Poly) ToMont()
- func (p *Poly) Unpack(buf []byte)
Constants ¶
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 )
Variables ¶
var DeriveX4Available = keccakf1600.IsEnabledX4()
DeriveX4Available indicates whether the system supports the quick fourway sampling variants like PolyDeriveUniformX4.
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,
}
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 Zetas = [128]int16{}/* 128 elements not displayed */
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 ZetasAVX2 = [...]int16{}/* 1054 elements not displayed */
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 covenient for use with AVX2.
Functions ¶
func PolyDeriveUniformX4 ¶
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.
Types ¶
type Poly ¶
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().
func (*Poly) BarrettReduce ¶
func (p *Poly) BarrettReduce()
Almost normalizes coefficients.
Ensures each coefficient is in {0, …, q}.
func (*Poly) CompressMessageTo ¶
Writes Compress_q(p, 1) to m.
Assumes p is normalized. m has to be of length at least PlaintextSize.
func (*Poly) CompressTo ¶
Writes Compress_q(p, d) to m.
Assumes p is normalized and d is in {3, 4, 5, 10, 11}.
func (*Poly) Decompress ¶
Set p to Decompress_q(m, 1).
Assumes d is in {3, 4, 5, 10, 11}. p will be normalized.
func (*Poly) DecompressMessage ¶
Set p to Decompress_q(m, 1).
p will be normalized. m has to be of PlaintextSize.
func (*Poly) DeriveNoise ¶
Samples p from a centered binomial distribution with given η.
Essentially CBD_η(PRF(seed, nonce)) from the specification.
func (*Poly) DeriveNoise2 ¶
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 (*Poly) DeriveNoise3 ¶
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 (*Poly) DeriveUniform ¶
Sample p uniformly from the given seed and x and y coordinates.
Coefficients are reduced and will be in "tangled" order. See Tangle().
func (*Poly) InvNTT ¶
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 (*Poly) MulHat ¶
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 (*Poly) NTT ¶
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 (*Poly) Normalize ¶
func (p *Poly) Normalize()
Normalizes coefficients.
Ensures each coefficient is in {0, …, q-1}.
func (*Poly) Pack ¶
Packs p into buf. buf should be of length PolySize.
Assumes p is normalized (and not just Barrett reduced) and "tangled", see Tangle().
func (*Poly) Tangle ¶
func (p *Poly) Tangle()
Puts p into the right form to be used with (among others) InvNTT().
Source Files
Directories