Today’s encryption methods are generally broken down into two types: symmetric and asymmetric. Symmetric encryption relies on the sender and receiver to have identical, secret cryptographic keys that are used to encrypt the data at the sender and decrypt it at the receiver. Asymmetric or “public-key” encryption instead uses a publicly-available key to let senders encrypt data to a recipient who has the private key required for decryption. Often, these are used together: the HTTPS protocol in your web browser is an example of a real-world deployment of combined symmetric and asymmetric cryptography.
These types of encryption are generally well-suited to protect against attacks that run on today’s computers, especially when longer key pairs are used, such as 256-bit elliptic curve keys or 3072-bit RSA keys. With the best modern computer, it would likely take thousands of years for an adversary to determine the private keys by brute force.
But what happens when today’s computers give way to quantum computing?
First, a bit of background. Today’s computer’s run on bits of data that are firmly either a 1 or a 0. Quantum computers run on qubits, which can be in a quantum superposition of both states. A quantum computer with many qubits entangled together allows for a superposition of exponentially many states. That’s where quantum computers get their power: qubits lead to massive leaps in processing power. According to the MIT Technology Review, “A quantum machine with 300 qubits could represent more values than there are atoms in the observable universe”. The article goes onto state “Hackers are also likely to exploit quantum algorithms that optimize certain tasks. One such algorithm, published by Lov Grover of AT&T’s Bell Labs in 1996, helps quantum computers search possible permutations much faster. Another, published in 1994 by Peter Shor… helps quantum machines find the prime factors of integers incredibly fast. Shor’s algorithm poses a risk to public-key encryption systems such as RSA, whose mathematical defenses rely in part on how difficult it is to reverse-engineer the result of multiplying very large prime numbers together. A report on quantum computing published last year by the US National Academies of Sciences, Engineering, and Medicine predicted that a powerful quantum computer running Shor’s algorithm would be capable of cracking a 1,024-bit implementation of RSA in less than a day.”
While there is a not a consensus on exactly when quantum computing will be available to the masses, most estimates place this somewhere in the 2030s [MH: see eg the bet between @hashbreaker and @frhenr; unless you have a source that says sooner?]. While that seems like a long time off, critical infrastructure takes years to design, is deployed a decade, and transports data that must be kept secret for longer still. As quantum computing technology continues to advance, it’s incumbent upon cryptographers to create algorithms designed to secure data in the age of quantum computing and beyond.
An initial thought on how to further secure data some might have could certainly be to just keep increase the number of bits in a key. For instance, doubling the bit-depth of a key basically squares the number of possible permutations, theoretically then squaring the time it takes to be cracked. This is sufficient for symmetric algorithms, but it won’t protect RSA and ECC keys from Shor’s algorithm. As a company of cryptographers, Rambus Security knows this, and believes something more revolutionary (rather than evolutionary) is needed.
NIST (the National Institute of Standards and Technology) launched an initiative back in 2016 focused on developing standards for Post-Quantum Crypto for use by the government. Of 82 initial proposals, 26 have been chosen to proceed in round 2. Rambus is proud that the “Three Bears” key exchange algorithm, created at Rambus by Mike Hamburg, has been chosen to proceed.
While the final decision likely isn’t until 2022, we continue to develop our products and research technologies with the post-quantum world in mind.