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

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Cfrg <[e-mail]> On Behalf Of Christopher Wood
> 
> Some existing standards [2] recommend taking at least log2(p) + 64 bits “so
> that bias produced by the mod function … is negligible.” If we were to follow
> this guidance for hash2curve, we’d lose out on several ciphersuite
> combinations, such as P-256 and Curve25519 with SHA256.
> 
> So, our question to the group is, how many extra bits are necessary?
> 

Zero (or perhaps less?) extra bits are necessary, at least for some hashes mentioned in Section 10:

 Elligator2, for example, only maps strings to "about half of all curve points,"
 whereas Icart's method only covers about 5/8 of the points.

The output points (for these hashes) are already biased and easily distinguishable from general points, hence biased field elements should thus be tolerable too. 

I vaguely recall reading about some of the hash-to-point functions aiming to produce a uniformly distributed point.  I am not sure if your draft includes such hashes.  If it does, the uniform field elements would likely be needed for those hashes, if only because uniformity is advertised.

Best regards,

Dan

PS

By "less" than zero extra bits, I meant using, say, SHA1 to map a bit string into a P256 point.  The only possible gain of such would be compression if one use a variable-length point representation.  This *might* be safe in some applications, similar in safety to the way that using a ECDH generator with a small coordinate might be safe, and the way of using points with 1 bit of bias is.  (I am ignoring the general questionability of SHA1, just focusing on its shorter length.)

The requirements from NIST SP 800-56a are about private key generation, where uniformity is more important, e.g. in signatures, and perhaps MQV.