The National Institute of Standards and Technology (NIST), which is part of the US Department of Commerce, recently released a Report on Post-Quantum Cryptography. In the report, they review the threat posed by quantum computers on today’s most popular cryptography and review the possible quantum-resistant solutions.
For those of you unfamiliar with the quantum computing threat on cryptography, check out some blogs I've written on the subject. In short, the threat can be summed up by this table from the NIST report.
As you can see, all of the popular encryption and signing solutions today are impacted by quantum computing. Symmetric algorithms and hash functions are weakened, but not broken by quantum computers. Unfortunately, the most commonly used asymmetric algorithms, RSA and ECC, are "no longer secure" once large-scale quantum computers arrive.
The next logical question is when will large-scale quantum computers be available? Nobody knows for sure, but the most common estimate from experts is about 10 years. But it takes years to change the crypto infrastructure, which is why NIST is warning companies now. There is also the threat of Harvest then Decrypt attacks in which your communications are stored today and broken when quantum computers arrive. This is not an issue that can be put off.
There are several quantum-resistant solutions that are available today. NIST gave a brief review of each family of solutions. I summarize their findings below.
Lattice-based cryptography
Most lattice-based algorithms are relatively simple and efficient, but it is difficult to precisely estimate the security of lattice schemes.
Code-based cryptography
While quite fast, most code-based primitives suffer from having very large key sizes. Newer variants to reduce the key sizes have led to successful attacks.
Multivariate polynomial cryptography
Several multivariate cryptosystems have been proposed over the past few decades, with many having been broken. Multivariate cryptography has historically been more successful as an approach to signatures rather than key exchange.
Hash-based signatures
Many hash-based signatures require the signer to keep a record of the exact number of previously signed messages, and any error in this record will result in insecurity. Another drawback is that they can produce only a limited number of signatures or the signature size must increase.
Other
A variety of systems have been proposed which do not fall into the above families, such as evaluating isogenies on supersingular elliptic curves have not had enough analysis to have much confidence in their security.
It is clear from this summary that NIST prefers Lattice-based solutions more than the other solutions, although they are not ready to declare a winner without a lot more research. However, a few years ago, NIST published a paper called Quantum Resistant Public Key Cryptography: A Survey in which they stated “Of the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical.” Lattice-based crypto appears to be the best solution to quantum computing attacks and NTRU is the best of the lattice-based solutions. As owners of NTRU patents, Security Innovation is in an enviable position, although many companies will wait until it is too late to seek our help.
