4 ms·

> series of questions, carefully chosen to expose any lie I don't understand, how this is possible. Is it assumed that every lie is necessarily a Bernoulli tri

by krick 7y ago

> series of questions, carefully chosen to expose any lie I don't understand, how this is possible. Is it assumed that every lie is necessarily a Bernoulli trial with a known probability? Because if not, what prevents a single oracle from telling consistently false story, taking into account all lies he told you before?

amluto 7y ago
The solution is very careful construction of the questions. A working protocol puts a low upper bound on the prover’s probability of successful cheating.
- 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 ago
    Here'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.

by krick 7y ago

amluto 7y ago

The solution is very careful construction of the questions. A working protocol puts a low upper bound on the prover’s probability of successful cheating.

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 ago
  Here'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.