jrswab

No-fluff tutorials and privacy-focused tools for the modern productivity-minded developer.

Encryption and Quantum Computers

Categories: [Technology]
Tags: [security], [privacy], [encryption]

Encryption becomes more of a backbone to our daily lives with every passing moment but what will happen when quantum computers are the norm?

What is Encryption

Put simply, Encryption is taking information and scrambling it, so it becomes gibberish. Turning this scrambled mess back into readable data can only be done through decryption.

To decrypt an encrypted file or message, you need the cipher. A cipher is usually a key that tells the user how to translate the original message from the gibberish.

The earliest cipher I am aware of is called the Caesar cipher. This is a shift cipher and one of the most accessible forms of encryption. This form of encryption was used to send secret messages around the world. If Caesar had a command for a general in a distant land, he would use a predetermined numb to shift each letter in the message.

For example, let's say Caesar and his General chose the number twenty-two in secret before parting ways to conquer the known world. Some time passes, and Caesar needs to tell the General to "grab the spoils and come home" but does not want that information to fall into the wrong hands.

By shifting the letters by the predetermined twenty-two, the message would now look like "cnwx pda olkeho wjz ykia dkia." Not very useful to an eavesdropper, but the General would know to count back twenty-two for each letter to learn what Caesar's message contained.

This method is straightforward to crack since language is predictable.

For the same reason we don't want to think up our own passwords, we would not choose to use a Caesar cipher today. Computers are very good at running millions of guesses per second and will crack the code very quickly.

Encryption and Quantum Computers

"Imagine a world where the most widely-used cryptographic methods turn out to be broken: quantum computers allow encrypted Internet data transactions to become readable by anyone who happened to be listening. No more HTTPS, no more PGP. It sounds a little bit sci-fi, but that’s exactly the scenario that cryptographers interested in post-quantum crypto are working to save us from." - hackaday.com

Any of the encryption methods based on factoring primes or doing modular exponentials is in trouble. This includes:

These are also the most currently used public-key cryptography methods today. RSA is the method that’s used in negotiating a TLS connection (the little green lock in your browsers' address bar).

Strong symmetric ciphers such as AES and Blowfish will also be easier to crack with quantum computers, but only by roughly a factor of two. So if you are happy with AES-128 today, all you will have to do is move to AES-256 in a quantum-computing future. After doing so, your security level will be the same as today.

Quantum computers have stirred up a good deal of buzz around the crypto space, which makes sense since our best crypto-systems depend on how hard the encryption is to crack. If a computer ends up breaking Bitcoin, then the value of that coin drops to zero overnight. This would have a significant effect on the entire ecosystem.

But is all lost?

I suggest reading Post-quantum RSA by Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta. However, it is a bit dense, so let's touch on some of the main points the authors bring up.

They estimate that attacking a terabyte-size key using Shor’s algorithm would require around 2^100 operations on a quantum computer. That's an enormous number! It's similar to the total number of bacterial cells on Earth.

Regarding today's computers, an Intel Core i7 6950X can perform 106 cycles per second. If we run one of the 2^100 operations per cycle, it would take around 3,792 Quintilian centuries! If you had that in 1 Million dollar bills, you'd have a trillion of them!

The paper doesn't convert this to a particular time estimate for quantum computers, but research listed in the Cornell University Library suggests that a real quantum computer wouldn’t be able to accomplish this in any reasonable amount of time.

This being said, a terabyte-sized key is not practical for most uses. It would take about 5 days for the average computer even to use this key. That's not efficient for either the sender or the receiver of the encrypted information.

If I needed to wait five days to decrypt my password, I would never get anything done.

Should we worry?

The short answer is no.

However, to keep our data secure as quantum computers get better and more available, we will need better encryption. Thankfully people are working on this, and there are already ideas on making this happen.

These are the people that need encryption to work.

The very same will spearhead or fund the advances in encryption technology. Think of all the governments and organizations that need to make sure their information stays private. Just sitting by without being proactive about their data is not what entities with secret information do.

What About the Quantum Computers That Already Exist?

There is no need to worry about the ones that exist either. They are still so new that they are only being used to research how to make them better. They are not cracking passwords or encrypted data, and definitely not wasting time with a random internet user's master password.

The people that want your data do not have access to these quantum computers, so there is no need to worry. Keep using encryption if you do and, if you don't, start! Programs like Keybase make it very easy to secure data, be it files or just text. Keybase even has a default encrypted folder that syncs across any computer you login to making the app much more secure than Dropbox.

If you are an email kind of nerd you can sign up for mine here. You can always replay to any of my emails to start a conversation or ask me a question. You can donate to this site from my Liberapay account if you so choose.