Hacker News new | ask | show | jobs
by lambdafu 790 days ago
Caution here. If your modulus is too close to the maximum truncated value, there can be a bias in the upper bits, too. For example, if you reduce a number between 0 and 15 by the modulus 13, the values 0, 1 and 2 will be twice as likely as the values 3-12. This means that the highest bit will be 0 in 11 out of 16 cases. Even such a small bias might be exploitable (for example, sub 1 bit bias up to 160-bit ECDSA here: Gao, Wang, Hu, He https://eprint.iacr.org/2024/296.pdf)
1 comments
aidenn0 790 days ago
Neither 15 nor 13 are powers of two.
link
some_furry 790 days ago
The interval [0, 15] represent 16 possible values, which is a power of 2.

The correct way to get an unbiased distribution from a sample of 2^x to a modulo that is not an even power of 2 is to use rejection sampling.

This is what RFC 6979 says to do https://datatracker.ietf.org/doc/html/rfc6979#section-3.2

But you can also see this technique in CSPRNG code; i.e. https://github.com/php/php-src/blob/d40726670fd2915dcd807673...

link
aidenn0 790 days ago
I missed it was [0,15]

This doesn't make 13 a power of two. I'm aware of rejection sampling; my point was if you have a N bit value X and want M bits, truncating X to M bits and X MOD 2*M is the same. Neither solve the problem where M > N, which is what TFA is about.

link
some_furry 790 days ago
> This doesn't make 13 a power of two.

Where did I imply that it is?

> I'm aware of rejection sampling; my point was if you have a N bit value X and want M bits, truncating X to M bits and X MOD 2*M is the same.

Sure.

> Neither solve the problem where M > N, which is what TFA is about.

If you observe my other comments, you'll see I'm well aware of what the article is about.

link
aidenn0 790 days ago
> Where did I imply that it is?

You used 13 as an example in a response to my comment that was:

Isn't modulo the same as truncation when dealing with powers of two?

link
some_furry 790 days ago
> You used 13 as an example

I don't see the number 13 in any of my comments on this thread (except this one, or where I quoted you). Perhaps you are confusing me with someone else?

link
wbl 790 days ago
But 16 is.
link