6
$\begingroup$

Suppose I have the witness $x$ and need to prove that I correctly computed $(g^x)^x$ to a verifier. $g$ and $g^x$ are public. The verifier asks me for $(g^x)^x$, but wants proof that I've given them the right answer.

Here's my attempt at a solution:

Let $X = g^x$ and $X' = (g^x)^x$

Step 1: Prover chooses a random $r$ and sends $R = g^r$ and $R' = X^r$

Step 2: Verifier sends a random $c$ (challenge)

Step 3: Prover sends $z = r + cx$ (response)

Step 4: Verifier checks if $g^z = RX^c$ and $X^z = R'(X')^c$.

I was wondering whether this is zero knowledge or just a proof of knowledge.

Thanks!

$\endgroup$
7
$\begingroup$

I guess that it's also zero-knowledge, but I'll let you do the proof. However, an easier thing to note is that if $X=g^x$ and $X'=g^{x^2}$ then it follows that $(g,X,X,X')$ is a Diffie-Hellman tuple (i.e., it is of the form $(g,g^a,g^b,g^{ab})$. As such, you could use the standard Diffie-Hellman tuple Sigma protocol as a "black box".

(Note that Sigma protocols are defined as honest-verifier zero-knowledge, so that is the level we are aiming for here.)

$\endgroup$
  • 2
    $\begingroup$ More precisely, it's honest-verifier zero-knowledge. $\endgroup$ – Geoffroy Couteau Oct 26 '18 at 9:34
  • $\begingroup$ @GeoffroyCouteau You are absolutely right, but this is the level of zero knowledge required for Sigma protocols, so I didn't clarify that. But, indeed, this should be stated so I'll add it to the answer. $\endgroup$ – Yehuda Lindell Oct 28 '18 at 7:16
0
$\begingroup$

A simulator $S$ might work as follows: it generates a random $(c,z)$ and calculates $R=g^{z}X^{-c}$ and $R^{'}=X^{z}(X^{'})^{-c}$. Clearly, $((R,R^{'}),c,z)$ have the same distribution as in a real run. Namely, random values satisfying $g^{z}=RX^{c}$ and $X^{z}=R^{'}(X^{'})^{c}$.

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