US standardization authority NIST has published the algorithms that participate in the Post-Quantum Crypto Competition. No fewer than 69 crypto systems enter the race.
In spring 2016, the US standardisation authority NIST announced a competetion. The goal was to find one or several asymmetric crypto algorithms that were secure against quantum computers. cryptographers had time until November 30, 2017, to hand in algorithms.
Now NIST has published the candidates. No fewer than 69 crypto systems have entered the race – more than ever before in a crypto algorithm contest.
The post-quantum competition is the fourth cryptographic “beauty contest” organized by the NIST. The previous three were milestones in crypto history.
The first NIST (then named NBS) competition took place in the early 1970s, when experts realized that the computer industry needed a suitable encryption method. The NBS thereupon solicited algorithm proposals in order to choose the best one. There were candidates, but none of them proved useful. Only after a restart of the competition a winner could be declared: Lucifer, an algorithm developped by IBM. After a few design changes, Lucifer became the Data Encryption Standard (DES). To date, the DES is considered the mother of all modern encryption algorithms.
Two decades later, NIST needed a DES successor. So, a new competition was started. 15 teams answered the call and handed in algorithms that underwent a year-long evaluation process consisting of several rounds. Cryptologists in all the world discussed design philosophies, vulnerabilities and encryption speeds of these ciphers with great enthusiasm. In 2000, the NIST finally chose the Belgian algorithm Rijndael as the winner. Rijndael has since become known as the Advanced Encryption Standard (AES) and today is by far the most important symmetric encryption algorithm.
In 2006, NIST launched its third crypto contest. This time, it was not about an encryption algorithm, but about a cryptographic hash function, which was to be named SHA-3. If the AES competition was a cryptologic feast, the SHA-3 competition was a cryptologic orgy. There were no fewer than 64 submissions. This meant that more cryptographic hash functions were developped for this competition than had existed in the entire history of cryptography before.
Again, there were a lot of new design ideas that went into the proposals. Countless discussions about the pros and cons of the candidate functions kept cryptologists in all the world busy. In the end, the hash function Keccak turned out to be the best design. Keccak was standardized as SHA-3.
The post-quantum competition
With the recent publication of the candidate algorithms, the fourth crypto algorithm competition organized by the NIST has reached the evaluation phase. The goal is to find one or several algorithms that are secure against quantum computers. In contrast to the three earlier competitions, more than one winner is desired – for instance, a key exchange algorithm and a signature algorithm.
A quantum computer is a machine that exploits quantum mechanical phenomena to solve mathematical problems that are difficult or intractable for conventional computers. So far, quantum computers are more Science Fiction than reality. It is not even clear if it will ever be possible to build quantum computers that are powerful enough to do a real job.
Virtually all asymmetric crypto systems currently in use (including RSA, Diffie-Hellman, and DSA) are not secure against quantum computers. This means that if large-scale quantum computers are available one day, thousands of crypto products will become as good as useless. The purpose of the competition is to establish a number of quantum-secure crypto systems before quantum computing becomes reality.
NIST now faces the difficult task of selecting a few algorithms that will be declared new US standards – in an evaluation process lasting several years. It is expected that many state authorities, companies and standardisation bodies worldwide will join this selection.
The list of candidate algorithms is available on a website operated by the NIST. In addition, I have created my own post-quantum competition website. Here it is:
Of course, this page is still under construction. My plan is to fill it with more and more information about the algorithms. It would be great if my readers could help me with this task. So, if you have any comments about the candidate algorithms, please let me know.
Further reading: New book about unsolved cryptograms