Is Fully Homomorphic Encryption now a reality?

We all know the problems with users picking weak passwords, whether it is “PassW0rd123” or “JamesBond007”. We also know that there are lists of passwords which have been obtained from hacks into websites, and from these we can work out what are the most commonly used weak passwords in circulation. Surely there must be a way of checking, when a user chooses a new password for a website, whether the password lies on the known list of common weak passwords? There are two obvious solutions to this problem: Firstly, the browser could maintain the list of weak passwords locally on the user’s computer. This solution however does not scale as the list is huge, and needs to be continually updated. The second solution is for the new password to be sent to a central site and compared against the list of common weak passwords. But this solution then leaks the new (potentially strong) password to the central site doing the checking. Is there a better way?

The answer is yes, and it comes from what at first sight seems an unlikely technology. The problem one is trying to solve with password checking is known “Private Set Intersection” (or PSI) in the cryptographic literature. We have two parties with two sets; the user with a set consisting of one element, namely their password; and the central site with a huge set of common weak passwords. The goal is to determine if the two sets intersect, without revealing anything about the set sets. Such a problem can now be solved very efficiently using a form of cryptography called Homomorphic Encryption (HE). For many years Homomorphic Encryption has been considered highly inefficient and not usable in real-life scenarios, yet this has now changed. Indeed a HE based solution to the PSI problem is now embedded into Microsoft’s Edge browser. So how come this unusable technology, is now usable?

To understand this change we have to look at the past, and introduce some terminology. A Homomorphic Encryption scheme allows a party to encrypt data (for example entries in a database, a vote in an election, or whatever) and then a second party can perform computations on the resulting ciphertexts. These computations produce a new ciphertext which encrypts a result. The result being what would have happened if they had computed on the underlying messages and then encrypted the result. Thus HE allows one to “compute on encrypted data”.  

There are, essentially, three types of HE schemes in deployment or development today. The first is “linear” homomorphic encryption. This variant allows one to compute linear functions (basically additions) on the ciphertexts. Thus a linear HE scheme can be used in a voting application, where one wants to sum up how many people voted for a given candidate, or it can be used to compute the average of an encrypted column in a database. The second type is “Somewhat” Homomorphic Encryption (or SHE), this allows one to compute more complex functions on the encrypted data, and not just linear functions. For example it could be used to compute an encrypted standard deviation. The third type is “Fully” Homomorphic Encryption (or FHE), this allows one to compute arbitrary complex functions on the encrypted data.

FHE had been postulated in the mid 1970’s, and linearly Homomorphic Encryption schemes had been known since the 1990s. Indeed many online electronic voting systems (for example a popular one called Helios) have used such linear HE schemes for around fifteen years. More complex HE schemes were not known until a breakthrough result in 2009 by Craig Gentry (then a PhD student at Stanford University). Gentry invented an SHE scheme, and then showed a method to turn his SHE scheme into an FHE scheme; using a method he dubbed “bootstrapping”. Gentry’s result created a huge interest in the field, with major investments being made into research into this technology by governments, industry and academia. IBM and Microsoft formed groups working on this technology, and the US Government invested in the technology via the DARPA funded PROCEED programme.

The original schemes in 2009 were very slow, and would take many minutes to simply compute the AND of two bits. But, as time progressed, our understanding of the mathematics has improved, the schemes have become more efficient and more expressive, and implementations have been improved. The PSI scheme mentioned above from Edge is implemented using a SHE scheme, whereas FHE schemes can now be used to evaluate (some) neural networks on encrypted data.

The number of companies working on HE technology has grown considerably. IBM and Microsoft, have been joined by Alibaba, Google, Intel, Meta, Samsung, SAP, … the list goes on. There are a number of startups working on technology in this space; most notably Duality and Enveil in the United States, and Inpher and Zama in Europe. Standards bodies are looking into standardizing the technology; there is an effort being run in one of the working groups of the International Standards Organization (ISO).

So what does the future look like for HE? The current technologies for HE are orders of magnitude faster than the first generation schemes from 2009, but are still a little too slow for many applications. However, this performance cost is likely to reduce significantly in the coming few years. A number of companies are developing hardware acceleration engines for HE computations, a bit like graphics cards were created to accelerate graphics calculations. These accelerators are built using novel computing architectures, for example one proposal aims to use optical computing to accelerate HE computations. The US government has again made a big bet in this space, via the DARPA funded DPRIVE programme; which aims to develop hardware accelerators for HE. The DARPA programme, is matched by other companies across the world also investing in hardware HE accelerators.  Once these accelerators come online one can expect (at least) a couple of orders of magnitude performance improvement in HE. These accelerators will widen the range of potential applications, especially when deployed in cloud server environments.

A common question in deployment of cryptography currently, is “What about the threat from Quantum Computers?” Interestingly, the technology behind modern HE is exactly the same technology that is behind the proposals for quantum resistant cryptography. Indeed, the development of so-called post-quantum cryptography and FHE have gone hand in hand, with an improvement in one often being able to be applied to the other. Thus, even if a quantum computer is just around the corner, the data encrypted using modern HE schemes will still be secure.