Quantum-resistant cryptographic algorithms
Synonyms: Post-quantum algorithms

  • Quantum-resistant (post-quantum) cryptographic algorithms are a family of asymmetric cryptographic algorithms, robust against classical and quantum computer attacks (quantum attacks);
  • The most common current asymmetric cryptographic algorithms, such as RSA, DSA, are not quantum-resistant, since there already exist efficient quantum algorithms (Shor's algorithm for factorization and discrete logarithm problems) able to analyze them. At the same time, symmetric cryptographic algorithms, such as block ciphers (AES) and hash functions (SHA-3), are less likely to be attacked by quantum computers. Although known quantum methods can make it potentially easier to analyze such algorithms, a complete analysis is still not feasible in the foreseeable future;
  • So, to make asymmetric cryptographic schemes quantum-resilient, one needs to turn to new classes of computationally complex problems, for example, lattice theory problems, error-correcting code theory problems, multivariate polynomial problems, cryptographic hash function problems etc.
More on the topic

Primary strategies for creating quantum-resistant algorithms include:
  • Lattice-based cryptography: shortest vector problem and its variations, learning with errors;
  • Code-based cryptography: decoding random code;
  • Multivariate cryptography: solving nonlinear systems of equations;
  • Hash-based cryptography: finding collision/ preimage/second preimage for cryptographic hash functions;
  • Supersingular isogeny-based cryptography: pathfinding in an isogeny graph.

«Exotic» problems:
  • search problem;
  • operations in braid groups;
  • octonion algebra;
  • Chebyshev polynomials.
    The finalists of the NIST post-quantum competition and the QApp's PQLR SDK library of quantum-resistant algorithms demonstrate how modern algorithm construction concepts are being implemented within specific cryptographic schemes.

    For example, some of the NIST finalists are based on lattice theory problems. These algorithms include CRYSTALS-KYBER, NTRU, SABER (implemented in PQLR SDK), CRYSTALS-DILITHIUM and FALCON, as well as alternate finalists, such as FrodoKEM and NTRU Prime.Coding theory problems ensure a considerable level of attack resistance in such algorithms as Classic McEliece (implemented in PQLR SDK) and alternate finalists, such as BIKE and HQC.

    Another finalist algorithm, Rainbow, along with the alternate finalist, GeMSS, is based on multivariate polynomials.

    Hash function-based algorithms receive great attention as well. For example, the finalist algorithm XMSS and the alternate finalist SPHINCS+ are already integrated into PQLR SDK. The QApp team is actively cooperating with the XMSS developers to substantiate the algorithm's cryptographic robustness. Our experts are also participating in the workgroup WG 2.5 "Post-quantum Cryptographic Mechanisms" of the Technical Committee for Standardization TC 26 "Cryptography and Security Mechanisms" standardizing the hash function-based digital signature schemes in Russia.

    The SIKE scheme, another NIST post-quantum competition finalist, is a supersingular isogeny-based algorithm.

    Finally, the only alternate finalist in the "exotic" category, the Picnic digital signature scheme, is based on zero-knowledge proofs. It is worth pointing out that of all 69 contestants, the algorithms belonging to this particular class were proven to be the least robust against attacks.

      How to implement post-quantum cryptography to protect your business data?

      Interested in using post-quantum cryptography? Explore our PQLR SDK library of quantum-resistant algorithms.

      Not only does the library help to implement post-quantum algorithms, but it also simplifies their integration process into existing data protection infrastructures. For this purpose, it includes a modified version of the OpenSSL library. Choosing it over the original OpenSSL ensures that applications can switch to post-quantum algorithms with minimal effort.

      Our library implements key distribution algorithms and digital signature algorithms based on various cryptographic schemes. When selecting and implementing certain algorithms, we rely on the opinion of international cryptography experts, on the experience of industry leaders and on our own performance assessment.