Post-Quantum Cryptography (PQC) Status

Post-Quantum Cryptography (PQC) Standardization Project

• Main NIST project page
• Memorandum on Improving the Cybersecurity of National Security, Department of Defense, and Intelligence Community Systems (JANUARY 19, 2022)
• NISTR 8309 - Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process (July 2020)
• NISTR 8105 - Report on Post-Quantum Cryptography (April 2016)

• [How Quantum Computers Break Encryption

  Shor’s Algorithm Explained](https://youtu.be/lvTqbM5Dq4Q)

• Miscellaneous Notes

Memorandum on Improving the Cybersecurity of National Security, Department of Defense, and Intelligence Community Systems (JANUARY 19, 2022)

• Memorandum
• Key Notes

  • (B) Within 60 days of the date of this memorandum, the NSA shall revise and make available to Chief Information Officers the CNSS Advisory Memorandum 01-07 (Information Assurance Cryptographic Equipment Modernization) and any associated enclosures and relevant references regarding modernization planning, use of unsupported encryption, approved mission unique protocols, quantum resistant protocols, and planning for use of quantum resistant cryptography where necessary.

  • (C) Within 90 days of the date of this memorandum, CNSS shall identify and prioritize for update all cryptographic-related policies, directives, and issuances, and CNSS shall provide to the Secretary of Defense, the Director of National Intelligence, and the National Manager a timeline, not to exceed 6 months, for the re-issuance of these policies, as appropriate.

  • (D) Within 180 days of the date of this memorandum, agencies shall identify any instances of encryption not in compliance with NSA-approved Quantum Resistant Algorithms or CNSA, where appropriate in accordance with section 1(b)(iv)(A) and (B) of this memorandum, and shall report to the National Manager, at a classification level not to exceed TOP SECRET//SI//NOFORN:

    • (1) systems where non-compliant encryption is being used, to include those operating under an existing waiver or exception;

    • (2) a timeline to transition these systems to use compliant encryption, to include quantum resistant encryption; and

    • (3) any exception from transition to compliant encryption, pursuant to section 3 of this memorandum, which shall additionally be reviewed by the National Manager and reported quarterly to the Secretary of Defense and the Director of National Intelligence for the systems within their respective jurisdictions. The National Manager, in coordination with and only after engaging the system owner, may include other relevant agencies if a shared risk is jointly determined.

NISTR 8309 - Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process (July 2020)

• Links / Resources
  • https://csrc.nist.gov/publications/detail/nistir/8309/final
  • https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf
• Highlights / Notes
  • The third-round finalist public-key encryption and key-establishment algorithms are Classic McEliece, CRYSTALS- KYBER, NTRU, and SABER
  • The third-round finalists for digital signatures are CRYSTALS-DILITHIUM, FALCON, and Rainbow
  • These finalists will be considered for standardization at the end of the third round
  • In addition, eight alternate candidate algorithms will also advance to the third round: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, and SPHINCS+
    • These additional candidates are still being considered for standardization, although this is unlikely to occur at the end of the third round
  • Public-Key Encryption / Key Establishment Mechanisms (KEMs)
    • 4 final candidates
      • At most will only standardize 2 of the four due to 3 of the 4 are lattice based schemes
  • Digital Signatures
    • 3 candidates
      • At most will only standardize 2 of the 3
  • Alternate candidates
    • A few of the alternate candidates have worse performance than the finalists but might be selected for standardization based on NIST’s high confidence in their security
    • NIST expects a fourth round for the candidates in the Alternate Candidates group (aka track)
  • As a general guideline, NIST expects that any modifications to the seven finalists should be relatively minor while allowing more latitude to the eight additional candidate algorithms
  • NIST expects to select a small number of candidates for standardization by early 2022
    • To achieve this goal, the third round will serve as a final round for the first phase of standardization, though some schemes will remain under consideration for future standards

NISTR 8105 - Report on Post-Quantum Cryptography (April 2016)

• Links / Resources
  • https://csrc.nist.gov/publications/detail/nistir/8105/final
  • https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf
• Highlights / Notes
  • The construction of a large-scale quantum computer would render many of these public key crypto systems insecure. In particular, this includes those based on the difficulty of integer factorization, such as RSA, as well as ones based on the hardness of the discrete log problem. In contrast, the impact on symmetric key systems will not be as drastic
  • Grover’s search algorithm proffers a quadratic speedup on unstructured search problems. While such a speedup does not render cryptographic technologies obsolete, it can have the effect of requiring larger key sizes, even in the symmetric key case
    • We don’t know that Grover’s algorithm will ever be practically relevant, but if it is, doubling the key size will be sufficient to preserve security. Furthermore, it has been shown that an exponential speed up for search algorithms is impossible, suggesting that symmetric algorithms and hash functions should be usable in a quantum era
  • Main Families of Post Quantum Cryptography
    • Lattice-based cryptography
      • Exciting new applications (such as fully homomorphic encryption, code obfuscation, and attribute- based encryption) have been made possible using lattice-based cryptography
      • Most lattice-based key establishment algorithms are relatively simple, efficient, and highly parallelizable
    • Code-based cryptography
      • In 1978, the McEliece crypto system was first proposed, and has not been broken since
      • While quite fast, most code-based primitives suffer from having very large key sizes
    • Multivariate polynominal cryptography
      • These schemes are based on the difficulty of solving systems of multivariate polynomials over finite fields. Several multivariate crypto systems have been proposed over the past few decades, with many having been broken
      • Historically been more successful as an approach to signatures
    • Hash-based signatures
      • Hash-based signatures are digital signatures constructed using hash functions. Their security, even against quantum attacks, is well understood
    • Other
      • A variety of systems have been proposed which do not fall into the above families. One such proposal is based on evaluating isogenies on supersingular elliptic curves
  • One challenge that will likely need to be overcome is that most of the quantum-resistant algorithms have larger key sizes than the algorithms they will replace
    • This may result in needing to change various Internet protocols, such as the Transport Layer Security (TLS) protocol, or the Internet Key Exchange (IKE)

Miscellaneous Notes

• Current encryption standards (collectively referred to as RSA) are not resistant to quantum computing attacks
• RSA is everywhere, there are 20 billion devices that will need a software upgrade
• To break current encryption a quantum computer with 20 million qubits will be required to break RSA 2048 in less than a day. State of the art quantum computers are currently operating at 66 qubits. Industry experts have estimated the time horizon to reach that level of compute at between one and two decades. Google Sandbox estimates between 5 and 15 years based on the level of investment undertaken by China. (approximately $10B annually)
• Modern encryption standards underpin the entirety of trust for all aspects of technology today to include but not limited to Public Key Infrastructure and related certificate authorities, secure software digital signatures, federated auth, key exchanges, secure mail, VPN, secure web browsing (SSL/TLS).