# Zero knowledge proof protocol example?

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!

-
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
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

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)” (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…

-
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
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
@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
@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
Paul Wagland is 100% correct. If Bob is teasing (he is lying, and Alice is actually wearing two same-color gloves), then there's no way Bob will be able to fool Alice into thinking her gloves are mismatched. But, if Bob claims that Alice is wearing matched gloves, Alice has no way to tell whether Bob is telling the truth or not (Bob might have noticed that Alice is wearing mismatched gloves and decided to lie about it; then when they conduct the ZKP, he answers randomly). In other words: there's a proof that Alice's gloves are mismatched, but there's no proof that Alice's gloves are matched. – D.W. Dec 26 '13 at 2:53

(I see that this is a very old question. I came across it from a search and then thought about the problem.)

I'm not an expert, I was just thinking about this problem and came up with an "idea". I'm also sort of hinging this on one of the comments above quoting that the problem says Bob always teases her saying they don't match.

In that case, couldn't she take one glove and pair it with each of the other gloves in turn (or just enough that one pair must have matched), and when he continues to say they're mismatched when logically at least one pair must have matched, she can determine that he is not being truthful? Meanwhile she learns nothing about whether any particular pair was matched.

-
Just to be sure – since this reads a bit as if you’re guessing and since you used a “?” sign – is this actually meant to be an answer or is it rather another question? If it’s the later, you should post it as a question. – e-sushi Feb 28 at 22:02
It's meant to be an attempt at an answer to this question, but, while I think I'm relatively knowledgeable about cryptography in general, I'm not accustomed to answering questions in this form. So, I guess I was looking for affirmation that this is a valid answer. – adfaklsdjf Feb 29 at 23:08
I see, thanks for helping me understand. Welcome to Crypto.SE by the way! – e-sushi Mar 1 at 18:54