# Perfect zero knowledge for the Schnorr protocol?

Can somebody explain (or point to a reference) why the Schnorr protocol cannot be proved zero knowledge?

-
There is a distinction between Perfect ZKPs and ZKPs that "only" rely on computationally hard problems. The title of your question includes the term "perfect", but the body of your question doesn't. Please clarify. –  Henrick Hellström Aug 27 '13 at 23:13

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$).

Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it to the prover. The prover computes $z = r + ue$ and sends it to the verifier. The verifier checks that $g^z = a y^e$.

Remember, (informally) a protocol is zero knowledge if for any verifier $V^*$ there exists a simulator that can create conversations with the same distribution as conversations between the honest prover and $V^*$.

Proof sketch: Our simulator chooses $z$ uniformly at random and guesses what challenge $V^*$ will issue. Based on the guess $e$, it computes its initial message $a$ as $g^z y^{-e}$. If $V^*$ chooses $e$ as its challenge, the simulator has the correct response and has created a challenge with the correct distribution. It is a fairly easy exercise to prove that it succeeds with probability $1/2$, when $V^*$ is restricted to respond with $0$ or $1$.

So Schnorr is zero knowledge when the challenge space is small (so that we can guess the challenge with significant probability), but Schnorr is also not very useful when the challenge space is small, since you need to run the protocol many times to be sure that the prover really knows the secret.

When the challenge space is large, the above simulator fails. I can't remember a proof that there cannot be a different simulator that succeeds, but no such simulator is known. Which means that while we cannot say that Schnorr is zero knowledge. On the other hand, as far as I know, we cannot say that it is not zero knowledge.

There are alternative notions of zero knowledge, e.g. honest verifier zero knowledge. We can prove that Schnorr satisfies these notions even when the challenge set is large, and for many applications this is sufficient. E.g. in the random oracle model, we can get non-interactive zero knowledge via the Fiat-Shamir heuristic. There are also constructions for converting honest verifier zero knowledge to zero knowledge.

-
The purpose of selecting $e \in \{0,1\}$ Schnorr protocol, is to reveal a dishonest prover (who has one authentic transcript but doesn't know the value of $x$) with a certain probability after a certain number of executions of the protocol. This means the protocol has to be played out in $2log_2(q)/2$ consecutive steps, to get the same level of assurance (that the prover knows $x$) that you would get from a single execution of the protocol if $e$ is selected uniformly from $\mathbb Z_q^*$. –  Henrick Hellström Sep 28 '13 at 15:03
It makes sense to mention why Schnorr with small challenge space is not so useful. I've edited the answer accordingly. –  K.G. Sep 28 '13 at 15:25

Given the definition of a zero-knowledge proof, it must satisfy three properties:

1. Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
2. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
3. Zero-knowledge: if the statement is true, no cheating verifier learns anything other than this fact. This is formalized by showing that every cheating verifier has some simulator that, given only the statement to be proven (and no access to the prover), can produce a transcript that "looks like" an interaction between the honest prover and the cheating verifier.

Define the Schnorr protocol as follows:

Setup

• $P$ chooses a large prime $p$ and a generator $g$ of the $q$ order subgroup of $\mathbb Z_p^*$.
• $P$ chooses a secret $x \leftarrow_{uniform} \mathbb Z_q^*$, computes $y = g^x$ and gives $y$ to $V$.

Protocol

• $P$ chooses $r \leftarrow_{uniform} \mathbb Z_q^*$, computes $t = g^r$ and sends $t$ to $V$
• $V$ chooses $c \leftarrow_{uniform} \mathbb Z_q$ and sends it to $P$
• $P$ computes $s = r + cx$ and sends $s$ to $V$
• $V$ verifies that $g^s = ty^c$.

Completeness follows from the observation that the equation in the last step will check out, provided that $P$ and $V$ follow the protocol.

A cheating verifier $V^*$ who is to simulate the steps of both $V$ and $P$ would do as follows:

• $V^*$ chooses $c \leftarrow_{uniform} \mathbb Z_q$.
• If $c = 0$, choose $r \leftarrow_{uniform} \mathbb Z_q^*$ and let $t = g^r$, $s = r$
• If $c \neq 0$, choose $s \leftarrow_{uniform} \mathbb Z_q^*$ and let $t = g^sy^{-c}$ (Note: Since both $g$ and $y$ belong to the same subgroup, so will $t$)
• Produce transcript
• $P \rightarrow V$: $t$
• $V \rightarrow P$: $c$
• $P \rightarrow V$: $s$

A third party seeing this transcript will be able to verify that $g^s = ty^c$, and the uniform selection of the values means they have the same distribution as the values of an authentic protocol round. This proves Zero-knowledge.

Soundness follows from the observation that the above simulator requires the cheating party $V^*$ to select $c$ before $t$ (i.e. there can't be any simulator that is guaranteed to work, if $t$ has to be selected prior to $c$). Hence, a cheating prover $P^*$ cannot use the same simulator for convincing a honest verifier $V$, except with a small probability that corresponds to correctly guessing $c$.

-
Regarding zero knowledge: What you prove is honest verifier zero knowledge. Regarding soundness: Proving soundness/proof of knowledge for Schnorr is done by rewinding: Run the cheating prover. If you accept, rewind the prover until just before it got the challenge. Then give it a new challenge. If you accept a second time, you can easily compute the secret. The biggest difficulty in this proof is showing that the probability of successfully computing the secret is significant. –  K.G. Sep 29 '13 at 12:32
@K.G.: Quite right, I do not prove perfect zero-knowledge (see the request for clarification in my comment to the OP). –  Henrick Hellström Sep 29 '13 at 15:10
Perfect zero knowledge: the simulated conversation is distributed exactly as real conversation. Statistical zero knowledge: the distribution of simulated conversation is statistically close to the distribution of real conversations. Computational zero knowledge: the distribution of simulated conversations is hard to distinguish from the distribution of real conversations. –  K.G. Sep 29 '13 at 15:14
I though Perfect Zero Knowledge was defined as security from an adaptive dishonest verifier. What is to be proved is that $s$ is uniformly distributed, even if we don't make it as our first assumption that $c$ is uniformly distributed. –  Henrick Hellström Sep 29 '13 at 18:12
See the section called "Variants of zero-knowledge" in the Wikipedia page. –  K.G. Sep 29 '13 at 21:11

The zero knowledge property from the Schnorr protocol is not given, because there is no efficient simulator.

This is quite hard to show formally, and I couldn't construct it on the fly or find references for it, but here's the reasoning:

• The simulator commits to a random number (perfectly binding, computationally hiding)
• The verifier chooses a challenge $e$
• The answer is an exponent, which is the secret, multiplied by the challenge $e$, and shifted by $r$ (addition).

The intuition behind this is:

• Given a group element $g^x$ and a number $e\neq 0$, computing $x$ from $g^x$ or $x$ from $g^{ex}$ should be equally difficult.
• The additional shift by $r$ does not change the problem at all.

Other ways of arguement:

• If the challenge $e$ is chosen randomly from $\mathbb{Z}_q$, the probability of a successful simulation is negligible. If the challenge $e$ is chosen just as a single bit, then the chance of success is 50%. In this case, a simulator with rewind advantage can be a PPT.
• In other proofs of knowledge the simulator's advantage can also be expressed as "knowing the challenges ahead of time" and succeed in every round. This would not help the simulator in this case, as he would still have to find the dlog of $y^e$. (Assuming the secret key $x$ and the public key $y=g^x$).
-