[curves] Generalizing EdDSA

Trevor Perrin trevp at trevp.net
Sun Sep 10 00:47:28 PDT 2017

On Thu, Sep 7, 2017 at 8:50 PM, Oleg Andreev <oleganza at gmail.com> wrote:

> Form (a):
> P is a pubkey,
> (R,s) is a signature (point R, scalar s),
> verifier checks that point (s*B) equals (R + Hash(msg || P || R)*P).
> Form (b):
> P is a pubkey,
> (k,s) is a signature (scalars k, s),
> verifier checks that Hash(msg || P || s*B - k*P) is equal to k.

> Are there some performance considerations that I missed that make (a)
> more performant (maybe allowing batch verification?) in existing EdDSA?

Hi Oleg,

Yes, I believe batch verification was one rationale for this decision in
Ed25519 [1]:

"Sending R instead of H(R,M) also has the advantage of allowing batch
signature verification, which is typically twice as fast as verifying one
signature at a time. That's why Ed25519 doesn't use this compression."

I think the utility of batch verification is debatable, since significant
speedup is only achieved with larger batches, which don't often occur in
protocols [2].  But one plausible use case I've heard proposed is

A Schnorr-based VRF (e.g. "VEdDSA" nee "VXEdDSA") is another case, similar
to your ring signature example, where it probably makes sense to send a
single hash value in place of multiple points [3].


[1] https://blog.cr.yp.to/20140323-ecdsa.html
[2] https://moderncrypto.org/mail-archive/curves/2016/000836.html
[3] https://signal.org/docs/specifications/xeddsa/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170910/c6b54a81/attachment.html>

More information about the Curves mailing list