PQCToday

Post Quantum Resistant Algorithms

The recognition that quantum computers pose a threat to currently used cryptographic systems has led to numerous efforts to mitigate this threat. These efforts are primarily consolidated through standardization processes, which aim to specify algorithms capable of resisting quantum attacks, test their security and efficiency, and guide their implementation and integration into larger IT systems.

Post-quantum cryptography (PQC), also known as quantum-resistant cryptography, focuses on developing cryptosystems that are secure against both quantum and classical computers. PQC can be broadly categorized into five main families, each relying on different mathematical problems that are believed to be hard for both classical and quantum computers to solve:

Lattice-based Cryptography

Lattice-based cryptography is based on the difficulty of solving problems related to lattices, which are mathematical structures consisting of regularly spaced points in space. Lattice-based cryptography provides very competitive schemes with good performance regarding bandwidth and efficiency.

Examples: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON.

Code-based Cryptography

Code-based cryptography relies on the difficulty of decoding random linear codes. It is considered one of the most mature and well-understood approaches to PQC.

Example: Classic McEliece

Multivariate Cryptography

Multivariate cryptography is based on the difficulty of solving systems of multivariate polynomial equations.

Hash-based Cryptography

Hash-based cryptography relies on the security of cryptographic hash functions. It is considered a conservative choice for post-quantum security, and it has been standardized for specific applications with long lifespans, those that cannot wait for the main standardization process, and those that are impractical to update.

Examples: SPHINCS+, XMSS, LMS.

Isogeny-based Cryptography

Isogeny-based cryptography is a relatively new approach based on the difficulty of computing special maps between elliptic curves, known as isogenies. It typically suffers from expensive operations resulting in slower cryptographic schemes.

Standardized PQC Algorithms

The National Institute of Standards and Technology (NIST) has been at the forefront of standardizing PQC algorithms. As of November 2024, NIST has released three post-quantum cryptography standards:

• Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM): Based on the CRYSTALS-Kyber algorithm, ML-KEM provides a mechanism for securely exchanging cryptographic keys, which is fundamental for establishing secure communications.
• Module-Lattice-Based Digital Signature Algorithm (ML-DSA): Derived from CRYSTALS-Dilithium, ML-DSA provides a way to create digital signatures, ensuring the authenticity and integrity of digital documents and transactions.
• Stateless Hash-Based Signature Algorithm (SLH-DSA): This algorithm, based on the SPHINCS+ scheme, provides an alternative approach to digital signatures that doesn’t require maintaining state information, simplifying implementation and management.

In addition, two existing post-quantum signature schemes, LMS and XMSS(MT), which are stateful hash-based signature schemes, were standardized by NIST in 2020 in NIST SP 800-208. These are designed for specific applications that are long-lived, can't wait for the main standardization process, and are impractical to update in the field.

PQC Algorithms in Progress

NIST also has several algorithms still under consideration as part of its ongoing PQC standardization efforts:

• Fourth Round KEMs: NIST is evaluating additional KEMs to diversify the hardness assumptions at the core of post-quantum cryptographic schemes and provide more options for secure key exchange. Three algorithms, Classic McEliece, BIKE, and HQC, all based on error-correcting codes, are in this final round.
• Additional Digital Signature Schemes: To further diversify the underlying assumptions of digital signatures, NIST has opened an additional call for signature schemes.

Benefits of PQC

• Security in the Quantum Era: PQC algorithms offer protection against both classical and quantum computers, ensuring the long-term security of sensitive data.
• Maintaining Confidentiality and Integrity: PQC preserves the core functions of cryptography, enabling secure communication, data protection, and digital authentication.
• Standardization and Interoperability: Standardization efforts by organizations like NIST promote the development of interoperable PQC solutions, facilitating widespread adoption and seamless communication across different systems.

Challenges of PQC

• Performance Overhead: Some PQC algorithms can be computationally more intensive than classical algorithms, leading to performance overheads in certain applications.
• Implementation Complexity: Integrating PQC into existing systems can be complex, requiring significant effort in adapting protocols, updating software libraries, and potentially upgrading hardware.
• Key and Ciphertext Size: PQC algorithms often involve larger key and ciphertext sizes compared to classical algorithms, impacting storage and communication bandwidth requirements.
• Lack of Maturity: Some PQC algorithms are relatively new and haven't undergone the same extensive scrutiny as classical algorithms. This raises concerns about potential undiscovered vulnerabilities.

To address these challenges, the transition to PQC should prioritize cryptographic agility, enabling the seamless integration of new algorithms and standards, and the adoption of hybrid approaches that combine classical and post-quantum cryptography during the transition phase.