Overview of quantum computing and post-quantum cryptography
Current quantum processors operate at roughly 1,000 physical qubits, far below the capacity needed to break public-key cryptosystems like RSA. However, recent theoretical and hardware breakthroughs have reduced the machine size required for an attack, shortening deployment timelines. In response, standardisation authorities have released post-quantum algorithms to counter threats like harvest-now, decrypt-later operations before cryptographically relevant quantum machines emerge.
Key facts
- Current quantum computing hardware is limited to roughly 1,000 physical qubits, while compromising modern public-key encryption is estimated to require approximately 500 times that capacity [1].
- Research indicates that the size of a quantum computer posing a cryptographic threat is roughly 20 times smaller than previous estimates, and fewer physical qubits are required per logical qubit [2][3].
- Established public-key cryptosystems like RSA and elliptic curve cryptography are secure against classical supercomputers but remain vulnerable to large quantum computers [4].
- Peter Shor's mid-1990s quantum algorithm established the theoretical mechanism capable of breaking modern public-key encryption schemes [5].
- Adversaries can carry out "harvest now, decrypt later" campaigns by intercepting and storing encrypted traffic today to decrypt once quantum processors become operational [6].
- In August 2024, the National Institute of Standards and Technology issued three post-quantum cryptographic standards—FIPS 203, FIPS 204, and FIPS 205—with FIPS 206 scheduled for late 2024 [7][8][9].
- Post-quantum algorithms generally perform faster computations than legacy schemes, but they demand significantly larger keys, ciphertexts, and digital signatures [10].
- The United States government has designated 2035 as the target year for completing the migration of its national security systems to post-quantum cryptography [11].
Current State and Scaling of Quantum Hardware
Current quantum computing hardware remains constrained in size and capability [1]. The largest existing quantum processors consist of approximately 1,000 physical qubits [1]. To pose an active threat to deployed public-key infrastructure, an attacker would require a quantum computer roughly 500 times larger than these current machines [1].
Despite this hardware gap, theoretical and engineering developments have accelerated estimated risk timelines [2][3]. A whitepaper published by Google Quantum AI showed that the size of a quantum computer needed to pose a cryptographic threat is approximately 20 times smaller than previously established estimates [2]. Concurrently, quantum hardware engineering has improved, significantly reducing the number of physical qubits required to produce a functional logical qubit [3].
Most experts project that large-scale quantum computers capable of breaking modern standards will not be constructed for at least another decade [12]. In the near term, the probability of a quantum computer successfully executing a cryptographic attack within three years is evaluated as less than one percent [13]. Over a timeline of five to ten years, however, the probability increases to an estimated five to ten percent or higher, prompting security experts to treat the risk as an urgent issue [14].
Cryptographic Vulnerabilities and Attack Vectors
The vulnerability of modern public-key encryption to quantum computation was first demonstrated in the mid-1990s, when Peter Shor developed a quantum algorithm capable of breaking modern cryptography schemes [5]. Widely deployed online security algorithms, specifically RSA and elliptic curve cryptography, are uncrackable by classical supercomputers [4]. However, a sufficiently large quantum computer would rapidly defeat both mechanisms [4]. RSA security depends on the mathematical difficulty of calculating the prime factors of large numbers on classical machines, an operation that large quantum computers would execute easily [15]. Elliptic curve schemes protect web browser and server traffic, cryptocurrencies, military encryption, and national security systems [4][16].
Cryptographic vulnerability creates immediate exposure through data harvesting strategies [6]. Hostile actors can intercept and store encrypted internet traffic today and retain it until a sufficiently capable quantum computer becomes available to decrypt it [6]. This intercept-and-store approach, termed "harvest now, decrypt later," threatens the confidentiality of sensitive data well before functional quantum decryption hardware exists [6]. In addition, many devices that rely on RSA security, such as connected automobiles and internet-of-things hardware, are expected to remain in active field operation for at least a decade [17]. As a result, these systems must incorporate quantum-resistant cryptography prior to deployment [17]. Recognizing the extended timelines required to upgrade critical systems, the United States government established 2035 as its target date for migrating all national security systems to post-quantum cryptography [11].
Standardization of Post-Quantum Algorithms
To replace vulnerable public-key mechanisms, the National Institute of Standards and Technology launched a public competition for quantum-safe algorithms in 2016 [18]. The standardization process organized candidate algorithms into two primary functional categories: key-establishment schemes and digital signature algorithms [19][20]. Key-establishment algorithms allow two parties communicating without prior contact to agree on a shared secret across public networks [19]. Digital signatures ensure the authenticity of data, providing critical integrity verification for code-signing operations to confirm software originates from legitimate developers rather than attackers [20].
In August 2024, NIST announced the standardization of three post-quantum cryptographic schemes, encouraging system administrators to initiate transitions immediately [7]. The winning algorithms, initially selected from competition rounds as CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, and FALCON, were transitioned into formal standards designated as FIPS 203 through FIPS 206 [8]. NIST finalized FIPS 203, FIPS 204, and FIPS 205, with FIPS 206 scheduled for standardization in late 2024 [9].
FIPS 203 and FIPS 204, along with the forthcoming FIPS 206, are constructed on lattice cryptography [21]. Lattice cryptography is based on finding the lowest common multiple among a set of numbers, which is formulated across multiple dimensions as a vector on a lattice [21]. In contrast, FIPS 205 is grounded in hash functions, which convert data into encrypted strings that cannot be readily reversed [22]. Concerns arose regarding lattice schemes after a preprint claimed lattice cryptography was not immune to quantum attacks, but scrutiny revealed an error in the paper's mathematical argument, affirming that lattice cryptography remains secure against quantum computers [23].
Performance Trade-Offs and Hardware Integration
Post-quantum cryptography exhibits markedly different operational characteristics compared to legacy public-key protocols [10][24]. While mathematical computations in post-quantum schemes are typically faster than RSA, the resulting public keys, ciphertexts, and digital signatures are significantly larger [10][24]. Larger data sizes pose bandwidth and transmission challenges across communications networks where throughput is limited [24]. In blockchain and cryptocurrency environments, where transaction space on the ledger carries a substantial cost premium, accommodating these expanded cryptographic payloads requires restructuring how protocols integrate security [10][25].
Hardware constraints are particularly pronounced in embedded architectures such as low-power internet-of-things devices [26]. Microprocessor implementations of early NIST lattice candidates identified two primary operational bottlenecks: random number generation and data storage [26]. In lattice-based systems, generating cryptographically secure random numbers through sampling consumes approximately 80 percent of the circuit's total computation energy [27]. Furthermore, storing and processing large vector data structures requires physical memory that traditionally occupies around 80 percent of a circuit's hardware footprint [28]. To address this constraint, researchers engineered customized architectures using a modified number theoretic transform that splits vector data across four single-port RAM devices, reducing memory area by roughly one-third relative to multiport memory while preserving required data throughput [29].
Beyond hardware optimization, systemic deployment presents extensive organizational obstacles [30]. The computing industry has navigated only one or two foundational cryptographic transitions since the late 1970s and lacks a standardized mechanism for executing cryptographic migration [30].
Sources
-
Post Quantum Cryptography Just Got a Lot More Urgent spectrum.ieee.org
- [1]
The largest machines currently consist of approximately 1,000 quantum bits, or qubits, and the whitepaper estimated that about 500 times as much is needed.
- [2]
In it, the team showed that the size of a quantum computer that would pose a cryptographic threat is approximately 20 times smaller than previously thought.
- [3]
The claim here was that the number of physical qubits needed to achieve a certain kind of logical qubit was also greatly reduced.
- [4]
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.
- [10]
Keys and cipher texts and digital signatures are all significantly larger in post-quantum cryptography, but the computations are actually faster, typically.
- [11]
The U.S. government has put 2035 as its target for migrating all of the national security systems to post-quantum cryptography.
- [13]
the chance of a cryptographic attack by quantum computers being successful in the next three years is extremely low, maybe less than a percent.
- [14]
as you get out to several years, like five, six, or 10 years, one has to seriously consider a probability, maybe 5 percent or 10 percent or more.
- [16]
Versions of elliptic curve cryptography are used in national security systems and military encryption.
- [25]
Especially in blockchain applications, like cryptocurrencies, space on the blockchain is at a premium.
- [30]
We’ve only had one or maybe two major transitions in cryptography since the early 1980s or late 1970s, when the field first was invented. We don’t really have a systematic way of transitioning cryptography.
- [1]
-
Securing the “internet of things” in the quantum age news.mit.edu
- [5]
In the mid-1990s, MIT Professor Peter Shor developed a quantum algorithm that can essentially break through all modern cryptography schemes.
- [26]
In the new study, the researchers first implemented on commercial microprocessors several NIST lattice-based cryptography schemes from the agency’s first phase. This revealed two bottlenecks for efficiency and performance: generating random numbers and data storage.
- [27]
This difficult mathematical problem consumes about 80 percent of all computation energy needed for lattice-based cryptography.
- [28]
Storing and moving those data requires physical memory components that take up around 80 percent of the hardware area of a circuit.
- [29]
The modified NTT splits vector data and allocates portions across four single-port RAM devices. Each vector can still be accessed in its entirety for sampling as if it were stored on a single multiport device. The benefit is the four single-port REM devices occupy about a third less total area
- [5]
-
Post-Quantum Cryptography Standard is Here spectrum.ieee.org
- [6]
Second, a nefarious individual could potentially download and store encrypted data today, and decrypt it once a large enough quantum computer comes online. This concept is called “ harvest now, decrypt later “ and by its nature, it poses a threat to sensitive data now
- [7]
Today, the U.S. National Institute of Standards and Technology (NIST) announced the standardization of three post-quantum cryptography encryption schemes.
- [8]
These four winning algorithms had intense-sounding names: CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, and FALCON. Sadly, the names did not survive standardization: The algorithms are now known as Federal Information Processing Standard (FIPS) 203 through 206.
- [9]
FIPS 203, 204, and 205 are the focus of today’s announcement from NIST. FIPS 206, the algorithm previously known as FALCON, is expected to be standardized in late 2024.
- [12]
Most experts believe large-scale quantum computers won’t be built for at least another decade.
- [15]
This scheme is based on a simple fact—it is virtually impossible to calculate the prime factors of a large number in a reasonable amount of time, even on the world’s most powerful supercomputer. Unfortunately, large quantum computers, if and when they are built, would find this task a breeze
- [17]
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.
- [18]
NIST announced a public competition for the best PQC algorithm back in 2016.
- [21]
Two out of the three schemes already standardized by NIST, FIPS 203 and FIPS 204 (as well as the upcoming FIPS 206), are based on another hard problem, called lattice cryptography.
- [22]
The third standardized scheme, FIPS 205, is based on hash functions —in other words, converting a message to an encrypted string that’s difficult to reverse
- [23]
The paper, authored by Yilei Chen of Tsinghua University in Beijing, claimed to show that lattice-based cryptography, the basis of two out of the three NIST protocols, was not, in fact, immune to quantum attacks. On further inspection, Yilei Chen’s argument turned out to have a flaw
- [6]
-
How the United States Is Developing Post-Quantum Cryptography spectrum.ieee.org
- [19]
The first category includes key-establishment algorithms that enable two parties that have never met to agree on a shared secret.
- [20]
A second category involves algorithms for digital signatures that ensure the authenticity of data. Such digital signatures feature in code-signing applications that establish confidence that a program was created by the intended developer and not by a hacker.
- [24]
Lattice-based cryptography is even faster than modern cryptographic approaches such as RSA, but its bigger data size could make a difference if bandwidth is relatively scarce.
- [19]