2
$\begingroup$

Some time ago i read the following problem (i don't remember the article from which i read it from) :

"Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), you search for a bit and don't find him so you become suspicious of the fact that waldo actually is in the picture, how can one prove to you that waldo indeed is without revealing where ? Well one can just take a very big sheet of paper, bore a hole inside it and place this sheet of paper on top of your picture so that waldo's head appears inside the hole."

My question is how could one transfer this idea to a mathematical concept ? One idea would be something along the lines of :

  • Let L be some language in complexity class C

  • given $a_1 , a_2 , ... a_n$ can one prove to you that there is a $i$ for which $a_i \in L$ without revealing for which $i$ it stands

However this falls short as it stands right now because one can just feed the same input $a$ n times for which it wishes to know appartenance to class L. So we either need to consider specific complexity class C for which the problem becomes interesting or loosen the condition of "non disclosure", and it doesn't seem that obvious. Or we could just change paradigm, my question is just how to convert the waldo idea to a computationnal model, i suspect the approach i gave isn't the right one.

Edit : I thought about it some more and the interesting question indeed seems to be finding languages for which this is possible, for instance let L bet the set of numbers divisible by 7. Given $a_1 , a_2, ...a_n$ n integers. Let p be their product then I can prove to someone easily that p is indeed their product and that p is divisible by 7 (iif one of the $a_i$ is). But by doing so I don't reveal which one.

There are two shortcomings with this however. The first one not too big is that divisibility by 7 is easy, but one could imagine harder languages. The second one is that it is not true that we don't reveal which $a_i$ is divisible by 7. If in the input we're given we have a rule of thumb to rule out all but one $a_i$ from being divisible by 7, then we know immediately which one is by knowing the whole product is divisible by 7. (Again just think of divisibility by 7 as a placeholder for "complex problem")

$\endgroup$
  • 1
    $\begingroup$ That quote is an analogy of what happens in a ZK proof that's intended to build intuition but should not be taken too seriously. I think asking how to transfer it is inherently subjective, as there might not be a precise translation. $\endgroup$ – D.W. Jan 13 at 18:00
  • $\begingroup$ But it still interesting to see how one could transfer it, it's a pretty natural problem after all. $\endgroup$ – PMercier Jan 15 at 2:51
  • $\begingroup$ I'm going to conjecture that every $L \in \mathbf{NP}$ has a "Waldo proof" that only reveals $O(1)$ bits of the location, by way of the PCP theorem. The idea is to take a nondeterministic machine that guesses the location and checks that it is the right one, and turn that into a PCP that only needs $O(1)$ bit accesses. This is only a vague idea for a solution, though. $\endgroup$ – Aaron Rotenberg Jan 15 at 4:14
  • $\begingroup$ Well the thing is I think we need a condition on the $a_i$-s too. Let's take L to be the SAT, if all but one $a_i$ are equal to $false$ then once the prover answers me I know in linear time whether the unique $a_i$ is SAT or not. $\endgroup$ – PMercier Jan 15 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.