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

[Michele Orrù <[e-mail]>]

On 4/6/19 7:47 PM, Ilari Liusvaara wrote:

> 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.
> 


Hi Ilari,

that's right, good point. It seems to us that there are two 
possibilities now:

- (as you note) we list the curves for which 64 extra bits are needed in 
order to smooth out the bias, i.e. the curves for which p = 2^λ - r is 
very close to a power of two, or more precisely (1-r/p) r/2^(λ-1)  < 2^-64.

- or we just advise developers to always take 64 + log(p) + 1 bits.
Unless those extra bits do not come cheap, it is perhaps the easiest 
solution?


In both cases, we think that the standard could be more explicit about 
how much entropy is needed for a (close to) uniform distribution. Thoughts?



PS. adding Brice in Cc; I forgot him in my previous mail.
--
μ.