91³Ô¹ÏÍø

The quantum algorithms: Grover's and Shor's

Quantum computers leverage the principles of quantum mechanics to perform certain types of calculations at unprecedented speeds. Two quantum algorithms pose a direct threat to today's deployed cryptography: Grover's algorithm and Shor's algorithm.

• Grover's algorithm: This algorithm can search an unsorted database quadratically faster than any classical algorithm. While it doesn't break cryptographic systems outright, it significantly reduces the security of symmetric key algorithms like AES (Advanced Encryption Standard) and SHA-2 (Secure Hash Algorithm 2), necessitating longer keys to maintain security.
• Shor's algorithm: This algorithm can factorize large integers exponentially faster than the best-known algorithms running on classical computers. This is particularly alarming for algorithms performing asymmetric cryptography like RSA (Rivest¨CShamir¨CAdleman), ECC (Elliptic Curve Cryptography), and DSA (Digital Signature Algorithm), which rely on the difficulty of factorizing large numbers or solving discrete logarithm problems. A sufficiently powerful quantum computer running Shor's algorithm will break these cryptographic systems, rendering them obsolete.

NIST post-quantum cryptography standards

Recognizing the urgent need for quantum-resistant cryptographic algorithms, the U.S. Department of Commerce¡¯s National Institute of Standards and Technology (NIST) has been at the forefront of catalyzing the development of post-quantum cryptography (PQC) standards. For this purpose, they have organized a competition to select the best PQC algorithms. On August 13, 2024, NIST announced the finalization of its first set of these algorithms designed to withstand cyberattacks from quantum computers. This milestone marks the culmination of an eight-year effort, rallying the global cryptography community to develop and evaluate algorithms that can protect the security of our digital future.

NIST¡¯s finalized standards include three primary algorithms, each designed for specific applications in key encapsulation and digital signatures. These algorithms are:

• ML-KEM (FIPS 203, formerly CRYSTALS-Kyber): This algorithm is based on lattice problems, which are believed to be resistant to quantum attacks. It offers a balance of security, efficiency, and ease of implementation, making it a suitable choice for general encryption tasks. Its small key sizes and rapid encapsulation/decapsulation processes are particularly advantageous for resource-constrained environments.
• ML-DSA (FIPS 204, formerly CRYSTALS-Dilithium): Similar to ML-KEM, ML-DSA is also based on lattice problems but is specifically designed for digital signatures. It provides strong security guarantees and efficient performance, making it an ideal choice for applications requiring identity authentication and data integrity.
• SLH-DSA (FIPS 205, formerly SPHINCS+): This algorithm employs a stateless hash-based approach, offering a different set of security assurances compared to lattice-based methods. SLH-DSA is particularly valued for its simplicity and robustness against a wide range of attacks.

Out of these three, ML-KEM and ML-DSA are expected to be the most deployed algorithms. NIST is also expected to publish the draft standard of the FN-DSA (FIPS 206), which is based on the Falcon algorithm, in late 2024. This digital signature algorithm leverages structured lattices.

Back in 2020, NIST also released the standard SP 800-208, which references the quantum-resistant stateful hash-based signature schemes Leighton-Micali Signature (LMS) system and eXtended Merkle Signature Scheme (XMSS). Both LMS and XMSS rely on the Merkle tree structure, which provides a secure and efficient way to manage and verify many signatures. The LMS system uses a basic Merkle tree, while XMSS incorporates more additional features. This causes the performance of these systems to differ depending on use case, ultimately influencing which system is more suitable for a given application.

Moving forward: NIST¡¯s fourth round of quantum-safe standards

NIST continues to evaluate additional algorithms to ensure a diversified and secure cryptographic landscape. It has already started a fourth round of its standardization efforts, in which an additional set of key encapsulation algorithms is undergoing evaluation with the intent to find more algorithms to complement the set of currently standardized algorithms. The fourth round will likely select one or two algorithms, for which a public draft is expected to be published in 2025. Key encapsulation algorithms selected for the fourth round evaluation include Classic McEliece, BIKE, and HQC.

In September 2022, NIST also started another standardization round for additional PQC digital signature schemes. Here NIST is primarily interested in additional general-purpose algorithms that are not based on structured lattices. Other interests include algorithms using short signatures and fast verification. Any lattice signature would need to significantly outperform ML-DSA and FN-DSA and/or ensure substantial additional security properties. Recently, NIST has selected 14 new digital signature algorithms to advance to the second round of the standardization process, including: CROSS, FAEST, HAWK, LESS, MAYO, Mirath, MQOM, PERK, QR-UOV, RYDE, SDitH, SNOVA, SQIsign and UOV. The second phase of evaluation is estimated to last 12 to 18 months.

CNSA v2.0: Driving quantum-resistant cryptography for U.S. national security

In September 2022, the National Security Agency (NSA) announced of the Commercial National Security Algorithm (CNSA) suite, which also received an update of its in April 2024. CNSA is a set of cryptographic algorithms recommended by the NSA for protecting U.S. government National Security Systems (NSS) and information. The threat that quantum computing poses on cryptographic algorithms was addressed for the first time in version 2.0. Hence, all algorithms recommended in version 2.0 are NIST standardized and quantum resistant (QR), including AES, SHA, LMS, XMSS, and the recently released PQC standards ML-KEM and ML-DSA.

The NSA also uses CNSA to drive the timelines for adoption of PQC in NSS. The importance of this matter for the NSA shows from quotes like this from CNSA v2.0: ¡°NSA expects the transition to QR algorithms for NSS to be complete by 2035 in line with NSM-10 [National Security Memorandum]. NSA urges vendors and NSS owners and operators to make every effort to meet this deadline. Where feasible, NSS owners and operators will be required to prefer CNSA 2.0 algorithms when configuring systems during the transition period. When appropriate, use of CNSA 2.0 algorithms will be mandatory in classes of commercial products within NSS, while reserving the option to allow other algorithms in specialized use cases.¡±

Besides PQC, the PKAs also support traditional ECC and RSA algorithms, ensuring broad cryptographic coverage now and in the future, including hybrid mode support. Being highly configurable and scalable, the IP can be optimized for performance, area, power, and latency.

Synopsys Agile PQC PKAs support full PQC digital signatures, key encapsulation and generation functions, with FIPS 140-3 certification support, secure key interfaces, and optional countermeasures against side-channel and fault injection attacks. With Synopsys Agile PQC PKAs, designers can protect sensitive data and systems against future quantum threats, ensuring long-term security for government, enterprises, and consumers.