The First NIST-approved PQC Algorithms Announced, CISA Poses Guiding Roadmap for Preparation

In July, NIST announced the first batch of standardized PQC algorithms which included four different algorithms. Despite commercial products will not be hearing from NIST regarding PQC standards for use until 2024, NISA and CISA both strongly recommend businesses and organizations to prepare for the future. CISA provided guidelines that include organizing and inventorying the business applications that use public key cryptography, creating a roadmap and policies for transitioning to new cryptographic standards, as well as alerting and providing applicable training to prep for the future.

Post-Quantum Cryptography (PQC) standardization has broken new grounds in the past year, and relevant developments can be traced back to a cryptography standardization competition held by the National Institute 0f Standards and Technology (NIST) in 2016. Out of all 82 submissions, 69 were chosen from the competition for further evaluations. After three rounds of competition that ran for six years, the first approved standardized algorithms were finally revealed on July 5th, 2022.

Four algorithms were chosen in the standardization process, and the two primary algorithms to be implemented are CRYSTALS-Kyber (Public-Key Encryption/KEMs) and CRYSTALS-Dilithium (Digital Signatures). Two other digital signature algorithms FALCON and SPHINCS+ were also selected to be standardized.

NIST Proposes Two Primary Algorithms in Hopes of Incorporating Different Mathematical Calculations.

Essentially, the PQC Standardization competition aims to single out top-tier quantum-resistant cryptography systems that can challenge the conventional public key cryptography. In other words, there need to be insolvable mathematical problems for traditional and quantum computers alike to protect digital security in the present and future.

If things went according to the initial timeline, there should have been the first group of standardized algorithms chosen at the end of January. However, NIST prolonged the decision by half a year, announcing the first group of candidates to be standardized in July.

As mentioned, NIST has handpicked two primary algorithms for standardization: CRYSTALS-Kyber and CRYSTALS-Dilithium.

For encrypted PKE/KEMx, CRYSTALS-Kyber is relatively more efficient than its competitors and its public key and ciphertext sizes are acceptable for most applications. Kyber’s bandwidth is also at acceptable levels.

Regarding the algorithms under digital signatures, CRYSTALS-Dilithium is similar to Kyber, both achieving high efficiency on most applications and proving to be highly secured. As for the other two selected candidates, FALCON has the smallest bandwidth and is fast when verifying signatures. Despite the low bandwidth, FALCON might be a more suitable choice in some constrained protocol scenarios. SPHINCS+ is a third-round alternate candidate that is different in that it is hash-based instead of lattice-based like its three other cohorts. This avoids having to rely on solely lattice-based algorithms. Though it may be slightly less efficient than others, it still holds high potential and value.

NIST also announced the KEM algorithm candidates that will head into the fourth round, including BIKE, Classic McEliece, HQC, and SIKE.

In the world we live in, applications of all sizes require digital security and encryption. Hence, NIST stresses the need to have a standard for all scenarios such that if one fails, other algorithms can immediately replace the previous one.

The reality is, despite lattice-based algorithms being mainstream, NIST has emphasized multiple times that there needs to be another type of algorithm ready to use if there were to be breakthroughs in lattice-based cryptography. Furthermore, NIST hopes to promote the concept of crypto-agility, quickly introducing a new algorithm into a secured system. After all, there is no guarantee that these standardized algorithms are impenetrable.

Right now, NIST encourages organizations to explore the new algorithms and consider how their applications will use them but they advise against “baking them into their systems” since there may still be minor changes before they officially standardize everything.

NIST has also planned to call for new public key digital signature algorithms that have “shorter signatures and faster verification.” The submission deadline for this is June 1, 2023.

In response to NIST’s current list of standardized algorithms, cryptography expert Daniel J. Bernstein notes that NIST did not secure the patent buyouts before announcing Kyber’s selection, which would provide the patent holders with more power. It is rumored that NIST may look to other candidates such as NTRU if agreements are not reached by the end of the year.

US Government Asked Organizations to Start Planning for the Transition and Issued Relevant Guidelines

As quantum computing continues to develop, public key cryptography is bound to be changing.

Though NIST devised its standards for the United States, this impacts how the rest of the world adjusts its standards, including Taiwan and its businesses.

Recently, many cryptographers have advised governments, businesses, and corporations to inspect applications that are already using public key cryptography.

There are Taiwanese IT companies that have been prepping for the NIST’s announcement. In May, hardware security company WiSECURE announced that their commercial hardware security platform kvHSM successfully implemented the SPHINCS+ digital signature algorithm. In addition, they also implemented CRYSTALS-Kyber and CRYSTALS-Dilithium on their HSM (hardware security module) platform. Such immediate successes are the results of efforts devoted to post-quantum cryptography application in years prior.

Regarding the current preparation of Taiwanese businesses for this change, Jimmy Chen, CEO of WiSECURE and the Assistant Professor of Mathematics at the National Taiwan University, emphasizes the credibility and value NIST publications provide. He suggests people look at the PQC report from the National Cybersecurity Center of Excellence (NCCoE), an entity under NIST, as a major source of information.

The American government has also responded quickly in its preparation. On May 4th, President Biden officially signed the 10th National Security Memorandum (NSM-10). The document includes guidance regarding the country’s development in quantum technology, one is requesting the federal government to transition towards PQC systems. NIST and CISA will be responsible for this request, each required to inventory all systems and assets on the federal level that have to do with public key cryptography.

Today, as the report from July 5th CISA report advises, organizations should devise the blueprints for PQC applications to ensure a smooth transition period with public key cryptography.

CISA has provided six guidelines:

  1. Inventorying your organization’s systems for applications that use public-key cryptography.
  2. Testing the new post-quantum cryptographic standard in a lab environment; however, organizations should wait until the official release to implement the new standard in a production environment.
  3. Creating a plan for transitioning your organization’s systems to the new cryptographic standard that includes:
    • Performing an interdependence analysis, which should reveal issues that may impact the order of systems transition;
    • Decommissioning old technology that will become unsupported upon publication of the new standard; and
    • Ensuring validation and testing of products that incorporate the new standard.
  4. Creating acquisition policies regarding post-quantum cryptography. This process should include:
    • Setting new service levels for the transition.
    • Surveying vendors to determine possible integration into your organization’s roadmap and to identify needed foundational technologies.
  5. Alerting your organization’s IT departments and vendors about the upcoming transition.
  6. Educating your organization’s workforce about the upcoming transition and providing any applicable training.

The following article is an adaptation/translation from iTHome’s recent article and the NIST report. For more information, please look at the full report on NIST’s website.