Recently, Gentry and others have established the feasibility of constructing fully homomorphic encryption schemes. Briefly, a fully homomorphic encryption (FHE) scheme is one that allows a third-party who has ciphertexts of several messages to construct---without knowing the decryption key---a new ciphertext that corresponds to an arbitrary efficiently computable function applied to the original messages. Fully homomorphic encryption has the potential to allow disparate organizations to compute basic functions on their pooled data-sets without revealing such data to each other. It is thus an ultimate solution for implementing ``need-to-know'' privacy.
Until Gentry's discovery, few researchers believed that FHE could be constructed. As a result, the concept has not been well-studied despite its clear potential to solve important tasks in a privacy-preserving manner. In particular, the basic relationship between FHE and traditional public-key cryptography remains unclear. The goals of this research project are to formalize this relationship, to build notions of FHE that satisfy stronger security guarantees such as security even when the adversary has access to a restricted decryption oracle, and to potentially use these stronger security guarantees to apply FHE in secure and privacy preserving computation.
To ensure the broader impact of the research, this project includes mentoring of students at all levels from undergraduate to post-doctoral and outreach activities to traditionally under-represented students and K-12 students. Research from this project will be disseminated through presentations and publications in conferences, journals and on the Internet.
Fully Homomorphic Encryption (FHE) is, like any other encryption technology, one that allows us to encrypt data so that it is unreadable to anyone without the appropriate decryption key. What makes FHE different is that once data is encrypted, we can compute with it, without ever decrypting. This allows in principle one to encrypt data and protect it, send it out to have computation performed on the cloud (which may not be trusted with sensitive data), and then retrieving the results from the cloud. This is all done with the cloud never having learned anything about the data. FHE technology was widely believed not to exist prior to 2009, when it was discovered by Gentry. Therefore, many of the implications of the technology had not been thought out. This project aimed to understand some other implications of this technology to other areas of cryptography. We were able to construct a secure multi-party computation protocol with the theoretically asymptotically minimal communication bounds based on a variant of FHE we constructed (Threshold FHE). Secure multi-party computation (SMC) protocols allow a group of people who have secret data to compute a function of their data without revealing their individual input data. SMC has many possible applications in practice. Examples include voting, corporate salary disclosure, matching records between sensitive databases in the medical and security fields, etc… In many of these protocols, because of the huge discrepancy between the general availability of computation and bandwidth, communication is what needs to be optimized in these protocols, not computation. Our work shows it is possible to optimize computation for very large inputs, but due to the asymptotic nature of our result, more work will be needed to move our results in to practice for more practically sized inputs. Other work focused on the ability to construct more secure public-key encryption systems from FHE schemes. By necessity of the homomorphic property, FHE schemes have security only against passive adversaries, but in other cryptographic contexts weaker homomorphic properties have often been successfully leveraged to generate different types of tools, often with strong security properties. Our goal was to show that the homomorphic property could be used to achieve strong security in a new public-key encryption scheme built out of the FHE one. Partial progress was made, in that we’ve shown that properties that many specific homomorphic schemes have can be used to make stronger encryption schemes. This relates to a fundamental question in cryptography which asks if strongly secure public-key encryption schemes which withstand active attackers can be built from weakly secure ones that are only secure against passive attackers. Answering such questions would help inform the field on the strength of the computational assumptions we need to make in order provide secure cryptography. This in turn helps us diversify the types of computational assumptions cryptographers make. Researching the above also led to insights in the relationship between some other weaker forms of cryptography: specifically weak forms of plaintext aware cryptography lead to traditional notions of security against active attackers. This was previously not known, and provides one of the very few examples of research which shows a seemingly weaker notions of public-key encryption security implying a stronger one. Research was published in leading conferences and journals. Graduate students were educated in this new, and rapidly advancing area of science, and some of these students have gone off to work for large technology corporations and startups, where they work on information and systems assurance and security. Similarly, the PIs worked with undergraduates and underrepresented groups exposing them to cryptography, and the ideas of fully homomorphic encryption. Th PIs also helped teach at a summer school for graduate students in cryptography at Penn State University.
