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.
- 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.