request@qapp.tech
RU
NIST post-quantum competition

Summary

The NIST Post-Quantum Cryptography Program (further referred to as "the NIST post-quantum competition") was organized by the US National Institute of Standards and Technology (NIST) to standardize a set of quantum-resistant cryptographic key encapsulation and digital signature schemes. The competition was launched in 2017 and is currently in its third stage. Out of 69 candidate algorithms submitted by developers worldwide, the NIST experts have selected seven finalist algorithms and eight alternate finalist algorithms that could potentially be standardized. Based on the similar competitions previously organized by the NIST for block ciphers (AES) and hash functions (SHA-3), the standardization process for quantum-resistant algorithms could be completed in 2022.

    More on the topic

    Since Shor's algorithms for factorization and discrete logarithm problems were published in 1994-1995, the quantum threat has become a major concern both for developers and users of cryptographic security products: the most popular asymmetric encryption and digital signature schemes, including RSA, DSA, would become vulnerable if a quantum computer of sufficient power appeared.

    In 2017 research of quantum-resistant cryptographic schemes was given a new boost by the US National Institute of Standards and Technology (NIST), which organized an open international competition for standardization of post-quantum cryptographic schemes.

    Candidate algorithms submitted to NIST implement key encapsulation and digital signatures. These mechanisms have to meet certain robustness requirements, both theoretical (formally provable) and practical (there several levels of robustness against all known quantum and classical attacks defined). Another important criterion is that the proposed algorithms are practically applicable.

    The algorithms are both internally reviewed by the NIST staff and openly validated by cryptographers around the world. The review results are published for discussion on the NIST website and distributed in a public mailing list.
    Competition progress

    The call for proposal was closed on November 30, 2017. A total of 69 submitted algorithms were accepted, 14 of which were either withdrawn or hacked already in the first round.

    Contestant algorithms are primarily based on:
    • lattice-based cryptography
    • error-correcting codes
    • hash-based cryptography
    • supersingular isogeny-based cryptography
    • "exotic" problems, such as the search problem, braid groups, octonion algebra, Chebyshev polynomials etc.
    On January 30, 2019, NIST published a list of 26 candidate algorithms, which had made it to the second round of the competition. The NIST experts did not explicitly prefer certain algorithm classes over the others; only "exotic" schemes, which often turned out to be the least robust, were excluded.

    Before the next deadline on March 15, 2019, developers had to iron out all the remaining kinks in their schemes.

    In July 2020, NIST launched the third round of the competition. It will last 12 to 18 months before the final list of algorithms up for international standardization is revealed. Fifteen algorithms, including eight alternate ones, made it to the third round.
    The mere existence of the NIST competition has had a significant impact on the development of new quantum-resistant cryptographic schemes. Over the past two rounds, the NIST experts and members of the international cryptographic community have analyzed more than 80 candidate algorithms.
    QApp is actively involved in the international standardization of quantum-resistant algorithms

    The QApp team is actively keeping up with the NIST post-quantum competition. Each algorithm is analyzed and validated by our experts. It allows us to:
    • proactively integrate the most promising algorithms from the NIST list into the existing QApp products;
    • report bugs in contestant algorithms and suggest improvements to NIST and the international cryptographic community.
    For example, the QApp team has reported a security proof flaw in the SPHINCS+ signature algorithm and is currently working with its developers to fix it.