Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Alice has two EC key pairs: $a_1$, $a_2$ are private keys (integers), $A_1$, $A_2$ are the corresponding public keys (points). Alice and Bob want to create a new public key $C$. Alice must prove that this key $C$ was created from exactly $A_1$ and $A_2$, i.e. Alice did not use other key pairs for $C$. The new public key $C$ would be used for ECDSA. The private key $c$ is created from $a_1$ and $a_2$ and is usable for ECDSA with $C$. The private key $c$ must not be able to be created from only $a_1$ or only $a_2$.

The algorithm will be generalized to $n$ key pairs. My thoughts for case of 2 keys are below.

Which algorithm can be used for that? I have two ideas:

  1. Addition of $A_1$ and $A_2$: $C = A_1 + A_2$. Bob can verify this, since he knows $A_1$ and $A_2$. The private key would be $c = a_1 + a_2$. This works because $(a_1+a_2) \cdot G = a_1 \cdot G + a_2 \cdot G = A_1 + A_2$. Clear. But how secure is it? Can an ECDSA signature of the public key $C$ be created without both $a_1$ and $a_2$? Maybe $a_1$ or $a_2$ only is enough for this? I don't know.

  2. Multiplication. $C = a_1 \cdot a_2 \cdot G$. Verification is complicated if it is even possible. If Bob knows $A_1$, $A_2$ and $C$, how can he verify that $C$ was composed exactly from private keys corresponding to $A_1$ and $A_2$ (maybe with Alice's help, but without possessing ability to sign with $C$)?

Example of vulnerable verification (for proposal 2): Bob generates a random number $r$ (not available to Alice), computes $r \cdot A_1$ and asks Alice to multiply this by $a_2$. Alice sends $a_2 \cdot (r \cdot A_1)$ to Bob. $a_2 \cdot r \cdot A_1 = r \cdot a_1 \cdot a_2 \cdot G = r \cdot C$. Bob compares $a_2 \cdot (r \cdot A_1)$ sent by Alice with $C$. Then he does the same with $A_2$.

This is vulnerable: Alice computes $C = a_1' \cdot a_2' \cdot G$. Bob generates $r \cdot A_1$ and asks Alice to multiply it with $a_2$, Alice multiplies it with $a_2' \cdot (a_1'/a_1)$. So the result of the multiplication is $a_2' \cdot (a_1' / a_1) \cdot (r \cdot A_1) = a_2' \cdot (a_1' / a_1) \cdot (r \cdot a_1 \cdot G) = r \cdot a_2' \cdot a_1' \cdot G = r \cdot C$. So Bob mistakenly believes that $C$ is derived from $A_1$ and $A_2$. Division by $a_1$ is multiplication by $a_1^{-1}$, which can be calculated from $a_1$ using a multiplicative inverse.

Please, prove that algorithm proposed in item 1 (addition) is correct or provide correct verification for algorithm 2 (multiplication) or provide your own or existing algorithm which is appropriate for the task.

share|improve this question
    
For people wanting to test #1, I have it implemented in my ed25519 implementation, as ed25519_add_scalar. Just treat $A_2$ as the scalar. –  nightcracker Oct 10 '13 at 15:17
    
@nightcracker, I have tested #1 with python-ecdsa and python-electrum. It works. But I don't whether this signing scheme is secure. –  Niar Oct 10 '13 at 18:02

1 Answer 1

As long as there is a probability that the adversary has the access to a valid signature on the message $m$ using one of the private keys, none of the schemes would be secure, and also any other scheme which is using a linear combination of the keys as the resulting private key.

Because, if an adversary has two valid ECDSA signatures on message $m$ which one is made by private key $a_1$ and the other is made by private key $a_2$, she can produce any signature on message $m$ using the private key $c=b_1a_1+b_2a_2+b_3$ where $b_1$,$b_2$ and $b_3$ are known to the adversary. This is due to the homomorphic properties of Elgemal signature.

So other than the algorithm #2 the algorithm #1 (Addition) seems to be unsecure. Whereas, If an adversary has a valid ECDSA signature on message $m$ using private key $a_1$ and she knows $a_2$ then it can produce a valid signature on message $m$ using private key $c=a_1+a_2$ quit efficiently. In other words for breaking the scheme it suffices to have just one of the private keys, say $a_2$, and a valid signature produced using the other private key, say $a_1$.

For making the answer more concise, I'm using the notations in Wikipedia article ~ "Elliptic Curve DSA".

assume the signature on message $m$ made using private key $a_1$ is $(r,s)$ and the forged signature made for private key $c=a_1+a_2$ is $(r',s)$.

$(r,y_1)=kG=zs^{-1}G+rs^{-1}a_1G$

$(r',y_1')=(r,y_1)+rs^{-1}a_2G$

share|improve this answer

Your Answer

 
discard

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.