Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
2  
Her brother Bob always teases her saying her gloves are mismatched and she should go change them $\quad\qquad$ If Bob always teases her, then there is no information (about her gloves) carried by his response, so she can't learn anything. I guess the point of my observation is does Bob decide to be honest/tease at the beginning of the 'game' and stick to his decision or something like that? –  figlesquidge Dec 18 '13 at 16:25
    
@figlesquidge yes –  user10956 Dec 18 '13 at 16:30
1  
Is the teasing Bob smart (he can plan his answers), random (uses a coin to choose whether he says they're matched or not), or does he always say her gloves are wrong? (answers to both this question, and my previous, would help clarify the question) –  figlesquidge Dec 18 '13 at 16:31
    
I would assume he teases at random. And yes, he decides at the beginning and does not change his answer –  user10956 Dec 18 '13 at 16:36
    
Thanks for the clarifications. Added to the question and upvoted-nice problem. –  figlesquidge Dec 18 '13 at 16:41
add comment

1 Answer

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 $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.)

EDIT

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

share|improve this answer
3  
Does this rely on Bob telling the truth when "guessing"? What if he "guesses" randomly even if he knows the correct answer (when gloves are different) hence making the probability of guessing 1/2 for different and same color gloves. –  Samuel Dec 19 '13 at 9:15
1  
No, Bob can choose to randomly tell the truth or not, just the way he wants to. Read the proof system again and remember… Alice may not know the color of the gloves but she knows if she has switched the gloves behind her back or not. If they are the same color and hence indistinguishable, there is no way Bob could guess correctly with probability higher than $1/2$. Repeating that $t$ times, the probability that Bob would have succeeded at identifying all the switch/non-switches is at most $2−t$ and that enables Alice to learn if the gloves actually have the same color or if they are different. –  e-sushi Dec 19 '13 at 10:58
2  
@e-sushi let's assume that bob is adversarial, then he just randomly answers to the switch/non-switch question, how is Alice meant to determine information from those random answers? Since there is no information in the answer, she clearly can't gather it. –  Paul Wagland Dec 24 '13 at 22:05
2  
@e-sushi but that is also my point, if bob decides to tell randomly, instead of always lying, or always telling the truth, then he gives no information to Alice, since he will only ever be right 50% of the time, regardless of whether Alice switches or not. If he answers randomly, then she can infer no information from those answers, as there is no information in the randomness. –  Paul Wagland Dec 25 '13 at 20:52
1  
@PaulWagland To avoid rendering this comment area into a (what the system calls) “discussion area”, I've added an EDIT to my answer. I'm sure you'll be able to grasp ZKP if you read the PDF I've linked to (as well as the several explanations and examples it contains). Besides that, it might be worth doing some research on your own as there are ample ZKP examples and papers available online. Whenever you need some answers, feel invited to post your own questions here at Crypto.SE… comments simply don't provide enough room for detailed answers. –  e-sushi Dec 25 '13 at 21:54
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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