### 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)$.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. SECURITY AND CRYPTOGRAPHY FOR NETWORKS – SCN 2022
Keywords
Homomorphic Encryption Homomorphic Secret Sharing Multi-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
2022-07-01: approved
See all versions
Short URL
https://ia.cr/2022/862

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},
note = {\url{https://eprint.iacr.org/2022/862}},
url = {https://eprint.iacr.org/2022/862}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.