# Is this EdDSA modification secure?

I am hoping to employ a signed set membership system which is valid iff each signer's contribution to the set is present. The system should allow for two or more mutually exclusive signed sets to be merged into a new signed set without requiring new signatures. Also, unless the set has a single signer, it should be intractable with the signed set alone to discover which elements of the set were signed by which signer. The following describes the system:

EdDSA signatures are of the form: $S = (r + H(M,R,A)*a)$ $mod$ $l$.

Consider the modified form: $S = (a + H(M, R)*r)$ $mod$ $l$, where we omit the public signing key A from the hash function and swap the private signing key $a$ with the private session key $r$.

Now, suppose we have two signers, $A_1$ and $A_2$, having signed a set of three elements, $(M_1,R_1)$, $(M_2,R_2)$ and $(M_3,R_3)$. The signature is then:

$S_{set} = (a_1 + a_2 + H(M_1,R_1)*r_1 + H(M_2,R_2)*r_2 + H(M_3,R_3)*r_3)$ $mod$ $l$

and is verified iff:

$S_{set}*B = A_1 + A_2 +H(M_1,R_1)*R_1 + H(M_2,R_2)*R_2 + H(M_3,R_3)*R_3)$ $mod$ $l$

So, does this system seem to accomplish the stated goals while maintaining the security of the unmodified EdDSA algorithm?

-
What is $B\hspace{.02 in}$? $\;$ –  Ricky Demer May 18 at 18:37
$B$ is a base point for the curve. That is, $A = a*B$ where $a$ is the secret key and $A$ is the public key. –  Ryan Stovall May 20 at 2:37

In your signature each signer only seems to add their secret $a$ in once. An attacker who could get someone to sign first $M_1$, then $M_2$ and finally both as a set could find $a = S_1 + S_2 - S_{12}$ $mod$ $l$, i.e. all but a few bits of the secret $a$, the rest being within easy brute force search.
True. This uses the fact that EdDSA derives the secret session key $r$ from the secret key $a$ and the message $M$. So, supposing a nonce were used to salt the derivation of $r$, does this problem remain? –  Ryan Stovall May 20 at 2:07
Depends on what happens when merging sets. If no two signatures reuse $r$ values, then that problem is solved. –  otus May 20 at 7:33