Overview of quantum computing and post-quantum cryptography

Contemporary quantum computers have reached approximately 1,000 qubits, leaving them far short of the scale required to break classical public-key cryptography. However, recent algorithmic and hardware advancements have lowered the threshold for threatening RSA and elliptic curve protocols, elevating urgency across cybersecurity. In response, organizations have begun standardizing and deploying post-quantum cryptographic schemes to counteract emerging risks, including retrospective decryption.

Key facts

• The largest quantum machines currently consist of approximately 1,000 quantum bits, or qubits, and a whitepaper estimated that about 500 times as much is needed ^[1].
• A whitepaper published by the team at Google Quantum AI showed that the size of a quantum computer that would pose a cryptographic threat is approximately 20 times smaller than previously thought ^[2].
• A concurrent paper showed that hardware was substantially improved, claiming that the number of physical qubits needed to achieve a certain logical qubit was greatly reduced ^[3].
• Most experts believe large-scale quantum computers will not be built for at least another decade ^[4].
• Algorithms commonly used today to protect data online—RSA and elliptic curve cryptography—are uncrackable by supercomputers, but a large enough quantum computer would make quick work of them ^[5].
• Today, almost all data on the internet, including bank transactions, medical records, and secure chats, is protected with RSA ^[6].
• A nefarious individual could potentially download and store encrypted data today and decrypt it once a large enough quantum computer comes online ^[7].
• This concept is called “harvest now, decrypt later” and poses a threat to sensitive data now, even if that data can only be cracked in the future ^[8].
• Four winning algorithms from NIST's competition are now known as Federal Information Processing Standard (FIPS) 203 through 206 ^[9].
• The U.S. government has put 2035 as its target for migrating all of the national security systems to post-quantum cryptography ^[10].

Current Scale of Quantum Hardware and Threat Timelines

The largest machines currently consist of approximately 1,000 quantum bits, or qubits, and a whitepaper estimated that about 500 times as much is needed ^[1]. Late last month, the team at Google Quantum AI published a whitepaper showing that the size of a quantum computer that would pose a cryptographic threat is approximately 20 times smaller than previously thought ^[2]. In addition, a concurrent paper showed that the hardware itself was substantially improved, claiming that the number of physical qubits needed to achieve a certain logical qubit was also greatly reduced ^[3].

Most experts believe large-scale quantum computers will not be built for at least another decade ^[4]. The chance of a cryptographic attack by quantum computers being successful in the next three years is considered extremely low, maybe less than a percent ^[11]. However, as time extends out to several years, like five, six, or 10 years, one has to seriously consider a probability of maybe 5 percent or 10 percent or more ^[12].

Vulnerability of Legacy Public-Key Cryptography

The algorithms that are commonly used today to protect data online—RSA and elliptic curve cryptography—are uncrackable by supercomputers, but a large enough quantum computer would make quick work of them ^[5]. Today, almost all data on the internet, including bank transactions, medical records, and secure chats, is protected with an encryption scheme called RSA ^[6]. This cryptography is also used for secure web connections between web browsers and web servers, while versions of elliptic curve cryptography are used in national security systems and military encryption ^[13].

First, many devices that use RSA security, like cars and some IoT devices, are expected to remain in use for at least a decade, so they need to be equipped with quantum-safe cryptography before they are released into the field ^[14]. Second, a nefarious individual could potentially download and store encrypted data today, and decrypt it once a large enough quantum computer comes online ^[7]. This concept is called “harvest now, decrypt later” and by its nature poses a threat to sensitive data now, even if that data can only be cracked in the future ^[8].

Post-Quantum Cryptography Standardization and Algorithms

NIST announced a public competition for the best post-quantum cryptography algorithm in 2016, receiving 82 submissions from teams in 25 different countries, and went through four elimination rounds before whittling the pool down to four algorithms in 2022 ^[15]. These four winning algorithms—CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, and FALCON—are now known as Federal Information Processing Standard (FIPS) 203 through 206 ^[9]. FIPS 203, 204, and 205 were the focus of an announcement from NIST, while FIPS 206, the algorithm previously known as FALCON, is expected to be standardized in late 2024 ^[16].

Digital signatures are essential for preventing malware attacks ^[17]. Two of the three schemes standardized by NIST, FIPS 203 and FIPS 204, as well as the upcoming FIPS 206, are based on lattice cryptography ^[18]. Lattice cryptography rests on the tricky problem of finding the lowest common multiple among a set of numbers, which is usually implemented in many dimensions, or on a lattice, where the least common multiple is a vector ^[19]. The third standardized scheme, FIPS 205, is based on hash functions, converting a message to an encrypted string that is difficult to reverse ^[20]. There are three levels of security for each protocol, designed to future-proof the standards in case some weaknesses or vulnerabilities are found in the algorithms ^[21]. Earlier in the year, a pre-print published to arXiv by Yilei Chen of Tsinghua University in Beijing alarmed the community by claiming that lattice-based cryptography, the basis of two of the three NIST protocols, was not immune to quantum attacks ^[22]. On further inspection, Yilei Chen's argument turned out to have a flaw, and lattice cryptography is still believed to be secure against quantum attacks ^[23].

Practical Engineering Challenges and Implementation Frameworks

Keys and cipher texts and digital signatures are all significantly larger in post-quantum cryptography, but the computations are actually faster, typically ^[24]. The cryptocurrency Algorand jumped 44% in price after the whitepaper called out Algorand specifically for implementing post-quantum cryptography on their blockchain ^[25]. Historically, cryptography is very hard to change, with only one or two major transitions occurring since the field was invented in the late 1970s or early 1980s ^[26]. To address migration timelines, the U.S. government has put 2035 as its target for migrating all of the national security systems to post-quantum cryptography ^[10].

A Systematisation of Knowledge study synthesised 33 publications and analysed post-quantum cryptography implementation approaches and challenges using a Human, Organisational, and Technological perspective ^[27]. The analysis identified four approach categories: guidelines, frameworks, tools and libraries, and educational interventions ^[28]. Technological support receives greater representation in the extracted mapping, while no approach is classified primarily as organisational, despite secondary organisational contributions in some approaches ^[29]. The challenge synthesis identified five layers covering implementation security, system integration and lifecycle, tooling, organisational governance, and human factors ^[30].