Beyond a Single Key: New Results in Multi-Key and Decentralized FHE
Rishab Goyal
Video
Abstract:
Fully homomorphic encryption (FHE) lets an untrusted server compute any function on encrypted data. Many of its most compelling uses, such as collaborative learning, private auctions, and secure multiparty computation, involve data from many mutually distrusting users. Two extensions of FHE target this setting. In multi-key FHE, each user encrypts under an independently generated key. In threshold FHE, users share a single key and authorized subsets decrypt jointly. Both have faced fundamental limitations. In all prior multi-key FHE schemes, ciphertext size and evaluation cost grow with the number of users, and removing this dependence remained open even assuming indistinguishability obfuscation. Threshold FHE has required a trusted dealer or interactive key generation. No construction with silent (non-interactive) setup was known from any assumption, and even with a trusted dealer, at least one of the parameters grew super-linearly in the number of parties. In this talk, I will describe recent progress on these problems. First, I will present the first multi-key FHE scheme from LWE whose ciphertexts and keys do not grow with the number of users. It comes with one-round distributed decryption where partial decryptions are rate-1 and simulatable, which yields MPC with asymptotically optimal communication. Second, I will show how to make multi-key FHE nearly as fast as single-key FHE. After a public, non-interactive preprocessing step, evaluation runs on ciphertexts the size of single-key ones, and our implementation is up to two orders of magnitude faster than prior schemes. Finally, I will introduce scaled linear secret sharing, a new tool that gives the first decentralized threshold FHE with silent setup from falsifiable lattice assumptions. It also gives threshold FHE with a trusted dealer from standard LWE, with all parameters sublinear in the number of parties for a broad range of thresholds.
Bio:
Rishab Goyal is an Assistant Professor of Computer Sciences at the University of Wisconsin–Madison. His research focuses on cryptography and computer security, particularly post-quantum and lattice-based cryptography, with an emphasis on building secure systems with advanced capabilities. Previously, he was a postdoctoral researcher at MIT and an Apple Research Fellow at the Simons Institute for the Theory of Computing. He received his PhD in Computer Science from the University of Texas at Austin.
