Re: [Cfrg] EdDSA and > 512 curve & hash (Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement)

[Vadym Fedyukovych <[e-mail]>]

On Sun, Jan 12, 2014 at 07:13:16AM -0800, Robert Ransom wrote:
> On 1/12/14, Adam Back <[e-mail]> wrote:
> 
> > So actually Bernstein went in the opposite direction, not only using
> > sub-group size, but double sub-group size hash, basically because he could
> > without increasing the signature size, and thereby slightly even further
> > reducing the dependency on hash security and hash properties.  I do not
> > consider its necessary, just its because he could, slightly more security
> > almost for free.  But I think an EdDSA variant that used a 512-bit curve
> > could safely use a 512-bit hash, because even the double width hash is
> > over-engineering.
> 
> It can for the hash of the message.
> 
> > EdDSA also uses the deterministic DSA k trick (computed from m and x the
> > private key).
> 
> Deterministic generation of message keys is the primary reason that
> EdDSA requires a double-length hash function.
> 
> EdDSA relies on the hash function having double-length output in two ways:
> 
> * Message key generation relies on the output being noticeably longer
> than the group order in order to generate *uniform* exponents.

Choosing a message key (an initial random in interactive system)
from a large interval is a well-known idea for a group of a hidden order.
For a group of known order, reducing almost anything modulo group order
would likely result in quite a non-uniform distribution.
It is non-trivial to see how/whether hash of roughly twice-bitlength of group order 
would be better than hash smaller than group order.

Hash bitlength is rather non-critical while choosing a challenge,
that should be just a large enough set.

Vadym Fedyukovych