Simple: Hash Into a Prime Field

Question

If I have some bytes, and I want to compute a secure hash into a prime field which is 300 bits long I can:

• Use a nice hash, like sha3_512, and then

  1. modulo my prime field (introduces some bias).

  2. toss bits most significant bits away until the number is < my prime (some bias toward smaller numbers)

  3. toss bits most significant bits away until 300 bits, and then modulo my prime if needed (less bias?).

  4. toss bits most significant bits away until 300 bits, then start over (hash the hash) if the number is too big (eventually converge). (no bias, slow)

  5. ???? some better method ????

How important is the bias overall?

1. If I'm using the resulting hash as the hash for a EC signature scheme, it's insignificant...since the hash isn't protecting anything... it's just collisions that are a concern, which we've made worse by a fraction of a bit.

2. If I'm using the resulting hash as a "nonce" to protect a secret value during, for example, an mpc computation, it could be "leaky". Over many uses of such a scheme someone might be use the bias to attack the key or the mpc. The same holds for deterministic nonces used to reduce signature malleability, which is why I think they are a very bad idea. See https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf, for just how bad this is.

3. If I'm using the resulting hash as the private part of an pairing based signature scheme (which requires mapping a message into the curve) , it seems to me that the bias just causes a similar collision loss.

Has anyone compared masking methods for bias? Is there a good reference on best practices? IS there a good analysis of the types of protocols for which such masking is a concern?

Answer 1

First thing to note is that, if your paradigm is the hash the message into a 512 bit value, and then map that 512 bit field into a value $(0, p-1)$, then (unless $p$ happens to be a power of 2, and very few primes are) there will always be some bias. $p$ is not a divisor of $2^{512}$, and hence some values will have more 512 bit preimages than others (and going to a complicated hash-of-a-hash method doesn't change this).

Secondly, if this is the paradigm we need to live with, your method 1 (compute $hash \bmod p$) achieves the minimal possible bias; some values will have $\lfloor 2^{512}/p \rfloor$ preimages (and hence occur with probability $2^{-512} \lfloor 2^{512}/p \rfloor$, others will have $\lfloor 2^{512}/p \rfloor + 1$ preimages (and so occur with probability $2^{-512} \lfloor 2^{512}/p \rfloor + 2^{-512}$; no other possibilities.

Thirdly, the amount of this bias (for $p \approx. 2^{300}$) is truly tiny; the ratio between $2^{-512} \lfloor 2^{512}/p \rfloor$ and $2^{-512} \lfloor 2^{512}/p \rfloor + 2^{-512}$ is circa $1 + 2^{-212}$; to even detect a bias that tiny (and an undetectable bias cannot be exploited) you'd need to sample circa $2^{424}$ hashes before the bias can be detected; and you will never ever generate that many.

Fourthly, one nice thing about the modulo method is that it is easy to test (assuming you're using a vetted modulo routine). With the methods that involve exceptions, well, those can be trickier (because you need to go through all the possible cases to make sure those are handled properly); with the modulo, there is only one case.