New Heights in Quantum Cryptography

I recently came across this article, which reports a successful attempt to establish a quantum communication channel over a record distance of 144 km. I take this as a good indication that quantum cryptography may soon become practical, improving everyone's security and privacy. Of course, we should still be weary of borked implementations.

As you may already know, having a pair of entangled particles, one's state can be inferred just by observing the other's. Alas, this by itself is not useful for transmitting information, as the end points cannot decide what said state is (a no-communication theorem can be proved). We need to be a bit more creative.

During World War II, Claude Shannon proved that in order for a cipher to have perfect secrecy, the key needs to be at least as long as the plaintext. (His work was declassified only after the war, in 1949—even then, by mistake.) Although keys can sometimes be exchanged in advance, this is generally considered impractical because if two parties have a way of securely exchanging such large keys they should probably use it to exchange the messages instead.

It turns out that such a secure cipher had already been invented in 1882, when Frank Miller came up with the OTP (one-time pad), which is a symmetric-key algorithm that performs a bit-wise xor (exclusive or) operation on the plaintext and key (that is, E(k, m) = m ⊕ k and D(k, c) = c ⊕ k). However, as Joseph Mauborgne later realized, reusing keys in whole or in part, results in ciphertexts susceptible to attacks (because E(k, m₁) ⊕ E(k, m₂) = m₁ ⊕ m₂, on which a number of attacks are possible). Although incepted much later, this is one of the vulnerabilities of WEP (Wired Equivalent Privacy).

	⊕		=
				⊕
	⊕		=
				=

(As an aside, I was taken slightly aback by learning that the symbol for the xor operation has not been standardized by ISO 80000-2.)

Unfortunately, the OTP had been forgotten until 2011, when Steven Bellovin found it in an old telegraph codebook. It was only in 1919, over three and a half decades after Miller's original invention, that Gilbert Vernam issued a patent that used a very similar idea. Vernam ciphers, like the aforementioned WEP, lie at the intersection of stream ciphers and the OTP: the only difference between them and the latter is that their plaintext-sized keystream is generated by a PRNG (pseudorandom number generator), where the seed is usually a password. Due to the fact that the seed is almost always very small compared to the message, the key space is almost always much smaller than the message space. Thus, stream ciphers strive for semantic security rather than perfect secrecy.

Vernam's proposed implementation.

The exact definition of semantic security, as introduced by Shafi Goldwasser and Silvio Micali, is a bit convoluted so I won't go into it here further than to say that, knowing some bits of the key, adversaries must be unable to guess in polynomial time what any of the other ones are, with a probability greater than 1/2 + ϵ, where ϵ is a negligible value. To achieve this, a special class of PRNG's, known as CSPRNG's (cryprographically secure PRNG's), must be employed. The definition of CSPRNG security is even more flaky, given that it is based on our guess of the lack of efficient adversaries, whose nonexistence we have yet to prove.

Note that nothing in the above paragraph is specific to stream ciphers, as all classical, elliptic, and hyperelliptic curve cryptography is based on the idea that adversaries must be able to solve a hard problem, such as factorization, in order to beat a semantically secure cipher. If we took out the requirement for efficiency, the hypothesis would become unsatisfiable (unlike your mom). Moreover, a proof that efficient CSPRNG adversaries exist would be quite surprising, as it would imply that P = NP (P vs NP, originally posed by Kurt Gödel in a letter to John von Neumann but introduced independently to the world by Stephen Cook in 1971, is the most important open problem in theoretical computer science; it's one of the Millenium Prize Problems).

Courtesy of Randall Munroe.

Quantum entanglement is so seductive for our purposes because of QKD (quantum key distribution): it allows establishing secure communication channels for transmitting large keys, meaning that we can switch from semantic security to perfect secrecy. As for keystream generation, quantum mechanics also helps us make the shift from PRNG's to RNG's. Furthermore, eavesdropping implies measuring the system and thus disturbing it, as per Heisenberg's uncertainty principle. A minor downside is that both parties will have to simultaneously be online.

I'd like to end this post with the observation that a system is like a chain: as secure as its weakest link. Current cryptographic constructions are typically the strongest link. This begs the question: Is there more to quantum cryptography than just the intellectual appeal? I will try to make a case for this in a future post.