Surviving the “quantum apocalypse” with fully homomorphic encryption
In the past few years, an increasing number of tech companies, organizations, and even governments have been working on one of the next big things in the tech world: successfully building quantum computers.
These actors see a lot of potential in the technology. Quantum computing spreads across a wide range of disciplines both on the hardware research and application development fronts, including elements of computer science, physics, and mathematics. The goal is to combine these subjects to create a computer that utilizes quantum mechanics to solve complex problems faster than on classical computers.
Despite this description evoking images and scenarios fit for a sci-fi blockbuster, it is still hard to pinpoint what a quantum computer would do. Indeed, it seems that the only major application which people have identified is that of cryptanalysis.
Quantum computing has the potential to break cryptosystems that are the foundations of the technology protecting the privacy of data and information created and shared every day. When (and if) an applicable quantum computer is created, we will need to upgrade all our digital security protocols.
What is a quantum computer?
A traditional (digital) computer processes zeros and ones, so called bits. These, to a first order approximation, are represented as on/off electrical signals. A quantum computer, though, processes quantum states; these are units that can be thought of as being both zero and one at the same time. Such a state is called a quantum bit, or qubit.
If you hold n bits in a traditional computer then these n bits can represent any number between zero and 2^n-1, but a single bit can only represent one number at a time. If you had n qubits, then the quantum computer can represent EVERY number between 0 and 2^n-1 simultaneously.
The physics of quantum phenomena is counter-intuitive. For example, two qubits can be “entangled” so that even though they can be separated by a large distance, an operation performed on one of the entangled qubits can have an instantaneous effect on the other qubit.
This is where the privacy concern around quantum computers comes from: they not only store data differently, but also process it differently, giving users a very different form of computational model. With this model, quantum computers could be faster than traditional ones with regards to a few known tasks: unluckily, the two main tasks which quantum computers are good at are factoring large numbers and solving so-called discrete logarithm problems. I say “unluckily,” as it is precisely these two hard mathematical problems which lie at the base of all current security protocols on the internet.
The ability of a quantum system to solve these two mathematical problems will break the internet and all the systems we use day to day. The advent of a quantum computer and its effect on cybersecurity and data privacy is often dubbed the “quantum apocalypse”.
Cryptography to the rescue
Thankfully, the advent of a suitably powerful quantum computer capable of breaking current cryptographic solutions does not yet seem to be on the horizon. But organizations and businesses that truly care about the privacy of their users and customers should start preparing for the worst by looking to integrate existing technologies and solutions in their operations and processes.
There are currently two distinct approaches to face an impending “quantum apocalypse”. The first uses the physics of quantum mechanics itself and is called Quantum Key Distribution (QKD). However, QKD only really solves the problem of key distribution, and it requires dedicated quantum connections between the parties. As such, it is not scalable to solve the problems of internet security; instead, it is most suited to private connections between two fixed government buildings. It is impossible to build internet-scale, end-to-end encrypted systems using QKD.
The second solution is to utilize classical cryptography but base it on mathematical problems for which we do not believe a quantum computer gives any advantage: this is the area of post-quantum cryptography (PQC). PQC algorithms are designed to be essentially drop-in replacements for existing algorithms, which would not require many changes in infrastructure or computing capabilities. NIST (the US standards institute) has recently announced standards for public key encryption and signatures which are post-quantum secure. These new standards are based on different mathematical problems, the most prominent of which is a form of noisy linear algebra, called the Learning-with-Errors problem (LWE).
The unbreakable power of FHE
NIST’s standards only consider traditional forms of public key encryption and signatures. Fully homomorphic encryption (FHE) is different from traditional public key encryption in that it allows the processing of the data encrypted within the ciphertexts, without the need to decrypt the ciphertexts first.
As a first approximation, one can view traditional public key encryption as enabling efficient encryption of data in transit, whilst FHE offers efficient encryption of data during usage. Most importantly, with FHE nobody would be able to see your data but you because they wouldn’t have your key.
All modern FHE encryption schemes are based on the LWE problem, thus FHE is already able to be post-quantum secure. So, if you deploy an FHE system today, then there is no need to worry about the future creation of a quantum computer.