From the beginning, cryptography took care of the protection of data. At first the data to be protected consisted of messages in transit, that had to be hidden from adversaries trying to intercept a communication. Lately, with the advent of modern computers and portable memory devices, cryptography also had to protect the data in storage. The last decades witnessed the beginning of the Cloud era, where millions of people store their data on public servers in order to be able to access it everywhere in the world at every time. In addition, people now want to be able to run computations, analytics or simple searches in the cloud. In this new scenario, protecting the data in transit and the data in storage is still necessary but not sufficient anymore: data in use also needs protection. When it comes to sensitive information, such as medical records, financial transactions or genomic material, the computations cannot be performed in clear.
To help protect the data in use, the “Three Musketeers” of secure computation come to help: Secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE) and Functional Encryption (FE). All of them have different properties and can handle different scenarios. They generally work alone, but can be very powerful when they start working together.
Secure Multi-Party Computation
In MPC, two or more parties would like to jointly compute a function F on their inputs, while keeping these inputs private. The first attempt to realize MPC is the one by Yao in 1982, who proposed a two-party computation (2PC) protocol based on Garbled Circuits in order to solve its famous Millionaires’ problem: two or more millionaires would like to learn who among them is the richest, without revealing to the others the money they own. Subsequent works solved the MPC problem by using secret sharing (binary and arithmetic), Beaver’s triples, oblivious transfer, etc.. In MPC, the input data is masked or secret shared, and the final result is generally revealed to all parties. The advantage of MPC is the somewhat low computational overhead, but it requires multiple rounds of interaction between the parties involved in the protocol.
Fully Homomorphic Encryption
In FHE (often defined as the Holy Grail of cryptography) the idea is to perform computations on encrypted data. Different types of homomorphic encryption exist: additive, partial, leveled, somewhat (SHE). When we talk about fully, we mean that potentially every function can be evaluated, while in the other cases there are limitations. One of the most common scenarios where FHE can be used is in outsourced computations: a client sends encrypted data to a server and asks this latter to evaluate a function F on this encrypted data. The inputs and outputs of the computation are encrypted with the client’s secret/public key and the server manipulates only encrypted data. The first solution was proposed by Gentry in 2009 (about 30 years after the seminal idea by Rivest, Adleman and Dertouzos), which introduced a technique called bootstrapping. Bootstrapping allows to refresh noisy ciphertexts and can be used to ensure a correct answer after decryption. In fact in the majority of the FHE solutions, the ciphertexts contain a little amount of noise that increases after each operation. If this noise is not controlled, the decryption can be wrong. The main FHE schemes are based on the LWE (Learning With Errors), Ring-LWE, NTRU and Approximate-GCD problems. FHE demands no interaction between the client and the server during the computations, but the computations are still very expensive.
Functional Encryption
FE is a public key construction, on which it is possible to produce functional secret keys allowing a party to evaluate a specific function F (generally public) on an encrypted input during its decryption. So the input is encrypted and the output is in cleartext: the party performing the (functional) decryption learns the result of the function on the specific data, but nothing else. A practical application of this technique could be its use in spam filters, on which a user wants his email provider to learn if a specific email is spam, without allowing him to learn anything else about the content of the emails. FE has been properly formalized in 2011 by Boneh, Sahai and Waters. Nowadays, there are no known FE schemes that can be used to efficiently evaluate general functions. However, the literature proposes multiple efficient constructions to evaluate linear and quadratic functions.
| MPC | FHE | FE | |
| Input | Masked/shared | Encrypted | Encrypted |
| Output | Cleartext | Encrypted | Cleartext |
| Interaction | Yes | No | No |
| Computation | Efficient | Reasonable in SHE Expensive in FHE | Efficient (for linear and quadratic functions) |
“All for one and one for all”
Even if there is still lot of space for improvement in all the three domains, these technologies are already very promising. And if they all look very powerful on their own, we could only imagine what happens if they decide to join forces. A few practical examples already exist in literature, and many others theoretical ones are left as open problems. Concerning the practical ones, we can already observe constructions mixing MPC with (additive) homomorphic encryption (like SPDZ): in these cases homomorphic encryption is used as a subroutine to produce correlated randomness, useful in the so-called online phase. FHE can also become “multi-party”, in the schemes allowing a multi-key functionality: e-voting schemes are a practical application of this technology. Regarding open problems, an interesting idea is the one of adding a FE decryption step after a huge FHE computation, in order to output a plaintext instead of a ciphertext. Unfortunately, no secure solution has been found yet, but such a solution (if efficient) could be a very powerful tool for secure computation. And what would happen if the three technologies were mixed together? Only the future will tell.
Copyright note
[The images in this blogpost have been created by using PowerPoint, with photos from Unknown Authors licensed under CC BY-NC and CC BY-SA (http://www.pngall.com/cloud-server-png, http://pngimg.com/download/8754, https://en.wikipedia.org/wiki/File:Text-x-generic.svg, https://commons.wikimedia.org/wiki/File:Golden_key_icon.svg, https://commons.wikimedia.org/wiki/File:Lock.svg, https://commons.wikimedia.org/wiki/File:User_icon_2.svg, https://commons.wikimedia.org/wiki/File:User_icon_3.svg).]
