Schnorr protocol: how does malicious verifier win?

Question

My question is about the challenge space size in Schnorr protocol. To be precise, I feel I've read all the Internet (twice) and I still don't understand why is it bad to allow challenge space to be large (say, why one shouldn't let $\text{Challenge} \in \mathbb{Z}_q$)

I'm interested only in situation of honest prover $P$ and malicious verifier $\tilde{V}$.

To settle the notation, recall that (one round of) Schnorr protocol has the following form:

1. Prover generates random $r \in \mathbb{Z}_q$, calculates $\text{Commit}=g^r \pmod p$, then sends $\text{Commit}$ to verifier.
2. Verifier generates $m$ random bits and forms the number $\text{Challenge}$ from them (thus $\text{Challenge}$ is the random number ranging from $0$ to $2^{m} - 1$), then sends $\text{Challenge}$ to prover.
3. Prover calculates $\text{Response} = r+s \cdot \text{Challenge} \pmod q$, then sends $\text{Response}$ to verifier.
4. Verifier checks that $g^{\text{Response}} = \text{Commit} \cdot y^{\text{Challenge}} \pmod p$

where $y = g^s \pmod p$ and $s$ is the prover's secret.

The simulator for this protocol is as follows.

1. The algorithm generates random $\text{Response} \in \mathbb{Z}_p$.
2. The algorithm asks verifier for the number $\text{Challenge}$ and receives it.
3. The algorithm sets $\text{Commit} = g^{\text{Response}} \cdot y^{-\text{Challenge}} \pmod p$
4. The algorithm appends $(\text{Commit}, \text{Challenge}, \text{Response})$ to the transcript.

The standard answer to my question is: if $\text{Challenge}$ is pseudorandom -- namely, depends on $\text{Commit}$, say, is equal to $\text{hash} (\text{Commit} || M)$ -- this simulator protocol cannot work, since at step 2 it requires the knowledge of parameter generated at step 3. There are no other simulators known for this protocol, so in the case of malicious verifier there's just no simulator. And since any ZK-protocol has simulator, the conclusion follows that malicious verifier case is not ZK.

Question 1. However, I still don't get how exactly can malicious verifier extract some information. Okay, there's no known simulator for malicious verifier case -- well, how does it help him?

Question 2. What about the challenge space size? Mao, Wenbo in their "Modern Cryptography" state that, thus, because of this simulator argument, $\text{Challenge}$ space size should NOT be large (don't get the logic again) ($\text{Challenge} \in \mathbb{Z}_q$ is prohibited) and state that the best choice is $\text{Challenge} \in [0, \log_2 p)$ (or, equivalently, $m = \log_2 \log_2 p$). Why such an odd and strange value?

Answer 1

I'll start by recalling what the (honest-verifier) zero-knowledge property actually means (informally).

In case of honest-verifier zero-knowledge, the protocol is only zero-knowledge when interacting with an honest verifier. This is modeled in a way that the simulator has black-box access to the verifier but has full control over all input tapes of the verifier (including it’s random tape) and thus the verifier behaves deterministic. Actually, this is modeled by giving the challenge to the simulator and then the simulator needs to compute a transcript of the entire conversation (this can easily be done even if the challenge comes from the whole $\mathbb{Z}_q$ - you can easily check that for the Schnorr protocol and this is exactly the simulator you provide in your question).

However, zero-knowledge is more tricky. In this case the simulator has black-box access to the potentially malicious verifier and so you have to construct a simulator that works for any malicious verifier strategy. Now what can you do to get zero-knowledge for the Schnorr protocol? Well, what the simulator can do is guess the challenge of the verifier before it computes the commitment and then send the commitment and get the challenge. If the guess is correct, then the transcript will be an accepting transcript. However, if the guess is not correct then the simulator would have to try again. Now, using the entire space $\mathbb{Z}_q$ makes the probability that the simulator guesses correctly exponentially small and so you fail to come up with such an efficient simulator. What you can do is to reduce the challenge space. If you choose the challenge space to be $\{0,1\}$ your simulator will guess correctly with probability $1/2$. Now you have to repat the porotocol sequentially a number of times and keep only the transcripts where your guess was correct (note that a single interaction will give you a protocol with bad soundness). Now you can show that if you want a soundness error of $1/2{^t}$ you have to run the simulator an expected number of $2t$ times which gives you an expected polynomial time simulator. Now, clearly, you can make the challenge space "slightly" larger (as long as it is not exponential) and can do the math (this is what Wenbo Mao discusses). However, to adjust the soundness such that the chance of a malicious prover to win is exponentially small with the latter approach you have to run many protocols sequentially (parallel is not safe as Schnorr is not concurrently secure) and this makes it quite inefficient for practical applications (you may want to look into turining honest-verifier zero-knowledge proofs into non-interactive zero-knowledge proofs using the Fiat Shamir heuristic).

Now back to your questions:

Q1: Think of the simulation strategy in the honest-verifier zero-knowledge case but the verifier is not honest. For instance, the verifier could make the challenge somehow depend on the first round of the protocol (the commitment). Then after it knows the challenge, the verifier rewinds the prover and runs it again such that the first round is identical, but the malicious verifier is clever and now sends another distinct challenge. Now, it should be easy for the Schnorr protocol to figure out how the malicious verifier is able to extract the secret from the prover (this is exactly how the special soundness of $\Sigma$ protocols is defined). For Schnorr, you can observe that you have $Response_1 = r + s\cdot Challenge_1$ and $Response_2 = r + s\cdot Challenge_2$ which you can now solve for the secret $s$ in $\mathbb{Z}_q$.

Q2: Thats exactly the last paragraph discussed above. Why such an odd value? Because it is small enough for the simulation strategy to work.

Maybe you should look into alternative lecture notes or books that cover topics like Sigma-protocols, honest-verifier zero-knowledge etc.

Answer 2

This all seems to be explained in the book (warning: large) you mention, all I mention here is taken from there.

This is the last sentence before $\S18.3.2$:

Enlarging challenge size not only improves performance (a positive result), in $\S18.3.2$ we will further see that this also has a negative consequence. Be careful, size matters!

This last sentence is of critical importance, but we will focus on the first one for now. Moving to $\S18.3.2$, we find the last sentence before $\S18.3.2.1$:

However, there is a subtlety for the problem. Let us examine it now.

This is followed by about 2 pages of explanation to your question, which indeed they agree to have subtleties. Although you have read all the internet twice (kudos), your answer suggests you may have missed this.

It seems that setting

$${\tt Challenge}={\tt prf}(M||{\tt Commit})={\tt prf}(M||g^{\tt Response}y^{\tt > Challenge}\bmod{p})$$

leads to two options:

1. The equation was constructed by Alice using her private input, and hence Alice discloses the fact that she has been in interaction with, and fooled by, $\tilde{Bob}$, or
2. $\tilde{Bob}$ has successfully broken the pseudo-random function ${\tt prf}$ of the large output space $\mathbb{Z}_q$, because he has constructed equation $${\tt Challenge}={\tt prf}(\cdots y^{\tt Challenge}).$$ This is a well-known hard problem because ${\tt prf}$ is assumed to be one-way.

Given that $\tilde{Bob}$ is assumed to be polynomially bounded, the third party will of course believe that (i) is the case.

The information revealed is thus the fact that the prover has been interacting with the malicious verifier. Luckily, the authors mention that

A small consolidation for Alice is that the information disclosure caused by $\tilde{Bob}$ is not a too disastrous one (though this assertion has to be based on applications really). [...] the proof transcript still does not disclose to $\tilde{Bob}$ or a third party any information about Alice's private input $a$.

Answer 3

There is zero knowledge and honest verifier zero knowledge; the difference is that honest verifier is less stringent by omitting verifier challenge from dataset that must be simulated in an indistinguishable way.

Expected running time of the simulator must be polynomial in problem size. For this protocol running time is defined by challenge space cardinality. That is, linear in number of possible challenges. This gives number of bits for challenge space being the logarithm of problem size.

To remind it: zero knowledge simulator (not honest verifier zero knowledge) must query verifier (run as a subroutine) to get a challenge according to his (unknown) distribution. This simulator keeps rewinding until the challenge is the right one.

Verifier wins not by extracting information, the term is distinguish simulated session transcript from a real transcript. Please note there are two different games: for zero knowledge and for soundness.

Answer 4

So, you're probably right that it's not enough for malicious verifier to extract information about secret key. But, it's already bad that verifier can prove for anybody that you actually know the secret. It may be already harmful for you, since you wanted to prove your knowledge for only the verifier and nobody else.

And I see another side-effect of that it's not zero-knowledge: malicious verifier could food you with special challenge and get signature of some document from you (without your knowledge): after you sent commitment C, verifier just need to send challenge hash(M||C), and that's it - you will effectively sing message M with Schnorr signature. This is possible exactly because of non-zero-knowledge scheme.