[curves] Generalizing EdDSA

[Trevor Perrin]

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
cryptocurrencies.

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].

Trevor

[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>