mldsa_sample_in_ball
stdlib/mldsa/mldsa_sample_in_ball.nbv
mldsa_sample_in_ball(ctilde)
SampleInBall for ML-DSA-44 (FIPS 204 Algorithm 29), tau = 39.
ctilde holds the 256 bits of the commitment hash. Returns the 256 coefficients of c in {-1, 0, 1} as field elements.
The first SHAKE256 block supplies 8 sign bytes and 128 candidate bytes. Candidates are consumed in order; step is a one-hot encoding of how many of the 39 positions i = 217 .. 255 have been placed. A candidate j is accepted when j <= i and positions remain, and then c[i] = c[j] and c[j] = +-1. Fewer than 39 acceptances among 128 candidates happens with negligible probability and makes the circuit unsatisfiable.
- Calls
bits/and_bits,bits/from_bits,bits/one_hot_bits,keccak/shake256,slice,bits/to_bits_exact- Precompiles
assert_eq!,assert_lt!,clone!,constrain_eq!,field_bit_width!,if_lte!,len!,loop!,wtns!- Used by
dilithium/mldsa/mldsa44_verify,dilithium/mldsa/mldsa44_verify_static,mersenne61/mldsa/mldsa44_verify,milli/mldsa/mldsa44_verify
Source
# SampleInBall for ML-DSA-44 (FIPS 204 Algorithm 29), tau = 39.
#
# `ctilde` holds the 256 bits of the commitment hash. Returns the 256
# coefficients of c in {-1, 0, 1} as field elements.
#
# The first SHAKE256 block supplies 8 sign bytes and 128 candidate bytes.
# Candidates are consumed in order; `step` is a one-hot encoding of how many
# of the 39 positions i = 217 .. 255 have been placed. A candidate j is
# accepted when j <= i and positions remain, and then c[i] = c[j] and
# c[j] = +-1. Fewer than 39 acceptances among 128 candidates happens with
# negligible probability and makes the circuit unsatisfiable.
(ctilde)
assert_lt! 22, field_bit_width!, "ML-DSA needs a field of at least q = 8380417 elements"
static TAU = 39
static FIRST = 256 - TAU
static CANDIDATES = 128
assert_eq! 256, len! ctilde
let stream = shake256(ctilde, 1088)
let mut c[256]
let mut step[TAU + 1]
step[0] = 1
loop! CANDIDATES, n {
let j_bits = slice((clone! stream), 64 + 8 * n, 8)
let j = from_bits(clone! j_bits)
let mut t = 0
loop! TAU, s {
t = t + s * step[s]
}
# j <= 217 + t: the shifted difference lies in [218, 512]
let diff_bits = to_bits_exact(FIRST + t - j + 256, 10)
let accept = and_bits(diff_bits[8] + diff_bits[9], 1 - step[TAU])
# sign bit for this step
let mut sign_bit = 0
loop! TAU, s {
sign_bit = sign_bit + and_bits(step[s], stream[s])
}
let sign = 1 - 2 * sign_bit
# gated[p] = accept * (j == p)
let gated = one_hot_bits(j_bits, accept)
let mut c_j = 0
loop! 256, p {
c_j = c_j + gated[p] * c[p]
}
loop! 256, p {
let mut next = c[p] + gated[p] * (sign - c[p])
# position i = 217 + t receives the old c[j] unless i = j
if_lte! FIRST, p {
let at_i = step[p - FIRST] * (accept - gated[p])
next = next + at_i * (c_j - c[p])
}
c[p] = wtns! next
}
# advance the step counter when accepted
let mut next_step[TAU + 1]
next_step[0] = step[0] - accept * step[0]
loop! TAU, s {
next_step[s + 1] = step[s + 1] + accept * (step[s] - step[s + 1])
}
step = next_step
}
constrain_eq! 1, step[TAU]
c