Alice and Bob, the ubiquitous characters in cryptography and quantum computing, have been guiding students and researchers through complex protocols since their introduction in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman. Originally conceived to explain the RSA encryption algorithm, these fictional personas have since become invaluable in illustrating a wide range of concepts in both classical and quantum information science.
In the realm of classical cryptography, Alice and Bob are often portrayed as two parties attempting to communicate securely over an insecure channel. Their adventures in symmetric key cryptography might involve sharing a secret key to encrypt and decrypt messages using algorithms like the Advanced Encryption Standard (AES). This process typically entails multiple rounds of substitution and permutation operations on blocks of data, with key sizes ranging from 128 to 256 bits.
When Alice and Bob venture into public key cryptography, they often employ the RSA algorithm. Here, Bob generates two large primes, p and q, and computes their product n and the value φ(n) = (p-1)(q-1). He then chooses a public exponent e and calculates a private exponent d such that ed ≡ 1 (mod φ(n)). Bob's public key becomes (n, e), while d serves as his private key. When Alice wants to send a message m to Bob, she computes the ciphertext c = m^e mod n. Upon receiving this, Bob can recover the original message by calculating m = c^d mod n.
Alice and Bob's cryptographic toolkit also includes digital signatures, which allow them to verify the authenticity and integrity of their communications. Using RSA for signing, Alice would compute s = m^d mod n (where d is her private key) to sign a message m. Bob can then verify the signature by calculating m' = s^e mod n (where e is Alice's public key) and checking if m' matches the original message m.
To establish a shared secret key over an insecure channel, Alice and Bob might employ the Diffie-Hellman key exchange protocol. They begin by agreeing on public parameters: a prime p and a generator g. Alice chooses a secret value a and sends A = g^a mod p to Bob, while Bob selects a secret b and sends B = g^b mod p to Alice. Both can then compute the shared secret K = g^ab mod p, which an eavesdropper cannot determine without solving the discrete logarithm problem.
As we transition to the quantum realm, Alice and Bob's adventures take on new dimensions. In Quantum Key Distribution (QKD), they leverage the principles of quantum mechanics to establish a secure key. The BB84 protocol, for instance, has Alice randomly choosing a bit value and a basis (rectilinear or diagonal) for each qubit she sends to Bob. Bob, in turn, randomly selects a basis to measure each received qubit. After their quantum exchange, Alice and Bob compare their chosen bases over a classical channel, retaining only the results where their bases matched. They then perform error estimation and privacy amplification on these bits to distill a secure key.
Quantum teleportation presents another fascinating scenario for our duo. Here, Alice aims to transmit the quantum state of a qubit |ψ⟩ = α|0⟩ + β|1⟩ to Bob using their shared entangled pair and classical communication. Alice performs a Bell measurement on her qubit and half of the entangled pair, then sends the two-bit result to Bob classically. Based on this information, Bob applies one of four unitary operations to his half of the entangled pair, thereby recreating the state |ψ⟩.
In the realm of superdense coding, Alice and Bob demonstrate how quantum entanglement can enhance classical communication. Starting with a shared entangled pair in the state |Φ+⟩ = (|00⟩ + |11⟩)/√2, Alice can encode two classical bits of information by applying one of four operations (I, X, Y, or Z) to her qubit. When Bob receives Alice's qubit and performs a Bell measurement on the pair, he can determine which of the four Bell states they are in, thus decoding Alice's two bits of information.
As quantum systems are inherently fragile, Alice and Bob must also contend with quantum error correction. A simple example is the three-qubit bit flip code, where Alice encodes a single qubit state |ψ⟩ = α|0⟩ + β|1⟩ as α|000⟩ + β|111⟩. If a single bit flip occurs during transmission, Bob can detect and correct it through a majority voting scheme.
The story of Alice and Bob continues to evolve, encompassing advanced concepts like the E91 protocol for QKD using entanglement, post-quantum cryptography to address the threat of quantum computers to classical systems, and even quantum Byzantine agreement protocols. As the field of quantum information science advances, Alice and Bob remain our steadfast guides, helping to elucidate complex ideas and protocols in both the classical and quantum domains.
