International Association
for Cryptologic Research

Ring-LWE based homomorphic encryption computations in large depth use a combination of two techniques: 1) decomposition of big numbers into small limbs/digits, and 2) efficient cyclotomic multiplications modulo $X^N+1$. It was long believed that the two mechanisms had to be strongly related, like in the full-RNS setting that uses a CRT decomposition of big numbers over an NTT-friendly family of prime numbers, and NTT over the same primes for multiplications. However, in this setting, NTT was the bottleneck of all large-depth FHE computations. A breakthrough result from Kim et al. (Crypto'2023) managed to overcome this limitation by introducing a second gadget decomposition and showing that it indeed shifts the bottleneck and renders the cost of NTT computations negligible compared to the rest of the computation. In this paper, we extend this result (far) beyond the Full-RNS settings and show that we can completely decouple the big number decomposition from the cyclotomic arithmetic aspects. As a result, we get modulus switching/rescaling for free. We verify both in theory and in practice that the performance of key-switching, external and internal products and automorphisms using our representation are faster than the one achieved by Kim et al., and we discuss the high impact of these results for low-level or hardware optimizations as well as the benefits of the new parametrizations for FHE compilers. We even manage to lower the running time of the gate bootstrapping of $\TFHE$ by eliminating one eighth of the FFTs and one sixth of the linear operations, which lowers the running time below 5.5ms on recent CPUs.

We propose a novel framework, $$\texttt{Manticore}$$ Manticore , for multiparty computations, with full threshold and semi-honest security model, supporting a combination of real number arithmetic (arithmetic shares), Boolean arithmetic (Boolean shares) and garbled circuits (Yao shares). In contrast to prior work (Mohassel and Zhang, in 2017 IEEE symposium on security and privacy (SP), 2017; Mohassel and Rindal, in Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, 2018), $$\texttt{Manticore}$$ Manticore mitigates overflows, which is of paramount importance for machine learning applications, without compromising efficiency or security. Compared to other overflow-free recent techniques such as MP-SPDZ (Escudero et al., in 40th annual international cryptology conference, CRYPTO. Lecture notes in computer science, 2020) that convert arithmetic to Boolean shares, $$\texttt{Manticore}$$ Manticore uses an efficient modular lifting/truncation method that allows for scalable high numerical precision computations with optimal numerical windows and hence, highly efficient online phases. We adapt basic MPC operations such as real-valued polynomial evaluation, division, logarithms, exponentials, Fourier series evaluations and oblivious comparisons to $$\texttt{Manticore}$$ Manticore by employing our modular lift in combination with existing efficient conversions between arithmetic, Boolean and Yao shares. We also describe a highly scalable computations of logistic regression models with real-world training data sizes and high numerical precision through PCA and blockwise variants (for memory and runtime optimizations) based on second-order optimization techniques. On a dataset of 50 M samples and 50 features distributed among two players, the online phase completes in 14.5 h with at least 10 decimal digits of precision compared to plaintext training. The setup phase of $$\texttt{Manticore}$$ Manticore is supported in both the trusted dealer and the interactive models allowing for tradeoffs between efficiency and stronger security. The highly efficient online phase makes the framework particularly suitable for MPC applications where the output of the setup phase is part of the input of the protocol (such as MPC-in-the-head or Prio ).