-1
$\begingroup$

I'm currently learning about ZKP and Non-interactive zero knowledge (NI-ZK) but I'm confused in the process of NI-ZK verification.

I have taken the following example to learn about NI-ZK from this link i.e

1) Anna wants to prove to Carl that she knows a value $x$ such that $y = g^x$ to a base $g$.

2) Anna picks a random value $v$ from a set of values $Z$, and computes $t = g^v$.

3) Anna computes $c = H(g,y,t)$ where $H()$ is a hash function. Anna computes $r= v – c*x$.

4) Carl or anyone can then check if $t = g^r * y^c$

From the example it is clear that verifier knows the value of $y$ and $g$, then isn't it simple to calculate the secret value ($x$) by the following formula:

since $y=g^x$

$x = \cfrac{log_y}{log_g}$

Or have I misunderstood something here?

$\endgroup$
3
  • 1
    $\begingroup$ What you're missing is that the discrete logarithm is assumed to not be efficiently computable in the group being used. $\endgroup$
    – Maeher
    Jan 16, 2019 at 15:14
  • $\begingroup$ Can you elaborate the factor that make it's impossible to compute ?? $\endgroup$ Jan 16, 2019 at 15:30
  • $\begingroup$ What your description is missing is that the exponentiation takes place not over the integers but in some finite cyclic group. g is a generator of this group. That means also the logarithm must be taken in that group. This is called the discrete logarithm problem. There are some groups where it is believed that computing discrete logarithms is hard. If the discrete logarithm problem is hard, then the protocol you describe is ZK. Otherwise it's not. $\endgroup$
    – Maeher
    Jan 16, 2019 at 16:06

1 Answer 1

0
$\begingroup$

In fact, the relevancy is not that Alice could not compute x (because if discrete log is easy she could). The relevancy is in the fact that the protocol doesn't give any information to compute x. That why it's called a zero knowledge protocol, because the verifier gains zero knowledge at the end of the protocol.

$\endgroup$
8
  • $\begingroup$ Thank you for answering but it's seem, verfier should have values of r,g,y & c to verify the proof. isn't it ?? then how protocol doesn't have enough information to compute x ?? $\endgroup$ Jan 16, 2019 at 15:33
  • $\begingroup$ g and y are not considered communicated in the protocol, they are "publicly" known. $\endgroup$
    – Ievgeni
    Jan 16, 2019 at 15:35
  • $\begingroup$ and in my example, it should be for Carl (verifier) to impossible for computing the value of x. Sorry for bad language because i'm not a native speaker. $\endgroup$ Jan 16, 2019 at 15:37
  • $\begingroup$ if g, y are publicly known and r, c are computed through protocol then where is the problem to compute ? $\endgroup$ Jan 16, 2019 at 15:40
  • $\begingroup$ As Maeher says If you are in group where discrete log is hard to compute you can not do it efficiently. $\endgroup$
    – Ievgeni
    Jan 16, 2019 at 15:43

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.