Cryptography is different. 

Cryptography is possibly the only area in which both 1) quantum computing will have an enormous impact and 2) the community at large is preparing for this impact. Most communities look forward to quantum computing. It offers new capabilities which will be a welcome addition to their work. At the very least, chemists, drug designers and material scientists will benefit from better molecular simulations and physicists will enjoy better simulation of quantum phases of matter. Others expect benefits for optimization and perhaps machine learning too, and there will be new, surprising applications discovered as large scale quantum computers come online. 

Cryptography is different. In the business of protection, success requires being proactive. The global financial system, state secrets and internet traffic are too valuable to be left vulnerable when cryptographically relevant quantum computers arrive. To preempt quantum attacks, cryptographers have already developed a number of post quantum cryptography (PQC) protocols: encryption and digital signature schemes that run on classical computers and are secure against quantum computers. 

Last week, NIST announced that it had chosen a new algorithm for post-quantum encryption and expects to release a draft standard in the next year. The American body has been working on soliciting, testing and standardizing post quantum algorithms since 2016. The first approved schemes were announced last August, including one general encryption scheme and three digital signature schemes. Those schemes are: 

  • ML-KEM: General encryption, based on CRYSTALS-Kyber and lattice problems. 
  • ML-DSA: Digital signature, based on CRYSTALS-Dilithium and lattice problems. 
  • SLH-DSA: Digital signature, based on Sphincs+ and hash problems. 
  • FN-DSA: Digital signature, based on FALCON and lattice problems. 
  • HQC: General encryption, based on error-correcting code problems. Announced 11th March. 

Codes, however, get broken. Just like RSA and ECC, these post-quantum schemes are not guaranteed secure, but must prove their worth over time and by withstanding sustained attention and attacks. NIST accelerates this process by motivating cryptographers to focus on attacking candidate schemes. New attacks may still emerge in the coming years though, so we need backup options. HQC, the algorithm announced last week, is a backup for general encryption, expanding our options from just one scheme (ML-KEM) to two. 

In July 2023, NIST shared 40 valid digital signature schemes that had been submitted for consideration. Today, attacks have been published for at least 21 of them. 14 are being considered as part of a second round. It appears that the most likely outcome of proposing a new scheme is a compromised one. 

Along with the research community’s work with NIST, companies are taking action too. iMessage, Signal, Cloudflare and Chrome have each implemented some form of ML-KEM (CRYSTALS-Kyber) in hybrid methods that use both a classical scheme and the post-quantum scheme. PQShield and other organisations are developing libraries and implementations for PQC. 

PQC as a whole is only going to accelerate. NIST’s timeline deprecates many elliptic curve and RSA methods in 2030 and disallows them entirely in 2035. Companies and public bodies relying on disallowed methods will no longer be compliant with NIST standards and they’ll suffer consequences. They won’t be eligible for some government and private contracts, their risk rating might change and insurance might cost more. Expect widespread adoption of the NIST protocols in the next few years, but remember that adoption does not guarantee security. 

There appears to be no drought in the industry-wide torrent of announcements that started with Google’s Willow in December 2024. 

PsiQuantum announced a new chipset and released a paper with new optimizations and resource estimations for Shor’s algorithm. The chipset, Omega, is the first public hardware release from PsiQuantum since being founded in 2016. The reported qubit quality is worse than trapped ions, but still good. They report 99.98% single-qubit fidelity and 99.22% two-qubit fidelity. Trapped ions currently achieve 99.9992% single-qubit and 99.97% two-qubit fidelities. 

Manufacturing might be the most interesting part of PsiQuantum’s chips. They are using semiconductor fab processes to produce millions of chips, in partnership with Global Foundries. This is good, but they may be bottlenecked by individual qubit quality and the quality of the connections between individual chips before they can benefit from manufacturing chips at scale and connecting them together to build a large-scale computer. 

On the theoretical side, their work on Shor’s algorithm will be useful for everybody in quantum computing. The main result is a 10x reduction in the number of gates required to run the algorithm. The practical impact of this is that the same number of logical qubits are needed to run Shor’s algorithm, but we might be able to use less physical qubits per logical qubit. 

Generally, an algorithm with a higher gate count takes longer and needs logical qubits that stay coherent for longer durations. The logical qubits need to be resistant to errors for as long as they are being used in the algorithm. How do you make them last longer? Use more physical qubits in the error correcting code that makes up the logical qubit. By lowering gate count, PsiQuantum indirectly reduces the total number of physical qubits required to run Shor’s algorithm. 

As an aside, PsiQuantum arrive at their estimates for gate count, qubit count and runtime through resource estimation. This is how we answer the question: “Without having a quantum computer, what sort of quantum computer is required to run this algorithm and what time, qubit and gate resources are required?” Any useful quantum algorithm will be, by definition, impractical to simulate on classical computers, so we need estimation techniques. This helps anybody interested in algorithms to predict how their algorithms will perform on a quantum computer, measure the impact of optimizations and compare requirements against current and predicted capabilities. 

For new readers, we are an applied quantum computing and cryptography group, working to protect Bitcoin and other systems from quantum attacks. 

Until next time, 

The Project Eleven Team 

P.S. Check if your browser is quantum-secure at projecteleven.com

Links

PQC 

PsiQuantum