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

TY - GEN

T1 - Scooby: Improved Multi-party Homomorphic Secret Sharing Based on FHE

AU - Chillotti, Ilaria

AU - Orsini, Emmanuela

AU - Scholl, Peter

AU - Smart, Nigel P.

AU - Leeuwen, Barry Van

PY - 2022

Y1 - 2022

N2 - 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· | 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· | F| + n 2· log n).

AB - 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· | 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· | F| + n 2· log n).

UR - http://www.scopus.com/inward/record.url?scp=85137973402&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-14791-3_24

DO - 10.1007/978-3-031-14791-3_24

M3 - Article in proceedings

SN - 978-3-031-14790-6

T3 - Lecture Notes in Computer Science

SP - 540

EP - 563

BT - Security and Cryptography for Networks - 13th International Conference, SCN 2022, Proceedings

A2 - Galdi, Clemente

A2 - Jarecki, Stanislaw

PB - Springer

CY - Cham

T2 - 13th Conference on Security and Cryptography For Networks

Y2 - 12 September 2022 through 14 September 2022

ER -