Would EdDSA be broken by replacing H(R, A, M) with H(A, M)?

Question

An EdDSA signature is (R, S) where R = r*B and S = r + H(R, A, M)*s. Notation from Wikipedia en.wikipedia.org/wiki/EdDSA.

Given that the hash function H, is indeed collision-resistant, would using S = r + H(A, M)*s be a secure variant?

In the original EdDSA paper, the authors mention the need for R to protect the signature scheme in case the hash function is not collision-resistant. To me, it indicates that the scheme could possibly be secure even when R is left out from the hash function input.

The reason I ask (in case it is of interest) is that using H(A, M) would be more threshold-friendly. Threshold signatures with that modification in place could be done using 1 round instead of 2 rounds.

Answer 1

This answer is assuming you are not removing the private key $a$ from the computation of $S$, and instead actually meant what is said in the title of the question:

$S = r + a H(A, M)$

Removing $a$ from the computation would be terrible.

---

The first issue that comes to mind is malleability, on top of collision resistance.

The signature process for EdDSA actually goes as follows:

Input: message $M$, secret key bits $(h_0, h_1, \ldots, h_{2b-1})$, basepoint $B$ and public key point $A$

1. $a \gets 2^{b-2} + \sum_{3 \leq i \leq b-3} 2^i h_i$
2. $h \gets H(h_b,\ldots,h_{2b-1},M)$
3. $r \gets h\mod \ell$
4. $R \gets r\cdot B$
5. $h \gets H(R, A, M)$
6. $S \gets (r + a h) \mod \ell$

Return: $(R,S)$

As you can see, if you do not include the value $R$ in the hash $h$, the value $S \gets (r + a h) \mod \ell$ can easily be modified in a way that would allow to produce new signatures for the same message:

1. pick a random $k$
2. compute the point $R' = R + k\cdot B$
3. compute the value $S' = S + k \bmod \ell$

And you now have a new, different signature $(R', S')$ for the same public key $A$ that will verify for the message $M$. This is possible because the value $r$ behind computed with the secret key, it is not meant to be public and is not necessary for verification. This property was used in a fault attack in 2017.

Malleability is not necessarily unwanted in cryptographic scheme, but is often frowned upon since it can very easily lead to issue with implementations.

Threshold cryptography is rough and full of dangers, and I wouldn't advise coming up with a malleable scheme as these have already proven to cause issue with threshold schemes.

Answer 2

would using S = r + H(A, M) be a secure variant?

Actually, it would become trivial to generate a signature for an abitrary message with just the public key.

The verification check would be:

$$2^h s G = 2^h R + 2^h H(A, M) A$$

where $h$ is the curve cofactor, $G$ is the curve generator, $A$ is the public key, $M$ is the message and $(R, s)$ is the signature.

So, what the attacker ould do is pick an arbitrary $s$ and try to solve:

$$2^h sG - 2^h H(A, M)A = 2^h R$$

Everything on the right side is known, and so it's easy to find an $R$ that satisfies this ($sG - H(A, M)A$ is one solution)