Google quantum chip
The National Institute of Standards and Technology (NIST) announced this week it's selected 26 out of the original 69 submitted post-quantum cryptographic algorithms that are supposed to resist attacks from future quantum computers. Quantum computers are currently predicted to break most of the existing encryption algorithms used to secure communications, such as RSA, ECC, DH and even AES.
Cryptography combines encryption and decryption. Contrary to popular belief, you don’t need encryption powered by quantum computing systems to protect against other quantum computers trying to break that encryption. There are other forms of cryptography that are supposed to be 'resistant' to quantum computers. Google, for instance, has already been experimenting with one such algorithm in Chrome. However, Google will likely end up implementing one of the standards approved by NIST.
Back in 2016, NIST started the competition for the standardization of post-quantum cryptographic algorithms. A total of 69 algorithms were submitted, and the agency has now selected 26 to go into the second round of standardization.
NIST selected this unusually high number of candidate algorithms compared to other similar competitions for two primary reasons. One is that post-quantum cryptography is radically different than what we’ve been used to so far in terms of cryptography.
The second is that we don’t know how well any of them will work in practice, and with a large portion of the submitted candidates having already shown vulnerability, NIST can’t afford to be too picky early in the process.
NIST has also encouraged the entrants to merge the algorithms similar to each other if the security of either can be improved by doing so.
Focusing on Performance Over Security
NIST has encouraged participants to focus on the performance of their algorithms over the next 12-18 months, before the next round begins.
Due to the rise of the Internet of Things (IoT), NIST has lately focused on “lightweight cryptography,” which can also be read as 'weaker cryptography.' The idea is that IoT devices don’t have enough processing power and that it’s too expensive to add a crypto-processor to each one of them.
Therefore, NIST would like device makers to implement weaker cryptography algorithms that have better performance on IoT devices compared to the type of cryptography you may see PCs or smartphones use.
The NSA has recently and controversially tried to standardize two such lightweight algorithms that Google also wanted to implement for low-performance Android devices. However, after outcry from the Android community, Google learned that regular cryptographic algorithms can be made to have just as high or higher performance than the lightweight algorithms promoted by the NSA.
NIST itself has also been in controversy post-Snowden revelations, in which it was discovered that NIST standardized an obviously backdoored algorithm also promoted by the NSA at the time.
NIST would now like the post-quantum algorithm submitters to also focus on lightweight algorithms over the ones that may have better security. The argument is not completely without merit this time because most, if not all, post-quantum algorithms, tend to have high processing requirements, have multi-megabyte key sizes requiring high bandwidth systems and so on.
The biggest obstacle to post-quantum cryptography adoption will likely be the high processing power requirements.
The Candidates' Algorithms
Most of the 26 candidates can be classified into three different cryptographic families: lattice, code-based and multivariate. NIST is looking for two types of algorithms based on how they will be used: public-key encryption and key-establishment algorithms, as well as digital signature algorithms.
The 17 public-key encryption and key-establishment algorithms that entered the second round of the post-quantum cryptography standardization competition are:
- Classic McEliece
- LEDAcrypt (merger of LEDAkem/LEDApkc)
- NTRU (merger of NTRUEncrypt/NTRU-HRSS-KEM)
- NTRU Prime
- ROLLO (merger of LAKE/LOCKER/Ouroboros-R)
- Round5 (merger of Hila5/Round2)
- Three Bears
The candidates for post-quantum digital signatures are: