Cryptography in the Era of Quantum Computers

  • Importance of Cryptography

    • Protects private communication of individuals and organizations online.
    • Safeguards information during transactions (e.g., online purchases, cloud uploads, accessing email).

  • Research Focus

    • Addressing the potential threats posed by future quantum computers.
    • Acknowledgment of the advancements quantum computers could bring across various fields.
    • Need to update current cryptographic methods to ensure continued security.

  • Existing Cryptographic Methods

    • Public-Key Cryptography (also known as Asymmetric Cryptography)
    • Relies on:
      • Difficulty of factoring large integers.
      • Difficulty of calculating elliptic curve discrete logarithms.
    • These problems could be efficiently solved by sufficiently advanced quantum computers.

  • Development of Post-Quantum Cryptography (PQC)

    • Aim to create cryptosystems rooted in mathematical problems that are resistant to quantum computing.
    • The work is collaborative and open-source, involving partnerships with academia and industry partners.
    • Goals include developing robust, trusted, tested, and standardized PQC.
    • Initiatives started in 2014, with initial papers published in 2015.

  • Standardization Efforts

    • Submission of cryptographic proposals to NIST's Post-Quantum Project throughout various rounds.
    • Outcomes from round 3 of NIST included:
    • CRYSTALS-Kyber for public-key encryption and key establishment.
    • CRYSTALS-Dilithium, Falcon, SPHINCS+ for digital signatures.
    • ISO approvals for FrodoKEM and two additional algorithms to facilitate standardization.

Considerations in Post-Quantum Cryptography

  • Integration with Existing Protocols

    • New cryptosystems must interface with established internet protocols such as TLS (Transport Layer Security).

  • Key Concerns for New Cryptosystems:

    • Size of encryption keys and signatures:
    • Must consider how key sizes will impact performance and usability.
    • Time required for operations:
    • Time to encrypt, decrypt, sign messages, or verify signatures should be efficient.
    • Traffic considerations:
    • Volume of data transmitted during encryption, decryption, or signature verification should be minimal.

  • Need for Cryptanalysis

    • Rigorous testing to identify any exploitable weaknesses in new cryptosystems is required.
    • Development must occur transparently, allowing global scrutiny from cryptographers, organizations, and governments.
    • Urgency is emphasized due to the unknown timeline regarding when classical cryptography will become vulnerable.
    • Risks include potential threats where adversaries might store encrypted data and decrypt it once quantum machines are available.

Active Research and Development in PQC

  • Project Participation
    • Involvement in the Open Quantum Safe project aimed at enhancing post-quantum cryptography via various protocols and libraries.
    • Development of liboqs library and integrations with protocols such as OpenSSL (for TLS) and OpenSSH (for SSH).
    • Creation of a deprecated fork of OpenVPN to demonstrate how PQC can function within VPN tunnels (not currently maintained).

Specific Post-Quantum Cryptographic Algorithms:

  • FrodoKEM

    • Based on the Learning with Errors (LWE) problem, which utilizes principles of lattices for security.

  • SQISign

    • A compact post-quantum signature scheme utilizing isogeny graphs from supersingular elliptic curves.
    • Designated as a candidate within the NIST PQC Signature project.

NIST Post-Quantum Project Participation

  • Collaboration and Submissions

    • Engagement with global cryptographers to offer candidates for review and analysis through the NIST PQC initiative.
    • Development of four candidates focusing on quantum-resilience while maintaining compatibility with existing communication protocols:
    • Two candidates related to key exchange systems.
    • One candidate for digital signatures.
    • Additional contribution in support of a second signature system.
    • Each proposal featured unique strengths and weaknesses, grounded in different mathematical challenges and exhibiting varied performance and key size trade-offs.
    • The post-quantum cryptography domain is still developing; extensive cryptanalysis is vital for confirming security of proposals.

  • Historical Notes on Non-Active Algorithms

    • Reference to earlier submissions no longer in active development for researcher awareness.
Notable Algorithm Distress.

  • SIKE (Supersingular Isogeny Key Encapsulation)

    • Involved arithmetic operations on elliptic curves over finite fields for key exchange.
    • Noted for a catastrophic vulnerability discovered in summer 2022.

  • Picnic

    • A public-key digital signature algorithm employing zero-knowledge proof systems centered on symmetric key primitives.

  • qTESLA

    • A post-quantum signature model based on the Ring Learning With Errors (R-LWE) problem.

NIST NCCoE PQC Migration Project

  • Collaboration
    • Participation in the NIST Cybersecurity Center of Excellence (NCCoE) PQC Migration project.
    • Collaboration with industrial and government entities to:
    • Build detection tools for vulnerable algorithms.
    • Test the interoperability and performance of post-quantum protocols and applications.
    • Reports and updates are available on the NCCoE project page: Migration to Post-Quantum Cryptography | NCCoE.