3 ms·
This is correct, and key to making this zero knowledge. But "accumulate" isn't quite the right word, I think. During a single round, by itself, Peggy reveals li
by kevhito 10y ago
This is correct, and key to making this zero knowledge. But "accumulate" isn't quite the right word, I think. During a single round, by itself, Peggy reveals literally nothing about the actual solution -- no information whatsoever -- so one might wonder, how can a bunch of repeated nothings "accumulate" to anything?
Here's how. If Peggy were to use the same permutation repeatedly, revealing different rows/columns/boxes, then Victor can cross-reference the permuted numbers in one revealed row against the same-permuted numbers in other rows. (E.g. Victor might notice that the top left corner has the same as the bottom center tile, which he didn't know before.) And each new reveal allows for more cross-referencing, and soon Victor can learn a lot. Notice that cross-referencing the numbers within a single revealed row don't tell Victor anything -- no number will appear more than once, so all Victor learns is that all the cells are different, which Victor knew already by the rules of Sudoku.
Of course, Peggy uses a different permutation each round, so each round Victor learns nothing, and the different permutations prevent Victor from cross-referencing numbers from different rounds to learn anything that way either.
- deleted 10y ago[deleted]
- Manishearth 10y ago> Peggy reveals literally nothing about the actual solution -- no information whatsoever -- so one might wonder, how can a bunch of repeated nothings "accumulate" to anything? The trick here is in the wording; Peggy does reveal something. She essentially reveals that she _may_ have a correct solution, with some probability. :) All information revealed is information that Victor knows to be true (and can guess beforehand) assuming that Peggy had a correct solution. The last part is the operative bit here; that still means that something is revealed if we are considering the space of all moves (but nothing is revealed if we're considering the space of all moves of a non-malicious Peggy). These probabilities accumulate and eventually we're reasonably certain that that assumption is true. This sleight of hand happens because from Peggy's side, Peggy knows that she is non-malicious and only cares about no information being leaked with this assumption in mind. On Bob's side, he has no idea about Peggy and must consider the case that Peggy is malicious. However, he doesn't care about defending from leaks, he would love leaks. He only wants the information that Peggy has a solution. From his side, he needs to obtain the information that Peggy has a solution (which Peggy is already assuming to be true). Our brains get confused whilst juggling these assumptions and it seems like something was revealed without anything being revealed -- the trick is in the difference of sample spaces and assumptions. Overall this is one reason why I love ZKP -- it seems like magic.