3 ms·

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 betwe

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 https://eprint.iacr.org/2024/296.pdf)

aidenn0 2y ago
Neither 15 nor 13 are powers of two.
- wbl 2y ago
  But 16 is.
- some_furry 2y 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 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/d40726670fd2915dcd8076738c56596e7c877b58/ext/random/csprng.c#L243-L248 https://github.com/php/php-src/blob/d40726670fd2915dcd807673...
  - aidenn0 2y 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.
    - some_furry 2y 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.
      - aidenn0 2y 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?
        some_furry 2y 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?
        aidenn0 2y ago
        Ah yes, that was lambdafu

aidenn0 2y ago

Neither 15 nor 13 are powers of two.

wbl 2y ago
But 16 is.
some_furry 2y 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 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/d40726670fd2915dcd8076738c56596e7c877b58/ext/random/csprng.c#L243-L248 https://github.com/php/php-src/blob/d40726670fd2915dcd807673...
- aidenn0 2y 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.
  - some_furry 2y 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.
    - aidenn0 2y 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?
      - some_furry 2y 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?
        aidenn0 2y ago
        Ah yes, that was lambdafu