During the 10th Heidelberg Laureate Forum last week, I had the opportunity to interview several of the laureates to hear their perspectives on current and future challenges in computing. Two of these laureates that I was fortunate enough to sit down with were Dr. Avi Wigderson and Dr. Yael Tauman Kalai (short bios are at the end of this blog).
With access to two leading experts in cryptography, I asked them both about the new era of cryptography we are entering, post-quantum cryptography (PQC).
RSA encryption, the most commonly used form of encryption today, was invented in 1977 by Ron Rivet, Adi Shamir, and Leonard Adleman at MIT. The security of this form of cryptography relies on the mathematical complexity of finding the prime factors of very large numbers (numbers which are 2048 bits long, or 617 digits). To give some context, it would take a classical computer 300 trillion years to break RSA encryption. In 1994 however, Peter Shor, a professor of applied mathematics at MIT, developed Shor’s algorithm, a quantum algorithm which, in theory, can find the prime factors of an integer much more quickly than a classical computer could. By much more quickly, I mean rather than taking 300 trillion years to break RSA encryption, it would take a quantum computer only 10 seconds.
Quantum computers, however, are still in their infancy. Most experts estimate that it will take at least several decades before we approach a quantum computer capable of performing Shor’s algorithm. But the advance in capability of quantum computers is not cryptographers’ only concern.
I asked Professor Wigderson about this shift to post-quantum secure algorithms, and he first turned my attention to a more pressing problem:
“First of all, you need to know, even today, that you are not protected against attacks by classical computers, because we don’t know that breaking RSA [encryption] is difficult, we just assume it. You have to realize that somebody tomorrow may find an algorithm to factor integers… A major problem in my field is proving that these problems are hard [to solve]. We don’t know how to do that yet despite many decades … this is something I have spent many, many years on and still am.”
Professor Kalai agreed that we have no proof that breaking RSA encryption is difficult, and she went even further, saying, “Actually, if anything we have evidence that it is not hard, because quantum computers can do it”, according to Shor’s algorithm. Dr. Kalai continued, “All modern cryptography is based upon unproven assumptions, so it is very important to be ready in case one of them is broken”.
Researchers are not waiting for quantum computers to catch up to encryption algorithms. New methods of encryption which are resistant to cryptanalytic attacks by quantum computers have already been developed, and companies and governments are already moving towards adopting them. The US Department of Commerce’s National Institute of Standards and Technology (NIST) is already implementing 4 new quantum resistant algorithms, with plans to be fully implemented by 2024.
Dr. Avi Wigderson, the Herbert H. Maass Professor of Mathematics at the Institute for Advanced Study in Princeton, New Jersey is recognized as a laureate for not one, but two of the most prestigious awards in mathematics and computer science. Professor Wigderson was awarded the IMU Abacus award (formerly known as the Nevanlinna award) in 1994 for his work on computational complexity and the Abel prize in 2021, along with Laszlo Lovasz, for their work in theoretical computer science and discrete mathematics.
Dr. Yael Tauman Kalai is a Senior Principal Researcher at Microsoft Research and an adjunct professor at the Massachusetts Institute of Technology. Dr. Kalai was awarded the ACM Prize in Computing in 2022 for her pioneering work in cryptography, including eliminating interaction in cryptographic proofs and thereby increasing their efficiency significantly. These more efficient cryptographic proofs, also known as “succinct proofs”, have been implemented by several blockchain companies, including Ethereum.
If you are interested in learning more about post-quantum cryptography and the difficulties associated with making the transition from cryptosystems based on integer factorization and discrete logarithm problems to quantum-secure algorithms, please check out the CCC report on PQC Migration and Cryptographic Agility. Also, the CCC recently held the 5 Year Update to the Next Steps in Quantum Computing workshop, which focused on quantum computing hardware and the next steps in its advancement. The CCC plans to release this workshop report by the end of the year, so stay tuned.
