# 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 = 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.

• 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. May 16, 2018 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. May 16, 2018 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)

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)$$.