# EdDSA Verification vs. Cofactorless Verification

In the EdDSA for more curve paper the authors defines:

## Keys

An EdDSA secret key is a $b$-bit string $k$. The hash $H(k) = (h_0, h_1, ... , h_{2b−1})$ determines an integer $s = 2^n+\sum_{c≤i<n} 2^ih_i$ , which in turn determines the multiple $A = sB$. The corresponding EdDSA public key is $A$.

Note that $B$ is defined to be a point of order $l$ where the cardinality of the curve is $\#E(p)=2^cl$

## Signature

The signature of a message $M$ under key $k$ is created as:

• Define $r = H(h_b, ...., h_{2b-1},M) \in \{0,1,...,2^{2b}-1\}$.
• Define $R = rB$.
• Define $S = (r + H(\underline{R},\underline{A},M)s) \mod l$

Output: $(\underline{R},\underline{S})$ (note that underline is a byte encoding of points or integers which doesn't matter for this question)

## Verification

Verification of a signature $(\underline{R},\underline{S})$ of a message $M$ is defined as:

$2^cSB = 2^cR+2^cH(\underline{R},\underline{A},M)A$

## Cofactorless Verification

Cofactorless verification of a signature $(\underline{R},\underline{S})$ of a message $M$ is defined as: $SB = R+H(\underline{R},\underline{A},M)A$

They comment that:

Any alleged signature that passes cofactorless verification will also pass verification. The signature of a message will pass cofactorless verification, so it will also pass verification. However, a signer using a secret key outside the above signing procedure can create strings that pass verification without passing cofactorless verification.

I can't really understand the above comment and I have a few questions.

1. What does it mean "secret key outside the above signing procedure" ? Does it mean that $s$ is a string without a leading nth-bit set and not multiple of $2^c$ ?
2. How does the $2^c$ factor affects the verification compared to cofactorless verification?
3. Can you provide me an example/way of generating a secret key "outside the above signing procedure" that generates a signature that pass verification without passing cofactorless verification ?
• I am not sure, but maybe they mean the following: If $C$ is an element from $E$ with $2^c C = 0$ , then $A' = A+C$ satisfies the cofactor equation but not the cofactorless equation. The same argument applies to $R' = R + C$. – user27950 Nov 7 '15 at 7:38
• @Cryptostasis. Thanks, I agree with you. Interestingly, a user can generate multiple different signatures (by adding different $C$ to $R$) which will pass verification. But nor this, nor $A'$ can be obtained with "secret key outside the above signing procedure". I'll try to edit the question to better focus on this. – Ruggero Nov 9 '15 at 10:38

1. It means that someone possessing the private key $s$ can create signatures which pass verification but not cofactorless verification with respect to the public key $A$.
3. For example, if $C\in E$ is a point of even order (e.g. $2^c$), and the signer replaces $R:=rB$ in step 2 of the signing procedure by $R:=rB+C$, then $$2^cR+2^cH(\underline R,\underline A,M)A \;=\; 2^cSB+2^cC \;=\; 2^cSB$$ but $$R+H(\underline R,\underline A,M)A \;=\; SB+C \;\neq\; SB \text.$$ The private key is necessary to create such a signature because anyone modifying $R$ (or one of the other parameters) after the signature has been finalized (e.g., someone who does not know the private key) is very likely to be caught by $H(\underline R,\underline A,M)$ contributing to the verification formula. (Note this contradicts Cryptostasis' comment above.)
2. Due to the Pohlig-Hellman algorithm, the security of the whole system is dependent on the large prime-order subgroup $E[\ell]$ of $E$, while small prime factors of the group order do not reasonably contribute to the hardness of computing discrete logarithms. Group-theoretically, multiplication by $2^c$ realizes a projection to the subgroup of $E$ of size $\ell$, which is a direct factor: From the structure theorem of finite abelian groups, $$E\;\cong\;E[\ell]\times G\text,$$ where $G$ is an abelian group of order $2^c$, hence multiplication by $2^c$ maps an element to $E[\ell]\times\{e\}\leq E[\ell]\times G$. (And since $\ell$ is coprime to $2$, multiplication by $2^c$ is an automorphism on $E[\ell]\times\{e\}$.) Thus multiplication by $2^c$ throws away a little bit of information from the factor group $G$, but that wasn't useful anyway.
In practice, it is not going to matter which variant you use. As explained above, cofactorless verification is a little stricter, hence you might run into interoperability problems with non-conforming signers (but I see no reason why anyone would implement it in a way that makes this happen). On the other hand, verification (with multiplication by $2^c$) will take a few cycles more.