3
$\begingroup$

Let us recall the Schnorr Protocol, following Chris Peikert's excellent Notes on the Theory of Cryptography.

Protocol. Let $G=\langle g \rangle$ be a cyclic group of order $q$. We consider an arbitrary element $x\in G$, having Discrete Logarithm $w=:\log_g(x)$. The input to the Prover $P$ is $x,w$ and to the Verifier $V$ is just $x$. The interactive Proof System is defined as follows:

enter image description here

My Question is on the Zero-Knowledge Property for a $\color{red}{\textrm{Malicious Verifier $V^*$}}$.

So, in the same Set of Notes, we define a simulator $S^{V^*}$ as follows:

$\underline{\text{Simulator $S^{V^*}(x)$}}$

REPEAT

  • $b \stackrel{\\\\\$}{\leftarrow}\{0,1\} \ ; \ a \stackrel{\\\\\$}{\leftarrow} G$
  • $z\leftarrow g^a x^{-b}$
  • $b' \stackrel{}{\leftarrow} V^*(z)$

UNTIL $(b'=b)$

RETURN $(z,b,a)$

I would be more than grateful if someone could rigorously show why this distribution, $S^{V^*}(x)$, is indistinguishable from the distribution $\mathrm{VIEW}_{(P,V^*)}^{V^*}(x)$ and what kind of indistinguishability we have.

It is noticeable that I couldn't find anywhere on the Internet a rigorous Proof for the Mailicious Verifier Case, but only for the Honest Verifier Zero-Knowledge (HVZK). Is that so easy that it is ommited?

Thanks in advance.

$\endgroup$
2
  • $\begingroup$ Let's wait Chris Peikert to answer this? $\endgroup$
    – kelalaka
    Mar 3 at 8:32
  • $\begingroup$ Sure, this will be great! However everyone who can show how to calculate this probability using the repeat statement in the algorithm, is more than welcome. $\endgroup$
    – Chris
    Mar 5 at 2:44

1 Answer 1

0
$\begingroup$

I think you might be overthinking the result? The key here is that the simulator has a very powerful advantage, which is that it can rewind $V^\ast$, that is, running with many inputs as much as it wants, until something happens.

With this in mind, note that in the simulated execution $(z,b,a)$ is distributed as:

  • $b$ random
  • $a$ random
  • $z$ constrained to $z = g^ax^{-b}$.

In the real world, the tuple is distributed as:

  • $b$ random
  • $z$ random
  • $a$ constrained to $a = r+bw$.

Both triples have exactly the same distribution. There are different ways to see this, some more formal than the others. Intuitively, it's a combination of the following two things:

  1. $z = g^ax^{-b}$ if and only if the discrete log $r$ of $z$ is $a -bw$, that is, $r = a-bw$
  2. Sampling $r$ at random and letting $a = r+bw$ leads to the same distribution for the tuple $(a,r)$ than first sampling $a$ and then letting $r = a-bw$.

If you want to prove this even more formally maybe it's useful to see why the one-time-pad is perfectly secure; it's the same proof.

$\endgroup$
2
  • $\begingroup$ Dear Daniel, many thanks for the answer. I already had this intuition, and this exactly why I posted here the question. It would be more than nice if you could provide a rigorous proof --it may help a lot of people! :) $\endgroup$
    – Chris
    Mar 19 at 0:44
  • $\begingroup$ But the verifier is malicious so $b$ is not random, it is an arbitrary randomized function of $z$. $\endgroup$
    – Mikero
    Apr 6 at 2:20

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.