The unbreakable man: How Gilles Brassard used the laws of physics to reinvent secrecy

Light cannot be secretly observed. Touch a photon and it changes; intercept it and it leaves a trace. For forty years, Gilles Brassard built his career on that fact, and this week the Association for Computing Machinery gave him the Turing Award, computing’s highest prize, for what he made of it.

Working with the physicist Charles Bennett, a physicist at IBM Research and co-recipient of the award, Brassard showed that this property of light could be turned into a lock whose security is guaranteed not by mathematics, but by physics itself. Their 1984 protocol, known as BB84, was the first provably secure method of exchanging an encryption key. Bennett and Brassard invented quantum cryptography, which, in the simplest possible terms, is a method of locking a secret so that the laws of physics themselves stand guard.

“What Charlie and I did was latch on to this gift from nature and turn it into a scheme for communication,” Brassard told IBM Think in an interview.

Brassard grew up in Montreal, obtained his doctorate in computer science from Cornell University in 1979, returned to the Canadian city, and has been at the Université de Montréal ever since, where he has held a full professorship since 1988 and a Canada Research Chair since 2001.

He is warm, slightly formal, fond of Bach and Mahler. He cooks. He goes to concerts in Amsterdam. The word he uses most often about his work is “fun.”

The idea for BB84 came from a paper. In 1976, while Brassard was still a doctoral student, his advisor, John Hopcroft, handed him a paper titled New Directions in Cryptography by Whitfield Diffie and Martin Hellman.

The paper proposed something that had never before appeared in the published scientific literature: that two strangers who shared no prior secrets could nonetheless conduct a private conversation, by exchanging information publicly and using mathematics to derive a shared secret that no eavesdropper could reconstruct.

For most of human history, secret communication required both parties to possess the same key in advance, a shared code that could be used to scramble a message and unscramble it again. The Spartan generals used physical ciphers. Julius Caesar used letter substitution.

During the Cold War, the hotline between Washington and Moscow was secured by keys printed onto physical tape and carried across the Atlantic by a diplomat in a briefcase handcuffed to his wrist. What Diffie and Hellman proposed was simpler and stranger: the idea that you could simply conjure a shared secret from nothing, using mathematics alone, was, in 1976, new.

“It was so very, very elegant that I dropped what I was doing essentially, and moved on to cryptography,” Brassard said. The paper’s approach, and the RSA cryptosystem that Ron Rivest, Adi Shamir and Leonard Adleman introduced the following year, became the foundation of the internet’s security architecture.

Every time someone shops online, logs into a bank or sends an email, one of these two systems is encrypting the connection in the background. Most users never think about this, which is roughly the state of affairs the systems were designed to produce.

Both systems rested on the same principle: that certain mathematical problems are so hard to reverse that solving them would take a conventional computer longer than the age of the universe. No one had proven they had to stay that way. They had simply never found a shortcut.

In 1994, a mathematician named Peter Shor at Bell Labs found the key. His algorithm demonstrated that a quantum computer, a device that exploits the counterintuitive behavior of particles at the subatomic scale to perform calculations in ways that conventional machines cannot, could factor large numbers efficiently. There was just one problem: quantum computers did not yet exist.

Most of the scientific community responded with the particular equanimity reserved for problems whose solutions remain hypothetical. The unease that remained found an unlikely home: the marginal territory between computer science and physics, where Brassard and Bennett met at a conference in Puerto Rico in 1979.

BB84 rests on a principle first articulated by Werner Heisenberg: in quantum mechanics, measuring a particle disturbs it. You cannot observe a quantum system without changing it, and that change is irreversible and unavoidable, unless you already possess information that tells you precisely how to measure it. In other words an eavesdropper who intercepts a quantum signal and tries to read it will leave a trace. The physics makes concealment impossible.

BB84 does not transmit messages through quantum channels. The quantum channel is used only to establish a shared secret key, a string of random bits known only to the two parties communicating. Once that key exists, it can be used to encrypt a message through entirely classical means. If an eavesdropper tries to intercept the quantum transmission, the disturbance is detectable, and the exchange begins again.

“The worst the enemy can do by eavesdropping is denial of service,” Brassard said. “The actual message will not be compromised, because it will remain with the sender.”

Nobody believed them at first. When Brassard and Bennett tried to publish an early version of their ideas in 1982, they submitted it to the Symposium on Theory of Computing, the flagship conference of the Association for Computing Machinery, the organization that just gave Brassard its highest prize. The paper was rejected.

“It’s ironic,” Brassard said, not without pleasure. “The ACM is giving us their top prize for what they rejected in 1982.”

Brassard considered the question of whether nature itself enforces privacy.

“You could say it that way,” he said. “The quantum world is inherently secret. And we exploit that.” He thought for a moment. “The past is gone. There is nothing anyone can do to save the past. All we can hope to do is secure the future.”