# Rigorous Proof on Malicious Zero-Knowledge Property of Schnorr Protocol

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:

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?

• Let's wait Chris Peikert to answer this? Commented Mar 3 at 8:32
• 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. Commented Mar 5 at 2:44

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.

• 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! :) Commented Mar 19 at 0:44
• But the verifier is malicious so $b$ is not random, it is an arbitrary randomized function of $z$. Commented Apr 6 at 2:20