If there is a boogeyman for encryption it’s quantum computing. Industry discussions border on hysteria when discussing quantum-proof encryption because the idea of computers so powerful they could break all current encryption standards in a few seconds is incredibly frightening. The era of quantum computing is here and there is no escaping the fact we only have decades before current encryption is potentially as good as the Caesar Cypher.
Current encryption is safe and here’s how it will stay that way
Google announced quantum supremacy in 2019 and published a paper in Nature explaining the feat. Although it’s an amazing computing achievement, the fastest quantum computers are still not capable of foiling today’s encryption. This is the most important part to remember about quantum computing: we know quantum computers will eventually be fast and powerful enough to decrypt messages, and quantum-proof encryption would be required, but they aren’t there yet.
However, scientists and cryptographers are planning ahead. The U.S. National Institute of Standards and Technology (NIST) started a competition in 2016 to look for new quantum-proof encryption methods. And recently the field has diminished from 69 encryption developers to just 15. Right now, it looks like the quantum savior could be lattice-based cryptography:
“While quantum machines are still a long way from being able to break modern encryption, NIST launched a competition in 2016 to develop new standards for cryptography that will be more quantum-proof. The race is long, with the winners set to be announced in 2022, but last week the organization announced that it had narrowed the initial field of 69 contenders down to just 15.
Via: The quest for quantum-proof encryption just made a leap forward | MIT Technology Review
And so far a single approach to ‘post-quantum cryptography’ accounts for the majority of the finalists: lattice-based cryptography.”
Is Lattice-Based Cryptography the answer for quantum-proof encryption?
Unlike traditional cryptography, including elliptic curve cryptography (ECC), which uses regular math, lattice-based cryptography uses a path through a lattice of billions of points to create keys. If you don’t know the path, you can’t get the answer. Even the NSA thinks lattice-based cryptography is a good direction to head in our post-quantum world. It’s the sheer complexity of a multidimensional grid of points that make it hard for quantum computers to solve the puzzle.
But there’s a catch: Effective post-quantum encryption needs to be fast to be functional.
Effective encrypted communications
One of the reasons ECC is used by us and other encrypted cell phone solutions is because the speed & security of encryption and decryption of data requires small key sizes. This is because the larger the key size, the ‘heavier’ the encrypted text becomes, so the more processing power and memory are needed, and the harder it is for mobile devices to cope.
Smartphone secure messaging app functionality
For something like a smartphone secure messaging app, you need an efficient and relatively lightweight system so there isn’t a lag between typing a message, encrypting the message, sending the message, receiving a message, and decrypting a message. Imagine how annoying it would be if you typed a message and it took 5 seconds to encrypt it, another 5 seconds to send it, and when the return message came back the same extra 10 seconds receive and decrypt the message.
ECC is a powerful choice for securing your phone
Striking a balance between efficacy and speed is why ECC is perfect for mobile devices because you can achieve strong encryption with small key sizes which means lower computational overhead.
To understand the key sizes relative to encryption standards:
With 521-bit ECC you have the equivalent of a 15,360-bit RSA key in a data package that mobile devices can handle.
Encryption functionality across a variety of devices
This is the additional challenge to finding quantum-proof encryption—it must be practical for cell phones including tiny mobile devices, like medical equipment that have only tiny amounts of memory, processing power, and storage space to work with:
“However, it’s not just how impenetrable or complex the math is that counts. Post-quantum approaches will only work if they can be used in all the places that high-level cryptography will be needed. For example, the size of the key required to decrypt data is important: imagine what will be possible inside a piece of medical equipment that has little memory and severely limited bandwidth. If the math is so complex that opening the lock requires a massive key, the solution may not pass the usability test.”
Patrick Howell O’Neill, MIT Technology Review. August 3, 2020
Post-Quantum Encryption requires advocacy
While quantum computing is technically here, even the best machines can’t solve “useful” problems yet so quantum-proof encryption is still some while away. The incredible promises of the quantum computing future, including rapid advances in medical research and drug trials, are not feasible yet.
“The next step is quantum computers solving a useful problem, which they haven’t done yet…. If that doesn’t happen for a long time, I think companies will forget the hype and implement the weakest thing that comes out of NIST until they are suddenly reminded of the problem in 30 years.”
Vadim Lyubashevsky in MIT Technology Review
This work led by NIST is essential to our future security, even if the threat seems a long way off. Don’t forget the internet itself is only 50 years old, and the web not even 30, and in this time we’ve increased what we considered “good enough encryption for banking” a couple of times (128-bit used to be okay, now 256-bit is the minimum standard). We can’t afford to ignore the issue and assume it will be forthcoming.
Putting the impact of quantum-computing on encryption into perspective
A quick Google search on ECC and quantum resistance turns up results that sound ominous, but aren’t once you start scratching the surface. By pure math, Shor’s algorithm can be used by a quantum computer to find the right key to decrypt the message, however:
“Shor’s Algorithm can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion Toffoli gates. In comparison, using Shor’s Algorithm to break the algorithm requires 4098 qubits and 5.2 trillion Toffoli gates for a 2048-bit RSA key, suggesting that ECC is an easier target for quantum computers than RSA. All of these figures vastly exceed any quantum computer that has ever been built, and estimates place the creation of such computers as a decade or more away.”
Elliptic-curve cryptography – Wikipedia
There’s a big difference between possible, probably, and practical. Right now, we know that it’s possible, but we’re a long way off from probable or practical because the largest quantum computer right now is only 53 qubits which is far short of the 2330 qubits required to have a chance at breaking ECC encryption.
Encryption keys are the answer
When we talk about computers “breaking encryption” we’re not actually talking about any computer looking at a stream of ciphertext and figuring out what the message is simply through guesswork. That’s a misconception. What computers are actually trying to do is find the private key used to encrypt the message in the first place. A computer is actually searching for the extremely long number which, when punched into the equation, will encrypt/decrypt the right result. As a result, it’s the discrete logarithm problem that the computer is trying to solve for, not actually “break the encryption” itself.
Even cracking the Enigma code wasn’t about breaking the encryption by brute force guessing—which is considered even today to be nearly impossible. The key to “cracking the enigma code” was finding the settings used on the Enigma machines that day to encrypt the messages. And that was only possible because they knew a certain message, sent nearly every day, started with the same text.
Effective security protocols ultimately support encrypted communication
The better your password, the larger the encryption key and the harder it is for any computer to make that guess and find the right number.
All strong encryption—including SKY ECC—would need a supercomputer cranking away at a message for several billion years to find the right answer.
By that time, I don’t think anything we’ve said today will be of interest to anyone.
