This is a summary of the talk “Quantum Computers vs. Computers Security”, given at the DEF CON 23 Hacking Conference in Las Vegas in August 2015 by Kudelski Security Principal Cryptographer, Jean-Philippe Aumasson.
Increasing numbers of cybersecurity experts and stakeholders are watching developments closely in the field of quantum computing. A quantum computer is a model of a computer that works completely differently from a classical one. It’s based on phenomena of quantum mechanics that facilitate the resolution of certain problems that classical computers cannot solve, e.g. breaking the crypto used for e-commerce transactions. How does a quantum computer work? Although it leverages complex quantum mechanical phenomena, the core concepts are pretty simple:
- Whereas a classical computer works on bits that are either 0 or 1, a quantum computer works on qubits, which can be 0 and 1 simultaneously. In quantum physics, this is called superposition.
- Superposition is characterized by some probabilities, but not the usual ones: a quantum computer relies on negative probabilities, which are called amplitudes.
- The actual computation is not performed with usual computer operations such as addition or bitwise logic, but uses basic linear algebra transformations, similar to operations between vectors and matrices like in high school physics.
The good (or bad) news is that quantum computers don’t exist yet. Building a quantum computer is a gigantic and fascinating engineering challenge, and we don’t know for sure if it’s even doable. There’s been some progress over the last decade, and some large companies are investing in quantum computing research – but don’t expect a useful quantum computer within the next decade! Cryptographers obviously pay special attention to quantum computing research. A large enough quantum computer could totally break the RSA and Diffie-Hellman cryptographic algorithms, and more generally, all cryptography based on the mathematical problems of factoring integers (such as RSA) and of solving discrete logarithms (such as Diffie-Hellman and elliptic curve cryptography). In short, if a quantum computer is created today, we’re doomed! But there’s hope: the field of post-quantum cryptography is about creating cryptographic systems that can resist quantum computers. These experimental systems are based on different mathematical problems that are expected to be hard for both classical and quantum computers to solve. One such family of hard problems is that of NP-complete problems, which occurs in many contexts. For example, the problem of finding the optimal scheduling of a group of events is NP-complete. And quantum computers cannot solve NP-complete problems. Quantum physics has more potential applications to cybersecurity than of just breaking crypto:
- Quantum key distribution establishes a secure link between two systems, leveraging quantum physics laws to prevent eavesdropping. Such systems are practical and are being deployed, though their actual added value in terms of security is sometimes disputed.
- Quantum money uses the physical “no-cloning” principle to prevent counterfeiting. Quantum money is only a theoretical idea, and seems difficult to put in practice.
- Quantum machine learning is an emerging field that attempts to leverage quantum computers to improve the efficiency of machine learning algorithms.