4 ms·

A while back I came up with a third ZK Where's Waldo protocol [1] that avoids the need to watermark the page or search Alice for contraband, and also has the (u

by SilasX 5y ago

A while back I came up with a third ZK Where's Waldo protocol [1] that avoids the need to watermark the page or search Alice for contraband, and also has the (usually desirable) property that it's only convincing to Bob. You instead have Bob randomly choose whether Alice must a) pull off the screen, revealing the original page, or b) punch a hole through to Waldo, but not both. Then you can do any number of rounds of this, with Alice putting the page in a random position each time. It's only convincing to Bob because bystanders (or rather, anyone not part of the random number generation for which challenge to use) can't rule out the possibility that they conspired to have Bob always pick the challenge that a faker Alice could solve. (Show the original page when the uses the real one, punch a hole when she uses a fake page.) [1] https://news.ycombinator.com/item?id=15323790 https://news.ycombinator.com/item?id=15323790 Edit: That original comment gives the "magic formula" for coming up with such ZKPs as well.

cmehdy 5y ago
After reading your post I understand that the challenge to show the picture is to test for a fake picture (one with only Waldo for example), so that makes more sense to me. Bob is just allowed to make sure the hidden image that Alice uses is the original (and she can still cheat when Bob choses the other option but the probabilities of succeeding the tricks become vanishingly small with tries, which is the point). And I assume the screen is meant to always cover the picture (i.e. MUST be much larger than the picture) and only Alice can know the actual coordinates of the picture behind the larger screen (otherwise Bob can infer the position of the Waldo), right? It is also possible that I have not understood something from your interesting proof there. Thanks for sharing the discussion about the finer points of ZKP being only between Alice and Bob.
- SilasX 5y ago
  That's correct. Ideally you'd want a screen with double the dimensions so that you can designate a portion of it with uniform probability of any location having Waldo. And my model has it so that (for the second challenge) Bob learns the position of Waldo relative to the screen, but not the position of Waldo relative to the page, which is what we mean by "finding Waldo". And, of course, on that challenge, Bob would not get to learn the position of the page relative to the screen (which would allow him to "find Waldo").

by SilasX 5y ago

cmehdy 5y ago

After reading your post I understand that the challenge to show the picture is to test for a fake picture (one with only Waldo for example), so that makes more sense to me. Bob is just allowed to make sure the hidden image that Alice uses is the original (and she can still cheat when Bob choses the other option but the probabilities of succeeding the tricks become vanishingly small with tries, which is the point). And I assume the screen is meant to always cover the picture (i.e. MUST be much larger than the picture) and only Alice can know the actual coordinates of the picture behind the larger screen (otherwise Bob can infer the position of the Waldo), right? It is also possible that I have not understood something from your interesting proof there. Thanks for sharing the discussion about the finer points of ZKP being only between Alice and Bob.

SilasX 5y ago
That's correct. Ideally you'd want a screen with double the dimensions so that you can designate a portion of it with uniform probability of any location having Waldo. And my model has it so that (for the second challenge) Bob learns the position of Waldo relative to the screen, but not the position of Waldo relative to the page, which is what we mean by "finding Waldo". And, of course, on that challenge, Bob would not get to learn the position of the page relative to the screen (which would allow him to "find Waldo").