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$

2 Answers 2

9
$\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
  • 2
    $\begingroup$ More precisely, it's honest-verifier zero-knowledge. $\endgroup$ Oct 26, 2018 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$ Oct 28, 2018 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 and acknowledge you have read our privacy policy.

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