White House drastically shortens deadline for dropping quantum-vulnerable crypto

“Critical infrastructure owners and operators can now expect support in developing their PQC migration plans,” Jordan Kenyon, senior quantum scientist at Booz Allen, told Ars. “Covered contractors could face future requirements from proposed rules to incorporate PQC compliant algorithms required by FIPS by the end of 2030 and incorporate reports of cryptographic vulnerabilities in their disclosures.” FIPS is short for Federal Information Processing Standards, a set of standards shepherded by NIST for use in computer systems of non-military US government agencies and contractors. In March, researchers said they discovered a way to break ECC-256, used to secure the bitcoin and ethereum blockchains, using only 30,000 physical qubits in 10 days. That same month, a Google research team said it developed two quantum circuits that could solve the elliptic-curve discrete logarithm problem using roughly 500,000 physical qubits, half of what the same team estimated last June was needed to break 2048-bit RSA, which has a much larger key size. In 2012, most estimates were that breaking a 2048-bit RSA key would require a billion physical qubits. By 2019, the estimate was lowered to 20 million physical qubits. The steady march of progress, as demonstrated by these latest research papers, is prodding organizations with the most to lose to err on the side of Q Day—the day a cryptographically relevant quantum computer arrives—coming sooner rather than later. Two of the most widely used public key cryptography algorithms—RSA and elliptic curve cryptography—are based on factoring composites, which are the product of two or more primes, and the discrete logarithm, respectively. These mathematical problems are simple to solve in one direction and nearly impossible in the other. A quantum computer with sufficient resources can run Shor’s algorithm to solve these problems in polynomial time, specifically cubic time, far faster than the exponential time provided by today’s classical computers. The post-quantum algorithms replacing RSA and elliptic curve cryptography are based on problems that quantum computers have no advantage over classical computers in solving. Contrary to what many people assume, substituting quantum vulnerable algorithms for PQC ones is anything but a drop-and-replace exercise. Public key sizes for ML-KEM—one of the replacements for RSA—are roughly three times bigger. The difficulty and scale of the work ahead is the reason the federal government is taking the move so seriously. Separately, the White House published a second executive order directing the federal government, in partnership with private industry, to support quantum computing. Among other things, it established a “national effort” to develop the world’s first quantum computer powerful enough to “initiate the era of quantum-enabled scientific discovery.”