Are NIST's Post-Quantum Cryptography Standards Still Safe? New Quantum Results and the Dihedral Coset Problem

What NIST's new post-quantum standards are replacing

For more than four decades, much of the world's digital security has relied on public-key cryptography whose security depends on the assumed computational hardness of three fundamental mathematical problems:

• the Integer Factorization Problem (IFP): RSA, used for encryption, key establishment, and digital signatures;
• the Discrete Logarithm Problem over finite fields (DLP): Diffie-Hellman (DH) for key establishment and DSA for digital signatures; and
• the Elliptic-curve Discrete Logarithm Problem (ECDLP): elliptic-curve Diffie-Hellman (ECDH) for key establishment, and elliptic-curve signature schemes such as ECDSA and EdDSA for digital signatures.

RSA, ECDSA, EdDSA, and ECDH are widely used to protect the world's digital infrastructure, including the Internet, financial systems, government and military communications, software updates, secure messaging, and cloud services. They also form a critical part of the security architecture of blockchain and digital-asset systems. In particular, ECDSA is used by Bitcoin and Ethereum to authorise transactions, while EdDSA and related elliptic-curve signature schemes are widely used across many other blockchain networks.

The long-term security of these systems, however, is threatened by the development of sufficiently powerful fault-tolerant quantum computers. A quantum computer capable of efficiently solving the integer factorization and discrete logarithm problems could break many of the public-key cryptographic systems on which today's digital infrastructure depends. This creates an urgent need for new cryptographic algorithms that can resist attacks from both classical and quantum computers.

To prepare for this transition, the U.S. National Institute of Standards and Technology (NIST) launched its Post-Quantum Cryptography Standardization Process in 2016, inviting researchers worldwide to submit candidate algorithms capable of resisting attacks from both classical and quantum computers. Following several rounds of international cryptanalysis, evaluation, and public competition, NIST finalised its first major post-quantum cryptography standards in 2024. These standards are intended to replace classical public-key algorithms that could become vulnerable to sufficiently powerful quantum computers, while preserving the essential functions of encryption, key establishment, and digital signatures in a future quantum computing environment.

The new standards include:

• ML-KEM, intended primarily to replace classical key-establishment and encryption mechanisms such as RSA key transport and Diffie-Hellman or elliptic-curve Diffie-Hellman key exchange;
• ML-DSA, intended to provide a post-quantum replacement for widely used digital signature systems such as RSA signatures and ECDSA;
• SLH-DSA, a hash-based digital signature standard providing a cryptographically different alternative to lattice-based signatures.

This transition is one of the largest changes in public-key cryptography since elliptic-curve cryptography became widely deployed.

Unlike RSA and elliptic-curve cryptography, ML-KEM and ML-DSA are based on the apparent hardness of mathematical problems involving high-dimensional lattices. In particular, their security is closely related to structured variants of the Learning With Errors problem, especially Module Learning With Errors (Module-LWE).

Compared with elliptic-curve cryptography, post-quantum schemes generally require much larger public keys and signatures. At approximately the 128-bit security level (meaning that the best known classical attack would require roughly 2^128 computational operations), ECDSA over the secp256k1 curve used by Bitcoin and Ethereum has a 33-byte compressed public key and a 64-byte signature. Post-quantum signatures are far larger:

ML-KEM, ML-DSA, and SLH-DSA are already supported by major cryptographic and technology platforms. For example, OpenSSL 3.5 supports all three NIST standards, while Microsoft has incorporated post-quantum cryptography into its Windows ecosystem.

A good example of post-quantum adoption in blockchain is NEAR Protocol, which added ML-DSA to its mainnet in the 2.13 upgrade in July 2026. ML-DSA is available as an additional post-quantum signing scheme, allowing NEAR accounts to add or migrate to quantum-safe access keys without changing their existing account identity.

Quantum and classical security of classical public-key cryptosystems

For RSA, Shor's algorithm can be implemented using roughly 3n logical qubits, where n is the bit length of the RSA modulus m. For example, an RSA-2048 modulus m = p*q is 2,048 bits long. Factoring it, extracting the two large primes p and q from m, which is part of the RSA public key, would therefore require roughly 3n = 3*2048 = 6,144 logical qubits.

What is ECDLP? The Elliptic-Curve Discrete Logarithm Problem (ECDLP) is the mathematical problem that protects elliptic-curve cryptography. Given two points G and P belonging to the same subgroup, an attacker must find a number x, with 0 < x < q, such that P = x*G. The number x is called the discrete logarithm of P with respect to G. For a well-chosen elliptic curve of prime order q, the best known general-purpose classical attacks require roughly 2^(n/2) operations, where n is the bit length of q. For Bitcoin's secp256k1 curve, the subgroup order is the 256-bit prime q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141. Solving the ECDLP therefore requires roughly 2^(256/2) = 2^128 operations on a classical computer, an astronomically large number that is considered computationally infeasible in practice.

The number of qubits for breaking ECDSA can be roughly estimated with the formula 9n + log2(n) + 10 from the paper of Roetteler et al. 2017, where n is the length of the main subgroup order (the number of points in the group in which we calculate the discrete logarithm). If we had a quantum computer with more than roughly 9n + log2(n) + 10 = 9*256 + 2*log2(256) + 10 = 2304 + 16 + 10 = 2330 qubits, then the ECDLP for such a 256-bit curve could be solved quickly, in polynomial time.

But no publicly known quantum computer has yet reached even 1,000 logical qubits. In fact, as of August 2026, even the most advanced systems have only tens of high-quality logical qubits. The main challenge in scaling to hundreds or thousands of logical qubits is quantum error correction. A logical qubit is built from many physical qubits that work together to protect quantum information from errors and noise, making large-scale fault-tolerant quantum computers extremely challenging to build.

Doubts about ML-KEM and ML-DSA: could quantum computers solve lattice hard problems faster than we currently believe?

Two recent papers have caught the attention of the cryptographic community and raised an important question: how secure are these lattice problems really against future quantum computers?

The first, "Module Learning With Errors and Structured Extrapolated Dihedral Cosets" by Weiqiang Wen and Jinwei Zheng, studies Module Learning With Errors (MLWE), the main hardness assumption behind both ML-KEM and ML-DSA. The authors establish a connection between MLWE and a structured version of the Extrapolated Dihedral Coset Problem (EDCP). In simple terms, they show that understanding the quantum difficulty of MLWE can be translated into understanding a particular hidden structure involving dihedral groups.

The second paper, Daniel R. Simon's "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem," goes a step further. Simon presents a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP), a problem that has long been connected to lattice problems. Combined with earlier reductions, his result gives polynomial-time quantum algorithms for certain versions of the Shortest Vector Problem (SVP) and Learning With Errors (LWE).

The required quantum resources may still be enormous, far beyond those estimated for breaking RSA or ECDSA. But the fact that the algorithm is polynomial-time is what makes the result particularly interesting: it suggests that, if future research can reduce its quantum resource requirements, problems that currently appear impractical could become much more accessible to large-scale quantum computers.

Simon's result does not break ML-KEM or ML-DSA. The algorithm applies to particular parameter regimes and relies on reductions whose parameters and assumptions matter. The ePrint paper itself describes the resulting LWE algorithms for specific regimes, rather than an attack on the standardised parameter sets used by ML-KEM or ML-DSA.

What this means

The arrival of large-scale quantum computers will eventually change the rules of public-key cryptography. Shor's algorithm shows that RSA, ECDSA, ECDH, and other systems based on factoring and discrete logarithms can be broken efficiently by a sufficiently powerful fault-tolerant quantum computer. This is why the cryptographic community, industry, and governments are moving toward post-quantum cryptographic standards.

But perhaps the most important lesson is that post-quantum cryptography is not "quantum-proof" by definition. It is a new, rapidly growing field based on hard mathematical problems that we currently believe are difficult for both classical and quantum computers. As quantum algorithms continue to develop, these assumptions must be continuously tested.

References

• FIPS 203, ML-KEM (key establishment / KEM): NIST FIPS 203
• FIPS 204, ML-DSA (digital signatures): NIST FIPS 204
• FIPS 205, SLH-DSA (digital signatures): NIST FIPS 205
• Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 1994, pp. 124-134.
• Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter, "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms," arxiv.org/pdf/1706.06752.
• Weiqiang Wen and Jinwei Zheng, "Module Learning With Errors and Structured Extrapolated Dihedral Cosets," eprint.iacr.org/2026/155.
• Daniel R. Simon, "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem," eprint.iacr.org/2026/1591.