Over the years, cryptography has improved and become more widespread, in particular since the introduction of the computer after the Second World War. Today, cryptography is everywhere: credit cards, phone calls, internet browsing… With the development of new telecommunications services (Cloud computing, Big Data, Internet of things, etc.), needs will increase even more. In particular, the protection of data belonging to individuals as well as to businesses is creating new challenges, notably that of combining usage and confidentiality of the data handled. In this arena, fully homomorphic encryption provides a “magical” solution.
In effect, this type of encryption enables an external – not necessarily trusted – body, to perform calculations on encrypted data, without learning anything about the input data or the end result.
Orange has been involved in the research and utilisation of homomorphic encryption for many years. Today, only a rare few systems are available, but major players such as IBM or Microsoft are positioning themselves in this niche. For its part, Orange is working on several aspects, such as finding the most efficient means of processing each line of code for optimal use of encryption, increasing the performances of homomorphic evaluation, or designing schemes enabling a precise functionality (electronic voting, data mining over encrypted data, processing images and videos, processing encrypted traffic, etc.). Even if there is still a lot of work to be done, progress on this subject is pretty much daily, and without a doubt concrete applications will be launched shortly.
Can we outsource medical analysis without giving away our medical information? Can we do biometrical identification without revealing our characteristics? Can we make statistics on data that we do not know? Yes we can, thanks to a cryptographic mechanism called “homomorphic encryption”.
Cryptography has known many transformations over the years. Many centuries ago, it was first used to protect military and political communications. Though very simple, the mechanisms then devised are still the foundation of current cryptography. The introduction of the computer during Second World War considerably increased the computation capacity. This increase reflected on cryptography in the late 70’s, when public key cryptography was invented. Cryptography became a thriving scientific field. Numerous academic works were produced, commercial standards were set and cryptographic algorithms began to secure our daily life. Today, cryptography is everywhere: in our credit cards, in our phone communications, in our internet browsing, etc.
But new services are today under deployment, such as mobile services, cloud computing, BigData or IoT. These services generate and process a huge amount of personal and sensitive information. As users become more and more concerned about their privacy, and industries want to protect their sensitive data, a new challenge arises for cryptography. Indeed, if this data was to be simply encrypted, processing it would be impossible. This leaves users and service providers with a dilemma: choose between usability and confidentiality of these sensitive data. Here comes fully homomorphic encryption!
What is homomorphic encryption? In a nutshell, a homomorphic encryption scheme allows an untrusted party to perform computations on ciphertexts, without learning anything about neither the plaintexts nor the result. The classical scenario is as follows[1]: a party A encrypts his data, sends the resulting ciphertext to an external entity B, which executes a chosen algorithm on the received encrypted data. It obtains the encrypted result of the execution of the algorithm on the initial data. This encrypted result is sent back to A, who is the only one who can decrypt it. The party A has outsourced the execution of an algorithm on his data while protecting them since the entity B has no way to obtain any information about neither the input, nor the result. This is homomorphic encryption’s magic!
What can be achieved today? Due to the structure of the mathematical objects implied, we can perform additions and multiplications on encrypted integers. This already allows us to handle a great deal of algorithms: in theory, this is sufficient to apply any Turing machine on encrypted input.
However, the efficiency of the evaluation greatly depends on the algorithm executed. The RSA or the ElGamal cryptosystems both efficiently enable the computation of multiplications: the multiplication of two (or more) ciphertexts leads to the ciphertext of the multiplication of the two underlying messages. The addition case can also be treated efficiently, using e.g., the Paillier cryptosystem. These cases, as simple as they may seem, already lead to interesting applications such as e-voting (addition of encrypted votes) or data statistics (e.g., mean, distance). What about more complex algorithms, which necessitate both additions and multiplications?
Finding a cryptosystem that can handle both multiplication and additions without limitation has long been an open problem. Such a scheme has been first proposed in 2009 and, since then, a lot of progress has been performed by researchers, improving performances, security, and the way to apply this tool to concrete algorithms. Cryptographers are now able of performing, in the encrypted domain, more and more complex algorithms, such as medical analysis, face recognition, sorting, etc. However, these schemes, also known as fully homomorphic encryption schemes, still suffer from limitations that prevent a wide adoption.
What are the main challenges? Firstly, fully homomorphic encryptions schemes suffer from performances problems. If the encryption and decryption steps are fast enough to be used in practice, the homomorphic evaluation is slowed down by the frequent execution of a costly procedure, namely the bootstrapping. Indeed, each multiplication in the encrypted domain adds some noise to the ciphertext that has to be removed to guarantee a correct decryption. The removal is done with this bootstrapping procedure. This operation is necessary to execute most of complex algorithms but incurs an important loss in performances.
Secondly, the size of an homomorphic ciphertext is significantly bigger than the size of the plain data. This data expansion between the clear data and the encrypted one may slow down the communication between parties.
Finally, computation on encrypted data can never be as fast as computation on clear data. The algorithm is blindly performed, and as such, the structure of the input cannot be used to improve computation performances.. Let us take as an example a data dependent branching, such as an “if c then a else b” statement. Evaluating the condition c depending on encrypted data can be done homomorphically, but then the result cannot exploited since it is encrypted! This statement has to be turned into a code whose execution does not depend on the result of the condition. This can be done as follows: one can compute “c.a + (1 – c).b”. The output will obviously be “a” if “c = 1” and “b” if “c = 0”. This illustrates how both branches of the condition (“a” and “b” in our case) are always evaluated, unlike clear data computation. This is inherent to the computation on encrypted data. The evaluation cannot indeed give any information on the input, otherwise it would mean that the encryption would not have hidden the input correctly. This means that an algorithm will always take its worst-case time to finish. As such, algorithms executed on encrypted data have to be carefully chosen, and, in some case, rewritten, as a good execution time on clear inputs does not guarantee the same on encrypted inputs.
What is the role of Orange on this subject? Orange is involved in the research and the use of homomorphic encryption since many years, and has now several results and ongoing initiatives.
As only a few efficient implementations of fully homomorphic encryption are available (notably the ones by IBM and Microsoft), we are working on our own, trying to find the most efficient way to treat each line of code for a practical use.
We also worked on improving performances of homomorphic evaluation, designing a method to minimize the number of times the time-consuming procedure named bootstrapping is evaluated.
We have also designed schemes that allow a precise functionality and we are today focusing on some applications of homomorphic encryption relevant for a telecom operator: e-voting, data mining over encrypted data, image and video processing, treatment of encrypted traffics, etc.
What is the future of homomorphic encryption? As we have seen before, it remains a lot of challenges around homomorphic encryption. We now focus on the way to improve existing schemes (regarding both cryptography and implementation dimensions) so that they better fit current needs.
Regarding the execution of an algorithm in the encrypted domain, our position is to work for each application with a specialist, in order to elaborate new algorithms dedicated to the needs of the encrypted domain: a minimal number of multiplications to perform and a worst case complexity close to the average one.
[1] In fact, cryptographers have provided two different tools to solve this puzzle: homomorphic encryption when the result of the treatment is also sensitive and functional encryption otherwise. They can then be applied in different applications. This article mostly focuses on the former case.
