Practical Integrity Protection for Private Computations

Fully Homomorphic Encryption (FHE) allows for computations to be carried out on encrypted data, and is slowly becoming used in real-world deployments (e.g., in the Microsoft Edge Password Monitor), notably thanks to theoretical improvements, implementation and hardware optimizations, as well as an ongoing ISO standardization. Despite its tremendous potential as a building block for privacy-preserving applications, FHE does not provide computation integrity, due to its inherent malleability; when using FHE to delegate computations on encrypted data to a third party, a client does not have any guarantee that the intended computation was carried out on its data.

This lack of integrity has obvious implications for the correctness of the result, but can also lead to a complete loss of privacy, as a malicious server could misuse the malleability of FHE to carry out a key-recovery attack. While this issue has been raised in the community, it has received scant attention, as FHE only recently matured enough to be deployed. The variety of efforts studying this and related issues have mostly remained isolated efforts, split across smaller sub-communities studying only certain aspects of the overall problem.

In this thesis, we are the first to consider this issue holistically: we map and unify the space of existing approaches, analyse and evaluate their relevancy to the needs of real-world FHE deployments, and use this newly gained understanding to point out gaps and generic attacks for a wide range of FHE integrity constructions in realistic settings. We then propose novel integrity notions for real-world FHE deployments that prevent these attacks, analyse their relation to existing notions and propose generic constructions to achieve them. In addition, we explore, improve and implement two families of promising, concrete integrity primitives, and sketch an initial design for a novel integrity scheme that would be capable of fully supporting the needs of real-world FHE deployments.

Master’s Thesis written at ETH Zurich, in the Privacy-Preserving Systems Lab and the Applied Cryptography Group Advisors: Alexander Viand, Dr. Anwar Hithnawi, Prof. Kenny Paterson