common

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

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.

Types

type Poly

type Poly [N]int16

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) Add

func (p *Poly) Add(a, b *Poly)

Sets p to a + b. Does not normalize coefficients.

func (*Poly) BarrettReduce

func (p *Poly) BarrettReduce()

Almost normalizes coefficients.

Ensures each coefficient is in {0, …, q}.

func (*Poly) CompressMessageTo

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 (*Poly) CompressTo

func (p *Poly) CompressTo(m []byte, d int)

Writes Compress_q(p, d) to m.

Assumes p is normalized and d is in {3, 4, 5, 10, 11}.

func (*Poly) Decompress

func (p *Poly) Decompress(m []byte, d int)

Set p to Decompress_q(m, 1).

Assumes d is in {3, 4, 5, 10, 11}. p will be normalized.

func (*Poly) DecompressMessage

func (p *Poly) DecompressMessage(m []byte)

Set p to Decompress_q(m, 1).

p will be normalized. m has to be of PlaintextSize.

func (*Poly) DeriveNoise

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 (*Poly) DeriveNoise2

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 (*Poly) DeriveNoise3

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 (*Poly) DeriveUniform

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 (*Poly) Detangle

func (p *Poly) Detangle()

Puts p back into standard form.

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

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 (*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

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 (*Poly) Sub

func (p *Poly) Sub(a, b *Poly)

Sets p to a - b. Does not normalize coefficients.

func (*Poly) Tangle

func (p *Poly) Tangle()

Puts p into the right form to be used with (among others) InvNTT().

func (*Poly) ToMont

func (p *Poly) ToMont()

Multiplies p in-place by the Montgomery factor 2¹⁶.

Coefficients of p can be artbitray. Resulting coefficients are bounded in absolute value by q.

func (*Poly) Unpack

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.