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)