Scooby: Improved Multi-party Homomorphic Secret Sharing Based on FHE
Ilaria Chillotti, Emmanuela Orsini, Peter Schöll, Nigel P. Smart, Barry Van Leeuwen
Abstract
We present new constructions of multi-party homomorphic secret sharing (HSS) based on a new primitive that we call homomorphic encryption with decryption to shares (HEDS). Our first construction, which we call $$\mathsf {Scooby} $$ , is based on many popular fully homomorphic encryption (FHE) schemes with a linear decryption property. $$\mathsf {Scooby} $$ achieves an n-party HSS for general circuits with complexity $$O(|F| + \log n)$$ , as opposed to $$O(n^2 \cdot |F|)$$ for the prior best construction based on multi-key FHE. $$\mathsf {Scooby} $$ can be based on (ring)-LWE with a super-polynomial modulus-to-noise ratio. In our second construction, $$\mathsf {Scrappy} $$ , assuming any generic FHE plus HSS for NC1-circuits, we obtain a HEDS scheme which does not require a super-polynomial modulus. While these schemes all require FHE, in another instantiation, $$\mathsf {Shaggy} $$ , we show how in some cases it is possible to obtain multi-party HSS without FHE, for a small number of parties and constant-degree polynomials. Finally, we show that our $$\mathsf {Scooby} $$ scheme can be adapted to use multi-key fully homomorphic encryption, giving more efficient spooky encryption and setup-free HSS. This latter scheme, $$\mathsf {Casper} $$ , if concretely instantiated with a B/FV-style multi-key FHE scheme, for functions F which do not require bootstrapping, gives an HSS complexity of $$O(n \cdot |F| + n^2 \cdot \log n)$$ .