3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – poncho May 16 '18 at 18:01
  • $\begingroup$ @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. $\endgroup$ – knaccc May 16 '18 at 18:07
3
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.