I recently had the opportunity to talk about post-quantum at the NewCrafts conference in Paris. My goal was to give an introduction to the topic of quantum computing and its impacts on cryptography.
We’ve been interested in the topic for a while at Dashlane. You can refer to our previous blog articles, such as An Update on Post-Quantum Work at Dashlane, as well as our first explorations and the post-quantum cryptography playground we built, which you can find on Github.
So, let's dive into it.
What is a quantum computer?
We should start with some basic information about quantum computers: a quantum computer is a machine that performs calculations based on the laws of quantum mechanics, which is the behavior of particles at the subatomic level.
Unlike traditional computers, quantum computers rely on quantum-specific mechanics and some specific behaviors of subatomic particles. (Traditional transistors rely on these mechanics as well, but quantum computers use other properties of the matter.)
Quantum computers handle information in a very different way from classical computers. Instead of relying on transistors, which can only represent either the “0” or the “1” of binary information at a single time, quantum computers use qubits, which can represent both 0 and 1 simultaneously.
Where classical computers use familiar silicon-based chips, qubits (sometimes called "quantum computer qubits") can be made from subatomic particles and use quantum-specific mechanics with cool names like “supra conductors,” “trapped ions,” “photons,” artificial or real atoms or quasiparticles.
Depending on the architecture and qubit systems, some implementations need their qubits to be kept at temperatures close to absolute zero. The need to control the temperature is one of the reasons that makes quantum computers really hard to build, use, and maintain today.
These qubits also make many errors (mostly because of the noise of the real world, like magnetic fields, temperature changes, etc.), so many error correction mechanisms are needed. Finding skillful solutions to those problems is part of what keeps the companies building those computers so busy (for example, IBM, Google, and Alice & Bob in France).
Qubits vs. Bits
A qubit uses the quantum mechanical phenomena of superposition to achieve a linear combination of two states. A classical binary bit can only represent a single binary value, such as 0 or 1, meaning that it can only be in one of two possible states.
Unlike a classical binary bit, a qubit can represent a 0, a 1, or any proportion of 0 and 1 in a superposition of both states, with a certain probability of being a 0 and a certain probability of being a 1.
Superposition allows quantum algorithms to process information in a fraction of the time that it would take even the fastest classical systems to solve certain problems.
Information that 500 qubits can easily represent would not be possible with even more than 2^500 classical bits. It would take a classical computer millions of years to find the prime factors of a 2,048-bit number. Qubits could perform the calculation in just minutes.
What about quantum computing and cryptography?
Thanks to quantum computing, two main algorithms could threaten existing cryptography:
- Shor's algorithm for factoring integers and solving discrete logarithms
- Grover's search, which can invert a black-box function
The first algorithm was developed in 1994 by the American mathematician Peter Shor. This algorithm is a method to leverage quantum computing power to find the prime factors of an integer much faster, which is at the heart of some cryptography, such as RSA and Diffie-Hellman public-key algorithms. If a quantum computer could operate with a sufficient number of qubits, then theoretically Shor's algorithm could be used to break those public-key cryptography schemes. In the past 30 years, other mathematicians have iterated on Shor’s algorithm to make it even faster and more resilient.
The second algorithm was devised by Lov Grover, another American computer scientist, in 1996. Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm used for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value. In cryptography, Grover's algorithm essentially solves the task of function inversion. Roughly speaking, Grover's algorithm can speed up many kinds of brute-force attacks on symmetric-key cryptography, but the improvement is only quadratic (where it’s exponential for Shor), i.e., AES256 can be simplified as AES128 using Grover’s algorithm.
Risk of cryptography
Let's go into some more details:
- Asymmetric encryption and key agreement use a private/public key pair to establish a key that can then be used for symmetric cryptography. Shor's algorithm impacts them, and they are vulnerable to store-now-decrypt-later attacks.
- Digital signatures use a private/public key pair to authenticate data and provide non-repudiation. Shor's algorithm impacts them, but they aren’t vulnerable to store-now-decrypt-later attacks.
- "Fancy" cryptography: This category depends on the specific algorithm and use case, but many privacy-preserving techniques (e.g., blind signatures, OPRF) will be impacted by Shor's algorithm, and are partially vulnerable to store-now-decrypt-later. Many of these techniques require further research. We recommend carefully assessing the impact of quantum threats on these schemes.
- Symmetric cryptography, using a single secret key to encrypt and authenticate data: Our current understanding is that quantum computers don’t impact symmetric cryptography for all practical purposes. Grover's algorithm could be used as an attack here, but is currently considered infeasible for even medium-term quantum computers.
The store-now-decrypt-later attack
“If we do not encrypt our data with a quantum-secure algorithm now, an attacker who is able to store current data will be able to decrypt it in as soon as a decade.” - Google
No known quantum computer today is capable of leveraging quantum algorithms to break the current cryptographic mechanisms.
However, the “store-now-decrypt-later” attack is the main motivator behind the need for post-quantum cryptography (PQC) to protect today’s data from future attacks.
There is a high probability that malicious actors, whether state-sponsored or not, are already harvesting and collecting encrypted sensitive data to break it in the future.
That’s why quantum computing is a threat today and requires a well-thought-out plan for migrating our current, classical cryptographic algorithms to PQC.
Quantum Threat timing: Q-Day
There is no consensus on when large quantum computers will be able to break encryption algorithms. This so-called Q-Day is expected to happen sometime between 10–15 years. But as quantum computers become exponentially faster, that timeline may be accelerating.
Only several years ago, quantum computers could only achieve a few qubits. Today in 2024, IBM’s Condor announced targeting over 1,000 qubits.
We don’t exactly know today how many qubits would be required to break RSA, and it’s important to remember that pure qubit power is not enough. To achieve this, you also need quantum computers that are stable and coherent enough for the task.
Nevertheless, the timeline is somewhat irrelevant due to the store-now-decrypt-later attack.
Post-Quantum Cryptography (PQC)
That's why organizations like the National Institute of Standards and Technology (NIST) in the U.S. are actively working on Post-Quantum Cryptography. The NIST has been running a competition to evaluate new post-quantum algorithms that could allow us to protect today's data against the future quantum threat.
We're in the final phase of the competition and expected to have winners by mid-2024, which will then be considered for standardization. No matter which algorithm wins the competition, we expect it will take many more years for those new post-quantum algorithms to mature.
| Finalists | Alternates | |
| KEMs/Encryption | Kyber NTRU SABER Classic McEliece | Bike FrodoKEM HQC NTRUprime SIKE |
| Signatures | Dilithium Falcon Rainbow | GeMSS Picnic SPHINCS+ |
TLS, the standard used to secure connections, most notably HTTPS for web communications, is based on Diffie-Hellman and ECC. As such, this standard needs to be protected as well. The Hybrid Key Exchange in TLS 1.3 entails the utilization of multiple key exchange algorithms, incorporating at least one classical and one post-quantum key exchange algorithm, to maintain the protocol's future security.
Crypto Agility and Hybridization
To prepare for the quantum threat, organizations need to achieve what is called “crypto agility.”
You need the ability in your systems to support multiple cryptography algorithms easily so you can ensure hybridization, which means supporting multiple ciphers in parallel, both pre-quantum and post-quantum cryptography.
This isn’t easy to achieve. Cryptography is fundamental to many of our implementations and is very sensitive.
Migrations to support crypto agility must be well-designed and well-thought-out.
Dashlane started evolving our cryptography primitives in 2018, moving from PBKDF2 to Argon2 for the derivation of the master passwords. Because of the inherent complexity of this migration, it took multiple years to migrate all our web and mobile customers. This journey allowed us to become crypto-agile and be ready for future hybridization with post-quantum cryptography.
What should you be doing today?
This doesn't impact all organizations the same way.
- Educate yourself
- Evaluate your use of cryptography.
- Prepare by introducing crypto agility in your systems
- Plan to start transitioning to hybrid mechanisms as soon as possible
This summary was written thanks to some of the following references, we encourage you to look at:
- 2023 Quantum Threat Timeline Report - Global Risk Institute
- Shor algorithm vulgarization: How Shor's Algorithm Factors 314191
- Blog: Google's Threat model for Post-Quantum Cryptography
- The state of the post-quantum Internet
- ANSSI views on the Post-Quantum Cryptography transition
- Q-Day and the Quantum Troll
- Quantum Computers Vs Classical Computers - What's the difference?
Want to learn more about how Dashlane can help your business stay secure in today’s evolving cyber culture? Read the latest blog, “Saying Goodbye to the Last Password.”
Sign up to receive news and updates about Dashlane
Thanks! You're subscribed. Be on the lookout for updates straight to your inbox.
