mldsa_rej_ntt_poly
stdlib/mldsa/mldsa_rej_ntt_poly.nbv
mldsa_rej_ntt_poly(seed)
RejNTTPoly (FIPS 204 Algorithm 30): sample a polynomial with uniform coefficients below q from SHAKE128(seed).
seed is a vector of bits. Returns base 2^10 limbs of the 256 coefficients, coefficient m at 3 m.
Candidates are 23 bit values from 3 byte chunks of 5 squeezed blocks (280 candidates), rejected when >= q. shift is a one-hot encoding of how many candidates have been rejected so far; output m takes the accepted candidate m + shift. More than 16 rejections before the 256th acceptance (probability below 2^-70) makes the circuit unsatisfiable.
Per candidate values are kept as vectors over the candidates (columns) so the work is done with vector operations.
- Calls
bits/and_bits,calloc,mldsa/mldsa_limbs,keccak/shake128,slice,valloc- Precompiles
assert_lt!,clone!,concat!,constrain_eq!,field_bit_width!,loop!,loop_flat_map!- Used by
mldsa/mldsa_expand_a
Source
# RejNTTPoly (FIPS 204 Algorithm 30): sample a polynomial with uniform
# coefficients below q from SHAKE128(seed).
#
# `seed` is a vector of bits. Returns base 2^10 limbs of the 256
# coefficients, coefficient m at 3 m.
#
# Candidates are 23 bit values from 3 byte chunks of 5 squeezed blocks
# (280 candidates), rejected when >= q. `shift` is a one-hot encoding of how
# many candidates have been rejected so far; output m takes the accepted
# candidate m + shift. More than 16 rejections before the 256th acceptance
# (probability below 2^-70) makes the circuit unsatisfiable.
#
# Per candidate values are kept as vectors over the candidates (columns) so
# the work is done with vector operations.
(seed)
assert_lt! 22, field_bit_width!, "ML-DSA needs a field of at least q = 8380417 elements"
static MAX_SHIFT = 16
static CANDIDATES = 256 + MAX_SHIFT
static S = MAX_SHIFT + 1
static ones = valloc(CANDIDATES, 1)
let stream = shake128(seed, 5 * 1344)
# bit k of every candidate at k CANDIDATES + t
let cols = loop_flat_map! 23, k {
loop_flat_map! CANDIDATES, t {
stream[24 * t + k]
}
}
# q = 2^23 - 2^13 + 1: rejected when bits 13..22 are all set and bits 0..12 are not all clear
let mut high = slice((clone! cols), 13 * CANDIDATES, CANDIDATES)
loop! 9, i {
high = and_bits(high, slice((clone! cols), (14 + i) * CANDIDATES, CANDIDATES))
}
let mut low_clear = (clone! ones) - slice((clone! cols), 0, CANDIDATES)
loop! 12, i {
low_clear = and_bits(low_clear, (clone! ones) - slice((clone! cols), (1 + i) * CANDIDATES, CANDIDATES))
}
let reject = and_bits(high, (clone! ones) - low_clear)
# limb u of every candidate at u CANDIDATES + t
let limbs = loop_flat_map! CANDIDATES, t {
mldsa_limbs(slice((clone! stream), 24 * t, 23))
}
let limb_cols = loop_flat_map! 3, u {
loop_flat_map! CANDIDATES, t {
limbs[3 * t + u]
}
}
# select[S t + s] = candidate t is accepted and preceded by s rejections
static shift_ones = valloc(S, 1)
let mut shift = concat! [1], calloc(MAX_SHIFT)
let select = loop_flat_map! CANDIDATES, t {
let r = reject[t]
let r_vec = loop_flat_map! S {
r
}
let sel = and_bits((clone! shift), (clone! shift_ones) - (clone! r_vec))
# shift moves up one position when candidate t is rejected
let shifted = concat! [0], slice((clone! shift), 0, MAX_SHIFT)
shift = (clone! shift) + r_vec * (shifted - (clone! shift))
sel
}
# output m takes candidate m + s when select[S (m + s) + s]
static out_ones = valloc(256, 1)
let mut found = calloc(256)
let mut out0 = calloc(256)
let mut out1 = calloc(256)
let mut out2 = calloc(256)
loop! S, s {
let sel = loop_flat_map! 256, m {
select[S * (m + s) + s]
}
found = found + (clone! sel)
out0 = out0 + (clone! sel) * slice((clone! limb_cols), s, 256)
out1 = out1 + (clone! sel) * slice((clone! limb_cols), CANDIDATES + s, 256)
out2 = out2 + sel * slice((clone! limb_cols), 2 * CANDIDATES + s, 256)
}
# exactly one candidate supplies coefficient m
constrain_eq! out_ones, found
loop_flat_map! 256, m {
concat! slice((clone! out0), m, 1), slice((clone! out1), m, 1), slice((clone! out2), m, 1)
}