27
$\begingroup$

Alice is color blind. She never knows if her gloves are matched. Her brother Bob always teases her saying her gloves are mismatched and she should go change them. Alice wants to know if Bob is telling the truth about her gloves.

Assuming Alice only has 2 colors of gloves, how can she design a protocol that she can use with her brother to determine if Bob is being truthful or just teasing her?

I would assume that Bob decides at the beginning whether to tease or be honest. If teasing, he chooses his response at random.

My intuition tells me this problem is similar to the coin toss over the phone problem... but I can't seem to create a scheme where Alice would know if he was telling the truth is she has no way of verifying? Any help would be appreciated as I'm studying for finals!

$\endgroup$
29
$\begingroup$

This is a classical example.

Here is the proof system…

Bob gives two gloves to Alice so that she is holding one in each hand. Bob can see the gloves at this point, but Bob doesn't tell Alice which is which. Alice then puts both hands behind her back. Next, she either switches the gloves between her hands, or leaves them be, with probability $1/2$ each. Finally, she brings them out from behind her back. Bob now has to "guess" whether or not she switched the gloves.

By looking at their colors, Bob can of course say with certainty whether or not Alice switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way Bob could guess correctly with probability higher than $1/2$.

If Bob and Alice repeat this "proof" $t$ times (with a large $t$), Alice should become convinced if the gloves are indeed differently colored; because if they would have the same color, the probability that Bob would have succeeded at identifying all the switch/non-switches is at most $(1/2)^{t}$.

(Furthermore, the proof is "zero-knowledge" because Alice never learns which gloves have what color; indeed, she gains no knowledge about how to distinguish the gloves… but the proof system helps her.)

In case anyone has problems understanding zero-knowledge proofs, I would like to point to “Zero-Knowledge Technique (PDF)” (PDF) which contains a colorblind example similar to mine, as well as a few more examples explaining ZKP, including the example by Jean-Jacques Quisquater which has been published in “How to Explain Zero-Knowledge Protocols to Your Children” (PDF). That should help…

$\endgroup$
  • 1
    $\begingroup$ In your protocol, even if Bob initially gave different colored gloves to Alice, he could prove to Alice that they are same colored right? Because, when Alice asks if she switched, Bob just ignores the gloves and answers with a coin toss. $\endgroup$ – satya Mar 7 at 2:59
  • 1
    $\begingroup$ @satya This is a bit too extensive a question to answer here. Please consider posting a question instead. Your comment and this comment will be removed over the weekend. $\endgroup$ – Maarten Bodewes Mar 8 at 11:43
  • $\begingroup$ @satya: Let's move into the non-zero knowledge variation of this question: Bob can prove that he is not color-blind by pointing at the green glove and saying, "this glove is green" A color-blind person will not consistently pass this test. Now, let's suppose Bob claims he is color-blind, then intentionally points at a red glove and claims it is green. Alice can't know if he's lying. A liar can trivially simulate ignorance by ignoring their knowledge. A liar cannot simulate knowledge by demonstrating that knowledge. $\endgroup$ – Brian May 24 at 20:59

protected by e-sushi Nov 26 '18 at 10:41

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.