An Efficient Threshold Access-Structure for RLWE-Based Multiparty Homomorphic Encryption
Christian Mouchet, Elliott Bertrand, Jean‐Pierre Hubaux
Abstract
Abstract We propose and implement a multiparty homomorphic encryption (MHE) scheme with a $$t$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>t</mml:mi> </mml:math> -out-of- $$N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> -threshold access-structure that is efficient and does not require a trusted dealer in the common random string model. We construct this scheme from the ring-learning-with-error assumptions and as an extension of the MHE scheme of Mouchet et al. (PETS 21). By means of a specially adapted share re-sharing procedure, this extension can be used to relax the $$N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> -out-of- $$N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> -threshold access-structure of the original scheme into a $$t$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>t</mml:mi> </mml:math> -out-of- $$N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> -threshold one. This procedure introduces only a single round of communication during the setup phase, after which any set of at least t parties can compute a t -out-of- t additive sharing of the secret-key with no interaction; this new sharing can be used directly in the scheme of Mouchet et al. We show that, by performing Shamir re-sharing over the MHE ciphertext-space ring with a carefully chosen exceptional set, this reconstruction procedure can be made secure and has negligible overhead. Moreover, it only requires the parties to store a constant-size state after its setup phase. Hence, in addition to fault tolerance, lowering the corruption threshold also yields considerable efficiency benefits, by enabling the distribution of batched secret-key operations among the online parties. We implemented and open-sourced our scheme in the Lattigo library.