International Association
for Cryptologic Research

We propose and implement a multiparty homomorphic encryption (MHE) scheme with a $$t$$ t -out-of- $$N$$ N -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$$ N -out-of- $$N$$ N -threshold access-structure of the original scheme into a $$t$$ t -out-of- $$N$$ N -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.

We present a bootstrapping procedure for the full-RNS variant of the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17, SAC 18). Compared to the previously proposed procedures (Eurocrypt 18 & 19, CT-RSA 20), our bootstrapping procedure is more precise, more efficient (in terms of CPU cost and number of consumed levels), and is more reliable and 128-bit-secure. Unlike the previous approaches, it does not require the use of sparse secret-keys. Therefore, to the best of our knowledge, this is the first procedure that enables a highly efficient and precise bootstrapping with a low probability of failure for parameters that are 128-bit-secure under the most recent attacks on sparse R-LWE secrets. We achieve this efficiency and precision by introducing three novel contributions: (i) We propose a generic algorithm for homomorphic polynomial-evaluation that takes into account the approximate rescaling and is optimal in level consumption. (ii) We optimize the key-switch procedure and propose a new technique for linear transformations (double hoisting). (iii) We propose a systematic approach to parameterize the bootstrapping, including a precise way to assess its failure probability. We implemented our improvements and bootstrapping procedure in the open-source Lattigo library. For example, bootstrapping a plaintext in C^32768 takes 18 seconds, has an output coefficient modulus of 505 bits, a mean precision of 19.1 bits, and a failure probability of 2^-15.58. Hence, we achieve 14.1x improvement in bootstrapped throughput (plaintext-bit per second), with respect to the previous best results, and we have a failure probability 468x smaller and ensure 128-bit security.