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!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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…

Improve this answer
$\endgroup$
3
  • 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
    Commented Mar 7, 2019 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 ♦
    Commented Mar 8, 2019 at 11:43
  • 1
    $\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
    Commented May 24, 2019 at 20:59

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