A subscriber to a Web site could sign on as a legitimate, registered user without revealing any identifying information by using anonymous authorization. The Web site would not even be able to associate the user with his or her previous visits. Such a protocol is an example of a zero-knowledge proof, in which one party proves a fact without revealing anything about the proof but its validity.
Imagine Alice and Bob play a game with a graph, three colored pens and some paper cups. The graph is a collection of dots, or vertices, connected by lines. Two vertices connected by a line are said to be adjacent. Only some graphs are three-colorable, meaning that three colors suffice to color in all the vertices without coloring any two adjacent vertices the same. Alice will prove to Bob that she has three-colored her graph without giving him any clues about how to three-color it.
The game begins with Bob out of the room. Alice draws six separate copies of the graph. Because she knows how to three-color the graph, she does so with the first copy. For the other five, she uses all of the six possible permutations of her colors. Thus, the six copies of the graph are threecolored in trivially different ways. She chooses one of the six copies at random, places it on the table and covers each vertex with a paper cup. Now Bob returns, and he gets to choose any two adjacent vertices and remove their cups. If the two vertices are the same color, he knows that Alice has been lying and that she has not drawn a valid three-coloring.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
They keep repeating the inspection procedure—Bob leaves the room each time while Alice randomly chooses one of the six copies of the graph to place under the cups. From Bob’s perspective, if Alice is cheating, she could be showing him many different invalid colorings, and the telltale matching adjacent vertices need not be in the same place on each one. But as he plays enough rounds, the probability that he will catch such cheating approaches 100 percent. Yet at the end of it all, he will not know how Alice has colored the graph. On each round, the two colors he sees on the chosen vertices are random; he might as well have picked the colors himself. For any statement that has a reasonably short proof (such as “I have the credentials showing that I am an authorized user and over 18”), one can concoct a version of this game that would prove the statement without disclosing any extra information (such as “I am Alice” or “I am user #4790561”).
