1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is $B\hspace{.02 in}$? $\;$ $\endgroup$ – user991 May 18 '14 at 18:37
  • $\begingroup$ $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. $\endgroup$ – Thomas Ryan Stovall May 20 '14 at 2:37
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Thomas Ryan Stovall May 20 '14 at 2:07
  • $\begingroup$ Depends on what happens when merging sets. If no two signatures reuse $r$ values, then that problem is solved. $\endgroup$ – otus May 20 '14 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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