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
)
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 InvZetas = [N]uint32{ 6403635, 846154, 6979993, 4442679, 1362209, 48306, 4460757, 554416, 3545687, 6767575, 976891, 8196974, 2286327, 420899, 2235985, 2939036, 3833893, 260646, 1104333, 1667432, 6470041, 1803090, 6656817, 426683, 7908339, 6662682, 975884, 6167306, 8110657, 4513516, 4856520, 3038916, 1799107, 3694233, 6727783, 7570268, 5366416, 6764025, 8217573, 3183426, 1207385, 8194886, 5011305, 6423145, 164721, 5925962, 5948022, 2013608, 3776993, 7786281, 3724270, 2584293, 1846953, 1671176, 2831860, 542412, 4974386, 6144537, 7603226, 6880252, 1374803, 2546312, 6463336, 1279661, 1962642, 5074302, 7067962, 451100, 1430225, 3318210, 7143142, 1333058, 1050970, 6476982, 6511298, 2994039, 3548272, 5744496, 7129923, 3767016, 6784443, 5894064, 7132797, 4325093, 7115408, 2590150, 5688936, 5538076, 8177373, 6644538, 3342277, 4943130, 4272102, 2437823, 8093429, 8038120, 3595838, 768622, 525098, 3556995, 5173371, 6348669, 3122442, 655327, 522500, 43260, 1613174, 7884926, 7561383, 7470875, 6521319, 7479715, 3193378, 1197226, 3759364, 3520352, 4867236, 1235728, 5945978, 8113420, 3562462, 2446433, 6136326, 3342478, 4562441, 6063917, 4972711, 6288750, 4540456, 3628969, 3881060, 3019102, 1439742, 812732, 1584928, 7094748, 7039087, 7064828, 177440, 2409325, 1851402, 5220671, 3553272, 8190869, 1316856, 7620448, 210977, 5991061, 3249728, 6727353, 8578, 3724342, 4421799, 7475901, 1100098, 8336129, 5282425, 7871466, 8115473, 3343383, 1430430, 6527646, 7031341, 381987, 1308169, 22981, 1228525, 671102, 2477047, 411027, 3693493, 2967645, 5665122, 6232521, 983419, 4968207, 8253495, 3632928, 3157330, 3190144, 1000202, 4083598, 6441103, 1257611, 1585221, 6203962, 4904467, 1452451, 3041255, 3677745, 1528703, 3930395, 2797779, 6308525, 2556880, 4479693, 4499374, 7426187, 7849063, 7568473, 4680821, 1600420, 2140649, 4873154, 3821735, 4874723, 1643818, 1699267, 539299, 6031717, 300467, 4840449, 2867647, 4805995, 3043716, 3861115, 4464978, 2537516, 3592148, 1661693, 4849980, 5303092, 8284641, 5674394, 8100412, 4369920, 19422, 6623180, 3277672, 1399561, 3859737, 2118186, 2108549, 5760665, 1119584, 549488, 4794489, 1079900, 7356305, 5654953, 5700314, 5268920, 2884855, 5260684, 2091905, 359251, 6026966, 6554070, 7913949, 876248, 777960, 8143293, 518909, 2608894, 8354570, 4186625, }
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)])
var Zetas = [N]uint32{ 4193792, 25847, 5771523, 7861508, 237124, 7602457, 7504169, 466468, 1826347, 2353451, 8021166, 6288512, 3119733, 5495562, 3111497, 2680103, 2725464, 1024112, 7300517, 3585928, 7830929, 7260833, 2619752, 6271868, 6262231, 4520680, 6980856, 5102745, 1757237, 8360995, 4010497, 280005, 2706023, 95776, 3077325, 3530437, 6718724, 4788269, 5842901, 3915439, 4519302, 5336701, 3574422, 5512770, 3539968, 8079950, 2348700, 7841118, 6681150, 6736599, 3505694, 4558682, 3507263, 6239768, 6779997, 3699596, 811944, 531354, 954230, 3881043, 3900724, 5823537, 2071892, 5582638, 4450022, 6851714, 4702672, 5339162, 6927966, 3475950, 2176455, 6795196, 7122806, 1939314, 4296819, 7380215, 5190273, 5223087, 4747489, 126922, 3412210, 7396998, 2147896, 2715295, 5412772, 4686924, 7969390, 5903370, 7709315, 7151892, 8357436, 7072248, 7998430, 1349076, 1852771, 6949987, 5037034, 264944, 508951, 3097992, 44288, 7280319, 904516, 3958618, 4656075, 8371839, 1653064, 5130689, 2389356, 8169440, 759969, 7063561, 189548, 4827145, 3159746, 6529015, 5971092, 8202977, 1315589, 1341330, 1285669, 6795489, 7567685, 6940675, 5361315, 4499357, 4751448, 3839961, 2091667, 3407706, 2316500, 3817976, 5037939, 2244091, 5933984, 4817955, 266997, 2434439, 7144689, 3513181, 4860065, 4621053, 7183191, 5187039, 900702, 1859098, 909542, 819034, 495491, 6767243, 8337157, 7857917, 7725090, 5257975, 2031748, 3207046, 4823422, 7855319, 7611795, 4784579, 342297, 286988, 5942594, 4108315, 3437287, 5038140, 1735879, 203044, 2842341, 2691481, 5790267, 1265009, 4055324, 1247620, 2486353, 1595974, 4613401, 1250494, 2635921, 4832145, 5386378, 1869119, 1903435, 7329447, 7047359, 1237275, 5062207, 6950192, 7929317, 1312455, 3306115, 6417775, 7100756, 1917081, 5834105, 7005614, 1500165, 777191, 2235880, 3406031, 7838005, 5548557, 6709241, 6533464, 5796124, 4656147, 594136, 4603424, 6366809, 2432395, 2454455, 8215696, 1957272, 3369112, 185531, 7173032, 5196991, 162844, 1616392, 3014001, 810149, 1652634, 4686184, 6581310, 5341501, 3523897, 3866901, 269760, 2213111, 7404533, 1717735, 472078, 7953734, 1723600, 6577327, 1910376, 6712985, 7276084, 8119771, 4546524, 5441381, 6144432, 7959518, 6094090, 183443, 7403526, 1612842, 4834730, 7826001, 3919660, 8332111, 7018208, 3937738, 1400424, 7534263, 1976782, }
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.
AES CTR stream used as a replacement for SHAKE in Dilithium[1234]-AES.
type AesStream struct {
// contains filtered or unexported fields
}
func NewAesStream128(key *[32]byte, nonce uint16) AesStream
Create a new AesStream as a replacement of SHAKE128. (Note that not all occurrences of SHAKE are replaced by AES in the AES-variants).
func NewAesStream256(key *[64]byte, nonce uint16) AesStream
Create a new AesStream as a replacement of SHAKE256. (Note that not all occurrences of SHAKE are replaced by AES in the AES-variants.)
Yes, in an AES mode, Dilithium throws away the last 32 bytes of a seed ... See the remark at the end of the caption of Figure 4 in the Round 2 spec.
func (s *AesStream) SqueezeInto(buf []byte)
Squeeze some more blocks from the AES CTR stream into buf.
Assumes length of buf is a multiple of 16.
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().
type Poly [N]uint32
func (p *Poly) Add(a, b *Poly)
Sets p to a + b. Does not normalize polynomials.
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 (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 (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 (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 (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 (p *Poly) Normalize()
Reduce each of the coefficients to <q.
func (p *Poly) NormalizeAssumingLe2Q()
Normalize the coefficients in this polynomial assuming they are already bounded by 2q.
func (p *Poly) PackB60(buf []byte)
Writes p with 60 non-zero coefficients {-1,1} to buf, which must have length 40.
func (p *Poly) PackLe16(buf []byte)
Writes p whose coefficients are in [0, 16) to buf, which must be of length N/2.
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 (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 (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 (p *Poly) ReduceLe2Q()
Reduces each of the coefficients to <2q.
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 (p *Poly) UnpackB60(buf []byte) bool
UnpackB60 sets p to the polynomial packed into buf with Poly.PackB60().
Returns whether unpacking was successful.
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 (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.
| Name | Synopsis |
|---|---|
| .. | |