# Keeping Your Secrets Safe: Anonymous Authorization

Showing you belong without saying who you are

• Overview

#### Cryptography: How to Keep Your Secrets Safe

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.

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

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Scientific American Magazine | 2 minutes ago | 2

### The Internet Has Become the External Hard Drive for Our Memories

• Scientific American Magazine | 2 minutes ago | 2

### Protecting Your Data on The Cloud

• Scientific American Mind | 1 hour ago

### Figurative Speech Sways Decisions

• Scientific American Magazine | 1 hour ago

### Genetic Cures for the Gut

• Features | 3 hours ago

More »

## Latest from SA Blog Network

• ### Mathematics+Fatherhood: an Interview with Darren Glass

Roots of Unity | 2 hours ago
• ### Gag Me With a Spoon: "Val-Speak" Takes Over SoCal

Cocktail Party Physics | 13 hours ago
• ### Nerds and Words: Week 49

Overthinking It | 20 hours ago
• ### Photoblogging: Muppet or Flamingo?

MIND
The Thoughtful Animal | 22 hours ago
• ### Sunday Species Snapshot: Fijian Monkey-Faced Bat

Extinction Countdown | Dec 8, 2013

## Science Jobs of the Week

Keeping Your Secrets Safe: Anonymous Authorization

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X