11.4 Post-quantum cryptography

Quantum computing poses a significant threat to current cryptographic systems. Post-quantum cryptography aims to develop algorithms resistant to both classical and quantum attacks, ensuring long-term security for sensitive data and communications.

Various approaches to post-quantum cryptography exist, including lattice-based, code-based, and multivariate cryptography. Each method has its own strengths and trade-offs, balancing security, performance, and practical constraints like key sizes and computational requirements.

Introduction to Post-Quantum Cryptography

Impact of quantum computing on cryptography

• Quantum computing threatens the security of classical cryptographic algorithms
  • Shor's algorithm efficiently factors large numbers and solves discrete logarithms (RSA, Elliptic Curve Cryptography)
  • Grover's algorithm provides quadratic speedup for searching unstructured databases effectively halving symmetric-key cryptosystem security
• Post-quantum cryptography is needed to maintain secure communication resistant to quantum computer attacks
  • Designed to withstand both classical and quantum attacks
  • Ensures long-term security of sensitive data and communications (financial transactions, medical records)

Post-Quantum Cryptographic Approaches

Approaches to post-quantum cryptography

• Lattice-based cryptography relies on the hardness of lattice problems (Shortest Vector Problem, Closest Vector Problem)
  • NTRU, Learning with Errors, Ring Learning with Errors
  • Strong security guarantees and efficient implementations
• Code-based cryptography relies on the difficulty of decoding random linear error-correcting codes
  • McEliece and Niederreiter cryptosystems
  • Strong security but large key sizes
• Multivariate cryptography relies on the difficulty of solving systems of multivariate polynomial equations over finite fields
  • Unbalanced Oil and Vinegar, Hidden Field Equations
  • Efficient signature schemes but large key sizes for encryption

Trade-offs in post-quantum schemes

• Security considerations
  • Resistance to known quantum attacks (Shor's algorithm, Grover's algorithm)
  • Concrete security level measured in bits
  • Assumptions about the hardness of underlying mathematical problems (lattice problems, error-correcting codes)
• Performance factors
  • Key generation, encryption, and decryption speeds
  • Key and ciphertext sizes
  • Computational and memory requirements (resource-constrained devices)
• Higher security levels often lead to larger key sizes and slower operations
• Balancing security requirements with practical constraints (bandwidth limitations, storage capacity)

Implementing Post-Quantum Cryptography

Implementation of post-quantum algorithms

1. Choose a post-quantum cryptographic algorithm to implement (simplified NTRU, code-based scheme)

2. Implement the key generation, encryption, and decryption functions

   • Use appropriate libraries or frameworks for the chosen programming language (liboqs, pqcrypto)
   • Optimize the implementation for performance

3. Assess the resistance of the implemented algorithm to quantum attacks

   • Analyze the underlying mathematical problem and its assumed hardness
   • Consider the impact of Shor's and Grover's algorithms on the scheme's security
   • Evaluate the algorithm's security level and compare it to classical cryptographic algorithms (AES, RSA)

4. Test the implementation with various input sizes and parameters

   • Verify the correctness of the encryption and decryption processes
   • Measure performance characteristics (key generation time, encryption time, decryption time)