# Derive a public EC key from two public EC keys

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.

-
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. – orlp 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

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$

-