Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
What is $B\hspace{.02 in}$? $\;$ – Ricky Demer May 18 '14 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 '14 at 2:37
up vote 2 down vote accepted

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.

Not sure if that's your only problem.

share|improve this answer
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 '14 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 '14 at 7:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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