All seminars will take place on Fridays at 11 a.m. in DBH 6011. Check seminar details below.
Danielle Micciancio
UCSD
April 14, 2023
11:00am - 12:00pm
Title:
Breaking and Fixing Homomorphic Encryption on Approximate Numbers
Abstract:
Fully Homomorphic Encryption (FHE) allows to perform computations on encrypted data, enabling, at least in theory, a wide range of security applications like the outsourcing of private data analysis to the cloud. Still, current FHE techniques carry a substantial computational cost, much higher than regular public key encryption.
In recent years, starting with the work of Cheon et al. (Asiacrypt 2018), a new approach has emerged that provides substantial efficiency gains compared to previous techniques at the cost of producing only approximate results. Since in many target application areas (like secure machine learning, or analysis of real world data subject to measurement noise) approximation is already present in the input or computation model, the approach has attracted a substantial amount of attention both within the theoretical and applied cryptography community, and support for approximate FHE has been added to all the mainstream general purpose FHE cryptographic libraries.
In this talk I will show that, while certainly attractive in terms of performance, approximate homomorphic encryption also raises serious security issues that have no analog in the setting of traditional (exact) homomorphic computation. In particular, I will show how approximate homomorphic encryption, as originally proposed and implemented in many applications, is completely insecure and subject to a very efficient total key recovery attack.
Then I will present our work providing a sound theoretical basis for the security analysis of approximate homomorphic encryption. More specifically, I will present theoretical notions of security that properly capture the intended applications of approximate homomorphic encryption, techniques to modify the original approximate FHE schemes to provably meet these security requirements, and ongoing work on refining these techniques to minimize the computational cost of fixing the security vulnerabilities of approximate homomorphic encryption.
In recent years, starting with the work of Cheon et al. (Asiacrypt 2018), a new approach has emerged that provides substantial efficiency gains compared to previous techniques at the cost of producing only approximate results. Since in many target application areas (like secure machine learning, or analysis of real world data subject to measurement noise) approximation is already present in the input or computation model, the approach has attracted a substantial amount of attention both within the theoretical and applied cryptography community, and support for approximate FHE has been added to all the mainstream general purpose FHE cryptographic libraries.
In this talk I will show that, while certainly attractive in terms of performance, approximate homomorphic encryption also raises serious security issues that have no analog in the setting of traditional (exact) homomorphic computation. In particular, I will show how approximate homomorphic encryption, as originally proposed and implemented in many applications, is completely insecure and subject to a very efficient total key recovery attack.
Then I will present our work providing a sound theoretical basis for the security analysis of approximate homomorphic encryption. More specifically, I will present theoretical notions of security that properly capture the intended applications of approximate homomorphic encryption, techniques to modify the original approximate FHE schemes to provably meet these security requirements, and ongoing work on refining these techniques to minimize the computational cost of fixing the security vulnerabilities of approximate homomorphic encryption.
Speaker Bio:
Daniele Micciancio received his PhD in Computer science from MIT in 1998 and he is currently a Professor at the University of California San Diego, which he joined in 1999. He is widely interested in theoretical computer science and cryptography, but he is mostly known for his work on the foundations of lattice-based cryptography and application to fully homomorphic encryption. He is the recipient of NSF CAREER Award, Sloan Research Fellowship, STOC Machtey award and FOCS Test of Time award. In 2019 he has been appointed Fellow of the IACR for his pioneering work on lattice-based cryptography and the complexity of lattice problems.