6 ms·
"Very careful" doesn't really explain much. If lie is not necessarily probabilistic (so we cannot figure it our based on frequency of some contradictory answers
by krick 7y ago
"Very careful" doesn't really explain much. If lie is not necessarily probabilistic (so we cannot figure it our based on frequency of some contradictory answers), and if we need an oracle at all (that is, there is some piece of knowledge we cannot possibly verify ourselves), why cannot oracle just always lie about that piece of knowledge and take this lie into consideration in all the other answers, to make story consistent?
I'm pretty sure there must be some additional constraints, otherwise I don't see how you could possibly detect a lie that you cannot verify yourself with a single oracle.
- isaacg 7y agoHere's an example of such a protocol, for the problem of graph (non)isomorphism. Verifier: Here are two graphs, A and B. Are they isomorphic? (Same except for relabeling vertices) Prover: No, they're different. Verifier: Here's one of the graphs, with the vertices relabeled uniformly randomly. Which one was it? Prover: It was A. (Repeat 100 times) Verifier: Ok, you got them all right. I believe you. Here, we've forced the prover into a situation where if it's lying, and graphs A and B are in fact isomorphic, it can't know which graph we started with, before permuting. As a result, it can only guess which graph we started with and hope to get lucky, and we'll catch it with very high probability. In contrast, if the verifier was telling the truth, it could figure out which graph we started with, and always answer correctly. Here it is impossible for the prover to make its lie, "the graphs are not isomorphic" consistent with its later inability to tell them apart, after random permutation. This kind of 'catching in a lie' is how interactive proofs typically work.