Index Mathematics Conjectures nbv lettuce Widgets

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