Alice picks random points P and Q in a group where DLP w.r.t. a base point G is hard (I am thinking an eliptic curve, but it doesn't have to be). Alice doesn't know the DLP of those two points.

Alice sends (P,Q) to Bob.

Bob is to pick a random scalar r, and return (r*P,r*Q) to Alice, while keeping r secret.

Is there a way for Bob to prove to Alice that he knows that r, and that the pair of points that he sent her are what she is expecting, but without revealing r?

  • 2
    $\begingroup$ Have a look at this and this related Q&A. $\endgroup$ – SEJPM Oct 3 '17 at 14:11

This looks like your typical Schnorr identification protocol. Here $r$ is some secret value, which we could think of as having two public keys $r\cdot P$ and $r\cdot Q$. You'll probably want to assume that the DLPs wrt base $P$ and $Q$ are hard as well, as otherwise Alice could possible solve one of these two for $r$. Let's just assume the group has prime order $n$.

Now we could proceeds as follows (similar to the questions the @SEJPM referred to):

  1. Bob chooses random $s\in \mathbb{Z}/n\mathbb{Z}$.
  2. Bob sends $(s\cdot P, s\cdot Q)$ to Alice.
  3. Alice chooses random $c\in \mathbb{Z}/n\mathbb{Z}$.
  4. Bob computes $t = (s + cr)\bmod{n}$.
  5. Bob sends $t$ to Alice.
  6. Alice checks that $tP = (s\cdot P) + c(r\cdot P)$ and $tQ = (s\cdot Q) + c(r\cdot Q)$.

If the checks of Alice pass, she will believe that Bob knows the DLP of $r\cdot P$ and $r\cdot Q$. I haven't done a too thorough checking, but the properties of a sigma protocol seem to hold.

Moreover the secrets must both be equal to $(t-s)c^{-1}\bmod{n}$, so they are the same.

| improve this answer | |
  • $\begingroup$ Thank you, that makes sense. $\endgroup$ – user141 Nov 27 '19 at 10:43

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.