Transcription
the verifier will ask a question that corresponds to a zero is negligible.
So, to summarize, if the cheating prover can convince the verifier with non-negligible probability while the input is not in the language, then we can construct a valid PCP that the verifier accepts with non-negligible probability, which contradicts the soundness of the PCP. Therefore, the only conclusion is that the cheating prover cannot succeed, and thus the soundness of the protocol holds.
In conclusion, we have shown that if the prover is honest, he will be accepted with probability 1, and if he tries to cheat, he will be caught with negligible probability. This completes the proof of soundness for the Kilian-Micali protocol, establishing it as a succinct interactive argument for NP languages.
Any questions about the soundness proof or the protocol itself?
We will hit locations where we fail and he succeeds is very, very, very small. So whenever we fail, he will fail, too, with very high probability, because if he succeeds there, we would have succeeded. We asked so many questions; we would finally get the right answer. That's the high-level idea.
OK. I don't want to go into more details. There's a link on the website, exactly on the proof. But there are two reasons I don't want to go into more detail—first, because it's tedious, so if you're interested, just look at the paper. But also, this is not the right proof. This is not the right proof.
And why is it not the right proof? Because, note, I cheated you, actually. I actually lied. I promised you that I broke soundness, but I didn't actually. There's a very minor—I don't know if you'd call it "bug," but I lied. And this doesn't quite do—it doesn't quite break the collision resistance with my—OK, when I say A breaks the collision resistance, I need to say A breaks—poly-T-lambda adversary that breaks—right, I said, I assume that you cannot break the collisions in time T lambda.
So I said let's just say there's a T lambda times P star, and I'm going to break the—I'm going to find the collision in time poly-T lambda. That's what gives me a contradiction. Right, I argue, my assumption is that there exist collisions in hash that cannot be broken; collisions cannot be found in time T. To break that, I need to say, if there is a cheating prover, then I can break the collision resistance in time poly T.
Now, let's look at the runtime of this adversary. The P times of time poly T. That's OK. But what does my adversary do? My adversary, he tries to generate an entire PCP. And then he says, if I succeeded, I can succeed, and therefore, I must be collision. But to generate an entire PCP, he needs to run in time poly in n.
What if T of lambda is smaller than n? Now, you can say, eh, come on, T of lambda must be bigger than n. Otherwise, this kind of—there's different—I don't like this definition, because we shouldn't allow the cheating prover to run in time poly n. If you don't, something's wrong with the definition. I don't know, maybe yes, maybe no.
I have no definition that says time T of lambda. Maybe you want T of lambda to be smaller than n because the application makes sense, because you use it in a way that actually the prover will never run in time n. So I have now some T of lambda. How it connects to N, I actually don't know.
And I want to ensure that I can break the adversary—I can find collision time T to the lambda. But actually, I run piece time which is in time T to the lambda. That's fine. But I run it n times. 1 over epsilon is fine, because epsilon is like—epsilon in lambda, or T to the lambda—OK, it's 1 over poly T to the lambda. Fine. That's good, T to the lambda—T of lambda, sorry.
But this n, n can be bigger than T of lambda. So really, this works if—this definition is good if, only if T of lambda is bigger than n. So this is a good proof if—and this has kind of—it's kind of bothered cryptographers, because even though it makes sense to assume that T of lambda is bigger than n, it makes sense to let the cheating prover run in time n, it's annoying that we need to do that.
So I think we should take a break, a five-minute break. After the break, I'll tell you just a very high-level idea. There's a beautiful paper that came in 2002 by Barak and Goldreich, that they showed how to get around it, how to do it for any t. They get around—they actually don't construct an entire PCP. They do what I think is more clever and more beautiful, kind of what I think of as the right proof for this.
And we'll see that after the break, and then we'll do the construction of the collision-resistant. But there were questions before.
Yeah?
AUDIENCE: Is the rewinding necessary so you get lower success probability but still polynomial [INAUDIBLE]?
YAEL KALAI: Great question. The rewinding for—OK, so the question is, Is the rewinding necessary? And it's a great question. The answer is, for all I know, yes, the rewinding is necessary. This question was very important also for post-quantum, because today, we're worried about quantum computers.
And if the cheating prover is a quantum device, you can't rewind him, because once you measure a quantum state, it collapses. Eh. And so proving post-quantum security of this protocol, it was—actually, it's known to be post-quantum secure. But it was a lot of work because it was work that required to kind of rewind the cheating prover in the quantum—to rewind the quantum cheating prover, and, Why can you rewind?
So they showed you can actually do it. But just to answer your question, Do you need to rewind? Yes, kind of we don't have a straight-line proof of soundness for this protocol.
AUDIENCE: And is it because the witness [INAUDIBLE]?
YAEL KALAI: You know, so it's—the other proof I'll show you after the break doesn't quite construct the PCP. But in order to find collisions, we need to run them at least twice. I run them and then—because how am I going to find collision? I give him queries. He's going to give me answers. How can I find collision from that?
But if I run him once, and I run him again with—the idea is I'm going to run him—I'm going to choose, like, a random query i. I'm once going to run him i with some queries, and then I'm going to run him i with other queries. And the only way you can cheat is if you're not always consistent. But at least, I need to remind you twice.
So that's the—any other questions?
Yeah?
AUDIENCE: Could the right group [INAUDIBLE] query if we had a concrete hash function instead of this abstract notion?
YAEL KALAI: No, I don't think the—actually, when you look inside the hash function, it just becomes messy. I think actually abstracting out the hash functions, and just thinking what property it gives you, makes the proof cleaner.
Kind of to put boxes around things and just modularize kind of what you need, it actually helps the understanding and simplifies the proof. Yeah, I think the problem with this proof is that it requires constructing an entire PCP, and sometimes you're saying, Why do I need to construct an entire PCP?
So the other proof kind of shows that you actually don't need to do that. And that's why the prover doesn't need to run time linear in n. It just runs in time that depends on t.
Any other questions before the break?
Yeah?
AUDIENCE: Just to clarify, n here is the size of the PCP, not the [INAUDIBLE].
YAEL KALAI: Yeah, you're right. n is the size of the PCP. But I'm thinking here, because I'm thinking of 3-SAT, I'm thinking the input, the instance, and the witness and the PCP are all poly-related. So because I have here a polynomial, it doesn't matter.
But I do want to say, in some settings, you can think of the witness can be much, much smaller than the instance or much, much bigger than the instance. So for example, take nondeterministic time T. x is of size n, but the witness is of size T of n, which can be superpolynomial in n. Then this becomes polynomial in the witness.
The PCP is always—or, OK, the PCP is always polynomially related to the instance and witness. Now, sometimes the witness is bigger. Sometimes the instance is bigger. And the relation does not need to be polynomially related. If they're all polynomially related, it doesn't matter here, because I put a poly.
But sometimes the witness can be much, much smaller, like a log clique. The witness is size log squared but the input is n. And sometimes the instance can be small and the witness can be big. So what I mean here is input plus witness length. Here, I just put one of them because I assume, 3-SAT, they're both the same.
So, yeah, but that's a good—what really I need to put here is PCP length. That's the truth.
Yeah. Great. Great point. Fantastic. Are there questions before we break?
OK, let's do a five-minute break, and then we'll return.