Rationale for verification with cofactor $2^c$ in EdDSA?

Question

EdDSA for more curves describes 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$? Why would it be faster / simpler, if it is that at all?

---

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

Answer 1

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.

Answer 2

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.

Answer 3

We make an example that doesn't pass the cofactorless verification. In this example, We suppose that the public and private keys haven't been produced whit the above procedure. Suppose that the point $B$ as a public parameter has the order of $2^c*l$ and $c=3$. The below values have been supposed:

$$l=11 ,\ \ \ s=10, \ \ \ A=10B ,\ \ \ r=7 $$ sign: $$ R=7B , \ \ H(\underline{R},\underline{A},M)=5, \ \ S=r+H(\underline{R},\underline{A},M)s \ mod(11)=7+5*10 \ mod(11)=2$$ verify: $$ (R,S)=(7B,2); \ \ SB=2B \ , \ R+H(\underline{R},\underline{A},M)A=7B+5*(10B)=57B$$

Note that the point $2B$ is not equal to $57B$. Because the order of point $B$ is $8l=88$. However, if we use a verification algorithm with a cofactor, the verification algorithm is correct.

In other words, the verification algorithm with cofactor is also useful for signing in the $8r$ group, but the cofactorless verification is useful just for signing in the $r$ subgroup.