0
$\begingroup$

Assume the zero knowledge protocol where the prover knows a $x$ such that: $g^x = h \pmod{p}$.

  • The prover chooses a random $t \in \mathbb{Z}^*_m$ and sends $y = g^t \pmod{p}$
  • The verifier sends random $c \in \mathbb{Z}^*_m$ and sends it
  • The prover calculates $s = t + c + x$ and sends it
  • The verifier accepts if and only if $g^s = yg^ch \pmod{p}$

Is this for honest verifiers?

Attempt:

The real transcript is $(t, g^t \pmod{p}, c, t +c+x)$, but I cannot find a simulated transcript $(t, \cdot, c, \cdot)$ that has the the same distribution as the real one. Can you give me some hints?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Can you give me some hints?

It's not a proof of knowledge, as someone without knowledge of $x$ can complete this protocol successfully with an honest verifier.

Hint: what happens if the ignorant prover sends $y = h^{-1}$?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Then the verifier will choose a $c$ and the prover will send back $s=c$ so that $g^s = h^{-1} g^c h = yg^ch$ and the prover will pass the challenge without knowing $x$ as you said. Can you elaborate on what does that show for the protocol? Does it mean that it's not a zero knowledge protocol or that it's not a zero knowledge protocol for honest verifiers? $\endgroup$
    – Paris
    Jan 23, 2021 at 17:03
  • 1
    $\begingroup$ @Paris: it's not a zero knowledge protocol for proof of knowledge of $x$, as you can 'prove' it without knowing $x$ $\endgroup$
    – poncho
    Jan 23, 2021 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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