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