ZK due to rewinds, why we need poly number of rewinds?

Question

I've been looking into rewinding techniques for proving ZK and got a bit confused.

This answer is good, but I still have questions about challenge size and the number of rewinds.

Consider an interactive sigma protocol, for which Simulator can always produce an indistinguishable transcript if he guessed the challenge. Since the probability of guessing is 1 over challenge space, Simulator would not be very useful, unless he has special rewinding powers.

A) If Verifier is honest, he would use only his tape to chose the challenge, thus after rewinding, he will select the same challenge. Simulator needs to rewind just once for obtaining the challenge.

B) If verifier is malicious, then it's a bit tricky. First of all, sigma is honest verifier zero knowledge and doesn't deal well with malicious Verifiers. For one thing, malicious Verifier can always select a challenge based on Simulator's first message. No poly number of rewinds would help in such case.

Still, if we modify sigma protocol a bit and ask Verifier to commit to the challenge first, we avoid the whole dependency thing. Though commitment should be a perfectly binding one aka one-way function, otherwise Verifier still may change his response and no way Simulator guesses it in poly time.

Now after rewinding, Simulator would get the same challenge and thus can finally create a transcript. Thus, again just one rewind.

Where poly number of rewinds is coming from? Why challenge space is important? How the existence of Simulator with super powers in unrealistic settings helps to claim simulatability in real ones? I've got why it's handy for proving extractability, but ZK?

Answer 1

Well, I mixed up everything. The answers to this question helped me figure it out.

Short answer: A polynomial number of rewinds and reduced challenge space are needed when we deal with the malicious verifier and don't ask for commitments. Rewinds are handy, cause they allow us to prove honest verifier ZK for interactive protocols (ZK as well but either for protocols with commitments or small challenge space).

---

Long answer: An interactive sigma protocol is an honest-verifier zero knowledge. This means there exists a simulator, that can falsify the transcript between Prover and Verifier without knowing a Prover's secret. The intuition behind simulation is the following: if verifier can't distinguish between a fake transcript that was generated by the simulator that knows nothing about Prover's secret at all and a real one produced by a Prover, no information about the Prover's secret is leaked. Ironically, in settings where Prover by default is not honest, zero-knowledge property aims to protect Prover's privacy.

Proving honest-verifier zero knowledge is a bit tricky. We know how to simulate the transcript but can't predict verifier's challenge. We can try to guess the challenge, but even for an honest verifier (who behaves and for sure selects it randomly), the probability of guessing is one over the challenge space. If challenge space is large, this probability is next to none.

So, challenge space is a problem. On the one hand, to make sure that a malicious prover's chance to win is exponentially small, challenge space should be reasonably large (soundness). On the other, if challenge space is large, our simulator has almost no chances to guess the challenge right.

The solution is to rewind Verifier - it's an equivalent of having a time machine. We guessed wrongly, went back in time and now we don't need to guess, we know an honest Verifier's challenge. The reason is simple: if Verifier is honest, he would use only his tape to chose the challenge, thus after rewinding, he will select the same challenge.

However, a classic interactive sigma protocol is an honest-verifier zero-knowledge and not just zero-knowledge for a reason. It's not secure against malicious verifier, because even with time-machine we can't guess a malicious verifier's challenge in the polynomial time.

The problem that even rewinds can't solve is a possible dependency on Prover's reply. No matter how many times the Simulator would rewind Verifier, he will not be able to guess the challenge right, cause (a) challenge space is big and (b) challenge depends on what Simulator sends.

There are several ways to solve this problem:

• Forget about interactive proofs and switch to non-interactive.
• Reduce challenge space (this is where a polynomial number of rewinds appear)
• Make Verifier commit to the challenge first

Reduction of the challenge space is not very practical. DrLecter explained it in details here. To sum it up: after each rewind, Verifier computes a new challenge based on what Simulator sent, but since challenge space is small several Simulator's first messages correspond to one challenge, so he will guess it eventually. The book "Modern Cryptography: theory and practice" by Wenbo Mao did the math and conclude that for a simulator to run in poly time a challenge ideally should be from $[0, \log_2 p)$. The only drawback, it's not enough for soundness. To make sure that a malicious prover's chance to win is exponentially small, we have to run many protocols sequentially.

Using commitments as a guarantee is an option too. It adds interactions but requires just one rewind. There are two types of commitments we can use: perfectly hiding and computationally hiding. The former gives ZK, same soundness as before, but require 2 additional interactions: Prover sends $h$, Verifier replies with $g^r h^e$ (Pedersen commitment - perfectly hiding). For the computationally hiding commitments, ZK and computational soundness can't be achieved. Both claims were proven by professor Yehuda Lindell. The first proof (Theorem 6.5.2) can be found in "Efficient Secure Two-Party Protocols" by C. Hazay and Y. Lindell (The proof has an error that was later corrected in An Erratum). The second claim is stated here with a sketch of a proof.