🔐Quantum Cryptography Unit 6 – Post–Quantum Cryptography

What's Post-Quantum Crypto?

• Field of cryptography focused on developing cryptographic systems secure against attacks by quantum computers
• Designed to resist quantum computing algorithms (Shor's algorithm, Grover's algorithm) that can break classical cryptography
• Uses mathematical problems believed to be difficult for both classical and quantum computers to solve efficiently
  • Includes lattice-based cryptography, code-based cryptography, multivariate cryptography, and hash-based cryptography
• Aims to provide confidentiality, integrity, and authentication of data in a post-quantum world
• Differs from quantum cryptography, which uses principles of quantum mechanics to secure communication
• Proactive measure to ensure data remains protected as quantum computing advances
• Standardization efforts underway by organizations (NIST, ETSI) to develop and evaluate post-quantum cryptographic algorithms

Why We Need It

• Quantum computers pose a significant threat to the security of classical cryptographic algorithms
• Shor's algorithm, run on a sufficiently powerful quantum computer, can break widely-used public-key cryptosystems (RSA, ECC)
• Grover's algorithm provides quadratic speedup for brute-force attacks against symmetric-key cryptosystems (AES, SHA-2)
• Need to develop and deploy quantum-resistant cryptography before quantum computers become powerful enough to break current systems
• Protects sensitive data (financial transactions, medical records, government secrets) from unauthorized access in the quantum era
• Ensures long-term security of data encrypted today against future quantum attacks
  • Data encrypted now with classical algorithms may be stored and decrypted later when quantum computers are available
• Maintains trust in digital systems and online transactions in a post-quantum world

Quantum Threats to Classical Crypto

• Shor's algorithm efficiently solves integer factorization and discrete logarithm problems on a quantum computer
  • Breaks RSA, Diffie-Hellman, and elliptic curve cryptography (ECDSA, ECDH) which rely on these problems for security
• Grover's algorithm provides quadratic speedup for brute-force search on a quantum computer
  • Reduces effective security of symmetric-key algorithms (AES, SHA-2) by half
  • Example: 128-bit AES key provides only 64-bit security against quantum attacks
• Quantum algorithms exploit superposition and entanglement to perform certain computations exponentially faster than classical computers
• Quantum computers with sufficient qubits and error correction can break most widely-used classical cryptographic algorithms
• Poses a significant risk to the confidentiality and integrity of data protected by these algorithms
• Necessitates the development and adoption of quantum-resistant cryptography to maintain security in the post-quantum era

Key Post-Quantum Algorithms

• Lattice-based cryptography
  • Uses hard problems in high-dimensional lattices (SVP, CVP, LWE, NTRU) as basis for security
  • Examples: Kyber, NTRU, Frodo, Dilithium
• Code-based cryptography
  • Relies on difficulty of decoding random linear codes (McEliece, MDPC) for security
  • Examples: Classic McEliece, BIKE, HQC
• Multivariate cryptography
  • Based on solving systems of multivariate polynomial equations over finite fields (MQ problem)
  • Examples: Rainbow, GeMSS, LUOV
• Hash-based cryptography
  • Constructs digital signature schemes from hash functions (Merkle trees, XMSS, LMS)
  • Provides quantum resistance if underlying hash function is quantum-resistant
• Isogeny-based cryptography
  • Uses hard problems in elliptic curve isogenies (SIDH, CSIDH) for key exchange
  • Example: SIKE (Supersingular Isogeny Key Encapsulation)
• Symmetric-key cryptography
  • Increase key sizes of existing algorithms (AES-256, SHA-3) to compensate for quantum speedup
  • Develop new quantum-resistant designs (Gimli, Xoodyak)

How Post-Quantum Crypto Works

• Uses mathematical problems believed to be hard for both classical and quantum computers
  • No known quantum algorithms provide significant speedup over classical algorithms for these problems
• Lattice-based cryptography
  • Represents data as points in a high-dimensional lattice
  • Security based on difficulty of finding shortest vector (SVP) or closest vector (CVP) in the lattice
• Code-based cryptography
  • Encodes data using error-correcting codes
  • Security relies on difficulty of decoding random linear codes (McEliece, MDPC)
• Multivariate cryptography
  • Represents data as solutions to systems of multivariate polynomial equations over finite fields
  • Security based on difficulty of solving multivariate quadratic (MQ) equations
• Hash-based cryptography
  • Constructs digital signature schemes using hash functions and Merkle trees
  • Security depends on the quantum resistance of the underlying hash function
• Isogeny-based cryptography
  • Uses isogenies between supersingular elliptic curves for key exchange
  • Security based on difficulty of finding isogenies between given curves (SIDH, CSIDH)
• Increases key sizes and output lengths compared to classical algorithms to maintain security against quantum attacks
• Provides quantum resistance while maintaining functionality (encryption, digital signatures, key exchange) of classical cryptography

Pros and Cons

• Pros:
  • Provides security against quantum computer attacks
  • Ensures long-term protection of sensitive data
  • Maintains trust in digital systems and transactions
  • Offers diverse range of mathematical approaches for quantum resistance
  • Can be implemented on existing classical computing infrastructure
• Cons:
  • Increased key sizes and output lengths compared to classical algorithms
    • Requires more storage, bandwidth, and computational resources
  • Some post-quantum algorithms have higher computational complexity than classical counterparts
    • May impact performance and latency of cryptographic operations
  • Lack of widespread deployment and real-world testing compared to established classical algorithms
  • Uncertainty about the actual quantum resistance of some proposed algorithms
    • Ongoing research to assess security against future quantum cryptanalysis
  • Compatibility issues with existing systems and protocols designed for classical cryptography
    • May require significant modifications or replacements to integrate post-quantum algorithms
  • Standardization and evaluation process is still ongoing
    • Final selection and adoption of post-quantum algorithms may take several years

Real-World Applications

• Securing sensitive data and communications in various domains
  • Financial transactions (online banking, payment systems)
  • Healthcare (electronic health records, telemedicine)
  • Government and military (classified information, national security)
  • Telecommunications (5G networks, satellite communications)
  • Internet of Things (IoT) devices and systems
• Protecting long-term data archival and storage
  • Ensures data encrypted today remains secure against future quantum attacks
• Implementing post-quantum algorithms in cryptographic libraries and protocols
  • OpenSSL, BoringSSL, GnuTLS, TLS, SSH, IPsec, VPNs
• Hybrid schemes combining classical and post-quantum algorithms
  • Provides backward compatibility and transition path to post-quantum security
• Quantum-resistant digital currencies and blockchain applications
  • Protects against quantum attacks on cryptocurrency wallets and transactions
• Secure communication channels for quantum key distribution (QKD) networks
  • Post-quantum algorithms used for authentication and integrity protection in QKD protocols

Future of Post-Quantum Crypto

• Ongoing standardization efforts by NIST, ETSI, and other organizations
  • Evaluation and selection of post-quantum algorithms for standardization
  • Development of guidelines and recommendations for implementation and deployment
• Continued research to assess the security of proposed post-quantum algorithms
  • Analysis of resistance against classical and quantum cryptanalysis
  • Refinement and optimization of algorithms for improved performance and security
• Integration of post-quantum algorithms into existing cryptographic libraries, protocols, and applications
  • Updating standards (TLS, SSH, IPsec) to support post-quantum algorithms
  • Developing tools and frameworks for easy adoption of post-quantum cryptography
• Hybrid schemes combining classical and post-quantum algorithms
  • Ensures backward compatibility and smooth transition to post-quantum security
  • Provides defense-in-depth against both classical and quantum attacks
• Advancements in quantum computing and cryptanalysis
  • Development of more powerful quantum computers and improved quantum algorithms
  • Potential discovery of new quantum attacks on post-quantum algorithms
  • Continuous evolution of post-quantum cryptography to address emerging threats
• Increasing awareness and adoption of post-quantum cryptography
  • Education and training for developers, security professionals, and decision-makers
  • Collaboration between academia, industry, and government to promote post-quantum security
  • Inclusion of post-quantum requirements in security standards and regulations