Index Mathematics Conjectures nbv lettuce Widgets

mldsa44_w_approx_static

stdlib/dilithium/mldsa/mldsa44_w_approx_static.nbv only in the dilithium field

mldsa44_w_approx_static(static a_hat, v_bits, c, static t_hat)

w_approx = NTT^-1(A_hat NTT(z) - NTT(c) t_hat) for ML-DSA-44 in the field Z_q itself (FIPS 204 Algorithm 8, step 7), with A_hat and t_hat known at compile time.

Every step is linear in the witness: the NTTs are linear maps and the pointwise products have a static factor. a_hat holds the static NTT domain coefficients of A_hat (polynomial (i, s) coefficient m at 256 (l i + s) + m), v_bits the 18 bits of each v = gamma1 - z, c the challenge coefficients in {-1, 0, 1} and t_hat the static NTT(2^13 t1). Returns 23 bits per canonical coefficient of w_approx.

Calls
bits/from_bits, mldsa/mldsa_assert_below_q, dilithium/mldsa/mldsa_intt_native, dilithium/mldsa/mldsa_ntt_native, slice, bits/to_bits_exact
Precompiles
assert_eq!, clone!, div_exact!, len!, loop!, wtns!
Used by
dilithium/mldsa/mldsa44_verify_static

Source

# w_approx = NTT^-1(A_hat NTT(z) - NTT(c) t_hat) for ML-DSA-44 in the field
# Z_q itself (FIPS 204 Algorithm 8, step 7), with A_hat and t_hat known at
# compile time.
#
# Every step is linear in the witness: the NTTs are linear maps and the
# pointwise products have a static factor. `a_hat` holds the static NTT
# domain coefficients of A_hat (polynomial (i, s) coefficient m at
# 256 (l i + s) + m), `v_bits` the 18 bits of each v = gamma1 - z, `c` the
# challenge coefficients in {-1, 0, 1} and `t_hat` the static NTT(2^13 t1).
# Returns 23 bits per canonical coefficient of w_approx.
(static a_hat, v_bits, c, static t_hat)

static GAMMA1 = 131072
static k = div_exact! (len! t_hat), 256
static l = div_exact! (len! v_bits), 18 * 256
assert_eq! (len! a_hat), 256 * k * l

let mut z[256 * l]
loop! 256 * l, i {
  z[i] = wtns! GAMMA1 - from_bits(slice((clone! v_bits), 18 * i, 18))
}
let z_hat = mldsa_ntt_native(z, 1)
let c_hat = mldsa_ntt_native(c, 1)

let mut y[256 * k]
loop! 256, m {
  loop! k, i {
    let mut x = 0 - t_hat[256 * i + m] * c_hat[m]
    loop! l, s {
      x = x + a_hat[256 * (l * i + s) + m] * z_hat[256 * s + m]
    }
    y[256 * i + m] = x
  }
}

let w = mldsa_intt_native(y)
let mut out[23 * 256 * k]
loop! 256 * k, i {
  let bits = mldsa_assert_below_q(to_bits_exact(w[i], 23))
  loop! 23, b {
    out[23 * i + b] = bits[b]
  }
}
out