dilithium

Documentation

Index

• Constants
• Variables
• func ReduceLe2Q(x uint32) uint32
• type Poly
  • func (p *Poly) Add(a, b *Poly)
  • func (p *Poly) Exceeds(bound uint32) bool
  • func (p *Poly) InvNTT()
  • func (p *Poly) MulBy2toD(q *Poly)
  • func (p *Poly) MulHat(a, b *Poly)
  • func (p *Poly) NTT()
  • func (p *Poly) Normalize()
  • func (p *Poly) NormalizeAssumingLe2Q()
  • func (p *Poly) PackB60(buf []byte)
  • func (p *Poly) PackLe16(buf []byte)
  • func (p *Poly) PackT0(buf []byte)
  • func (p *Poly) PackT1(buf []byte)
  • func (p *Poly) Power2Round(p0PlusQ, p1 *Poly)
  • func (p *Poly) ReduceLe2Q()
  • func (p *Poly) Sub(a, b *Poly)
  • func (p *Poly) UnpackB60(buf []byte) bool
  • func (p *Poly) UnpackT0(buf []byte)
  • func (p *Poly) UnpackT1(buf []byte)

Constants

const (
	SeedSize     = params.SeedSize
	N            = params.N
	Q            = params.Q
	QBits        = params.QBits
	Qinv         = params.Qinv
	ROver256     = params.ROver256
	D            = params.D
	PolyT1Size   = params.PolyT1Size
	PolyT0Size   = params.PolyT0Size
	PolyLe16Size = params.PolyLe16Size
)

Variables

var InvZetas = [N]uint32{}/* 256 elements not displayed */

InvZetas lists precomputed powers of the inverse root of unity in Montgomery representation used for the inverse NTT:

InvZetas[i] = zetaᵇʳᵛ⁽²⁵⁵⁻ⁱ⁾⁻²⁵⁶ R mod q,

where zeta = 1753, brv(i) is the bitreversal of a 8-bit number and R=2³² mod q.

var Zetas = [N]uint32{}/* 256 elements not displayed */

Zetas lists precomputed powers of the root of unity in Montgomery representation used for the NTT:

Zetas[i] = zetaᵇʳᵛ⁽ⁱ⁾ R mod q,

where zeta = 1753, brv(i) is the bitreversal of a 8-bit number and R=2³² mod q.

The following Python code generates the Zetas (and InvZetas) lists:

q = 2**23 - 2**13 + 1; zeta = 1753
R = 2**32 % q # Montgomery const.
def brv(x): return int(''.join(reversed(bin(x)[2:].zfill(8))),2)
def inv(x): return pow(x, q-2, q) # inverse in F(q)
print([(pow(zeta, brv(i), q)*R)%q for i in range(256)])
print([(pow(inv(zeta), -(brv(255-i)-256), q)*R)%q for i in range(256)])

Functions

func ReduceLe2Q

func ReduceLe2Q(x uint32) uint32

Returns a y with y < 2q and y = x mod q. Note that in general *not*: ReduceLe2Q(ReduceLe2Q(x)) == x.

Types

type Poly

type Poly [N]uint32

An element of our base ring R which are polynomials over Z_q modulo the equation Xᴺ = -1, where q=2²³ - 2¹³ + 1 and N=256.

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 polynomials.

func (*Poly) Exceeds

func (p *Poly) Exceeds(bound uint32) bool

Checks whether the "supnorm" (see sec 2.1 of the spec) of p is equal or greater than the given bound.

Requires the coefficients of p to be normalized.

func (*Poly) InvNTT

func (p *Poly) InvNTT()

Execute an in-place inverse NTT and multiply by Montgomery factor R

Assumes the coefficients are in Montgomery representation and bounded by 2*Q. The resulting coefficients are again in Montgomery representation and bounded by 2*Q.

func (*Poly) MulBy2toD

func (p *Poly) MulBy2toD(q *Poly)

Sets p to 2ᵈ q without reducing.

So it requires the coefficients of p to be less than 2³²⁻ᴰ.

func (*Poly) MulHat

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

Sets p to the polynomial whose coefficients are the pointwise multiplication of those of a and b. The coefficients of p are bounded by 2q.

Assumes a and b are in Montgomery form and that the pointwise product of each coefficient is below 2³² q.

func (*Poly) NTT

func (p *Poly) NTT()

Execute an in-place forward NTT on as.

Assumes the coefficients are in Montgomery representation and bounded by 2*Q. The resulting coefficients are again in Montgomery representation, but are only bounded bt 18*Q.

func (*Poly) Normalize

func (p *Poly) Normalize()

Reduce each of the coefficients to <q.

func (*Poly) NormalizeAssumingLe2Q

func (p *Poly) NormalizeAssumingLe2Q()

Normalize the coefficients in this polynomial assuming they are already bounded by 2q.

func (*Poly) PackB60

func (p *Poly) PackB60(buf []byte)

Writes p with 60 non-zero coefficients {-1,1} to buf, which must have length 40.

func (*Poly) PackLe16

func (p *Poly) PackLe16(buf []byte)

Writes p whose coefficients are in [0, 16) to buf, which must be of length N/2.

func (*Poly) PackT0

func (p *Poly) PackT0(buf []byte)

Writes p whose coefficients are in (-2ᵈ⁻¹, 2ᵈ⁻¹] into buf which has to be of length at least PolyT0Size.

Assumes that the coefficients are not normalized, but lie in the range (q-2ᵈ⁻¹, q+2ᵈ⁻¹].

func (*Poly) PackT1

func (p *Poly) PackT1(buf []byte)

Writes p whose coefficients are less than 1024 into buf, which must be of size at least PolyT1Size .

Assumes coefficients of p are normalized.

func (*Poly) Power2Round

func (p *Poly) Power2Round(p0PlusQ, p1 *Poly)

Splits p into p1 and p0 such that [i]p1 * 2ᴰ + [i]p0 = [i]p with -2ᴰ⁻¹ < [i]p0 ≤ 2ᴰ⁻¹. Returns p0 + Q and p1.

Requires the coefficients of p to be normalized.

func (*Poly) ReduceLe2Q

func (p *Poly) ReduceLe2Q()

Reduces each of the coefficients to <2q.

func (*Poly) Sub

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

Sets p to a - b.

Warning: assumes coefficients of b are less than 2q. Sets p to a + b. Does not normalize polynomials.

func (*Poly) UnpackB60

func (p *Poly) UnpackB60(buf []byte) bool

UnpackB60 sets p to the polynomial packed into buf with Poly.PackB60().

Returns whether unpacking was successful.

func (*Poly) UnpackT0

func (p *Poly) UnpackT0(buf []byte)

Sets p to the polynomial packed into buf by PackT0.

The coefficients of p will not be normalized, but will lie in (-2ᵈ⁻¹, 2ᵈ⁻¹].

func (*Poly) UnpackT1

func (p *Poly) UnpackT1(buf []byte)

Sets p to the polynomial whose coefficients are less than 1024 encoded into buf (which must be of size PolyT1Size).

p will be normalized.