I'm confused about the maze example in the article: I can "prove" that I know the path to exit as I traverse the maze in limited time, okay. But interactive proofs have many iterations to sufficiently convince the verifier, however if I found the exit by luck in first try, I've already found it and I can simply follow the same path in the next iterations.
How does the interactivity exactly work with the maze example?
Imagine the maze is large and complicated, so that it would be very unlikely you could find the exit by luck. Not impossible, but like winning the lottery odds. You could brute force the search but you don't have time. The probability of finding a path by luck is called "soundness error". When the verifier sees you appear at the exit, they know you either knew the path, or with a soundness error probability, you were just lucky.
Now imagine the maze has a large number of exits, all hard to find by luck, and the verifier tells you before you go in which exit they want to see you come out of. You don't know in advance which exit they will ask for. After you come out, they ask you for another one, and again you don't know in advance which one. These rounds are the interactivity.
Each time through, you have a soundness error's probability of finding the requested path by luck, i.e. winning the lottery kind of odds. The probability that you found all the exits the verifier asked for, is like winning the lottery multiple times in a row. Because you don't know which the verifier will ask for in advance, you can't take advantage of patterns in those requests to skew the combined probability in your favour. They are like independent random events: The probabilities multiply.
After N rounds, your probability of finding all the requested exits by luck is lottery kind of odds raised to the power of N. Pick a sufficiently large N and you have extreme probabilities like those used in other cryptography, numbers like 2⁻¹⁰⁰ or 2⁻²⁵⁶, which are so infeasibly unlikely they are similar to the probability of guessing someone's private key or guessing a SHA-256 hash preimage. We trust this demonstrates you know the maze, even though there's an astronomically unlikely possibility that you guessed right every time.
Yeah, this article tries too hard to appeal to all audiences in a way that ends up making it confusing for everyone. Starts off with the clumsy maze example, then hops over into graph theory and NP-complete proofs, then hand waves something about sharing bits and quantum computing... But enough about that, it turns out blockchain will prevent nuclear war!
And they lost me with the graph example… because both graphs are the same! How are you not leaking information about the solution if you’re showing the path in the exact same graph!
If they consider two graphs drawn differently as different graphs, they should clarify it from the start … and maybe not pose it as a graph problem.
Imagine the graphs are really, really big. Graph isomorphism is NP-hard.
Alice gives Bob a graph. Bob can ask Alice to show the bijection (hard) or show a path (hard) but not both.
Say Alice and Bob do this 40 times.
Can you see how Bob should be convinced that Alice is giving him isomorphic graphs and that she knows a path through the graph? Otherwise Alice would have failed to answer one of his questions along the way.
How does the interactivity exactly work with the maze example?