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

Question

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 = H_s( (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 == H_s((A+B) $ $||$ $ (sig.r*(G+H) + sig.c*(A+B)))$

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

$||$ means byte concatenation.

Answer 1

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)

Answer 2

A Chaum-Pedersen discrete logarithm equivalence (DLEQ) proof will demonstrate that the private key for the public key $A$ on the base point $G$ is the same private key for the public key $B$ on the base point $H$.

The DLEQ proof $(c,r)$ is calculated as follows: $k$ is a random scalar, $c=H_s(kG\mathbin\|kH)$ (where $H_s$ means a cryptographically secure hash that produces a scalar value) and $r = k - cx$. All scalar operations are mod the order of the base point.

The DLEQ proof is verified by checking $c==H_s(rG+cA \mathbin\| rH+cB)$.