Re: [Cfrg] Recommended bit length before truncating a hash mod p

[Ilari Liusvaara <[e-mail]>]

On Tue, Apr 02, 2019 at 10:07:13AM +0200, Michele Orrù wrote:
> 
> Together with Anita (in Cc.) we independently thought that the draft could
> be a bit more precise about how many bits to take before reducing mod p.
> More specifically, the sentence:
> 
> ```
> To address this, our hash2base algorithm greedily takes as many bits as
> possible before reducing mod p, in order to smooth out this bias. This is
> preferable to an iterated procedure, such as rejection sampling, since this
> can be hard to reliably implement in constant time.
> ```
> 
> is imprecise: a developer should know exactly how many bits to add (for the
> current security level) in order to have a distribution indistinguishable
> from uniformly random mod p. Taking into account what has been said so far,
> we would like to change the above sentence to:
> 
> ```
> In order to smooth out this bias, our hash2base algorithm takes 64 +
> floor(log2(p)) + 1 bits in order to smooth out this bias. This is preferable
> to an iterated procedure, such as rejection sampling, since this can be hard
> to reliably implement in constant time.
> ```
> 
> This should at least give an intuition that adding 64 bits makes the
> difference of the two distributions statistically negligible.
> What do you think? Is this relevant?

In fact, the uniformity can heavily depend on p. Any p very close to
power of two gives very uniform results. And one needs lots of extra
bits to increase the uniformity further.

Looking at Curve25519, Curve448 and NIST P-384, the SD is <2^-200 and
that won't bulge with 64 extra bits.

NIST P-256 has much bigger base SD (~2^-32), and that starts to move
with ~30 extra bits. 64 extra bits seems to decrease SD by factor of
~2^64.



-Ilari