How can crypto get ready for quantum computers?

Quantum computers are becoming a reality. It could be a decade before they become ubiquitous enough for the average Joe. Until then, there could very well be a period that a quantum computer is powerful enough to break our encryption algorithms, and rare enough that it could only be used by governments and the ultra rich.

In this scary future, governments can read all the encrypted communications, break cryptocurrencies at will, and read all the secrets we were confident could not be cracked by a supercomputer in millions of years. This future could very well be on the horizon and we have a duty to be ready for it.

To be clear, quantum computers are not necessarily bad for cryptography. They can bring about physically unbreakable encryption and unspoofable communication. In fact, using quantum communication (different from quantum computers), researchers have transferred encrypted messages across the world that are guaranteed to be unbreakable by the laws of physics. See this video if you want to understand how it is done.

Some technical details

The good news is that quantum computers are not capable of breaking all the encryption methods. For example, symmetric encryption that uses a secret key to encrypt messages should still be safe in the quantum world.

The encryption methods that could be potentially broken by quantum computers are asymmetric methods, where you have a private key to encrypt the data and a public key to decrypt it. Specifically, the group of asymmetric algorithms that are based on finite fields are prone to be broken by quantum machines. Coincidentally, these methods are the most popular methods and tend to work very well today.

The two major crypto techniques, Elliptic curve geography (ECC) and Rivest, Shamir, and Adelman (RSA) can be broken if one can efficiently factor very larger numbers or solve the discrete logarithm problem. Read this paper if you want to go deep.

The factorization problem is easy for small numbers. For example, you know that the number 8 is 2x2x2. Try solving this for a 1024 digit number. Mathematician tends to believe that this is an NP problem, meaning that cannot be solved in polynomial time. So it would take a classical computer all the time in the universe to solve a sufficiently large factorization problem. However, Shor has figured out an algorithm that can solve this problem in polynomial time. This means a quantum computer capable of running the Shore algorithm can crack RSA relatively fast.

The security of ECC comes from the fact that in certain finite discrete domains, it is very hard to solve a simple division, which is trivial in the domain of real numbers that we are all familiar with from primary school. This, though not exactly a factorization problem, can still be solved with the Shors’ algorithm and a quantum computer.

The bright side

However, the future of cryptography is not gloomy at all. ECC and RSA may not be the algorithms of tomorrow, but several encryption algorithms exist that are safe from quantum computers. To get a good chance that an encryption algorithm is safe from quantum computers you need to base it on a method that is not reducible to a factorization problem.

Examples of such encryption algorithms are such as BLISS, NTRU, SPHINCS and a lot more.

How can networks prepare for future

ECC, as used by Bitcoin and Ethereum, is very practical and perfectly safe for the foreseeable future. Founders of these projects probably did not expect such level of success and it is sensible that they were not worried about a few decades from now. But the transition for any network does not have to be too complicated.

By abstracting the signature and using algorithms such that they can be easily replaced with post-quantum methods, the migration can happen relatively fast and easy.

Networks can start experimenting with post-quantum techniques as a side to their main method, and when the time comes users can transfer their funds to the post-quantum addresses.

Named addresses makes the transition seamless

The idea of named addresses is very similar to domain names on the internet. We point our browser to https://www.ferrumnet.org, we are actually pointing it to a machine with an IP address of 206.81.5.249 (based on the time of writing this article). Not only is using the domain name instead of IP address human-friendly, but it also allows us to change the server hosting the web resource without affecting the users.

Users of a network that supports named addresses can move their funds and activities to new post-quantum addresses, and update their name registries with minimal disruption to their operations.

Ferrum Network is an example of a network that aims to be forward-looking and prepared for the post-quantum without compromising security or flexibility of today.

Stay tuned…