Index Mathematics Conjectures nbv lettuce Widgets

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