Feat of Nerdiness: The Zero-Knowledge Drinking Game

Last semester in Models of Computation and then again in Cryptography, Anna showed us the zero-knowledge proof for 3-Colorability.

(Informal Definition: A graph is 3-Colorable if you can assign each of the vertices one of 3 different colors such that no two vertices connected by an edge have the same color.)

(Informal Definition: A zero-knowledge proof occurs when a Prover wants to demonstrate to a Verifier that she knows some piece of information without the Verifier learning anything about that piece of information.)

She eloquently describes the proof at
http://www.scientificamerican.com/article.cfm?id=anonymous-authorization,
but I will do my best to describe it here:

In this situation, the Prover knows a 3-coloring for a given graph and wants to prove to the Verifier that she knows the 3-coloring without the Verifier learning anything about the 3-coloring. The Prover 3-colors the graph, then covers all of the vertices with paper cups so that only the edges show. The Verifier then gets to choose an edge. The Prover then reveals the vertices on that edge, demonstrating that they are indeed different colors.

Well. Naturally, when my friend and I saw this, we HAD to turn it into a drinking game (not with alcohol, of course, since we're not 21). We planned a party, and I drew 6 graphs on poster board, half of which were 3-colorable.

The question remained: what's the best way to 3-color a giant graph? With jello shots! (not containing alcohol, of course, since we're not 21) I made a grand total of 90 jello shots in red, green and yellow. We labeled the 3-colorable graphs with directions for coloring them and the non-3-colorable graphs with suggested colorings containing only one bad edge.

Once the party had a critical mass of people, I used my excessively loud voice to make everyone be quiet and listen to the rules. I'll put them here because I highly suggest trying the game for yourself:

Choose two Provers and two Verifiers. The Verifiers leave the room. The Provers color the vertices using jello shots, then cover the jello shots with solo cups. The Verifiers come back into the room. They can choose up to 3 edges to reveal, but for each edge they must drink the jello shots they reveal. Then they make their guess: 3-Colorable or no? If they guess correctly, the Provers must match all of the jello shots they took, and the Verifiers become the Provers. If they guess incorrectly, the Provers remain.

SUCH a fun night. All of the CS people at the party didn't know whether to be excited at playing the game or exasperated at the extent of our nerdiness. A great moment was when a team of non-CS people got really into the game and solved the graph while revealing very few jello shots. Another team decided to divide up the roles into "thinker" and "drinker". Conclusion? Computer science drinking games make for very fun parties, and I plan to come up with more in the future. The only question now is whether to tell the professor about our abuse of the material...