Proving knowledge of a value and computation that uses it

Question

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 elliptic 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?

Answer 1

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.