Decrypting the History of Alice and Bob

By Hannah Pell
Alice and Bob are recurring characters in science. They can usually be found chatting over the phone or playing games of chance with each other, such as poker or flipping coins. But no matter Alice’s and Bob’s thought-experiment scenario, there is always some sort of a communication problem at the core of it: they want to send a private message to each other without an interception (usually from Eve the eavesdropper). Because of these secret messages, Alice’s and Bob’s interactions are commonly used to frame questions about how information can transfer securely — from point A(lice) to point B(ob).

Image from Physics World (Courtesy of John Richardson).

Alice and Bob have a long history rooted in cryptography, the study of secure communications. To trace how Alice and Bob became such a well-known archetype in computer science, electrical engineering, physics, and mathematics, we’ll first have to go back to the emergence of public key cryptography in the 1970s.

Cryptography and the RSA Paper
“Public key” cryptography refers to a cryptographic system that uses a pair of keys — public and private — to transmit information securely. The keys are generated by algorithms based on mathematical problems to produce one-way functions. Public key cryptography was first discovered in secret in 1970 at the UK Government Communications Headquarters (GCHQ), but wasn’t shared with the public until it was declassified 27 years later. Meanwhile, other cryptosystems were developed publicly, notably the “RSA algorithm” attributed to three MIT researchers: Ron Rivest, Adi Shamir, and Leonard Adleman.

Image from wikipedia.com

Rivest, Shamir, and Adleman were the first to mention Alice and Bob in their 1978 paper “A Method from Obtaining Digital Signatures and Public-Key Cryptosystems”. Often simply referred to as the “RSA paper,” the authors presented an encryption method with the property that revealing the encryption key does not also reveal the corresponding decryption key. “For our scenarios we suppose that A and B (also known as Alice and Bob) are two users of a public-key cryptosystem,” they wrote. Their encryption method outlines “how [Bob can] send a private message M to Alice.” It was the first instance of Alice and Bob trying to talk to one another in scientific literature.

Rivest, Shamir, and Adleman then re-introduced Alice and Bob several years later. In a 1981 co-authored book chapter titled “Mental Poker,” the authors create a scenario in which Alice and Bob are playing poker over the phone. “Can two potentially dishonest players play a fair game of poker without using any cards?,” they ask. “This paper provides the following answers: “No. (Rigorous mathematical proof supplied).” and “Yes. (Correct and complete protocol given).”

Image from “Mental Poker” by Rivest, Shamir, and Adleman (1981).

That same year, Alice and Bob showed up in another highly regarded cryptography paper. “Bob and Alice each have a secret, SB and SA, respectively, which they wish to exchange,” begins a paper by mathematician and computer scientist Michael O. Rabin titled “How to Exchange Secrets with Oblivious Transfer.” The science of public-key cryptosystems was picking up speed, and Alice and Bob were certainly along for the ride.

Alice and Bob Get a Backstory
Over time, computer scientists started giving Alice and Bob a more detailed personal story. “Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car),” according to M. Blum in his 1981 paper: “Coin Flipping by Telephone: A Protocol for Solving Impossible Systems.” In another instance, data security expert John Gordon dedicated his invited speech on coding theory at a 1984 seminar in Zurich, Switzerland to assembling a detailed (yet fictitious) biography of Alice and Bob. “Coding theorists are concerned with two things. Firstly and most importantly they are concerned with the private lives of two people who are called Alice and Bob,” Gordon said. “The other thing coding theorists are concerned with is information.”

According to Gordon, Bob is most likely a stockbroker and Alice is a “speculator,” or a stock trader. From all the scenarios we’ve seen in which they’re speaking over the phone to transmit secret information, Gordon infers that Bob and Alice have shared financial interests. They also have “very powerful enemies,” including the “Tax Authority” and the “Secret Police,” who represent the potential eavesdroppers in their conversations. Another issue is that Alice doesn’t trust Bob at all (remember the telephone poker game?) and also doesn’t even really know what he sounds like. But there is important, classified information that Alice needs and, despite all of these obstacles and dangerous risks, she refuses to give up. “A coding theorist is someone who doesn’t think Alice is crazy,” Gordon concludes.

“Today, nobody remembers I invented Strong Primes, but everyone knows me as the guy who wrote the story of Alice and Bob,” he would remark several years later.

Alice and Bob and Quantum Entanglement
In the 1990s, new theories of quantum communication and computation became an important topic in physics research. Given the topical overlap with cryptography and computer science more generally, physicists naturally adopted the use of Alice and Bob to demonstrate concepts of quantum entanglement and quantum teleportation.

Image from C.H. Bennett, Physics Today 48, 24 (1995).

In a 1999 Physical Review Letters paper by M.A. Nielsen, “Conditions for a class of entanglement transformations,” Bob and Alice share a quantum state (our old ket-friend |ψ⟩), which they want to transform into another shared state (|φ⟩). Nielsen asks: “Into what class of states |φ⟩ may |ψ⟩ be transformed, assuming that Alice and Bob may only use local operations on their respective systems, and unlimited two-way classical communication?”

The situation above is how Alice and Bob are usually referenced in many introductory quantum mechanics classes, demonstrated and explained in the video below:

Alice and Bob Have a Secret
Since their first introduction in 1978, Alice and Bob have remained a popular archetype across computer science, mathematics, and physics. They were born of efforts to try to make complex and difficult concepts more easily understandable. Forever enshrined in the Encyclopedia of Cryptography and Security and among countless scholarly publications (a full-text search for “Alice and Bob” on the arXiv produced a list of 326 papers), their lasting influence in science is certainly worth exploration. Alice and Bob continue to serve as a helpful reminder that humanizing scientific ideas is often an effective way to make them more accessible.