Quantum-Proof Encryption: How much should you really prepare?

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.
And so far a single approach to ‘post-quantum cryptography’ accounts for the majority of the finalists: lattice-based cryptography.”

Via: The quest for quantum-proof encryption just made a leap forward | MIT Technology Review

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:

Encryption Table

With 521-bit ECC you have the equivalent of a 15,360-bit RSA key in a data package that mobile devices can handle.

secure cellphones rely on fast and effective encryption like ECDH
Photo by Maxim Ilyahov on Unsplash

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.

quantum-proof encryption is still in development and will be for a long while - SKY ECC
Photo by Jonas Leupe on Unsplash

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.

Asset 1

Protect Your Privacy with SKY ECC