Round 3 of NIST Post-Quantum Contest Has Started

We are watching the standardization process closely at Wultra as we already work on making the PowerAuth authentication protocol quantum-safe. Let us share our comments about the progress of the NIST PQC contest.

Last week, NIST announced the round 3 of the contest for Post-Quantum cryptographic (PQC) algorithms. From 26 candidates in the second round, we are now down to just 7 third round finalists and 8 alternate candidates.

First of all, it is already clear that NIST does not aim to choose one “winner.” There are two categories in the competition: the public key encryption/KEMs, and digital signatures. So, there will be at least two selected candidates because of this.

We will not analyze digital signatures in this article because they are less important right now. The digital signatures can be made quantum-safe later on with additional signing. For example, you can use an LTV scheme to allow an easy signature upgrade. The key agreement, on the other hand, is critical right now. All traffic that uses classical encryption may be recorded today and decrypted once a large enough quantum computer is available, as discussed in our introductory article to PQC.

NIST also hinted that a 4th standardization round might revisit some of the alternate candidates. Clearly, some of the algorithms still need more research and work on performance optimizations. It seems that each round will aim to standardize different algorithms for different PQC families and potentially even different use cases.

Third Round Finalists

The 2nd round results for KEMs seem to imply that lattice-based cryptography, especially the Learning With Errors (LWE) category, is of particular interest for NIST because two algorithms were chosen for this category: CRYSTALS-KYBER and SABER. There are quite a few variants of the LWE problems — Ring learning with errors (RLWE), Module learning with errors (MLWE), and others. The issue with this family of algorithms, which is being discussed in recent papers, is that while the underlying problem is very solid in general, choosing the correct algorithm parameters for its particular instances may be tricky.

Another lattice-based candidate is NTRU, which is a good second candidate in case the LWE approach fails. Although the underlying mathematics was initially considered tricky from the security point of view, it has been around for almost 20 years, and so far, no major flaws have been found. Hopefully, NTRU’s security has been well researched, given that it has always been sort of an outsider.

Code-based cryptography is still in the game with Classic McEliece. The key sizes are very large (100kB — 1MB), making the algorithm a bit less practical, especially for key agreement over unstable networks. There were attempts to create lightweight variants of McEliece. However, they have failed to prove to be as secure as the classic variant with the Goppa code. The good thing about Classic McEliece is that it provides a fallback algorithm for the hopefully unlikely case everything else goes wrong.

Alternate Candidates

The most surprising change of events for us is that there are also so-called alternate candidates that are likely to reach standardization during round four. We are talking now about the timeframe beyond 2021 — perhaps 2022 or 2023. This makes us quite confident that unlike in the previous contests in which AES and SHA-3 were chosen, this contest will run for a lot longer, and there will likely be multiple successful candidates in each category.

From our point of view, this is really good news for new algorithms, such as SIKE (which is our favorite algorithm, by the way, due to its basis in EC cryptography). There is more time available for SIKE and other alternate candidates to gain the trust of security researchers. This also provides time for these alternate algorithms to improve performance. SIKE is right now an order of magnitude slower than other contestants, although the key sizes are among the smallest of all candidates, making it very practical for specific use cases where the key size matters.

We think that this turn of events also allows standardizing different algorithms for different use cases. Establishing a key agreement over a fast and reliable network is a much different scenario than some real-life situations where packets drop often and need to be resent in case of network errors. Furthermore, it may be non-trivial to embed algorithms with large key sizes into existing algorithms, such as TLS or SSH. You can review the experiments done by Cloudflare, Amazon, and Microsoft, which discuss these issues.

Next Steps for PowerAuth

We are working on extending our PowerAuth security scheme to support post-quantum algorithms for the key agreement. The announcement of the 3rd round by NIST has changed only one thing for us. We will take the extra steps to ensure that our scheme is not dependent on a particular algorithm. We will integrate both a 3rd round finalist and an alternate candidate from the fourth round (most likely, SIKE). This way, we will be ready to switch the algorithm based on the NIST contest results when the right time comes and choose a better algorithm for our use case, given that our software runs over mobile networks with varying reliability and speeds.

We will share more details in a future post once the PowerAuth PQC integration is available.

We prepared this post in close cooperation with the Cryptology and biometrics competence center of Raiffeisen Bank International (RBI) led by Tomáš Rosa. RBI is one of the few financial institutions with their own in-house theoretical research capabilities. As an innovator of the field, RBI actively examines the potential use of quantum computers and the application of post-quantum cryptography. Cooperation with the RBI competence center provides a solid background for educational posts like this one and practical implementations of proof-of-concept solutions.

As usual, feedback to this article is welcome. Let us know if you are already working on PQC migration or rather waiting for the NIST contest results. If you have any questions or feedback, please add a comment to this article or send us a message at hello@wultra.com.