mldsa_hint_unpack
stdlib/mldsa/mldsa_hint_unpack.nbv
mldsa_hint_unpack(y)
HintBitUnpack for ML-DSA-44 (FIPS 204 Algorithm 21), omega = 80, k = 4.
y holds the 84 hint bytes as 8 bits each. Bytes 0..80 are hint positions, bytes 80..84 the running count of positions after each polynomial. Constrains the encoding to be well formed (FIPS 204 returns ⊥ otherwise) and returns the 4 * 256 hint bits, polynomial i at 256 i.
- Calls
bits/and_bits,bits/from_bits,bits/one_hot_bits,slice,bits/to_bits_exact- Precompiles
assert_eq!,assert_lt!,clone!,constrain_eq!,field_bit_width!,if_lt!,len!,loop!- Used by
mldsa/mldsa44_parse_sig
Source
# HintBitUnpack for ML-DSA-44 (FIPS 204 Algorithm 21), omega = 80, k = 4.
#
# `y` holds the 84 hint bytes as 8 bits each. Bytes 0..80 are hint
# positions, bytes 80..84 the running count of positions after each
# polynomial. Constrains the encoding to be well formed (FIPS 204 returns
# ⊥ otherwise) and returns the 4 * 256 hint bits, polynomial i at 256 i.
(y)
assert_lt! 22, field_bit_width!, "ML-DSA needs a field of at least q = 8380417 elements"
static OMEGA = 80
static K = 4
assert_eq! 8 * (OMEGA + K), len! y
# byte values
let mut v[OMEGA + K]
loop! OMEGA + K, m {
v[m] = from_bits(slice((clone! y), 8 * m, 8))
}
# counts are non-decreasing and at most omega
let _ = to_bits_exact(OMEGA - v[OMEGA + K - 1], 7)
let _ = to_bits_exact(v[OMEGA], 7)
loop! K - 1, i {
let _ = to_bits_exact(v[OMEGA + i + 1] - v[OMEGA + i], 7)
}
# below[OMEGA i + m] = (m < count_i). count_i + 127 - m lies in [47, 207],
# bit 7 is set exactly when count_i > m.
let mut below[K * OMEGA]
loop! K, i {
loop! OMEGA, m {
let b = to_bits_exact(v[OMEGA + i] + 127 - m, 8)
below[OMEGA * i + m] = b[7]
}
}
# member[OMEGA i + m] = 1 when slot m holds a position of polynomial i
let mut member[K * OMEGA]
loop! OMEGA, m {
member[m] = below[m]
}
loop! K - 1, i {
loop! OMEGA, m {
member[OMEGA * (i + 1) + m] = below[OMEGA * (i + 1) + m] - below[OMEGA * i + m]
}
}
loop! OMEGA, m {
# unused slots are zero
constrain_eq! 0, (1 - below[OMEGA * (K - 1) + m]) * v[m]
# positions within a polynomial strictly increase
if_lt! 0, m {
let mut same = 0
loop! K, i {
same = same + and_bits(member[OMEGA * i + m], member[OMEGA * i + m - 1])
}
let _ = to_bits_exact(same * (v[m] - v[m - 1] - 1), 8)
}
}
# h[256 i + p] = sum over slots of polynomial i of (position == p)
let mut h[256 * K]
loop! OMEGA, m {
loop! K, i {
let onehot = one_hot_bits(slice((clone! y), 8 * m, 8), member[OMEGA * i + m])
loop! 256, p {
h[256 * i + p] = h[256 * i + p] + onehot[p]
}
}
}
h