Score:2

Crypto

Understanding the "rewinding argument"

AXX

8/26/23, 2:20 AM

I read through related questions on this SE, but I still do not understand why we can use the rewinding argument. Specifically, rewinding seems like a really strong superpower to me, and I don't understand why such strong assumption does not undermine the strength of the conclusion. Sure, the adversarial verifier learns nothing from a simulator that can manipulate time, but if some entity is so strong that it can manipulate time, I am not surprised that it is secure against any adversary, nor am I convinced that other entities without this power remains secure.

I thought that maybe this rewinding ability has something to do with the simulator's oracle access to the verifier, so that the simulator can actually perform "look-ahead" to learn which question the verifier is going to ask, and then prepares the answers accordingly. If this is the case, then I am convinced that there is really no superpower, as it is something that the verifier itself can do, and so the zero-knowledge property follows.

158

0 + 0

zero-knowledge-proofs

Score:4

Crypto

baro77

8/26/23, 7:25 AM

As far as I know, you got the point. "Rewinding" is just the "look-ahead" strategy made possible by oracle access of the simulator to the verifier

It's usually referred to as "superpower" 'cause it's a capability a Prover hasn't during normal protocol execution, otherwise the soundness could be compromised (since the simulator can produce a convincing transcript of the interaction without knowing anything, it could impersonate a cheating prover pretending to prove a false statement)

Regarding the fact that simulation is exactly something verifier can do alone, that's true: the simulator has to know nothing to prove ZKness, and who is a better candidate than the Verifier for the role of someone who doesn't know?!

EDIT TO ANSWER FOLLOW-UP COMMENT:

In chapter 6 of Tutorials on the Foundations of Cryptography (Springer) Yehuda Lindell writes:

First, one may wonder how it is possible to “technically” rewind the verifier. In fact, when considering black-box zero knowledge, this is trivial. Specifically, the simulator is given oracle access to the next message function V*(x, z, r, ·) of the verifier. This means that it provides a transcript m' = (m1, m2, . . .) of incoming messages and receives back the next message sent when V* has input x, auxiliary input z, random tape r and incoming messages m'

so it's just the next message, not the whole resulting transcript at the end of interaction (if this was your doubt).

Given the foregoing definition of next message function (where the prover's challenge belongs to the messages previously received by the verifier) your "obvious way" seems wrong to me for a generic (aka potentially cheating) verifier V*.

If the verifier is honest (so the challenge is honestly "random" - even if not necessarily uniformly distributed) you can simply revert the order in which the simulator get the messages (so first the result, then challenge, then commitment): BTW, it's the strategy to prove that Schnorr identification protocol is HVZKP (omitting -for the sake of simplicity- that we are dealing with distributions and not just actual values).

But if we have to deal with a potentially cheating verifier V* (and that's the supposed case of section 8.7 of your lecture), maybe challenges are function of commitments, so they are not mutually independent, so your best strategy is to try all results until you find the valid one (or, adopting your lecture point of view, given a result you begin trying all the commitments until the function produces the "right" challenge)... anyway you have to test a number of cases growing exponentially if you have only one degree of freedom, so a PPT Simulator cannot handle it, aka ZK is not proved:

This means that after the simulator rewinds, it is as if the entire protocol is starting again from scratch. This implies that the expected number of rewinds is exponential, and that we cannot construct a PPT simulator, implying that we cannot prove the zero-knowledge property.

So no contradiction imho between foregoing definition of rewinding and the conclusion of first paragraph in section 8.7 of your lecture.

I admit I haven't thought a lot about why a simulator has to be PPT and cannot -let's say- be computationally unbounded, at least in principle: I would like to hear from others about it. In the meanwhile my educated guesses are that:

"we consider intractable those tasks that cannot be performed by PPT machine" (Goldreich, Foundation of Cryptography Volume I pag 19)
for any actual use, we are always constrained to use efficient entities (provers included, even if theoretically no problem to consider them unbounded)
the existence of a simulator is a sufficient but not necessary condition for ZK, so employing this paradigm already means missing any most comprehensive assumptions: in this scenario it seems acceptable to use an overly cautelative definition

0 + 0

AXX

8/26/23, 11:32 PM

I have another follow up question now... If we really understand rewinding as look-aheads, then we can prove the zero knowledge property of a 3 round protocol (mentioned in [this note](https://courses.grainger.illinois.edu/cs598dk/fa2019/Files/lecture08.pdf) in 8.7) in the obvious way: we perform a look-ahead to find all the $n$ messages that the verifier is going to ask, and then we prepare our commitments in the first stage accordingly. So, is my understanding of the oracle wrong? Does it actually retrives the next message or merely the end result when interacting with verifier?

baro77

8/27/23, 4:31 PM

the reply in the edited answer :)

AXX

8/27/23, 5:10 PM

Thanks for the edit, I think now I finally have a solid grasp on the subtleties in the rewinding arguments. Indeed, I never realized that the challenges verifier sends can be "adaptive" to the commitments in the first phase.

Score:2

Crypto

fgrieu

8/26/23, 7:42 AM

Rewinding a program is common in computing. One way to call it is taking a snapshot, then re-running it, as virtual execution environments allow. One application is finishing a classic arcade game without restarting from scratch after a mistake. All it takes is deciding at what point we want to rewind; making a copy of all the machine's state (RAM and registers) at that point; then later putting everything back in place.

At least some proofs using rewinding work in this way: we return an hypothetical attacker program and oracles to a saved sate, then restart with a different random tape / different oracle answers from that point. We control the random tape (thus the new values of the oracles), much like a VM host can control the RNGs of the client virtual machine. That ability allows us to turn that hypothetical attacker program into something that attacks a different protocol, thus proving security of this later protocol implies there can't be such hypothetical attacker program.

Rather than a "superpower", I see this as a construction using a slightly more powerful computing environment, much like a host computer for a virtual machine.

Note: I'm uncertain about if this analogy works for rewinding as in ZK simulator.

0 + 0

baro77

8/26/23, 8:19 AM

imho a VMs infrastructure is just an ACTUAL example of how a black-box oracle access to _next_message_ subroutine of the verifier could be attained in a "real world" nowadays scenario. However when we deal with ZK Simulator we are interested in its existence condition, not how to implement it.. so "superpower" here refers not to a specific computer environment, but to capabilities permitted outside interactive proof constraints (aka the protocol rules, coarsely speaking)

AXX

8/26/23, 4:19 PM

Thank you for the answer! It does give me a taste of how one can rewind a program in a physical world. It does seem like this requires the attacker to run on a virtual environment controlled by the defender, which I suppose is something that the ZK scenario does not allow for (or otherwise a malicious prover can win easily like @baro77 noted).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Understanding the "rewinding argument"

TH: ทำความเข้าใจกับ "อาร์กิวเมนต์ย้อนกลับ"

RO: Înțelegerea „argumentului de derulare”

RU: Понимание «перемотки аргумента»

VI: Hiểu "đối số tua lại"

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.