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?

Improve this question
$\endgroup$
2
  • $\begingroup$ What is $B\hspace{.02 in}$? $\;$ $\endgroup$
    – user991
    Commented May 18, 2014 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
    Commented May 20, 2014 at 2:37

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented May 20, 2014 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
    Commented May 20, 2014 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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