Homomorphic Encryption

Encryption schemes which allow mathematical operations to be performed on the underlying data whilst keeping the data in the encrypted space.

Homomorphic Encryption

By

James Marchant

Published on

August 6, 2022

Most people are familiar with the concept of encryption: making data unreadable to anyone but those who hold the correct key(s). Encryption is often used to secure data at rest (e.g. encrypted files on a hard drive, encrypted databases, etc.) or in transit (e.g. web connections, SSL, etc.), and it is typically just spoken about in these terms.

But what about encrypting data in use? What if we could allow people to still run analyses, operations, or mathematics on data without them having to (or indeed being able to!) decrypt it and see the raw data itself?

“Ah”, you may say, “but a ‘good’ encryption scheme is supposed to make encrypted data almost indistinguishable from random data, there should be no links between encrypted values even if the un-encrypted values are right next to each other.” So how can we expect to perform operations on encrypted data? And more specifically, even if we could, how could we do so in a way that doesn’t require breaking or weakening the underlying encryption?

The solution: Homomorphic Encryption.

What is Homomorphic Encryption?

Homomorphic Encryption methods are encryption schemes which allow mathematical operations to be performed on the underlying data whilst keeping the data in the encrypted space; there’s no need to decrypt the data in order to perform the operations on it, and the result (still in encrypted space) can later be decrypted to make the result available.

For instance an additively homomorphic encryption scheme allows:

where ε is the encryption scheme. This is demonstrated in greater detail in the figure below:

An overview of how additive homomorphic encryption works

This allows us to perform operations on the encrypted data, and get the result, without having to reveal the contents of the encrypted data, fully maintaining the privacy of the data in question! It allows computation in untrusted environments whilst maintaining confidentiality and integrity. For example, if you have three parties with disparate datasets who compete in an industry and wish to understand the average sales performance of a given product type, homomorphic encryption could be used to perform that calculation without revealing each party’s underlying sales figures.

Types of Homomorphic Encryption

Given encrypting data can be computationally expensive and time-consuming, researchers have developed various types of homomorphic encryption to better serve simpler use cases. As a result, there are a few different types of homomorphic encryption that exist, and it is helpful to be able to differentiate between them based on what they can achieve.

Partially Homomorphic Encryption

Partially Homomorphic Encryption (PHE) schemes are those that only allow select mathematical functions to be applied to the encrypted data, although these functions can be applied an unlimited number of times.

In practice this means that one of addition or multiplication is supported by the encryption scheme and can be applied to the ciphertext.

Whilst this may appear quite limiting, in reality often only one of these is needed. For instance the Diffie-Hellman Key Exchange, which underpins almost all of our web interactions via SSL/TLS, utilises the multiplicatively homomorphic nature of RSA encryption to work.

Some examples of PHE include ElGamal encryption (a multiplicative scheme) and Paillier encryption (an additive scheme).

Somewhat Homomorphic Encryption

Somewhat Homomorphic Encryption (SHE) schemes are those that support a “full” set of operations (i.e. addition and multiplication) but they can only be applied a pre-determined, finite number of times. Most SHE schemes are purely academic in nature but were a stepping stone to…

Fully Homomorphic Encryption

Fully Homomorphic Encryption (FHE) schemes are the holy grail of homomorphic encryption allowing the “full” set of operations (addition and multiplication, from which arbitrary computations can be derived) and allowing these operations to be applied an unlimited number of times.

Some of the FHE schemes in existence are GSW, FHEW, TFHE, and CKKS (mostly the names of the researchers who discovered them).

With FHE we can effectively run full analyses, ML training, anything! So why is this not seen more often? Well…

Downsides

FHE schemes are still primarily academic at this point. Whilst great strides have been made in efficiency and complexity for FHE they are still often many orders of magnitude slower than traditional encryption or even PHE schemes and require substantially more memory for computations as well. These factors combined mean that we are still likely some distance away from seeing FHE being used frequently except for very small examples or where time is not of the essence. For things like Federated Learning given the size of datasets or the complexity or ML models this is likely not very feasible… for now.

How is Homomorphic Encryption applied in practice?

Some examples of how homomorphic encryption is used (or could be used) in the real world:

1. As mentioned before, the Diffie-Hellman Key Exchange algorithm is underpinned by the PHE nature of RSA which allows a shared secret key to be created between two or more parties without having to send that key itself! This underpins much of our public-key web infrastructure from website certificates to encryption of larger messages.

2. Data analytics in regulated industries (such as healthcare) where there are both logistical and legal constraints on how data can be shared or viewed between parties will benefit hugely from FHE allowing healthcare to reap the benefits of the advances in AI whilst keeping data fully private. In the meantime, other approaches, such as those possible with the Bitfount platform, allow advantages and approaches to be utilised within private or siloed datasets.

3. Secure Electronic Voting will be enabled by HE. Currently electronic voting has a number of shortcomings compared to traditional paper ballots but by integrating HE people would be able to vote securely and keep their votes private whilst still allowing things like vote tallying to occur.

Resources for Further Learning