Biased sampling by truncation may weaken soundness security

[this-vishalsingh]

Context: crates/backend/fiat-shamir/src/challenger.rs

Severity: LOW

Description

The sample_in_range() maps field elements to bits-wide integers via bitmask truncation. Unless the underlying distribution is exactly uniform over a multiple of 2^bits, this introduces modulo/truncation bias (acknowledged by the comment).
If these samples are used in security-critical contexts (e.g., choosing verifier queries/indices), bias can slightly reduce soundness margins or make some outcomes more likely than intended.

/// Warning: not perfectly uniform
pub fn sample_in_range(&mut self, bits: usize, n_samples: usize) -> Vec<usize> {
    assert!(bits < F::bits());
    let sampled_fe = self.sample_many(n_samples.div_ceil(RATE)).into_iter().flatten();
    let mut res = Vec::new();
    for fe in sampled_fe.take(n_samples) {
        let rand_usize = fe.as_canonical_u64() as usize;
        res.push(rand_usize & ((1 << bits) - 1));
    }
    res
}

Recommendation

Use rejection sampling to obtain unbiased values in [0, 2^bits) (e.g., resample when the candidate exceeds the largest multiple of 2^bits below the field modulus / 2^64 range used).
Document acceptable bias if it is proven negligible for the protocol parameters.