Exchanges of digital information have long been protected by public-key cryptography, which lets senders encrypt their data with confidence that only the intended recipient could decrypt and read it. The recipient can freely share their public key for encryption because deducing the private key for decryption would require an impractically large calculation, such as factoring the product of two very large primes.
In the 1990s, however, mathematician Peter Shor (then at Bell Labs and successor AT&T Research, now at the Massachusetts Institute of Technology (MIT)), showed quantum computers could do factoring and compute “discrete logarithms” exponentially faster, greatly stimulating research in quantum computing. Despite billions of dollars of investment and significant experimental progress, however, quantum computers are still too small and error-prone to pose a cryptographic threat—yet. If they do succeed at scale, though, both new data and encrypted archives could become vulnerable to snooping.
To address this possibility, the U.S. National Institute of Standards and Technology (NIST) has been evaluating proposals for “post-quantum cryptography” (PQC). Although it is now clear that quantum computers can solve some large problems much faster than classical computers ever could, the hope is that there are other cryptographic schemes that are forever beyond their easy reach.
Hybrid Systems
The security risks are real, but they do not directly threaten the vast majority of encrypted data. “There is no quantum problem with bulk encryption,” said security technologist Bruce Schneier. Most data is encrypted using symmetric algorithms, such as the Advanced Encryption Standard (AES), which uses the same key for decryption. As long as the sender and recipient can keep this shared key secret, this computationally efficient scheme works fine. A second quantum algorithm developed in the 1990s by Lov Grover (then also at Bell Labs) can crack symmetric encryption faster than classical computing, but “the best you can do in speeding up this computation with a quantum computer … is by a factor of a square root,” Schneier said, so an attack can be defeated with modestly longer keys.
The challenge is securely establishing the shared key. Key distribution once used methods like a secure channel or physical exchange, but these are cumbersome for everyday use. (Quantum key distribution could detect any eavesdropping, but the demanding technology is unlikely to matter for commercial purposes.)
The situation changed with the 1976 work of Whitfield Diffie and Martin Hellman (who shared ACM’s A.M. Turing Award in 2015), which described how two parties can share a secret without exposing it. The scheme exploits mathematical groups, such as elliptic curves, that support a multiplication operation. The parties agree on a starting point, then each applies a private multiplier and passes the result to the other, who then applies their own private multiplier. In this way they compute the same secret key, but the intermediate results can be sent in the clear without revealing it.
Although the multiplications are relatively easy, the scheme’s security hinges on the exponential difficulty of reversing the calculation. A quantum computer, however, could do it much faster using Shor’s algorithm, then use the result to decrypt bulk data encrypted with a symmetric algorithm.
Not a Competition
NIST began preparing its program in 2011, said Lily Chen, a mathematician who is group manager of the cryptographic technology group, and began requesting PQC proposals in 2016. In addition to public-key protocols, the project solicited algorithms for digital signatures, which are used in key establishment, signing documents, and software source verification.
To conserve its own resources and the critical attention of the community, NIST narrowed 69 first-round submissions to 26 candidates for the second round, and then to seven finalists and eight alternative candidates for the third round. European collaborators are heavily represented in the proposals.
Selection assessed not only classical and quantum security, but also performance requirements such as processing power and key size, as well as side-channel resistance, Chen said. In addition, she said, “We wanted candidates from different categories,” so the list included lattice-based, code-based, hash-based, multivariate-quadratic, and isogeny-based algorithms.
“Without the community we cannot do this work,” Chen said, adding that open public review will be critical to the project’s success. “There are not many people who understand the deep mathematics theory and also the cryptography to attack it.”
In July 2022, NIST announced four finalists for their standards—CRYSTALS-Kyber for encryption and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for digital signatures. NIST also chose several additional candidates for further consideration. The agency expects to release a formal standard in 2024.
Classical Elimination
Despite the lengthy evaluation, some of the successful candidates have only recently been discovered to be vulnerable to classical attack. The multivariate public-key system Rainbow, for example, had been expected to join the ranks of digital signature algorithms. In March 2022, however, Rainbow was completely broken “over the weekend on a laptop,” by Ward Buellens of IBM Research in Zurich, Switzerland.
Another proposal, called SIKE (for supersingular isogeny key encapsulation), had been in the further-study list for encryption. However, just weeks after the NIST announcement, Wouter Castryck and Thomas Decru, mathematicians at KU Leuven in Belgium, demonstrated how to crack it “in about one hour on a single core.”
“There are not many people who understand the deep mathematics theory and also the cryptography to attack it.”
The SIKE algorithm extends the Diffie-Hellman protocol. Rather than sender and receiver multiplying points on an elliptic curve by secret scalars, they perform a secret sequence of transformations (isogenies) on an entire elliptic curve. Unfortunately, clearly specifying this more-abstract process required exchanging some auxiliary data.
This is “a very nice trick actually, but also a trick that has been concerning already from the start” said Castryck, which led to it receiving only probationary approval for the fourth round. The extra information “was also the key ingredient in the attack,” Castryck said. “I think NIST handled it correctly,” he said, “but indeed, it makes you wonder whether you are standardizing things too quickly.”
“It’s a really good reminder to the community that these kinds of things can happen and do happen,” said Peter Schwabe of the Max Planck Institute for Security and Privacy in Bochum, Germany, and Radboud University in Nijmegen, the Netherlands. “Somebody proposes something, and then many, many smart people look at it for a very long time and fail to break it,” said Schwabe, who is a member of the CRYSTALS team. “Ideally, they fail to break it publicly, and describe how they failed breaking it, and then we gain trust in that system.”
Long Learning Process
However, “With the exception of hash-based signatures, the schemes that are being standardized now, and also the schemes that are still in round four of the competition, none of them have been studied to the same extent that, say, elliptic-curve crypto has that we’re using today,” Schwabe said.
Quantum attacks are even harder to assess, since “We don’t really know yet what quantum computers can do,” Schwabe said. Researchers have convincingly established that problems exist that quantum computers can solve with polynomial resources, but which will always require exponential resources for classical computers. Google and others have demonstrated “quantum advantage” (originally called “quantum superiority”) on selected problems even with today’s research machines.
The goal of PQC, though, is practical algorithms that will assuredly require exponential resources even with a full-scale, error-corrected quantum computer. Indeed, a 2011 paper from Scott Aaronson (then at MIT, now at the University of Texas at Austin) and Andris Ambainis of the University of Latvia argued that exponential speedup could be achieved “only for certain ‘structured’ problems.” For example, Shor’s algorithm tackles factoring and discrete logarithms by identifying periodicity in the states of many quantum bits (qubits) at once. In April 2022, however, Takashi Yamakawa of the NTT Social Informatics Laboratories, and Mark Zhandry of NTT Research and Princeton University, conjectured that “structure” is not actually needed for exponential speedup for search problems (unlike the decision problems discussed by Aaronson and Ambainis). This represents the first major expansion of the scope of efficient quantum algorithms since the 1990s.
“It doesn’t immediately say anything about whether there’s classical attacks or quantum attacks on anything at this stage,” Zhandry cautioned, but “It shows that there are potentially more problems where there is a quantum advantage relative to classical algorithms than there were previously.” More importantly he said, even if an algorithm’s security against classical attacks has been demonstrated, “Things will not be fine, necessarily,” for quantum attacks.
Establishing Trust
Schwabe noted there was “overwhelming evidence” the U.S. National Security Agency (NSA) had subverted protocols to retain some access for themselves, but with NIST’s earlier competitions involving AES and Secure Hash Algorithm 3 (SHA-3), “They gained a really good reputation,” he said. Today, “I would find it extremely hard to imagine that in any of the schemes there would be the kind of back door where only the NSA can decrypt,” or that they would promote weakened protocols.
“I would find it extremely hard to imagine that in any of the schemes there would be the kind of back door where only the NSA can decrypt.”
“NIST needs transparency if their standard is going to be used at all,” Schneier agreed. “I think NIST is a trustable honest broker.” However, “because you see things being broken left and right,” he emphasized that future systems should be agile, letting users easily swap out broken protocols in the same way they might change the lock on a front door.
Further Reading
National Institute of Standards and Technology Computer Security Resource Center, Selected Algorithms for NIST Program on Post-Quantum Cryptography, https://bit.ly/3SpCyvg
Shor, P.W.
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Sci. Statist. Comput. 26 (1997) 1484. arxiv.org/abs/quant-ph/9508027
Grover, Lov K.
A fast quantum mechanical algorithm for database search, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC ’96. Association for Computing Machinery: 212–219. arXiv:quant-ph/9605043
Aaronson, S. and Ambainis, A.
The Need for Structure in Quantum Speedups, Proceedings of ICS (Innovations in Computer Science) 2011. arxiv.org/abs/0911.0996.
Yamakawa, T. and Zhandry, M.
Verifiable Quantum Advantage without Structure, (2022). arxiv.org/abs/2204.02063
Join the Discussion (0)
Become a Member or Sign In to Post a Comment