MHE from RLWE: When MPC Meets Homomorphic Encryption

Secure multiparty computation (MPC) delivers on cryptography's ambitious promise: computing on private inputs while maintaining correctness and distributing trust. Yet this promise comes at a steep price in communication overhead. Every multiplication in a secret-sharing protocol demands an interactive round, meaning a circuit with multiplicative depth $D$ requires at least $D$ synchronized exchanges between all parties. When you factor in the common broadcast patterns where message count per layer scales as $O(N^2)$, the bottleneck becomes clear, throughput is limited not by arithmetic speed but by network latency. The liveness requirements make things even more fragile, as all parties must remain online throughout computation, and a single straggler can stall everything while a dropout might force a complete restart.

Multiparty Homomorphic Encryption (MHE) tackles these exact pain points, communication overhead and synchronization requirements, without sacrificing the distributed trust model that makes MPC valuable in the first place. The core insight is elegant: instead of sharing the data, we share the decryption power. Parties collaborate to generate a public key while keeping the corresponding secret key additively shared among themselves. This setup phase unlocks something remarkable, anyone can evaluate arbitrary circuits on ciphertexts completely non-interactively, with no parties needing to be online during computation. The only interaction happens at the output boundary, where parties collaborate in a short, bandwidth-efficient step to deliver the final result.

This architectural shift fundamentally transforms the cost structure from "one round per multiplication layer" to "one short round per result," with per-party communication scaling linearly in $N$ and supporting asynchronous, wide-area deployments.

Understanding the MPC Baseline

Security Model

MPC protocols are analyzed under several choices:

Adversary behavior.

• Semi-honest (a.k.a. passive): parties follow the code but try to infer extra from the transcript; privacy is proved by simulation.
• Covert ($\varepsilon$-covert): an adversary may deviate, but is caught with probability $\ge 1-\varepsilon$; useful when deterrence suffices.
• Malicious (active/Byzantine): arbitrary deviations allowed; protocols add checks/MACs/zero-knowledge to keep correctness and privacy despite cheating.

Corruption pattern.

• Static: the corrupted set is fixed before the protocol starts.
• Adaptive: the adversary can pick whom to corrupt during the run (even based on seen messages or keys).
• Rushing / strong rushing: in each round the adversary sees honest messages first, then chooses its own, models worst-case scheduling power.

Threshold / who’s stronger.

• Honest majority: $t < n/2$ (or $t < n/3$ with broadcast) enables stronger liveness, fairness and guaranteed output delivery (GOD) are often achievable with simpler tools.
• Dishonest majority: $t \ge n/2$ requires heavier primitives (OT, commitments, HE); typically you get privacy + correctness with (identifiable) abort, but not fairness/GOD.

Goals (what you prove).

• Privacy: nothing beyond the output leaks (via a simulator for the ideal/real paradigm).
• Correctness / soundness: honest parties’ output equals $f(x_1,\dots,x_n)$.
• Robustness / liveness: the protocol completes despite up to $t$ corruptions.
• GOD (guaranteed output delivery) and fairness: everyone gets the output, and nobody learns it earlier; often impossible without honest majority/extra setup.
• Identifiable-abort and selective-abort resistance: if it stops, you can pinpoint a cheater; aborts shouldn’t leak input-dependent bits.

Proof frameworks / composability.

• Stand-alone (simulation-based): security when run in isolation.
• UC / GUC / JUC, IITM, CoSP: composable models where security is preserved under arbitrary concurrency; specify an ideal functionality $\mathcal{F}$ and build a simulator $\mathcal{S}$ against an environment $\mathcal{Z}$.
• Computational vs. statistical/perfect: guarantees under polynomial-time assumptions vs. information-theoretic security.

What we assume here. Throughout this post, we work in a dishonest-majority, semi-honest model with static corruptions and no private channels.

---

To appreciate what we're improving upon, let's briefly examine how traditional MPC handles computation. In additive secret sharing over a field $\mathbb{F}_p$, a secret $x \in \mathbb{F}_p$ gets split into shares $\langle\!\langle x \rangle\!\rangle = (x_1, \dots, x_N)$ where $\sum_i x_i \equiv x \pmod p$. The beauty of this approach lies in its linearity, additions and scalar multiplications become purely local operations that require no communication whatsoever.

Multiplication presents a different challenge entirely. While parties can locally compute $\langle\!\langle x \rangle\!\rangle_i \cdot \langle\!\langle y \rangle\!\rangle_i$, the result isn't a proper sharing of $xy$. The standard solution relies on Beaver triples, authenticated sharings of $(a,b,c)$ where $c = a \cdot b$. Given sharings of $x$ and $y$ along with a triple, the online multiplication protocol opens the masked values $d = x - a$ and $e = y - b$ through synchronized broadcasts, then computes the result locally using the identity $xy = c + ae + bd + de$.

This preprocessing paradigm, exemplified by protocols like SPDZ, splits the work into an offline phase that produces authenticated triples using somewhat homomorphic encryption, followed by a lightweight online phase that consumes these triples. While this separation enables fast online computation even in malicious settings, it doesn't eliminate the fundamental bottleneck: you still need one interactive opening per multiplication layer.

The practical costs add up quickly. Each opening typically involves broadcasts, creating $\Theta(N^2)$ messages per layer unless you deploy more sophisticated network primitives. A single straggler delays the entire round, dropouts require resharing or abort protocols, and in malicious settings each opening carries additional MAC checks and consistency verification overhead. Even with vectorized batch operations, the core constraint remains unchanged, additions are free, but multiplications demand interaction.

This is the baseline we're working to improve: replacing those $D$ interactive multiplication layers with non-interactive evaluation while preserving the "no single party can decrypt alone" trust model.

The MHE Paradigm

Our goal is straightforward yet ambitious: keep computation non-interactive like standard homomorphic encryption while keeping decryption power distributed like MPC. The setup phase has $N$ parties run a distributed key generation (DKG) for an RLWE/BFV scheme, publishing a joint public key $pk$ along with the necessary evaluation keys for relinearization, Galois operations, and bootstrapping. The secret key is never assembled, instead, it remains additively shared as $s = \sum_{i=1}^N s_i$, with party $i$ holding only $s_i$.

Once setup completes, the workflow becomes remarkably simple. Any data owner can encrypt their input $x$ as $ct \leftarrow \mathrm{Enc}_{pk}(x)$, and from that point forward, anyone, even a completely untrusted server, can compute arbitrary functions by evaluating $ct_{\text{out}} \leftarrow \mathrm{Eval}(f; ct_1,\ldots,ct_m; \text{eval-keys})$ without any interaction with the parties or learning anything about the inputs. This eliminates the "one round per multiplication layer" bottleneck entirely.

The only remaining interaction happens at output time, where parties collaborate in a collective key switch (CKS) to move from the shared secret $s$ to a target key $s'$. Often this target is $s'=0$ for collective decryption, or it might be another party's public key through a public key switch (PCKS) protocol. The crucial point is that this heavy computation, the entire circuit evaluation, runs offline and non-interactively, with parties only coming online once for a single short transcript whose size per party scales linearly in $N$.

The contrast with traditional MPC is illuminating. Where MPC shares the data itself, replacing each secret $x$ with additive shares $\langle\!\langle x\rangle\!\rangle=(x_1,\dots,x_N)$ and running computation directly on those shares, MHE shares the decryption power instead. Inputs get encrypted once under a joint public key while the secret key remains additively shared. Anyone can evaluate on ciphertexts non-interactively, and only at the end do parties collaborate to decrypt.

MBFV-based MPC Protocol

This section presents our concrete instantiation using BFV/RLWE encryption over power-of-two cyclotomic rings $R_q=\mathbb{Z}_q[X]/(X^n+1)$ and $R_t=\mathbb{Z}_t[X]/(X^n+1)$ with scaling parameter $\Delta\approx \lfloor q/t \rfloor$. The protocol involves $N$ parties $\mathcal{P}_1,\ldots,\mathcal{P}_N$ who jointly hold an additively shared secret key $s=\sum_i s_i$ while publishing a joint public key $pk$ and making the necessary evaluation keys available for relinearization, Galois operations, and bootstrapping.

The workflow follows a clean separation of concerns. Data owners encrypt messages in $R_t$ under the public key $pk$, an untrusted evaluator $\mathcal{E}$ performs all homomorphic work offline without any party interaction, and at the end a qualified set of parties collaborates to release results either collectively or to a designated receiver $\mathcal{R}$. Throughout this process we maintain a public-transcript discipline where all interactive steps can be logged on an authenticated broadcast channel without requiring private communication channels.

Distributed Secret Key Generation

The foundation of our approach lies in creating a BFV secret key that never gets assembled while still behaving like a standard small-norm key. The process is surprisingly simple and requires no communication whatsoever. Each party $\mathcal P_i$ locally samples a small share $s_i \leftarrow \texttt{BFV.SecKeyGen}()$ using the standard BFV secret key generation algorithm, and the collective secret key is defined additively as $s = \big[\sum_{i=1}^N s_i\big]_q$.

This non-interactive approach means no messages get exchanged, no private channels are needed, and the full secret key $s$ never exists anywhere in the clear. The trade-off is that $s$, being a sum of $N$ small polynomials, has norm that increases with $N$. Parameter selection must account for this growth, but it doesn't create a fundamental bottleneck even for moderately large party counts.

Once parties complete this distributed key generation, they proceed to derive the collective public key and evaluation keys using the public-transcript procedures that follow, all building on the additive structure of the shared secret $s$.

Collective Public Key Generation

Creating a BFV public key for the collective secret $s=\sum_i s_i$ without ever assembling $s$ requires careful coordination, but the protocol itself is elegantly straightforward. The key insight is using a common reference string to ensure all parties work with the same random polynomial $p_1 \in R_q$. In the passive security model, this can be derived deterministically from a shared seed using a pseudorandom function like BLAKE2b, guaranteeing that everyone derives identical $p_1$ values.

Each party $\mathcal P_i$ samples a small error term $e_i \leftarrow \chi$ from the designated error distribution and publishes their contribution $p_{0,i} = \big[-s_i p_1 + e_i\big]_q \in R_q$. The aggregation step is straightforward, anyone can sum these contributions to obtain

$$p_0 = \big[\sum_{i} p_{0,i}\big]_q = \big[-\big(\sum_{i} s_i\big) p_1 + \sum_{i} e_i\big]_q$$

which gives us the collective public key $\mathrm{cpk} = (p_0, p_1)$.

This construction maintains the exact BFV structure with secret $s$ and aggregated error $e=\sum_i e_i$. The security argument is clean: since $p_1$ is uniformly distributed in $R_q$ and the aggregated error $e$ has small norm, the pair $(p_0,p_1)$ becomes computationally indistinguishable from a standard BFV public key under the decisional RLWE assumption.

While the worst-case norms $\lVert s\rVert$ and $\lVert e\rVert$ grow linearly in $N$, this parameter scaling can be accounted for during setup without creating fundamental scalability barriers for reasonable party counts. The communication profile is highly efficient, requiring only one broadcast per party with a completely public transcript that needs no private channels. With the collective public key $\mathrm{cpk}$ established, standard BFV encryption proceeds exactly as in the single-key setting, but now operating under the shared secret $s$.

Relinearization Key Generation

Generating relinearization keys in the multiparty setting requires more sophistication than public key generation, since we need to "encrypt" $s^2\mathbf{w}$ under the shared secret $s=\sum_i s_i$ without using the public encryption oracle and while maintaining low noise levels.

The following solution uses public coins combined with the additive structure of the shared secret to emulate the quality of centralized BFV relinearization keys. The protocol takes as public input a vector $\mathbf{a}\in R_q^{\ell}$ sampled from the common reference string along with a decomposition basis $\mathbf{w}=(w^0,\ldots,w^{\ell-1})^\top$, while each party $P_i$ contributes its private key share $s_i$.

The protocol proceeds in two coordinated steps. In the first step, each party $P_i$ samples a small masking term $u_i$ along with error vectors $\mathbf{e}_{0,i},\mathbf{e}_{1,i}\leftarrow\chi^{\ell}$, then publishes the contribution

$$(\mathbf{h}_{0,i},\mathbf{h}_{1,i})=\big(-u_i\mathbf{a}+s_i\mathbf{w}+\mathbf{e}_{0,i}, s_i\mathbf{a}+\mathbf{e}_{1,i}\big).$$

When aggregated, these contributions yield

$$\mathbf{h}_0=\sum_j\mathbf{h}_{0,j}=-u\mathbf{a}+s\mathbf{w}+\mathbf{e}_0 \text{ and } \mathbf{h}_1=\sum_j\mathbf{h}_{1,j}=s\mathbf{a}+\mathbf{e}_1,$$

where $u=\sum_j u_j$, $s=\sum_j s_j$, and $\mathbf{e}_d=\sum_j\mathbf{e}_{d,j}$.

The second step uses these aggregated values $\mathbf{h}_0,\mathbf{h}_1$ to complete the relinearization key construction. Each party samples fresh error terms $\mathbf{e}_{2,i},\mathbf{e}_{3,i}\leftarrow\chi^{\ell}$ and publishes

$$(\mathbf{h}'_{0,i},\mathbf{h}'_{1,i})=\big(s_i\mathbf{h}_0+\mathbf{e}_{2,i}, (u_i-s_i)\mathbf{h}_1+\mathbf{e}_{3,i}\big).$$

Aggregating these final contributions produces the relinearization key

$$\mathbf{rlk}=(\mathbf{r}_0,\mathbf{r}_1)=(\mathbf{h}'_0+\mathbf{h}'_1, \mathbf{h}_1) = \big(-s\mathbf{b} + s^2\mathbf{w} + s\mathbf{e}_0 + \mathbf{e}_1 + u\mathbf{e}_2 + \mathbf{e}_3,\; \mathbf{b}\big).$$

The communication requirements are modest, two public broadcasts per party across $\ell$ digits, with no private channels required. This construction successfully uses public coins and the shared secret structure to emulate centralized BFV relinearization key quality, which substantially improves the noise profile of relinearized ciphertexts.

Collective Key Switching

The collective key switching (CKS) protocol provides the crucial bridge between the non-interactive evaluation phase and result delivery. Given a ciphertext $ct=(c_0,c_1)$ encrypted under the collective secret $s=\sum_i s_i$, CKS switches it to an output key $s'$ known collectively by the parties without revealing any individual share $s_i$. The target key $s'$ might be zero for decryption purposes or represent a new shared key after rotating the access set.

The protocol design prioritizes simplicity and efficiency. Each party contributes by sampling fresh smudging noise $e_i$ and publishing $h_i = (s_i - s'_i)c_1 + e_i \in R_q$, where $s'_i$ represents their share of the target key. Any aggregator can then compute $h = \sum_{i} h_i = (s - s')c_1 + e_{\text{CKS}}$ with $e_{\text{CKS}}=\sum_i e_i$, and output the switched ciphertext $ct'=(c_0',c_1)$ where $c_0' = c_0 + h$.

To see the correctness run BFV decryption under $s'$

$$\begin{aligned} \mathrm{BFV.Dec}(s',ct') &= \left\lfloor \tfrac{t}{q}\Big[\, c_0' + s'c_1 \,\Big]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\Big[\, c_0 + (s-s')c_1 + e_{\text{CKS}} + s'c_1 \,\Big]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\Big[\, \Delta m + e_{\text{ct}} + e_{\text{CKS}} \,\Big]_q \right\rceil \;=\; m, \end{aligned}$$

provided the post-switch noise $\lVert e_{\text{ct}} + e_{\text{CKS}} \rVert_\infty$ remains within the BFV decoding radius $q/(2t)$. Each contribution $h_i$ gets masked by fresh noise $e_i$, ensuring that individual $(s_i - s'_i)c_1$ terms remain information-theoretically hidden while the transcript reveals only what's implied by the output ciphertext $ct'$.

The communication profile is excellent, just one broadcast of a ring element per party plus a single aggregation step. This represents the "short boundary round" that concludes an otherwise completely offline evaluation. For the special case of decryption, setting $s'=0$ gives us

$$c_0' = c_0 + s c_1 + e_{\text{CKS}} \approx \Delta m + (e_{\text{ct}}+e_{\text{CKS}})$$

allowing direct decoding under the zero key to recover the message $m$.

Public Key Switching

While collective key switching handles cases where parties collectively know the target secret key, public key switching (PCKS) addresses the scenario where results must be delivered to an external receiver who has only exposed a public key $pk'=(p_0',p_1')$ for some unknown secret $s'$. This capability is essential for "push" delivery of outputs to recipients outside the decryption access set, where CKS would not be applicable.

The protocol maintains the same public-transcript discipline while handling the additional complexity of not knowing the target secret key. Each party $P_i$ samples small terms $u_i$ and fresh noises $e_{0,i}, e_{1,i}$ from the designated error distributions, then publishes

$$(h_{0,i}, h_{1,i}) = \big(s_i c_1 + u_i p_0' + e_{0,i}, u_i p_1' + e_{1,i}\big).$$

After aggregation, the switched ciphertext becomes $ct'=(c_0',c_1') = (c_0 + h_0, h_1)$ where $h_0=\sum_i h_{0,i}$ and $h_1=\sum_i h_{1,i}$.

Using $p_0' = -\big(s' p_1' + e_{\mathrm{pk}}\big)$ and $u=\sum_i u_i$, $e_d=\sum_i e_{d,i}$ for $d\in\{0,1\}$, decryption under $s'$ yields

$$\begin{aligned} \mathrm{Dec}(s',ct') &= \left\lfloor \tfrac{t}{q}\,[\, c_0' + s' c_1' \,]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\,[\, c_0 + s c_1 + u p_0' + e_0 \;+\; s' (u p_1' + e_1) \,]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\,[\, \Delta m + e_{\mathrm{ct}} \;+\; e_{\mathrm{PCKS}} \,]_q \right\rceil \;=\; m, \end{aligned}$$

as long as the total noise stays within the BFV decoding radius, where

$$e_{\mathrm{PCKS}} \;=\; e_0 \;+\; s' e_1 \;+\; u\, e_{\mathrm{pk}}.$$

Hence $\|e_{\mathrm{ct}} + e_{\mathrm{PCKS}}\|_\infty < q/(2t)$ guarantees correctness.

The security argument mirrors CKS, each contribution gets masked by fresh noise and public-key terms, making transcripts simulatable given the output ciphertext in the semi-honest model. No party learns the target secret $s'$ and no private channels are required. The cost profile matches CKS with one broadcast of two ring elements per party plus aggregation, enabling efficient delivery to external receivers while maintaining all security properties.

Bridging Between Representations

The ability to move seamlessly between ciphertexts (MHE representation) and additive shares (MPC representation) using single-round protocols with public transcripts opens up powerful hybrid computation strategies. These bridging protocols, Enc2Share and Share2Enc, serve as the fundamental building blocks for our collective bootstrapping approach.

From Ciphertext to Shares

The Enc2Share protocol starts with a BFV ciphertext $ct=(c_0,c_1)$ encrypting message $m\in R_t$ under the collective key and produces additive shares $M_1,\dots,M_N\in R_t$ such that $\sum_i M_i \equiv m \pmod t$. The approach cleverly combines collective key switching with local masking to maintain privacy throughout the conversion.

Each party $P_i$ samples a fresh mask $M_i \leftarrow R_t$ and smudging noise $e_{0,i} \leftarrow \chi_{\text{CKS}}$, then computes a masked partial decryption

$$h_{0,i} = s_i c_1 - \Delta M_i + e_{0,i}, \qquad \Delta=\lfloor q/t\rfloor.$$

Parties $P_2,\ldots,P_N$ publish their $h_{0,i}$ values while the designated party $P_1$ withholds its own term. The public contributions aggregate as

$$h_0 = \sum_{i=2}^N h_{0,i} = (s-s_1)c_1 - \Delta(M-M_1) + e_0,$$

where $M=\sum_i M_i$ and $e_0=\sum_{i=2}^N e_{0,i}$.

Party $P_1$ then adds its secret piece $s_1 c_1$ locally and applies the BFV rounding map to obtain its share:

$$\begin{aligned} y &= c_0 + h_0 + s_1 c_1 = c_0 + s c_1 - \Delta(M-M_1) + e_0,\\ M_1 &= \Big[\Big\lfloor \tfrac{t}{q}[y]_q \Big\rceil\Big]_t \equiv m - \sum_{i=2}^N M_i \pmod t, \end{aligned}$$

since $c_0+s c_1=\Delta m+e_{\text{ct}}$ and rounding removes the bounded noise.

Privacy protection comes from the $-\Delta M_i$ masks and fresh smudging noise $e_{0,i}$ applied to each published $h_{0,i}$, ensuring no party learns the underlying message $m$ while maintaining simulatable transcripts. Only $P_1$ combines the public sum with its private term $s_1 c_1$ to obtain its share $M_1$; no party ever sees $m$ itself. The communication cost is minimal, one ring element per party except for the holder of the private residual, plus one decoding operation. The role of $P_1$ is arbitrary and can rotate across different protocol executions.

From Shares to Ciphertext

The Share2Enc protocol reverses this process, starting from additive shares $M_1,\dots,M_N$ of message $m$ and producing a single BFV ciphertext $ct=(c_0,c_1)$ encrypting $m$ under the collective key. The core insight treats $(\Delta M_i, a)$ as a "plaintext ciphertext" under the trivial key zero, then applies collective key switching to move from key zero to the shared key $s$.

Using a public element $a \in R_q$ sampled from the common reference string, each party $P_i$ samples fresh noise $e_{1,i} \leftarrow \chi$ and computes a contribution

$$u_i = -s_i a + \Delta M_i + e_{1,i}$$

with the noise $e_{1,i}$ providing the usual smudging. All parties publish their $u_i$ values simultaneously in a single round.

The combiner (any party) aggregates these contributions to form the output ciphertext:

$$ct' = \big(\sum_{i=1}^N u_i, a\big) = \big(\Delta m - s a + e, a\big)$$

where $e=\sum_i e_{1,i}$, which has the standard BFV encryption shape. Correctness follows since

$$c_0' + s c_1' = \sum_i(-s_i a + \Delta M_i + e_{1,i}) + \Big(\sum_i s_i\Big)a = \Delta \sum_i M_i + \sum_i e_{1,i} = \Delta m + e,$$

and the BFV rounding map recovers $m$ with overwhelming probability under the standard decoding bound.

The intuition is that each party contributes its share of the collective secret key term $-as$ (namely $-a s_i$), its share of the scaled message $\Delta M_i$, and its own fresh noise $e_{1,i}$. Summing these contributions yields the proper BFV ciphertext structure. Alternatively, one can view $(\Delta M_i, a)$ as a "plaintext ciphertext under key zero," and the protocol realizes a collective key switch from key zero to the shared key $s$.

Privacy protection comes from the fresh smudging noise $e_{1,i}$ in each contribution, ensuring that each published pair $(a, u_i)$ appears as a standard RLWE sample with secret $(-s_i)$ and embedded message $\Delta M_i$. The communication cost is minimal, one ring element per party in a single round with a public transcript. The combiner requires no secret information, only the public values $a$ and the published $u_i$ terms, yet produces a ciphertext that only the parties collectively can decrypt.

Collective Bootstrapping

BFV ciphertexts inevitably accumulate noise through addition and multiplication operations, and once this noise approaches the decoding bound, some form of refreshing becomes necessary. Traditional bootstrapping evaluates the decryption function homomorphically, which is computationally expensive. Our collective bootstrapping approach trades this heavy computation for a single short interactive round among the parties who already share the secret key, producing a ciphertext that is essentially a fresh encryption of the same plaintext.

The approach leverages the BFV decryption structure where a ciphertext $(c_0, c_1)$ decrypts to plaintext $m$ through the formula:

$$m = \Big[\Big\lfloor \tfrac{t}{q}\,\big[c_0+s\,c_1\big]_q \Big\rceil\Big]_t, \qquad \Delta \approx \big\lfloor\tfrac{q}{t}\big\rfloor$$

The protocol takes as public input a common reference string element $a \in R_q$ along with the ciphertext $ct=(c_0,c_1)$ that needs refreshing. Each party $P_i$ contributes its secret share $s_i$ where $s=\sum_i s_i$, and the protocol produces a refreshed ciphertext $ct'=(c_0',c_1')$ whose noise variance has been reset to approximately $N\sigma^2$.

The Protocol Mechanics

Each party performs the same local computation during the single communication round. Party $P_i$ begins by sampling a mask share $M_i \in R_t$ that will be used to hide the underlying plaintext, along with smudging noise $e_{0,i} \leftarrow \chi_{\mathrm{CKS}}(\sigma_{ct}^2)$ and fresh noise $e_{1,i} \leftarrow \chi$. These random elements ensure that no individual party can learn anything about the plaintext being refreshed. The party then publishes two components:

$$\begin{aligned} h_{0,i} &= s_i c_1 - \Delta M_i + e_{0,i}\\[2pt] h_{1,i} &= -s_i a + \Delta M_i + e_{1,i} \end{aligned}$$

When these contributions are aggregated across all parties, we obtain values that capture the collective secret while maintaining the masking structure:

$$h_0=\sum_i h_{0,i}= s\,c_1 - \Delta M + e_0,\qquad h_1=\sum_i h_{1,i}= -s\,a + \Delta M + e_1$$

Here $M=\sum_i M_i$ represents the sum of all mask shares, while $e_0=\sum_i e_{0,i}$ and $e_1=\sum_i e_{1,i}$ are the aggregated noise terms that provide the necessary randomization for security.

Constructing the Fresh Ciphertext

The combiner uses these aggregated values to construct a refreshed ciphertext that encrypts the same plaintext with reset noise. The construction follows a specific pattern that ensures the result has the proper BFV structure:

$$\begin{aligned} c_1' &= a\\[2pt] c_0' &= \Big[\Big\lfloor \tfrac{t}{q}\,[\,c_0+h_0\,]_q \Big\rceil\Big]_t\,\Delta + h_1 \end{aligned}$$

This construction might appear complex, but it follows naturally from the BFV decryption structure and the additive properties of the secret sharing scheme.

Why This Works: The Correctness Argument

The key insight lies in understanding what happens inside the rounding operation. When we compute $c_0+h_0$, we're essentially performing a partial decryption while maintaining the additive structure:

$$c_0+h_0 = c_0 + s c_1 - \Delta M + e_0 = \Delta m + \underbrace{e_{\text{ct}}}_{\text{old noise}} - \Delta M + e_0$$

The rounding and scaling operation extracts the plaintext information while removing the old noise:

$$\Big[\Big\lfloor \tfrac{t}{q}\,[c_0+h_0]_q \Big\rceil\Big]_t = (m - M + \text{small}) \bmod t$$

where the "small" term represents residual effects from $e_{\text{ct}}$ and $e_0$ that get controlled by the rounding process. Substituting this back into our construction gives us:

$$c_0' = -s a + \Delta m + (e_1 + \Delta \cdot \text{small}),\qquad c_1'=a$$

This is precisely the structure of a valid BFV encryption of plaintext $m$ under secret key $s$, but now the noise term comes entirely from the fresh randomness $e_1$ rather than the accumulated noise from previous operations.

Understanding the Bootstrapping Property

What makes this protocol qualify as bootstrapping is the complete renewal of the noise profile. The refreshed ciphertext has noise that comes from the sum $\sum_i e_{1,i}$ with variance approximately $N\sigma^2$, plus small contributions from the rounding process. Crucially, this new noise is completely independent of the old accumulated noise $e_{\text{ct}}$ that was threatening to breach the decoding bound.

The smudging noises $e_{0,i}$ serve a different but equally important purpose, they ensure the protocol transcript can be simulated without knowledge of the plaintext $m$, maintaining privacy throughout the refreshing process. This means the resulting ciphertext $ct'$ behaves exactly like a brand-new encryption of the same plaintext $m$, enabling further homomorphic evaluation without the noise constraints that necessitated bootstrapping in the first place.

The efficiency profile is compelling: the output ciphertext $ct'=(c_0',a)$ encrypts the same plaintext $m$ with noise reset to fresh levels scaling as $N\sigma^2$. Privacy is maintained since no party learns $m$ and all transcripts remain simulatable. The communication cost involves just one broadcast round where each party contributes two ring elements, giving overall complexity linear in the number of parties $N$.

Example

The following example demonstrates a 3-party Multiparty Homomorphic Encryption (MHE) workflow using Lattigo’s BGV scheme. Three locally simulated parties run collective public-key generation (CKG), each encrypts one integer, a coordinator adds the ciphertexts, and the result is re-encrypted to a receiver via Public Key Switch (PCKS) and decrypted, so no single party ever holds the joint secret key.

package main

import (
	"flag"
	"fmt"
	"log"

	"github.com/tuneinsight/lattigo/v6/core/rlwe"
	"github.com/tuneinsight/lattigo/v6/multiparty"
	"github.com/tuneinsight/lattigo/v6/ring"
	"github.com/tuneinsight/lattigo/v6/schemes/bgv"
	"github.com/tuneinsight/lattigo/v6/utils/sampling"
)

type party struct {
	sk *rlwe.SecretKey
}

func main() {
	// CLI
	a := flag.Int("a", 7, "party A integer")
	b := flag.Int("b", 12, "party B integer")
	c := flag.Int("c", 20, "party C integer")
	flag.Parse()

	// Parameters: small demo (N=2^12, t=65537). Very short Q-chain for adds only.
	params, err := bgv.NewParametersFromLiteral(bgv.ParametersLiteral{
		LogN:             12,
		PlaintextModulus: 65537,
		LogQ:             []int{54, 55},
		LogP:             []int{55},
	})
	check(err)

	encoder := bgv.NewEncoder(params)

	// Receiver keypair (for output via PCKS)
	tsk, tpk := rlwe.NewKeyGenerator(params).GenKeyPairNew()

	// 3 parties with independent secret shares
	var parties = make([]party, 3)
	for i := range parties {
		parties[i].sk = rlwe.NewKeyGenerator(params).GenSecretKeyNew()
	}

	// Collective Public Key Generation (CKG)
	crs, err := sampling.NewKeyedPRNG([]byte("mpbgv-sum-ckg-seed"))
	check(err)
	pk := execCKG(params, crs, parties)

	// Each party: encode & encrypt its scalar under collective pk
	ctA := encryptScalar(params, pk, encoder, *a)
	ctB := encryptScalar(params, pk, encoder, *b)
	ctC := encryptScalar(params, pk, encoder, *c)

	// Homomorphic addition
	eval := bgv.NewEvaluator(params, nil, false)
	tmp := bgv.NewCiphertext(params, 1, params.MaxLevel())
	sum := bgv.NewCiphertext(params, 1, params.MaxLevel())
	check(eval.Add(ctA, ctB, tmp))
	check(eval.Add(tmp, ctC, sum))

	// Re-encrypt result to receiver’s pk (PCKS)
	encOut := execPCKS(params, tpk, sum, parties)

	// Receiver decrypts (Decrypt returns no value in v6)
	decryptor := rlwe.NewDecryptor(params, tsk)
	pt := bgv.NewPlaintext(params, encOut.Level())
	decryptor.Decrypt(encOut, pt)

	// Decode first slot
	dec := make([]uint64, params.MaxSlots())
	check(encoder.Decode(pt, dec))
	res := int(dec[0])

	fmt.Printf("Inputs: a=%d, b=%d, c=%d\n", *a, *b, *c)
	fmt.Printf("Homomorphic sum (decrypted): %d\n", res)
	if res == *a+*b+*c {
		fmt.Printf("Check: %d+%d+%d = %d ✅\n", *a, *b, *c, res)
	} else {
		fmt.Printf("Check: %d+%d+%d != %d ❌\n", *a, *b, *c, res)
	}
}

// encryptScalar encodes x in slot 0 and encrypts it under the collective pk.
func encryptScalar(params bgv.Parameters, pk *rlwe.PublicKey, enc *bgv.Encoder, x int) *rlwe.Ciphertext {
	pt := bgv.NewPlaintext(params, params.MaxLevel())
	batch := make([]uint64, params.MaxSlots())
	if x < 0 {
		t := uint64(params.PlaintextModulus())
		batch[0] = (t - uint64(-x)%t) % t
	} else {
		batch[0] = uint64(x)
	}
	check(enc.Encode(batch, pt))

	encryptor := rlwe.NewEncryptor(params, pk)
	ct := bgv.NewCiphertext(params, 1, params.MaxLevel())
	check(encryptor.Encrypt(pt, ct))
	return ct
}

// execCKG runs multiparty collective public-key generation.
func execCKG(params bgv.Parameters, crs sampling.PRNG, P []party) *rlwe.PublicKey {
	ckg := multiparty.NewPublicKeyGenProtocol(params)
	crp := ckg.SampleCRP(crs)

	shares := make([]multiparty.PublicKeyGenShare, len(P))
	for i := range shares {
		shares[i] = ckg.AllocateShare()
		ckg.GenShare(P[i].sk, crp, &shares[i])
	}

	combined := ckg.AllocateShare()
	for i := range shares {
		ckg.AggregateShares(shares[i], combined, &combined)
	}

	pk := rlwe.NewPublicKey(params)
	ckg.GenPublicKey(combined, crp, pk)
	return pk
}

// execPCKS re-encrypts ctIn to tpk using the PublicKeySwitch protocol.
func execPCKS(params bgv.Parameters, tpk *rlwe.PublicKey, ctIn *rlwe.Ciphertext, P []party) *rlwe.Ciphertext {
	pcks, err := multiparty.NewPublicKeySwitchProtocol(
		params,
		ring.DiscreteGaussian{Sigma: 1 << 30, Bound: 6 * (1 << 30)},
	)
	check(err)

	shares := make([]multiparty.PublicKeySwitchShare, len(P))
	for i := range shares {
		shares[i] = pcks.AllocateShare(params.MaxLevel())
		pcks.GenShare(P[i].sk, tpk, ctIn, &shares[i])
	}

	combined := pcks.AllocateShare(params.MaxLevel())
	for i := range shares {
		check(pcks.AggregateShares(shares[i], combined, &combined))
	}

	out := bgv.NewCiphertext(params, 1, params.MaxLevel())
	pcks.KeySwitch(ctIn, combined, out)
	return out
}

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

Conclusion

Multiparty Homomorphic Encryption fundamentally reshapes collaborative private computation by moving from "share the data" to "share the decryption power." This paradigm shift transforms the cost profile from needing one interactive round per multiplication layer to requiring just one short round per result, with communication scaling linearly in the number of parties.

The MBFV toolkit makes this practical through carefully designed protocols that maintain BFV-level security while enabling distributed operations. Collective key generation produces standard-looking public keys without ever assembling the secret, and the key-switching protocols (both CKS and PCKS) provide efficient output delivery with public transcripts only.

Perhaps most importantly, this approach enables truly asynchronous computation where heavy evaluation happens offline without requiring all parties to be online simultaneously. The only synchronization point occurs at output time, dramatically improving practical deployability compared to traditional MPC protocols that stall on stragglers and struggle with network partitions.

Acknowledgements

This post is inspired by “Multiparty Homomorphic Encryption from Ring-Learning-with-Errors” by Victor Mouchet, Juan Ramón Troncoso-Pastoriza, Jean-Philippe Bossuat, and Jean-Pierre Hubaux. Big thanks to the maintainers of Lattigo whose implementations helped shape intuition about practical parameterization and costs.