2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Doesn't the answer satisfies you? $\endgroup$
    – kelalaka
    Sep 15, 2022 at 21:14
  • $\begingroup$ @kelalaka - it does to an extent. But I would like to see if there are any other reasons. It kind of seems strange to me that cofactored verification wouldn't be made standard for both batched & unbatched. If there are no other good answers, I will give the bounty to the existing answer $\endgroup$
    – user93353
    Sep 16, 2022 at 0:32

1 Answer 1

2
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat, at the initiative of a helpful bot. $\endgroup$
    – fgrieu
    Sep 14, 2022 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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