Homomorphic encryption (HE) is a privacy technology that enables computation on encrypted data without peeking underneath the hood.
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.
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.
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.
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.
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.
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.
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:
But keep in mind:
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.
Read the latest Gradient Flow newsletter to learn why SMPC is the answer to fully exchanging data while protecting privacy.
Mastercard launched a proprietary AI model to detect fraud. Will other companies be able to catch up to Mastercard's AI savvy?
The IDC 2024 MarketScape recognized Pyte as a Major Player for its secure data collaboration solution, SecureSuite.