Index Mathematics Conjectures nbv lettuce Widgets

mldsa_use_hint

stdlib/mldsa/mldsa_use_hint.nbv

mldsa_use_hint(r_bits, h)

UseHint(h, r) for ML-DSA-44 (FIPS 204 Algorithms 36 and 40), gamma2 = (q - 1) / 88.

r_bits are the 23 bits of a canonical r < q and h a hint bit. Returns the 6 bits of the result, a value in [0, 43].

r = 2 gamma2 quot + rem with quot in [0, 44], rem in [0, 2 gamma2) and rem = 0 when quot = 44, so the right hand side is at most q - 1 as an integer and the field equation is an integer equation in any field of at least q elements, including Z_q itself. Decompose gives r1 = quot + (rem > gamma2) and r0 = rem - 2 gamma2 (rem > gamma2), except when r1 = 44 (r - r0 = q - 1) where r1 = 0 and r0 decreases by one.

Calls
bits/and_bits, bits/from_bits, bits/to_bits_exact
Precompiles
assert_eq!, assert_lt!, clone!, constrain_eq!, div_floor!, field_bit_width!, len!, loop!, modulo!
Used by
mldsa/mldsa44_finish

Source

# UseHint(h, r) for ML-DSA-44 (FIPS 204 Algorithms 36 and 40), gamma2 = (q - 1) / 88.
#
# `r_bits` are the 23 bits of a canonical r < q and `h` a hint bit. Returns
# the 6 bits of the result, a value in [0, 43].
#
# r = 2 gamma2 quot + rem with quot in [0, 44], rem in [0, 2 gamma2) and
# rem = 0 when quot = 44, so the right hand side is at most q - 1 as an
# integer and the field equation is an integer equation in any field of at
# least q elements, including Z_q itself. Decompose gives
# r1 = quot + (rem > gamma2) and r0 = rem - 2 gamma2 (rem > gamma2), except
# when r1 = 44 (r - r0 = q - 1) where r1 = 0 and r0 decreases by one.
(r_bits, h)

assert_lt! 22, field_bit_width!, "ML-DSA needs a field of at least q = 8380417 elements"

static GAMMA2 = 95232
assert_eq! 23, len! r_bits

let r = from_bits(r_bits)
let quot_bits = to_bits_exact((div_floor! r, 2 * GAMMA2), 6)
let quot = from_bits(clone! quot_bits)
let rem = modulo! r, 2 * GAMMA2
constrain_eq! r, 2 * GAMMA2 * quot + rem

# quot <= 44, rem < 2 gamma2, and quot = 44 (bits 5, 3 and 2 set) forces rem = 0
let _ = to_bits_exact(44 - quot, 6)
let _ = to_bits_exact(rem, 18)
let _ = to_bits_exact(2 * GAMMA2 - 1 - rem, 18)
let quot_44 = and_bits(and_bits(quot_bits[5], quot_bits[3]), quot_bits[2])
constrain_eq! 0, quot_44 * rem

# high = rem > gamma2. Shifted by 2^17 the value lies in [0, 2^18) and bit 17
# is set exactly when rem >= gamma2 + 1.
let high_bits = to_bits_exact(rem - GAMMA2 - 1 + 131072, 18)
let high = high_bits[17]

# r1 before the wrap at 44, at most 44 because quot = 44 implies high = 0
let r1_bits = to_bits_exact(quot + high, 6)
let is_44 = and_bits(and_bits(r1_bits[5], r1_bits[3]), r1_bits[2])
let r1 = from_bits(clone! r1_bits) - 44 * is_44

# r0 > 0. The unwrapped r0 lies in (-gamma2, gamma2], shifted by 2^17 - 1 bit
# 17 is set exactly when it is positive. When r1 wraps the unwrapped r0 is
# already <= 0, so the decrement never changes the sign test.
let positive_bits = to_bits_exact(rem - 2 * GAMMA2 * high - 1 + 131072, 18)
let r0_positive = positive_bits[17]

let up = and_bits(h, r0_positive)
let down = h - up

# r1 = 43 (bits 5, 3, 1, 0 of the unwrapped value) and r1 = 0 (unwrapped 0 or 44)
let is_43 = and_bits(and_bits(r1_bits[5], r1_bits[3]), and_bits(r1_bits[1], r1_bits[0]))
let mut r1_zero = 1 - r1_bits[0]
loop! 5, i {
  r1_zero = and_bits(r1_zero, 1 - r1_bits[i + 1])
}
let is_0 = is_44 + r1_zero

# (r1 + 1) mod 44 when up, (r1 - 1) mod 44 when down
let w1 = r1 + up - down + 44 * (and_bits(down, is_0) - and_bits(up, is_43))
to_bits_exact(w1, 6)