Re: [CFRG] EdDSA and ECDLP

[Bas Westerbaan <[e-mail]>]

> > Many sources I can find say that the public key is generated as it is
> > done for ECDSA, i.e., the public key Q = [k]G, but that that is not
> > how I read RFC 8032 and NIST FIPS 186-5.  Here the private key is
> > hashed with an algorithm that that produces a digest having a size
> > twice the size of the private key. Only the first half of the digest
> > is used to generate the public key and by solving the ECDLP you can
> > only get half of the digest. However, to generate a false signature,
> > you also need the other half of the digest, so that does not really
> > help you. So, I am still wandering how a quantum computer can break
> > EdDSA.
>
> The generated signatures still work if the attacker just substitutes
> something random as the second half (it is just RNG seed). Or the
> attacker might just use random r in signing, that also works.
>

Correct. To wit, to create a forgery on M, pick a random R, compute h = H(R
|| A || M) and Q := R + [h] A. Find S such that [S]B = Q. Now (R,S) is a
valid signature for M.