Open stefandeml opened 5 years ago
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.
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
I have the following proposal:
Sounds good to me! - Thanks for addressing this.
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