6
$\begingroup$

In EdDSA for more curves, it's described two options of signature verification

  • Verification, which checks $2^c\,S\,B\,=\,2^c\,R+2^c\,H(\underline R,\underline A,M)\,A$
  • Cofactorless verification, which checks $S\,B\,=\,R+H(\underline R,\underline A,M)\,A$

Cofactorless verification is more stringent: "any alleged signature that passes cofactorless verification will also pass verification", but "a signer using a secret key outside the normal signing procedure can create strings that pass verification without passing cofactorless verification".

So, what's the rationale for the first kind of verification, with cofactor $2^c$? If somewhat it's faster/simpler, why?


Update: after looking at this answer and it's references, I wonder if the only reason Verification¹ is defined is so that it holds the following

Proposition: If a set of signatures passed batch verification, then each signature passes Verification¹ with cryptographic certainty (including if signers are intentionally messing up or if adversaries modify signatures).

Is this proposition true? What's a proof? Why would not it hold if Verification was defined as Cofactorless verification?

Is there any other reason for Verification with cofactor? Like, a Fast Single-Signature Verification as in section 5 of Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang, High-Speed High-Security Signatures, in proceedings of CHES 2011)?


¹ Verification as defined above, that is with cofactor $2^c$.

$\endgroup$
0
1
+500
$\begingroup$

It's flawed to imagine that "more stringent" is somehow stronger. Actually ed25519-dalek's verify_strict method makes this mistake.

There are many plausible verification methods, which all define valid signature schemes based upon the same ed25519 keypairs. You'll find them described in https://eprint.iacr.org/2020/1244 and https://hdevalence.ca/blog/2020-10-04-its-25519am

Almost none of those schemes agree perfectly with batched ed25519 signature verification however because batch verification randomly cancels out some cofactor tweaks.

If you employ ed25519 in a consensus protocol, like for accounts on a blockchain, then you'll want batched ed25519 verification that agrees perfectly with single ed25519 verification. In such cases, you should use ZCash's ed25519 crate ed25519-zebra. Afaik, all other ed25519 implementations exhibit variations between batched and single verification (as of march 2021).

I doubt TLS would adopt cofactor clearing verification, in part because cofactor-less verification runs slightly faster than cofactor clearing verification. In fact, TLS could already batch verify ed25519 because one never has third parties check TLS handshakes in consensus protocols. I suppose a CA could issue a certificate that worked only intermittently and only on some clients.

$\endgroup$
3
  • $\begingroup$ Reading between your lines, I get that the rationale for verification with cofactor is not speed ("cofactor-less verification runs slightly faster than cofactor clearing verification"), but rather batch verification. Could you confirm that, and detail what / why it matters there? Be assured I understand "more stringent" does not mean more secure. $\endgroup$ – fgrieu Mar 22 at 9:56
  • $\begingroup$ It matters if you're using batch verification where everyone must agree upon the signature's correctness, like a consensus protocol. It does not matter if you're using batch verification where only one party's judgement matters, like TLS. $\endgroup$ – Jeff Burdges Mar 22 at 15:38
  • 3
    $\begingroup$ The Ed25519 implementation in the Zig standard library doesn’t exhibit variations between batched and single verification. The Taming the many EdDSAs explains the reasoning behind doing verification with the cofactor. $\endgroup$ – Frank Denis Mar 23 at 12:43
1
$\begingroup$

This is somewhat speculation on my part.

The cofactor verification scheme seems to originate with RFC 8032. Although the usual common Edwards curves are quoted as suitable instantiations of EdDSA, the sign and verify algorithms are defined separately (and prior to) the familiar Edwards curves. It's not unusual for standards designers to be defensively minded in making standards forward compatible and I suspect that they wanted a signature verification method that still worked in the circumstance that a future desirable curve was generated with a base point $B$ that lay in a cofactored subgroup (such as the full elliptic curve group). Such a $B$ feels like a bad idea (thought future developments may cause this to be rethought) and are sort of blocked by other parts of the specification. The relevant bits of the specification in section 3 of the RFC are parameter 9. which has that $B!=(0,1)$ (the identity), but only implicitly note that $B$ should be of prime order when specifying parameter 10. $\ell$ such that $\ell B=0$ (this notation for the identity not being used or remarked on elsewhere). It's not clear that this point was well thought through.

It’s worth noting that when verification is specified for the usual curves, cofactorless verification is permitted, but in the generic case (section 3.4) it is not.

My best guess then is that people implement cofactored verification to comply with the RFC (when in doubt standards compliance reduces lawsuits), and that the RFC specified cofactored verification for forward compatibility with seemingly unwise choices of base points on future Edwards curves.

One could envision a particularly optimisation-focused implementation where a particular $B$ with optimal coordinates happened to lie in a cofactored subgroup. It would then be good if this could be dropped into full usage without rewriting everyone’s code.

EDIT (29/3): The cofactored verification scheme does seem to pre-date the RFC and goes back to the original Bernstein et al. paper added. This paper shares the frustrating feature of describing $\ell B=(0,1)$ as a condition on $\ell$. However, the only reason that I can think of for cofactored verification is to deal with $B$, $R$, and $S$ outside the subgroup now or in the future (it's not really faster or simpler). It's very straightforward for people with the signing key to produce signatures that pass cofactored verification but not cofactorless; this would make an environment that supports both schemes dangerous.

$\endgroup$
1
  • $\begingroup$ A lot of this is flying high above my head. I'm even unable to tell if the cofactor Verification scheme of RFC 8032 (and EdDSA for more curves) is any different from the Fast Single-Signature Verification from the original exposition of Ed25519, now linked at the end of the question. $\endgroup$ – fgrieu Mar 29 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.