Index Mathematics Conjectures nbv lettuce Widgets

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