Lecture Notes on Post-Quantum Cryptography

Introduction to Post-Quantum Cryptography (PQC)

  • Course Overview: CSC2056, Systems Security & Cryptography at Queen's University Belfast.
  • Instructor: Dr. Ciara Rafferty, Senior Lecturer.

Learning Outcomes

By the end of the lecture, you should be able to:

  • Understand the concept of Post-Quantum Cryptography (PQC).
  • Recognize the necessity for PQC algorithms.
  • Be informed about PQC standardization efforts.
  • Understand the challenges in transitioning from classical cryptography to PQC.

What is Quantum Computing?

  • Definition: Utilization of quantum mechanics to solve complex problems.
  • Advantage over classical computing: Potential ability to solve problems infeasible for classical computers.
Types of Quantum Computing Techniques:
  • Superconducting qubits
  • Trapped ion qubits
  • Quantum dots
  • Photons
  • Neutral atoms
Properties of Quantum Computing:
  • Superposition: Ability to exist in multiple states simultaneously.
  • Entanglement: Instantaneously affecting another particle's state regardless of distance.
  • Decoherence: Loss of quantum interference.
  • Interference: Enhancing the probabilities of certain outcomes.
Applications of Quantum Computing:
  • Medicine and health
  • Machine learning and AI
Challenges of Quantum Computing:
  • Scalability (building more qubits)
  • Security & noise issues
  • Many ongoing research initiatives

Motivation for Post-Quantum Cryptography (PQC)

  • Risk: Certain public-key cryptographic systems might be broken by quantum computers due to Shor’s algorithm.
  • Probability of fundamental public-key cryptography being compromised:
    • 1 in 7 by 2026
    • 1 in 2 by 2031
  • Vulnerable Algorithms:
    • RSA, DSA, Diffie-Hellman, ECC, ECDSA.

Symmetric vs. Asymmetric Cryptography

Symmetric Cryptography:
  • Vulnerability: Attacked via exhaustive key search (e.g. AES).
  • With Grover’s algorithm, attacks can be reduced to 2^64 computations increasing the need for larger keys.
Asymmetric Cryptography:
  • Question: How to ensure security against quantum attacks?
  • Need for algorithms based on hard mathematical problems not solvable by Shor's algorithm.

Types of Post-Quantum Cryptography

  • Hash-based
  • Lattice-based: Focus of modern implementations due to promising security efficiency.
  • Code-based
  • Multivariate
  • Isogeny-based
Lattice-based Cryptography (LBC):
  • Definition: Utilizes geometric structures (lattices) for cryptographic security.
  • Key Problem: Shortest Vector Problem (SVP) and Learning With Errors (LWE).
Learning With Errors (LWE) Problem:
  • Given matrix A and target point t, find secret vector s such that A·s + e ≡ t mod q, where e is a small error vector.
Challenges with LWE:
  • Large parameter sizes and complexity in error distribution.
  • Security relies on interdependent parameters and complexity of computation.

Current Status of Lattice-Based Cryptography

  • Standardization includes:
    • Kyber (key establishment)
    • Dilithium (digital signatures)
    • Ongoing research and implementation in major cloud services like AWS and Google.

Migration to PQC

Key Considerations:
  • Follow best practices and standards (NCSC guidance).
  • Avoid implementing proprietary cryptographic solutions.
Standards in Cryptography:
  • Importance: Ensure interoperability and security consensus.
  • Various organizations involved: ISO, NIST, etc.
  • NIST PQC competition: Identifying suitable algorithms for post-quantum standards.

NIST PQC Standards and Efforts

  • Current Finalists: Include Lattice-based (CRYSTALS-KYBER) and Code-based schemes (Classic McEliece).
  • Additional Signature Schemes: New proposals expected from ongoing competitions.
Challenges in Practical Implementation:
  • Must match efficiency of classical systems like RSA.
  • Compatibility with constrained devices.
  • Scalability of parameters while maintaining security.

Conclusion and Future Implications of Cryptography

  • Need: For robust, quantum-resistant encryption protocols as quantum technologies develop.
  • Continuous adaptation to new standards is crucial to maintain security.