Paper 2022/862
Scooby: Improved Multi-Party Homomorphic Secret Sharing Based on FHE
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 Scooby, is based on many popular fully homomorphic encryption (FHE) schemes with a linear decryption property. 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. Scooby can be based on (ring)-LWE with a super-polynomial modulus-to-noise ratio. In our second construction, 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, 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 Scooby scheme can be adapted to use multi-key fully homomorphic encryption, giving more efficient spooky encryption and setup-free HSS. This latter scheme, 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)$.
Note: Correction of the HSS Protocol
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. SECURITY AND CRYPTOGRAPHY FOR NETWORKS – SCN 2022
- Keywords
- Homomorphic EncryptionHomomorphic Secret SharingMulti-Party Computation
- Contact author(s)
-
ilaria chillotti @ zama ai
emmanuela orsini @ kuleuven be
peter scholl @ cs au dk
nigel smart @ kuleuven be
barry vanleeuwen @ kuleuven be - History
- 2024-11-08: revised
- 2022-07-01: received
- See all versions
- Short URL
- https://ia.cr/2022/862
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/862, author = {Ilaria Chillotti and Emmanuela Orsini and Peter Scholl and Nigel Paul Smart and Barry Van Leeuwen}, title = {Scooby: Improved Multi-Party Homomorphic Secret Sharing Based on {FHE}}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/862}, year = {2022}, url = {https://eprint.iacr.org/2022/862} }