In Ed25519, why not make both batch & unbatched verification follow the cofactored verification approach rather than unbatched using cofactorless?

Question

Ed25519 uses a composite order Elliptic Curve (with a cofactor $8$) The algorithm however in the prime order subgroup of the main group. The signing operation should be using a generator/Base Point from the prime order subgroup.

There are the parameters

Order of the curve is $8.q$ where $q$ is a large prime.

$a$ = scalar/pvt key

$B$ = base point, generator of the prime order subgroup

$A = a.B$ = public key /verification key

In the signing process, a secret nonce $r$ is generated deterministically.

Then, $R = rB$

$k = Hash(R + A + M) \bmod q$

$s = r + ka \bmod q$

and $\lbrace R, s \rbrace$ is output as the signature.

The verification process however depends a check which is different between batched & unbatched verification.

As per this blog,

Batched verification uses a cofactored formula

$[8]R = [8] ([s]B−[k]A) $

Unbatched uses a cofactorless formula

$R=([s]B−[k]A)$

The original blog explains why batched verification will verify even if you use non-torsion safe cofactor clearing while unbatched will verify only if you use a torsion-safe cofactor clearing.

This Q & A from CryptoSE explains the difference & why cofactored is better.

This preprint also says the following

We claim that only cofactored verifica-tions, single and batch, are compatible with each other 4. Other combinations (cofactorless-single with cofactorless-batch; cofactorless-signle with cofactored-batch; cofactored-single with cofactorless-batch) are all incompatible.

I can understand the other differences between batched & unbatched verification (batch optimizations can be done). However, why don't both batched & unbatched both use cofactored verification?

Answer 1

Consider the un-batched cofactorless verification $R\overset{?}{=} sB-kA$, for the signature $(R,s)$.

There are 7 different small torsion points that could be added to $R$ to bump it out of the prime-order subgroup. (It's 7 rather than 8, because the eighth point is the point at infinity which is in the prime-order subgroup).

It would be impossible for cofactorless individual verification to pass, no matter what values of $k$ or $s$ are used.

However, depending on the choice of random scalars used when performing cofactorless batch verification, the batch verification will sometimes pass and sometimes fail when at least one of the signatures in the batch has a point that isn't in the prime-order subgroup.

Therefore, a choice has to be made. Should we:

1. Allow inconsistent batch verification results, and the resulting confusion?

2. Prevent inconsistent batch verification results by multiplying by the cofactor to force all points into the prime-order subgroup.

Option 2 makes the most sense. It provides consistency. You might argue that it comes at the cost of successfully verifying signatures that would not verify with cofactorless individual verification. However, that's not as terrible a situation as it may seem. It's not as though the signature with an $R$ value that is not in the prime-order subgroup is a forgery. It's just that it's been tweaked such that it won't individually verify. It is still a sufficient zero-knowledge proof of knowledge of the private key $a$.

As the paper that you linked explains the reason that individual verification was originally implemented in cofactorless form:

The original paper of Bernstein et al... was not multiplying by 8, which is called cofactorless verification. Almost all the cryptographic libraries use the cofactorless version to make verification slighly faster

Cofactorless verification removes the need for scalar multiplication of the point by 8, and so would make sense if you know you will never need to perform any batch verifications.