<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Sep 7, 2017 at 8:50 PM, Oleg Andreev <span dir="ltr"><<a href="mailto:oleganza@gmail.com" target="_blank">oleganza@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
Form (a):<br>
<br>
P is a pubkey,<br>
(R,s) is a signature (point R, scalar s),<br>
verifier checks that point (s*B) equals (R + Hash(msg || P || R)*P).<br>
<br>
Form (b):<br>
<br>
P is a pubkey,<br>
(k,s) is a signature (scalars k, s),<br>
verifier checks that Hash(msg || P || s*B - k*P) is equal to k.<br></blockquote><div>[...] </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Are there some performance considerations that I missed that make (a)<br>
more performant (maybe allowing batch verification?) in existing EdDSA?<br></blockquote><div><br></div><div><div>Hi Oleg,</div><div><br></div><div>Yes, I believe batch verification was one rationale for this decision in Ed25519 [1]:</div><div><br></div><div>"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."</div><div><br></div><div>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.</div><div><br></div><div>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].</div><div><br></div><div>Trevor</div><div><br></div><div>[1] <a href="https://blog.cr.yp.to/20140323-ecdsa.html">https://blog.cr.yp.to/20140323-ecdsa.html</a> </div><div>[2] <a href="https://moderncrypto.org/mail-archive/curves/2016/000836.html">https://moderncrypto.org/mail-archive/curves/2016/000836.html</a></div></div><div>[3] <a href="https://signal.org/docs/specifications/xeddsa/">https://signal.org/docs/specifications/xeddsa/</a></div><div><br></div></div></div></div>