Homomorphic Encryption: Universality at a Cost

HE has so many possible applications that researchers dubbed it "the Swiss army knife of crypto." Yet real-world HE sightings remain rare. What gives? To solve this mystery, let's take a tour of the HE zoo and see the beasts in their habitats.

What is Homomorphic Encryption?

Imagine Alice and Bob want to figure out who has a higher salary without revealing the actual numbers to each other. Alice puts her salary amount in a locked box and sends it to Bob. Bob has a magic box that can compare the locked boxes without opening them. The magic box spits out another locked box that contains the result: either “Yes, Alice’s box holds a higher amount” or “No, Alice’s box does not hold a higher amount.”

Bob sends the locked result box back to Alice. Now Alice unlocks the result box and reads the message privately. Neither Alice nor Bob ever saw what was inside the other’s locked boxes, but they learned the result of the comparison.

This allows Alice and Bob to operate on concealed information in a way that generates useful results without compromising privacy. Using normal lockboxes alone wouldn’t enable that kind of blind operation and comparison. The magic box is what permits it while keeping the contents obscured.

Types of Homomorphic Encryption

Not all homomorphic encryption schemes are equally useful for Alice’s scenario. Some, called partially homomorphic encryption (PHE), can only compute additions or multiplications of encrypted data. For example, the standard RSA encryption algorithm is partially homomorphic because it allows multiplying ciphertexts to get an encrypted product of the underlying plaintexts.

To perform more complex computations, homomorphic encryption algorithms must support both adding and multiplying encrypted data. Schemes that can do this are called fully homomorphic encryption (FHE). FHE is very versatile and has gained a lot of attention recently.

However, FHE has performance issues. So for practical uses, researchers often rely on somewhat homomorphic encryption (SHE) or approximate homomorphic encryption (AHE) instead. Like FHE, SHE can add and multiply encrypted data. But SHE has limits on how many operations can be done before the scheme becomes too complex. The more operations, the larger the encryption parameters and ciphertexts. This means more complex tasks lead to a bigger performance hit compared to unencrypted algorithms. FHE has fixed overhead regardless of the task.

AHE is similar to SHE but produces encrypted approximate results. For example, multiplying two encrypted messages a and b with AHE yields an encryption of a value roughly equal to a*b. This approximation error is acceptable for some uses like machine learning.

Is HE better than secure multi-party computation (SMPC)?

Traditionally HE is compared and contrasted with Secure Multi-Parity Computation technologies (SMPC), which enable the following scenario. Each party holds an input and they would like to compute some function of the inputs in a way that no information about any input leaks to any other party short of what you can infer from the output.

Technically, HE is one of the SMPC technologies. It has several parties exchanging messages to compute on encrypted data. However, HE has several special properties that single it out.

1. Universality. With FHE, any algorithm can be computed securely. Furthermore, running a different computation on already encrypted data can be done without adapting encryption parameters or a communication protocol between the parties.
2. Minimal interaction. The parties encrypt data and send it to one party that runs a computation and distributes the (encrypted) result. This is how a typical HE computation is organized. Note that the parties do not need to be online during computation, which is a good fit for private cloud computing.
3. Compute burden is shifted to one party. HE computation is usually done by only one party while the others only encrypt and decrypt the data. This is great for use cases where a client wants to outsource execution of a heavy algorithm to a cloud provider with much larger computational resources.

Looking at these qualities, one might think that HE (especially FHE) is poised to be a popular tool for privacy and security practitioners. However, it is not yet the case due to the following reasons.

1. Poor performance. In simple use cases, such as computing an elections tally or aggregating simple statistics, HE is on a par with other SMPC protocols in terms of running time and RAM demand. However, more complex and practically interesting tasks such as private database queries or machine learning inference/training require significantly more compute and RAM.

For instance, a single multiplication of (encrypted) 32-bit integers via a state-of-the-art FHE scheme takes around 9 seconds, while state-of-the-art SMPC protocols in the same time can perform 50 Million multiplications thus exhibiting the gap of more than 7 orders of magnitude.

Moving on to more practically interesting benchmarks, let us consider the problem of computing an equality join of two databases (or as it’s called in the research literature, Private Set Intersection). Here, a state-of-the-art HE approach requires 31 seconds on 24 cores to join databases with five thousand and one million rows, while taking 192 GB of RAM (memory). Moreover, the complexity of this algorithm scales as the product of database sizes, so one can’t hope to run a join on two databases of a million rows each. At the same time, a state-of-the-art SMPC protocol for the same problem can join two million-sized databases in 0.4 seconds on a single core of a standard laptop with as little as 16 GB of RAM.

2. Hard to deploy. Since FHE, SHE and AHE systems are relatively young technologies, there are only a few production-quality libraries implementing them. Moreover, the standard parameters of these libraries are often too restrictive for practical applications. Encryption parameters define not only how secure an HE algorithm is, but also its functionality. This introduces a tug-of-war game between efficiency and security. In particular, the least functional PHE schemes are the easiest to use out of the box. Their standard parameters support addition or multiplication of 64-bit integers. But more sophisticated HE algorithms demand an intricate fine-tuning of parameters to achieve sensible performance without compromising security. Practically, one should resort to special homomorphic compilers that, given a desired functionality, estimate optimal parameters to execute it with HE. However, some SMPC algorithms rely on much easier cryptographic primitives such as hash functions and block ciphers that can be instantiated only once with standardized parameters for any application.
3. Only PHE is standardized. All advanced HE schemes are based on a relatively new type of encryption algorithm called lattice-based encryption. Lattice-based signatures and encryption schemes have been thoroughly scrutinized in recent years and then recognized by the National Institute of Standards and Technology as the official standard that can withstand even attacks by quantum computers. However, FHE, SHE and AHE algorithms subtly deviate from these schemes, which introduces new challenges in the security analysis. Hence, advanced HE algorithms need additional research to be standardized. Only PHE systems are recognized by standardization bodies at this moment (see ISO/IEC 18033-6:2019), but they are vulnerable to attacks by quantum computers. Several interactive SMPC protocols have a more solid ground as they rely on already standardized cryptosystems such as AES or SHA-3.
4. Hard to support more than two parties. By default, HE algorithms assume two participating players, namely, the data owner and evaluator. In practice, there might be multiple clients (e.g., voters, auction bidders) willing to jointly compute on their data. In use cases where only addition or multiplication has to be done (e.g., computing an election tally), it is easy to extend HE to more than two parties. However, more sophisticated applications (e.g., comparing bids) demand so-called multi-key FHE/SHE/AHE schemes, whose performance is still impractical. Interactive SMPC protocols support any number of parties and can be deployed even for thousands of participants.
5. Hard to verify results. As mentioned above, HE assumes that one powerful party does all computations. How can we make sure that this party doesn't cheat and performs only authorized operations? In interactive SMPC protocols, there are several standard techniques to prevent such malicious behavior at modest cost. In contrast, HE relies on heavy machinery such as homomorphic signatures, homomorphic MACs and zero-knowledge proofs that have a prohibitive performance overhead in practice.

‍

Does my use case need Homomorphic Encryption?

Homomorphic encryption is not a one-size-fits-all solution and should be applied carefully based on your specific needs and constraints. Consider the following to determine if HE suits your use case:

Little interaction or high-latency channels: If your application requires minimal interaction or communication, HE could be a good fit. It does not demand much back-and-forth interaction between parties.

Simple computations: If your application only needs a few additions or multiplications (e.g. basic statistics), HE may work well. For more complex problems, interactive SMPC protocols are far more efficient.

Outsourcing heavy computation: If you want to outsource intensive processing to a cloud provider or other third party, HE allows encrypting your data and sending it to them to do the computational work, then returning encrypted results. This avoids revealing raw data.

HE also may not provide a straightforward drop-in replacement for an unencrypted system. Achieving good functionality and performance with HE typically demands customizing a scheme’s encryption parameters for your needs. This requires expertise to set up and maintain. Also, HE provides weaker security guarantees than fully interactive protocols.

So in summary, consider HE if:

• Your application needs little back-and-forth or functions well with high latency
• The computation involves only basic operations like addition and multiplication
• You want to outsource intensive processing of sensitive data to an external party

But keep in mind:

• HE schemes usually require expertise to configure and run efficiently
• HE typically provides weaker security than fully interactive SMPC protocols
• HE may demand significantly more computational resources than an unencrypted system to perform the same tasks

If your needs include complex computations, tight security, low latency, or easy deployment and maintenance, interactive SMPC protocols are probably a better choice than HE. But for suitable applications, HE enables unique benefits like outsourcing intensive sensitive data processing.

With various options available, you can choose the right privacy-enhancing technology for your specific use case and requirements. But apply them judiciously based on a full understanding of their capabilities and limitations.

‍

‍