Thursday, April 13, 2017

Alice and Bob and Pat and Vanna

"The only useful thing computer science has given us is Alice and Bob" - A physicist at a 1999 quantum computing workshop
Alice and Bob, great holders of secrets, seemed to pop into every cryptography talk and now you see them referenced anytime you have two parties who have something to share. Someone at Dagstuhl a few weeks back asked who first used Alice and Bob. What a great idea for a blog post, and I decided to do some binary searching through research papers to find that elusive first Alice and Bob paper. Turns out Wikipedia beat me to it, giving credit to Rivest, Shamir and Adleman in their paper A method for obtaining digital signatures and public-key cryptosystems, the paper that won them the Turing Award.

In grad school attending a square dance convention we ran into a married couple Alice and Bob and they couldn't figure out why we were laughing. Yes, I square danced in grad school, get over it.

The Wikipedia page lists a number of other common names used in protocols including perennial third wheel Charlie and nosy eavesdropper Eve. I can claim credit for two of those names, Pat and Vanna. In my first conference talk in 1987 I had to explain interactive proofs and for the prover and verifier I picked Pat and Vanna after the hosts, Pat Sajak and Vanna White, of the popular game show Wheel of Fortune. Vanna didn't trust Pat and spun the wheel to get random questions to challenge him. Half of the audience laughed hysterically, the other half had no clue what I was talking about. I heard the FOCS PC took a break by watching an episode of Wheel of Fortune to understand the joke.

Howard Karloff insisted we use Pat and Vanna in the LFKN paper. Pat and Vanna have since retired from interactive proving but thirty years later they still host Wheel of Fortune.

No comments:

Post a Comment