# How to prove that two EC public keys created with two different generators share the same secret key?

Consider a situation where there is a (scalar) secret key $x$, known only to Alice.

There are two well known generator points $G$ and $H$, known to both Alice and Bob. $H$ is chosen such that discrete log of $H$ base $G$ is unknowable.

Alice provides Bob with the points $A$ and $B$, where $A = xG$ and $B = xH$.

Without Alice revealing $x$ to Bob, how can Alice prove to Bob that both $A$ and $B$ were constructed with the same $x$? The proof should be non-interactive.

Is it safe to simply provide a Schnorr signature using the private key $x$ and public key $(A+B)$ on the basis of a generator point $(G+H)$?

The Schnorr signature would be:

$sig.c = Hs( (A+B)$ $||$ $k(G+H))$

$sig.r = k - x * sig.c$

where $k$ is a random number generated only for this Schnorr signature.

The Schnorr signature would be verified by checking that:

$sig.c == Hs((A+B)$ $||$ $(sig.r*(G+H) + sig.c*(A+B)))$

$Hs()$ means hash the contents to produce a scalar

$||$ means byte concatenation.

• Can we assume that no one knows the discrete log of $H$ base $G$? If so, proving that you know a solution $x$ to $aA + bB = x(aG + bH)$ (for verifier chosen $a, b$) is sufficient. – poncho May 16 '18 at 18:01
• @poncho Yes, we can assume no one knows the discrete log of $H$ base $G$. I'm specifically looking for a way for it to be proven non-interactively. I'll amend the question as such. – knaccc May 16 '18 at 18:07

Is it safe to simply provide a Schnorr signature

Actually, a single Schnorr signature is insufficient. For your proposal, someone could pick an arbitrary $A$ and compute $B = x(G+H)-A$ (for some $x$ he picks), and he could generate the signature.

I will also assume that the order of the subgroup that $G, H$ generate is prime (which is usually the case)

Instead, you can use three signatures:

• One is sig.c = Hs(A || kG), sig.r = k - x * sig.c; this shows that we know a solution $x$ to $A = xG$

• Next is sig.c' = Hs(B || k'H), sig.r' = k' - x * sig.c'; this shows that we know a solution $y$ to $B = yH$

• Third is sig.c" = Hs((A+B) || k"(G+H)), sig.r" = k" - x * sig.c"; this shows that we know a solution $z$ to $A+B = z(G+H)$

[Don't forget to use three different $k$ values for the three signatures]

It is easy to show that if we know solutions to the above three with $x \ne y$, then we can rederive the discrete log of $H$ wrt $G$. We assumed that we don't know that, and hence we have $x=y$ (which is what we are trying to prove)