Bias in sample_bits
#613
Comments
|
@SyxtonPrime had an interesting idea for an improvement on the usual rejection sampling. I think it can be summarized as: check for the most significant bit that differs, then emit all the less significant bits, which should be uniformly random. We could view it as rejecting certain bits rather than an entire field element. Another approach could be: assume The above method just suffers from If we're okay with that imperfect uniformity, I suspect this latter method may be easier to implement in recursive proofs, at least in certain settings where there could be complications with variable-time methods. |
|
I have found one general difficulty for sampling bits in recursion is that you mu
5D56
st bit decompose an arbitrary field element It seems any kind of bit based rejection sampling will still run into this issue. Your latter approach with |
Currently
sample_bits(bits)is implemented by sampling a random field elementrand_fand then applying a mask:rand_usize & ((1 << bits) - 1). This can introduce some bias, for example if we dosample_bits(3)over GF(13), the masking is a 13-to-8 map where some outputs have one associated input while some have two.If we look at one bit in isolation, a less-significant bit will have shorter runs (i.e. more frequent flips), so it won't have much bias which only comes from a final run of 0s. A bit close to the most-significant one could be heavily biased.
I think we use this in two places, one for FRI grinding and one for FRI query locations. Both can tolerate some bias, so if
bitsis significantly smaller than the field size (which I think it normally is), the security loss might be minor. But we should quantify and account for it, if not eliminate it outright.I think the only way to eliminate bias is rejection sampling, like maybe reject if the MSB is 1, otherwise apply the mask. This would mean a variable-length loop which might complicate recursion? cc @yi-sun, @jtguibas. If so, might be better to quantify the bias, show that it's acceptable, and in extreme cases (if
bitsis close to the field size) maybe sample more than one field element so we can use some low bits from each.The text was updated successfully, but these errors were encountered: