All RLWE-based FHE schemes are inherently noisy. The CKKS scheme (Cheon, Kim, Kim, Song, Asiacrypt 2017) considers the noise as a part of the message, yielding approximate computations but also considerable performance gains. Since it grows with each homomorphic operation and incurs a precision loss, it is paramount for users to be able to estimate the noise level throughout a given circuit in order to appropriately estimate parameters and control the precision loss in the message. In this work, we develop a noise model that allows for tight estimates of the precision loss, and propose a tool prototype for computing these estimates on any given circuit. Our noise model relies on a novel definition, the component-wise noise, which makes the average-case noise estimates tighter and more composable. As a result, our model and tool can derive accurate estimates of complex circuits such as bootstrapping. We experimentally demonstrate the tightness of our noise estimates by showing that our theoretical estimates never deviate by more than 0.01 bits from experimental estimates, even for large circuits, and hold with high probability. Furthermore, we demonstrate how to apply our techniques to obtain an exact version of the CKKS scheme in which the decryption removes all the noise (with high probability). Such a scheme has many applications, as it allows to take advantage of the efficiency of CKKS, while preserving an exact message space, hence further strengthening CKKS against IND-CPA-D attacks.

We revisit the problem of constructing protocols for multiparty private set intersection (MPSI) in light of the recent advances in multiparty homomorphic encryption (MHE). In MPSI, N larger than 2 parties jointly compute the intersection of their respective private set. Kissner and Song proposed an MHE-based MPSI scheme in 2005, but their approach was limited by the then-available HE schemes. Today, however, MHE schemes have become both more versatile and more efficient. As an early result, we implemented the MPSI approach of Kissner et al. with the recently proposed Helium framework (CCS 2024) for MHE-based MPC. We show that even this simple protocol can outperform the state-of-the-art implementation (in the passive-adversary setting) by Kolesnikov et al. (CCS 2017), both in terms of latency and communication cost.

We introduce Helium, a novel framework that supports scalable secure multiparty computation (MPC) for lightweight participants and tolerates churn. Helium relies on multiparty homomorphic encryption (MHE) as its core building block. While MHE schemes have been well studied in theory, prior works fall short of addressing critical considerations paramount for adoption such as supporting resource-constrained and unstably connected participants. In this work, we systematize the requirements of MHE-based MPC protocols from a practical lens, and we propose a novel execution mechanism that addresses those considerations. We implement this execution mechanism in Helium, which makes it the first implemented framework to support MPC under network churn based solely on cryptographic assumptions. We show that a Helium network of 30 parties connected with 100Mbits/s links and experiencing a system-wide churn rate of 40 failures per minute can compute the product between a fixed 512 × 512 secret matrix (e.g., a collectively-trained private model) and a fresh secret vector (e.g., a feature vector) 8.3 times per second. This is ∼1500 times faster than a state-of-the-art MPC framework operating under no churn.