EdDSA Verification vs. Cofactorless Verification

Question

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 ?

Answer 1

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.

Answer 2

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.