Fully Homomorphic Encryption: the Holy Grail of cryptography

Samuel Cristobal

2018-12-05 14:08:49
Reading Time: 3 minutes

It has been a while since the FHE acronym flooded the Internet: Fully Homomorphic Encryption. Everyone nowadays is familiar with the concept of encryption – it is a way to encode messages so that, once encoded, the original message can not be recovered unless the one requesting the message is entitled to it somehow. Mathematically, this means creating a mapping that can be reverted, a two-way function, but it is practically impossible to compute the inverse of any element without knowing additional information.

Homomorphic might be a little more complicated to grasp. Two objects do not need to be the same to have the same properties. With a set of integers, consider addition as usual and then take just the even integers with addition. Since the base set is different, the two end results are different. Still, the transformation n → 2n and its inverse gives a 1:1 relationship that preserves the operations! ie. if n+m = k then 2n+2m =2k. They are mathematically identical.

Essentially, anything that can be done using integers and addition can be proven using only even integers and addition. The two groups are called homomorphic and the map n → 2n homomorphism. Regardless of the underlying structure, the notion of homomorphism applies. It is a loose definition or description used by mathematicians. However, that definition also depends on the specific theory at hand. For instance, our previous example does not work when considering multiplication instead of addition. This sometimes can cause confusion, as a mug (with circular closed handle) and a donut are indistinguishable for a topologist, but definitively look different to a geometer. This is because both work with different base theories. Topologists are allowed to squeeze the forms while geometers usually only allow themselves to translate and rotate objects.

Since cryptography is part of group theory in mathematics, mathematicians say that when two groups are indistinguishable they are called homomorphic. That means that there is a 1:1 function preserving all axioms of groups. A group is basically a set and an operation that satisfies associability, identity, invertibility and closure, basic algebra in other words. Integers with addition form one of the best known examples of a group from which one could derive most algebra.

Now if both terms were mixed, homomorphic encryption, it would result in a kind of an oxymoron. On the one hand, the cryptographic function will try to destroy the original information so that it can not be easily recovered. On the other, the homomorphic function will try to keep an exact copy of the original information so that all the operations and properties remain intact. A homomorphic encryption scheme allows the performance of the group operations on cyphered data. The result will correspond to the operation on original plain data, granted one can decipher the output.
Fully homomorphic encryption goes beyond that and aims to provide homomorphisms that preserve any kind of algorithm on the cyphered data, not just the group operations. For years, the concept existed, but no one was sure it was possible to find a solution. That was the dream of cryptographers, or the holy grail.

In 2009, Craig Gentry gave the first proof of the existence of such FHE scheme, latter implemented in the so-called Gentry-Halevi crypto system, making it available to the public in 2011 and more recently open source implementations like HElib, FHEW and TFHE. Despite his efforts, the major caveat of those is the higher computational complexity and therefore longer computation times, especially when compared with usual crypto systems.
Due to the increase in complexity, FHE systems are both more demanding in terms of computational power and difficulty of maintenance. The growth of cloud computing solutions will soon mitigate the computational requirements; however, in some cases, a trusted, secure 3rd party could be enough to perform the operations. In those cases, FHE is simply overkill as there is no clear benefit to using it. Only when 3rd party solutions seem untrustworthy would FHE be the solution.

In aviation, for instance, there are several central authorities that act as trusted 3rd parties. However, new initiatives lack the required trust for stakeholders to join. A proper implementation of FHE for aviation could lower the entry barrier for cooperation programs. For instance, measuring route performance among different airlines, without disclosing strategic information.

© datascience.aero