Post-quantum cryptography (PQC)

Post-quantum cryptography (PQC) is the development and study of cryptographic algorithms designed to remain secure against the computational power of quantum computers. Classical cryptographic systems like RSA and ECC (Elliptic Curve Cryptography) rely on problems like integer factorization and discrete logarithms, which can be efficiently solved by quantum algorithms such as Shorโ€™s algorithm. This could render traditional encryption methods insecure once practical quantum computers are built. PQC seeks to create algorithms that resist both classical and quantum attacks.

Key Concepts of Post-Quantum Cryptography:

  1. Quantum Threat:
    • Shorโ€™s algorithm, a quantum algorithm, can efficiently solve the mathematical problems underpinning most current public-key cryptography, threatening its security.
    • Symmetric encryption schemes (e.g., AES) are more resistant to quantum threats but would still require larger key sizes due to Groverโ€™s algorithm, which provides a quadratic speedup for brute-force attacks.
  2. Mathematical Foundations:
    • PQC algorithms are based on mathematical problems that remain hard for both classical and quantum computers. Some of the most promising approaches include:
      • Lattice-based cryptography: Relies on the hardness of problems like the Learning with Errors (LWE) and Ring-LWE, which are believed to be resistant to quantum attacks.
      • Code-based cryptography: Uses error-correcting codes, with schemes like McEliece considered resilient against quantum and classical attacks.
      • Hash-based cryptography: Relies on the security of cryptographic hash functions, as seen in the Sphincs+ algorithm.
      • Multivariate polynomial cryptography: Based on solving multivariate quadratic polynomial equations, which is believed to be hard for quantum computers.
  3. Hybrid Systems:
    • As a precaution during the transition to PQC, many systems are adopting hybrid cryptography, combining classical algorithms (e.g., RSA or ECC) with post-quantum schemes to maintain security in the face of quantum developments.

NIST Post-Quantum Standardization:

The National Institute of Standards and Technology (NIST) has been leading the global effort to standardize PQC algorithms. On August 13, 2024, NIST released the first three finalized post-quantum encryption standards. These standards are the result of a rigorous selection process aimed at ensuring the long-term security of data in a future where quantum computers are widely available.

The three finalized algorithms are:

  1. ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism): Based on the CRYSTALS-Kyber algorithm, designed for key encapsulation and secure encryption with efficient performance and small key sizesโ€‹.
  2. ML-DSA (Module-Lattice-Based Digital Signature Algorithm): Based on the CRYSTALS-Dilithium algorithm, used for digital signatures, providing both high security and computational efficiencyโ€‹.
  3. SLH-DSA (Stateless Hash-Based Digital Signature Algorithm): Based on the Sphincs+ algorithm, offering a hash-based signature scheme for additional diversity in cryptographic approachesโ€‹.

These PQC algorithms are expected to secure digital communications and infrastructure for decades, ensuring safety against both classical and quantum threats. The transition to these new standards will be critical for governments, industries, and individuals to protect sensitive data in the quantum era.

By introducing quantum-resistant algorithms, PQC provides the foundational security necessary for the future of cryptographic systems.

See more details on: