public-key recovery in EdDSA implementation

[stefandeml]

Hello,

based on the implementation here you only bind the message to the nonce, but not the public key. Usually in EdDSA one also binds the public key: https://tools.ietf.org/html/rfc8032#section-3.3 https://eprint.iacr.org/2015/677.pdf

By inverting the verification equation the current implementation allows to compute the public key if the message and the signature are known. Is there any particular reason/use-case why you deviated from standard implementations?

Thanks

[shamatar]

This algorithm is not strictly EdDSA, of course. But EdDSA also requires use of 64bit hashes that are definitely snark friendly. Anyway, it’s just a Schnorr signature. Attaching public key eliminates only some kind of an attack, but in the implementation I was optimizing for a smallest number of constraints. Binding for public key will require another round of Blake2s or Sha256, that is around 24k constraints.

[HarryR]

This also means that signatures are malleable.

Anybody, who observes an existing signature, can derive a new public key and s parameter for the same message and R, to spoof a valid signature for the same message - without needing to know the secret key.

For example, where x is any random field element of our choice, we can modify A (the public key) and s as follows, which results in a valid signature:

sage: factor(R + ((A + (G*x))*h))
(a*h + h*x + r)*G
sage: factor((s+(x*h))*G)
(a*h + h*x + r)*G

Where h = H(R,M) and G is the curve generator point.

While this may be OK for some use cases, people expect that signatures are not malleable - this is part of every standard for signatures - to avoid malleability, so it should probably be fixed by including the public key in the hash used for the fiat-shamir transform - or including a huge flashing disclaimer/caveat.

@stefandeml

[shamatar]

I have the following proposal:

• Rename the existing function to "schnorr signature"
• implement variants for "sha256" as a hash function too

[stefandeml]

Sounds good to me! - Thanks for addressing this.