Multi-Key Homomorphic Secret Sharing: From Theory To Practice

Homomorphic secret sharing (HSS) enables efficient, low-communication secure computation without the use of fully homomorphic encryption. In all existing HSS schemes, parties participate in a correlated setup phase or a public-key infrastructure, then exchange shares of their inputs and perform local computations to obtain additive shares of the output.

In the first part of the talk, we define multi-key homomorphic secret sharing (MKHSS), which replaces the setup in HSS with only a common reference string, and construct MKHSS for NC1 circuits from the decisional composite residuosity (DCR) assumption. This implies the first realization of succinct two-round secure computation for NC1 circuits without lattice-based assumptions.

In the second part of the talk, we present optimizations to speed up the MKHSS construction by 45x. Crucial to this speedup is an insight that reduces the largest modulus from N^4 to N^2. As a bonus, we discover a structural simplification that is of independent interest to other HSS schemes.

A practical application of MKHSS is a non-interactive conditional key exchange protocol, where two parties obtain the same key only if their inputs satisfy some predicate, which can be an arbitrary branching program. We give practical instantiations for two concrete predicates—geolocation proximity and fuzzy password matching—and achieve a total running time in a few seconds for realistic parameters.

Joint works with Geoffroy Couteau (Université Paris Cité, CNRS, IRIF), Srini Devadas (MIT), Aditya Hedge (Johns Hopkins University), Abhishek Jain (Johns Hopkins University and NTT Research), and Sacha Servan-Schreiber (Tinfoil).