Paper 2022/862

Scooby: Improved Multi-Party Homomorphic Secret Sharing Based on FHE

Ilaria Chillotti, Zama
Emmanuela Orsini, imec-COSIC, KU Leuven
Peter Scholl, U. Aarhus
Nigel Paul Smart, imec-COSIC, KU Leuven & Zama
Barry Van Leeuwen, imec-COSIC, KU Leuven
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.