Homomorphic Encryption 

Jarred McGinnis
April 2, 2021

Functionality becomes consistent with privacy

What do dragons do with their treasure anyway? As far as I can tell, their whole goal is to ensure their hoard is secure. End of list. Yet it seems to defeat the purpose of amassing a large amount of fungible assets not to put them to use. Surely, it would be better for the dragon to invest some of that treasure into seed funding for a direct-to-lair sheep delivery app. But, who am I to question the wisdom of the wyrm. Allowing for the occasional invisible hobbit, dragons have always done a good job at data security, sorry, treasure security.

Data hoarding is every SecOps optimal strategy. Your data is safe as long as you do nothing with it. Lock it away and set an incident responder atop poised to breath fire at any incursion. Though there is some satisfaction in the sight of the charred remains of script kiddies scattered before your firewall, the value of data is its use. Begrudgingly, with private keys in claw, SecOps must allow data to be used and that’s when it is most at risk.

Homomorphic Encryption (HE) enables you to keep your treasure safe while still putting it to work. More specifically, by using a homomorphic encryption scheme, the holder of the data can enable computation to be performed without compromising it. The data stays encrypted while a service is performed without the service provider having any access to the data or even knowing what functions or operations are being performed on the data. It’s mind boggling stuff, but as Craig Gentry, the Gandalf the White of HE, said, ‘Cryptography is full of these kinds of paradoxes’.

What if Smaug had an Advanced Degree in Mathematics?

Imagine how much simpler and safer cloud computing becomes if fully homomorphic encryption is realized. Processing of sensitive data can be outsourced without concern. Competitors or even allied States can collaborate safely. Malware attacks become superfluous. Our machines become quantum secure and elves chant their ancient victory songs in the hills.

By relying on the property of certain mathematical operations having same-shape (i.e. homomorphic) effects on the data, it is possible to perform operations on encrypted data that would have the same result on the underlying data. For example, you have a doubling function but you don’t want anyone to know what you are doubling. You can obfuscate (or encrypt) what you are doubling by multiplying a random number to the amount you want to double, relying on the properties of multiplication. Specifically after you’ve doubled, you can get the needed product by dividing by your random number again. Any attacker even with access to the doubling function will have no idea what you were doubling.

My secret number 4. Desired product 8 (which is four doubled, 4x2)
My random seed = 3.
Number sent to the doubler = 12
Number returned by doubler = 24
Divide out the seed 8 (24/3)
???
Profit.

Obviously the real means by which homomorphic encryption occurs is vastly more complex, we're talking n-dimensional lattices NP-hard complex.

Like our previous articles about ZKPs and SMCs, the theoretical work for HE has been going on for decades, as the value of it was obvious. A number of schemes were proposed that offered either partially homomorphic encryption (PHE) or somewhat homomorphic encryption (SHE) which limited the kind of operations that could be performed on the data. The goal of the fully homomorphic encryption (FHE) scheme, with the ability to perform arbitrary computations, was not achieved until 2009 when Gentry introduced his lattice-based approach. If you think that was a lot of acronyms, hold on to your halfling. 

For a set of problems, SHE is good enough without paying the quite dear performance cost. FHE is generally achieved by starting with a SHE scheme and adding noise via huge polynomials, a process described as bootstrapping in the literature. Each operation adds to the noise making it increasingly difficult to decrypt without the key. Since 2009, most of the innovation has been focused on addressing the orders of magnitude in performance cost that FHE entails. This is where the current implementations of FHE become alphabet soup. For example, the BLLN scheme builds upon the LTV’s NTRU-based scheme. A number of libraries exist: BGV, BFV, FHEW, TFHE and the increasingly popular CKKS. Currently, the optimization schemes are seen as efficient for relatively simple tasks with ‘low depth’. Computational costs of 40 and 50 have been reported and are echoed in the linked paper from IBM.

Applications for FHE

The end goal is to be able to do secure computation anywhere. If FHE can be fully realized and implemented, it will be as revolutionary as packet-switching was for networked computers. However, that’s a big ‘if’ that we’ll address in the next section. 

If FHE can be implemented the issues around using privacy-sensitive data for research such as genetics or epidemiology become irrelevant. Companies with sensitive data can now outsource computation rather than being forced into risky and expensive development projects. Data-monopolistic companies have lost their leverage. Consumers can browse, search, and download without worrying that their data is being compromised or used without their consent. It will enable secure collaboration (e.g. between governments and private industries) where they can discover intersections of data or other insights without compromising their data. Ironically, it could foster the dream of open data by ensuring data remains secure. There is already interest, especially from the financial sector. Details of a proof of concept can be found in papers and reports of field trials.

State of the Art and Drawbacks of HE

As with the other technologies we discussed recently, FHE is far away from a practical solution. There are many many issues still to address. Its complexity and computational cost is foremost of these. There are a lot of clever people in big organizations working on the problem because the value of the solution is that huge. Most recently DARPA announced a funding program seeking a 100,000-fold improvement in processing speed and has already awarded a number of contracts.

It’s still the wild west in terms of approach and it is early days for standardization, with a lot of acronym schemes still battling it out. CKKS has been shown to be promising in reducing the costs of bootstrapping and has performance benefits for Machine Learning which is proving to be a use-case of interest. CKKS’s benefits bring with it new issues because its operations are approximate and every operation results in a loss of precision. Additionally, HE schemes are inevitably seen to be more malleable (i.e. an attacker is able to modify ciphertext) than non-homomorphic schemes due to modification, albeit by participants, being an intended feature.

If the dream of FHE can be realized in a scalable and practical manner, it will be nothing short of transformative to computing. Solving the trust issue by making it immaterial is the only solution to the hyperconnected reality of today’s and tomorrow’s computing. Until the One Ring (learning with errors) is found, we must make do with best practices such as securing keys, implementing sound SecOps strategies and performing regular security audits.