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 02:39:42PM -0800, Watson Ladd wrote:
> On Sun, Jan 12, 2014 at 2:29 PM, Vadym Fedyukovych <[e-mail]> wrote:
> > 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.
> 
> Completely wrong for trivial reasons. Let's say we are picking a
> random number up to k by taking one up to n and reducing.
> Write n=kq+r, with r the remainder. Then the bias is exactly r/n,
> which for n the square of k is at most 1/k, and hence negligible if
> k is big enough. This is clearly better than if the hash length is
> smaller than the group order, in which case a significant number of
> group elements will never be picked.

Wrong conclusion starting from irrelevant definition.

Observable S (response in Schnorr protocol) is from ring modulo group order.
For a non-uniform probability distribution of S,
one would consider bias like max_{i,j} | p(S(H_i)) - p(S(H_j)) |,
for uniform distribution of H (hash function samples).
No chance to reduce such a bias by increasing hash bitlength.

Additional consideration may be helpful
to decide whether bias is small enough.

Vadym Fedyukovych