| Each week Quanta Magazine brings you an update on one of the most important ideas driving modern research. This week, computer science staff writer Ben Brubaker describes how cryptographers have discovered new kinds of encryption over the past 50 years. | | There's More Than One Way to Encrypt a Secret By BEN BRUBAKER | | Say you want to send a private message to a friend, but you're worried that it might fall into the wrong hands. How do you ensure that your message will remain secret even if it gets intercepted? That's the oldest question in cryptography, the mathematical study of codes for safeguarding secrets.
From antiquity all the way to the 1970s, cryptographic techniques grew ever more sophisticated, but one underlying assumption went unquestioned: Two people who want to communicate privately must first agree on a secret key for encrypting and decrypting messages, and that step must happen confidentially in person. Otherwise, the message containing the key might itself be intercepted, and then all future communications will be easy to decipher.
That's a reasonable assumption, but it's wholly inadequate to the demands of our hyperconnected age. The New York University cryptographer Oded Regev summed it up succinctly when I interviewed him last year. "We don't physically go to Google and get some secret key," he said. "Yet each time I connect to Gmail, it's secure communication."
How is that possible? It all goes back to a revolutionary idea called public-key cryptography.
Instead of a single secret key, public-key encryption methods use a pair of keys with a special mathematical relationship: A message encrypted using one of them can only be decrypted using the other. That makes it possible to send a secret message to someone you've never met. Not only that, you can prove that the message really came from you.
In the late 1970s, cryptographers developed the first public-key encryption methods and proved that there's no way to break the codes without solving notoriously difficult math problems, such as decomposing enormous numbers into their prime factors. It was the first sign that the landscape of cryptographic possibility was far richer than anyone had ever imagined.
As groundbreaking as it was, public-key cryptography still dealt with the same basic problem that cryptographers had studied for centuries: how to share secret information selectively. But in the 1980s, researchers started realizing that there was more to cryptography than that. Since then, they have devised many other ways to protect secret information that go far beyond secure communication.
What's New and Noteworthy
Let's say you want to prove to a friend that you've solved a puzzle without spoiling the solution. In 1985, the cryptographers Shafi Goldwasser, Silvio Micali and Charles Rackoff showed that this was possible using a new, strikingly simple cryptographic protocol called a zero-knowledge proof. In a 2022 explainer for Quanta, Sheon Han described how these proofs work and how researchers in computer science and other fields have continued to find new uses for them.
Cryptography researchers have studied many other problems that involve keeping information completely secret, like fetching data from a public database without revealing anything about where you looked. Just last year, three of them proved that this sort of "private information retrieval" really is possible.
Cryptographers' ambitions even extend beyond protecting data sets — they've also studied ways to conceal the inner workings of computer programs. In 2020, after nearly a decade of false starts, a team of cryptographers finally developed a secure encryption scheme called indistinguishability obfuscation, which makes it impossible to tell apart different programs that perform the same task.
Innovations in cryptography often begin with mathematical constructions that would be unwieldy to put into practice. That's the current status of the private information retrieval and indistinguishability obfuscation methods that researchers developed in the past several years. But in cryptography, theoretical inventions rarely remain purely theoretical for long. And they've found unexpected applications to problems in other areas of computer science, from the security of neural networks to the intrinsic difficulty of computational problems. | | | The Numberphile channel on YouTube released a playful video explainer about public-key cryptography featuring Ron Rivest, a pioneering cryptographer who helped develop one of the most widely used public-key encryption methods in 1978. | | | Stanford Magazine published a fascinating retrospective on the fraught relationship between academic researchers and the National Security Administration in the years that followed the invention of public-key cryptography. | | | Communications of the Association for Computing Machinery published an entertaining nontechnical article exploring different strategies that two people can use to determine whether they both know the same piece of secret information without giving it away. | | | | | | |
