• *Hybrid* $\mathcal{H}_1$. In this hybrid, we replace $k_B$ with a uniformly random key and set $k_A = k_B + C(x_A, x_B) \cdot \Delta_A \cdot \Delta_B$. This hybrid is computationally indistinguishable from the previous one by the external security of MKHSS.

• *Hybrid* $\mathcal{H}_2$. In this hybrid, we sample $(k_A, k_B)$ as a uniformly random tuple over $\mathbb{F} \times \mathbb{F}$. This hybrid is computationally indistinguishable from the previous one by the pseudorandomness of $\Delta_A \cdot \Delta_B$ (which are generated internally using the PRF). To see this, it suffices to note that, in $\mathcal{H}_1$, we already have that $k_B$ is computationally indistinguishable from a random field element conditioned on $k_A$, since we can view $\Delta_A \cdot \Delta_B$ as being a uniformly random element.

At this point, it suffices to note that $\mathcal{H}_2$ is distributed identically to the output of the ideal functionality when the predicate is not satisfied. This concludes the proof for the case where both parties are honest.

- *Case 2: Alice is corrupted.* The simulator computes $(pk_B, sk_B) \leftarrow \text{MKHSS.KeyGen}(\text{crs})$ and $([\mathbf{0}]_B^A, [\mathbf{0}]_B^B) \leftarrow \text{MKHSS.Share}(\text{crs}, B, pk_B, \mathbf{0})$, to define $pe_B := (pk_B, [\mathbf{0}]_A^B)$, where $\mathbf{0} := 0^{\lambda+|x|}$.

The simulated view of Alice consists of crs and $pe_B$. Eventually, the simulator recovers $x_A$ and $\text{st}_A = (\text{sk}_A, [[K_A \| x_A]]_A^A)$. It computes $k_A := \text{MKHSS.Eval}(\text{crs}, A, sk_A, pk_B, [[K_A \| x_A]]_A^A, [\mathbf{0}]_A^B)$ and sends $k_A$ to the functionality on behalf of the ideal adversary. The functionality outputs $k_A$ to Alice and $k_B$ to Bob. By the security of MKHSS and a straightforward hybrid argument, the joint distribution of Bob's message and the output of both parties in the real world is indistinguishable from the simulation of Bob's message and the output of the ideal functionality.

- *Case 3: Bob is corrupted.* This case follows by symmetry.

<figure><img src="image_5.png" /></figure>

**Corollary 3.** *Assuming the existence of PRFs in NC¹, there exists an attribute-based non-interactive key exchange supporting predicates described by polynomial-size RMS programs under either (1) the DCR assumption or (2) the DDH and small exponent assumptions in the NIDLS framework.*

# 6 Public-Key PCFs from MKHSS and Applications

Practical secure computation protocols are realized in the preprocessing model [DPSZ12]: During an “offline” preprocessing phase, the computing parties generate a large amount of *pseudorandom correlations* that are independent of any function. Then, during an online phase, the parties use the stored correlations to compute a function over their inputs in a secure protocol. The advantage of this model is that it pushes the bulk of the communication and computation costs of the function-dependent online phase to the preprocessing phase. Pseudorandom correlation generators (PCGs) and functions (PCFs) push this model of secure computation to the limit by allowing parties to locally expand a short key into a virtually unbounded amount of correlated randomness. However, traditional approaches still require the parties to run an interactive protocol to generate their key.

**Public-key PCFs.** A *public-key* PCF (PK-PCF) is a PCF equipped with a non-interactive key distribution protocol. Public-key PCFs were originally introduced in the work of Orlandi et al. [OSY21] and formalized in the recent work of Bui et al. [BCM+24]. PK-PCFs are motivated by their direct application to secure computation in the preprocessing model.

Let $\mathcal{Y}$ be a correlation such that a secure access to random samples from $\mathcal{Y}$ enables efficient information-theoretic two-party computation (typically, $\mathcal{Y}$ can sample an oblivious transfer correlation, Beaver triples, authenticated Beaver triples, or other types of correlated randomness, depending on the application at hand). A PK-PCF for $\mathcal{Y}$ induces the following appealing template for communication-efficient secure two-party computation:

**Non-interactive preprocessing.** Ahead of time, all participants $P_i$ of a secure computation network upload their PK-PCF public key $pk_i$ to some public bulletin board.

**Fast, online secure computation.** Whenever two parties $P_i$ and $P_j$ want to securely compute a function, they can retrieve each other's public keys, non-interactively derive correlated PCF keys, and generate as many pseudorandom samples from $\mathcal{Y}$ as they need to enable a fast online phase for a two-party protocol in the correlated randomness model (e.g., GMW [GMW87] or SPDZ [DPSZ12]).
In this section, we construct PK-PCFs for all correlations computable by RMS programs over a finite ring. As another application of our construction, in Section 6.3, we show a protocol for generating *multi-party* correlations with quadratic improvement in communication relative to the prior constructions of PCFs.

## 6.1 Background: Public-key pseudorandom correlation functions

In this section, we provide some background and a formal definition of PK-PCFs, following the formalization of Bui et al. [BCM$^{+24}$].

The standard PCF (and PK-PCF) definition requires the correlation to be “reverse sampleable” which, roughly speaking, means that given any (possibly adversarially generated) share of the target correlation, the other (honest) share can be efficiently sampled. We note that all additive correlations, which will be the target of our constructions, are reverse sampleable.

**Remark 5 (Notation).** In this section, we will identify the two parties using indices 0 and 1, instead of letters A and B as we did in previous sections. This simplifies notation when we define *multi-party* PCFs in Section 6.3.

**Definition 12 (Reverse-Sampleable Correlation).** Let $\lambda$ be a security parameter and $n = n(\lambda) \in \text{poly}(\lambda)$ be an output length. Define two efficient algorithms $\mathcal{Y}$ and $\text{RSample}$ with the following syntax:

- $\mathcal{Y}(1^{\lambda}) \to (y^0, y^1)$. The randomized correlation sampling algorithm takes as input the security parameter and outputs a pair $(y^0, y^1) \in \{0, 1\}^n \times \{0, 1\}^n$ defining a correlation.

- $\text{RSample}(1^{\lambda}, \sigma, y^{\sigma}) \to y^{1-\sigma}$. The deterministic reverse-sampling algorithm takes as input the security parameter, an index $\sigma \in \{0, 1\}$, and a string $y^{\sigma} \in \{0, 1\}^n$. It outputs a string $y^{1-\sigma} \in \{0, 1\}^n$.

We say that $\mathcal{Y}$ defines a reverse-sampleable correlation if for all $\sigma \in \{0, 1\}$, it holds that:

$$ \left\{ (y^0, y^1) \mid (y^0, y^1) \leftarrow \mathcal{Y}(1^{\lambda}) \right\} \approx_s \left\{ \begin{array}{l} (y^0, y^1) \mid \begin{array}{l} (\hat{y}^0, \hat{y}^1) \leftarrow \mathcal{Y}(1^{\lambda}) \\ y^{\sigma} := \hat{y}^{\sigma} \end{array} \\ y^{1-\sigma} \leftarrow \text{RSample}(1^{\lambda}, \sigma, y^{\sigma}) \end{array} \right\}. $$

Exp$_{\mathcal{A},N,0}(\lambda)$:
crs $\leftarrow$ pkPCFSetup(1$^{\lambda}$)
(pk$_{\sigma}$, sk$_{\sigma}$) $\leftarrow$ pkPCF.KeyGen(crs, $\sigma$), $\forall \sigma \in \{0, 1\}$
foreach $i \in [N]$:
$x_i \leftarrow \$ \{0, 1\}^n$
(y$_i^0$, y$_i^1$) $\leftarrow$ $\mathcal{Y}(1^\lambda)$
b $\leftarrow$ $\mathcal{A}$(pk$_0$, pk$_1$, (x$_i$, y$_i^0$, y$_i^1$)$_{i \in [N]}$)
return b

Exp$_{\mathcal{A},N,1}(\lambda)$:
crs $\leftarrow$ pkPCFSetup(1$^{\lambda}$)
(pk$_{\sigma}$, sk$_{\sigma}$) $\leftarrow$ pkPCF.KeyGen(crs, $\sigma$), $\forall \sigma \in \{0, 1\}$
k$_{\sigma}$ $:= \text{pkPCF.KeyDer}(\text{crs}, \sigma, \text{pk}_{1-\sigma}, \text{sk}_{\sigma})$, $\forall \sigma \in \{0, 1\}$
foreach $i \in [N]$:
x$_i \leftarrow \$ \{0, 1\}^n$
y$_i^{\sigma}$ $:= \text{pkPCF.Eval}(\text{crs}, \sigma, k_{\sigma}, x_i)$, $\forall i \in \{0, 1\}$
b $\leftarrow$ $\mathcal{A}$(pk$_0$, pk$_1$, (x$_i$, y$_i^0$, y$_i^1$)$_{\sigma \in [N]}$)
return b

<caption>**Fig. 12:** Pseudorandom $\mathcal{Y}$-correlated outputs for a weak PK-PCF.</caption>

**Definition 13 (Public-Key Pseudorandom Correlation Function [BCM$^{+24}$]).** Let $\lambda$ be a security parameter, $\mathcal{Y}$ be a reverse-sampleable correlation with output length $n = n(\lambda) \in \text{poly}(\lambda)$, and $\lambda \le m = m(\lambda) \in \text{poly}(\lambda)$ be an input length. A Public-Key Pseudorandom Correlation Function (PK-PCF) for $\mathcal{Y}$ is defined by a tuple of algorithms pkPCF = (Setup, Gen, KeyDer, Eval) with the following functionality:

- pkPCFSetup(1$^{\lambda}$) $\to$ crs. The randomized setup algorithm takes as input the security parameter $\lambda$ and outputs a common reference string (CRS) crs.

- pkPCF.KeyGen(crs, $\sigma$) $\to$ (pk$_{\sigma}$, sk$_{\sigma}$). The randomized key generation algorithm takes as input the CRS crs and a party identifier $\sigma \in \{0, 1\}$. It outputs a public and secret key pair (pk$_{\sigma}$, sk$_{\sigma}$) for the party.
Exp<sup>sec</sup><sub>A,N,σ,0</sub>(λ):
crs ← pkPCF.setup(1<sup>λ</sup>)
(pk<sub>σ̂</sub>, sk<sub>σ̂</sub>) ← pkPCF.KeyGen(crs, σ̂), ∀σ̂ ∈ {0, 1}
k<sub>1-σ</sub> := pkPCF.KeyDer(crs, σ, pk<sub>σ̂</sub>, sk<sub>1-σ</sub>)

foreach i ∈ [N]:

x<sub>i</sub> ← $\{0, 1\}^n$

y<sup>1-σ</sup><sub>i</sub> := pkPCF.Eval(crs, 1 - σ, k<sub>1-σ</sub>, x<sub>i</sub>)

b ← A(pk<sub>0</sub>, pk<sub>1</sub>, σ, sk<sub>σ</sub>, (x<sub>i</sub>, y<sup>1-σ</sup><sub>i</sub>)<sub>i∈[N]</sub>)

return b

Exp<sup>sec</sup><sub>A,N,σ,1</sub>(λ):
crs ← pkPCF.setup(1<sup>λ</sup>)
(pk<sub>σ̂</sub>, sk<sub>σ̂</sub>) ← pkPCF.KeyGen(crs, σ̂), ∀σ̂ ∈ {0, 1}
k<sub>σ</sub> := pkPCF.KeyDer(crs, σ, pk<sub>σ</sub>, sk<sub>1-σ</sub>)

foreach i ∈ [N]:

x<sub>i</sub> ← $\{0, 1\}^n$

y<sup>σ</sup><sub>i</sub> := pkPCF.Eval(crs, σ, k<sub>σ</sub>, x<sub>i</sub>)

y<sup>1-σ</sup><sub>i</sub> ← RSample(1<sup>λ</sup>, σ, y<sup>σ</sup><sub>i</sub>)

b ← A(pk<sub>0</sub>, pk<sub>1</sub>, σ, sk<sub>σ</sub>, (x<sub>i</sub>, y<sup>1-σ</sup><sub>i</sub>)<sub>i∈[N]</sub>)

return b

<caption>Fig. 13: Security of game for a weak PK-PCF. Here, RSample is as defined in Definition 12.</caption>

- pkPCF.KeyDer(crs, σ, pk<sub>1-σ</sub>, sk<sub>σ</sub>) → k<sub>σ</sub>. The deterministic key derivation algorithm takes as input the CRS crs, a party identifier σ ∈ {0, 1}, the public key pk<sub>1-σ</sub> of another party, and the secret key sk<sub>σ</sub> of this party. It outputs an evaluation key k<sub>σ</sub> for this party.

- pkPCF.Eval(crs, σ, k<sup>σ</sup>, x) → y<sup>σ</sup>. The deterministic evaluation algorithm takes as input the CRS, the party identifier σ ∈ {0, 1}, an evaluation key k<sup>σ</sup>, and an input x ∈ {0, 1}<sup>m</sup>. It outputs a string y<sup>σ</sup> ∈ {0, 1}<sup>n</sup>.

We say that pkPCF = (KeyGen, Eval) is a PK-PCF for the reverse-sampleable correlation $\mathcal{Y}$, if the following two properties hold:

Correctness / Pseudorandom $\mathcal{Y}$-correlated outputs. For every $\sigma \in \{0, 1\}$, all efficient adversaries $\mathcal{A}$, and all $N = N(\lambda) \in \text{poly}(\lambda)$, there exists a negligible function $\text{negl}(\cdot)$ such that:

$$ \text{Adv}_{\mathcal{A},N}^{\text{pr}}(\lambda) := \left| \Pr[\text{Exp}_{\mathcal{A},N,0}^{\text{pr}}(\lambda) = 1] - \Pr[\text{Exp}_{\mathcal{A},N,1}^{\text{pr}}(\lambda) = 1] \right| \le \text{negl}(\lambda), $$

where $\text{Exp}_{\mathcal{A},N,b}^{\text{pr}}(\lambda)$, for $b \in \{0, 1\}$, is as defined in Figure 12. In particular, the adversary is given access to $N$ samples.

Security. For all $\sigma \in \{0, 1\}$, and all efficient adversaries $\mathcal{A}$, there exists a negligible function $\text{negl}(\cdot)$ such that:

$$ \text{Adv}_{\mathcal{A},N,\sigma}^{\text{sec}}(\lambda) := \left| \Pr[\text{Exp}_{\mathcal{A},N,\sigma,0}^{\text{sec}}(\lambda) = 1] - \Pr[\text{Exp}_{\mathcal{A},N,\sigma,1}^{\text{sec}}(\lambda) = 1] \right| \le \text{negl}(\lambda), $$

where $\text{Exp}_{\mathcal{A},N,\sigma,b}^{\text{sec}}(\lambda)$, for $b \in \{0, 1\}$, is as defined in Figure 13 (again, with the adversary given $N$ samples).

Remark 6 (Weak vs. Strong PCFs). We remark that, contrary to pseudorandom functions, the default notion of a PCF is a weak PCF, where the inputs are chosen uniformly at random. A PCF (as defined in Definition 13) can be generically converted to a strong PCF using a random oracle.

## 6.2 Public-key PCFs from MKHSS

In this section, we provide a construction of a PK-PCF for any additive correlations computable by RMS programs (which includes the class $\mathbb{NC}^1$). We start by defining additive correlations:

**Definition 14 (Additive Correlation).** Let $\lambda$ be a security parameter, and let $n_y = n_y(\lambda) \in \text{poly}(\lambda)$ be an input length and $n_z = n_z(\lambda) \in \text{poly}(\lambda)$ be an output length. We say that $\mathcal{Y}$ (as defined in Definition 12) is an additive correlation over a ring $\mathcal{R}$ defined by a function family $\{C_\lambda: \mathcal{R}^{n_y} \times \mathcal{R}^{n_z} \to \mathcal{R}^{n_z}\}_{\lambda \in \mathbb{N}}$ if $\mathcal{Y}(1^\lambda)$ outputs pairs of samples $((y_0, z_0), (y_1, z_1))$, where $(y_\sigma, z_\sigma) \in \mathcal{R}^{n_y} \times \mathcal{R}^{n_z}$ are uniformly random conditioned on $z_0 + z_1 = C_\lambda(y_0, y_1)$. We will drop the subscript $\lambda$ when clear from context.

**Remark 7.** Additive correlations are naturally reverse-samplable. To see this, observe that given $(y_\sigma, z_\sigma)$, it is possible to efficiently sample $y_{1-\sigma} \leftarrow \mathcal{R}^{n_y}$, and set $z_{1-\sigma} := C(y_0, y_1) - z_\sigma$.

We present our PK-PCF construction for correlations computable by RMS programs in Figure 14.
Public-Key PCF from MKHSS

**Public Parameters.** Let MKHSS = (Setup, KeyGen, Share, Eval) be an externally secure MKHSS scheme for polynomial-size RMS programs defined over a ring $\mathcal{R}$. Let $n_k = n_k(\lambda)$ and $n_x = n_x(\lambda)$ be polynomials denoting the PRF key length and output length, respectively. Let $F_k: \mathcal{R}^m \to \mathcal{R}^{n_x}$ be a PRF with keys sampled from $\mathcal{R}^{n_k}$, such that $F_k(\mathbf{x})$ is computable by a polynomial-size RMS program over $\mathcal{R}$. Let $\mathcal{Y}$ be an additive correlation over a ring $\mathcal{R}$ defined by a correlation circuit $C$ computable by polynomial-size RMS programs.

**The evaluated program.** For all vectors $\mathbf{x} \in \mathcal{R}^m$, define the program $P_{\mathbf{x}}: \mathcal{R}^{n_k} \times \mathcal{R}^{n_k} \to \mathcal{R}$ to be the polynomial-size RMS program that, on input $k_0, k_1 \in \mathcal{R}^{n_k}$, computes $\mathbf{y}_{\sigma} := F_{k_{\sigma}}(\mathbf{x}) \in \mathcal{R}^{n_x}$, for all $\sigma \in \{0, 1\}$, and outputs $C(\mathbf{y}_0, \mathbf{y}_1)$.

pkPCF.setup(1^λ):

1: crs ← MKHSS.setup(λ)

2: return crs

pkPCF.KeyGen(crs, σ):

1: k ← R$^{n_k}$

2: (pk, sk) ← MKHSS.KeyGen(crs)

3: ([[k]]$^{\sigma}_0, [[k]]^{\sigma}_1) \leftarrow$ MKHSS.Share(crs, σ, pk, k)

pkPCF.KeyDer(crs, σ, sk$^{\text{pcf}}_{\sigma}$, pk$^{\text{pcf}}_{1-\sigma}$):

4: pk$^{\text{pcf}}_{\sigma} := (pk, [[k]]^{\sigma}_{1-\sigma})

1: return k$_{\sigma}$ := (sk$^{\text{pcf}}_{\sigma}$, pk$^{\text{pcf}}_{1-\sigma}$)

5: sk$^{\text{pcf}}_{\sigma} := (sk, [[k]]^{\sigma}_{\sigma}, k)

6: return (pk$^{\text{pcf}}_{\sigma}$, sk$^{\text{pcf}}_{\sigma}$)

pkPCF.Eval(crs, σ, k$_{σ}$, x):

1: parse k$_{σ}$ := ((sk$_{σ}$, [[k$_{σ}$]]$^{\sigma}_{σ}$, k$_{σ}$), (pk$_{1-σ}$, [[k$_{1-σ}$]]$^{1-σ}_{σ}$))

2: y$_{σ}$ := F$_{k_{σ}}$(x)

3: z$_{σ}$ := MKHSS.Eval(crs, σ, sk$_{σ}$, pk$_{1-σ}$, [[k$_{σ}$]]$^{\sigma}_{\sigma}$, [[k$_{1-σ}$]]$^{1-\sigma}_{\sigma}$, P$_{x}$)

4: return (y$_{σ}$, z$_{σ}$)

<caption>Fig. 14: Public-key PCF from MKHSS.</caption>

**6.2.1 Security analysis** We now turn to the security analysis of the PK-PCF from Figure 14.

**Theorem 4 (Security of PK-PCF).** *Assuming the existence of an externally-secure MKHSS scheme MKHSS for polynomial-size RMS programs over a finite ring $\mathcal{R}$ and the existence of PRFs in $\text{NC}^1$, the construction described in Figure 14 is a PK-PCF for arbitrary additive correlations described by polynomial-size RMS programs over $\mathcal{R}$.*

**Pseudorandomness.** Consider the following sequence of hybrid games.

- *Hybrid* $\mathcal{H}_0$. This hybrid game consists of the pseudorandomness experiment $E_{\mathcal{A},N,0}^{\text{pkpr}}$.

- *Hybrid* $\mathcal{H}_1$. In this hybrid game, the outputs $(z_0, z_1)$ are computed by first sampling $z_1 \leftarrow \mathcal{R}$, and then setting $z_0 := z_1 + P_{\mathbf{x}}(k_0, k_1)$.

*Claim.* $\mathcal{H}_1 \approx_c \mathcal{H}_0$ assuming the external security of MKHSS.

*Proof.* An efficient distinguisher immediately contradicts the external security of MKHSS. $\square$

<figure><img src="image_6.png" /></figure>

- *Hybrid* $\mathcal{H}_2$. In this hybrid game, the challenger is given oracle access to $F_{k_{\sigma}}(\cdot)$, for all $\sigma \in \{0, 1\}$. Instead of computing $F_{k_{\sigma}}$ using $k_{\sigma}$, the challenger obtains the PRF evaluation by querying the respective oracles. Then, the challenger samples $z_1 \leftarrow \mathcal{R}$, and set $z_0 := z_1 + C(\mathbf{y}_0, \mathbf{y}_1)$.

*Claim.* $\mathcal{H}_2 \approx_s \mathcal{H}_1$.
Proof. By definition of $P_x$ in Figure 14, the output distribution is identical to that of $H_1$. ☐

- *Hybrid* $H_3$. This hybrid game proceeds as $H_2$, except that the key $k$ in pkPCF.KeyGen is replaced by 0. That is, pkPCF.KeyGen computes ($\llbracket k \rrbracket_0^\sigma, \llbracket k \rrbracket_1^\sigma$) $\leftarrow$ MKHSS.Share(crs, $\sigma$, pk, 0).

*Claim.* $H_3 \approx_c H_2$ assuming the security of MKHSS.

*Proof.* The claim follows immediately by the security of MKHSS. ☐

- *Hybrid* $H_4$. This hybrid game proceeds as $H_3$, except that the PRF oracles $F_{k_\sigma}$, for $\sigma \in \{0, 1\}$, are replaced with random oracles $H_\sigma$. Hence, $y_\sigma$ is computed as $y_\sigma := H_\sigma(\mathbf{x})$, for all $\sigma \in \{0, 1\}$.

*Claim.* $H_4 \approx_c H_3$ assuming the security of the PRF.

*Proof.* The claim follows from the standard PRF security property (note that we can apply the PRF security since the shares ($\llbracket k_\sigma \rrbracket_0^\sigma, \llbracket k_\sigma \rrbracket_1^\sigma$) do not depend on the PRF key $k_\sigma$ anymore). ☐

- *Hybrid* $H_5$. In this hybrid game, the challenger samples $y_\sigma \leftarrow_S \mathbb{R}^{n_y}$, for all $\sigma \in \{0, 1\}$.

*Claim.* $H_5 \approx_s H_3$.

*Proof.* Observe that the probability of any two inputs $\mathbf{x}$ to the random oracle $H_\sigma$ colliding is negligible, hence $H_5$ is statistically indistinguishable from $H_4$. ☐

At this point, it suffices to note that $H_5$ is equivalent to the experiment $E_{A,N,1}^{pkpr}$, concluding the proof.

**Security.** We now turn to proving the security of our PK-PCF. We proceed as above via a sequence of hybrid games.

- *Hybrid* $H_0$. This hybrid game consists of the security experiment $E_{A,N,0}^{pksec}$.

- *Hybrid* $H_1$. In this hybrid game, the challenger computes $z_{1-\sigma}$ by first computing

$$z_{\sigma} \leftarrow \text{MKHSS.Eval}(\text{crs}, \sigma, \text{sk}_{\sigma}, \text{pk}_{1-\sigma}, \llbracket k_{\sigma} \rrbracket_{\sigma}^{\sigma}, \llbracket k_{1-\sigma} \rrbracket_{\sigma}^{1-\sigma}, C_{\mathbf{x}})$$

and then setting $z_{1-\sigma} := z_{\sigma} + (-1)^{1-\sigma} C_{\mathbf{x}}(y_0, y_1)$.

*Claim.* $H_1 \approx_c H_0$ assuming the correctness of MKHSS.

*Proof.* The claim follows directly from the correctness property of MKHSS. ☐

*Hybrid* $H_2$. This hybrid game is identical to $H_1$ except that pkPCF.KeyGen outputs:

$$\left(\llbracket k_{1-\sigma} \rrbracket_0^{1-\sigma}, \llbracket k_{1-\sigma} \rrbracket_1^{1-\sigma}\right) \leftarrow \text{MKHSS.Share}(\text{crs}, 1 - \sigma, \text{pk}, 0).$$

*Claim.* $H_2 \approx_c H_1$ assuming the security of MKHSS.

*Proof.* The claim follows directly from the security property of MKHSS. ☐

- *Hybrid* $H_3$. In this hybrid game, the challenges is given oracle access to $F_{k_{1-\sigma}}$. The challenger uses this oracle access to compute $y_{1-\sigma} := F_{k_{1-\sigma}}(\mathbf{x}) \in \mathbb{R}^{n_x}$.

*Claim.* $H_3 \approx_s H_2$.

*Proof.* By definition of $P_x$, the output distribution is identical to that of $H_2$. ☐
- *Hybrid* $\mathcal{H}_4$. This hybrid game is identical to $\mathcal{H}_3$ except that the oracle for $F_{k_{1-\sigma}}$ is now replaced with a random oracle $H$. Hence, $\mathbf{y}_{1-\sigma}$ is computed as $\mathbf{y}_{1-\sigma} := H(\mathbf{x})$.

*Claim.* $\mathcal{H}_4 \approx_c \mathcal{H}_3$ assuming the security of the PRF.

*Proof.* The claim follows from the security of the PRF. In particular, note that we can apply the PRF security since the shares $(\llbracket k_{1-\sigma} \rrbracket_0^{1-\sigma}, \llbracket k_{1-\sigma} \rrbracket_1^{1-\sigma})$ do not depend on $k_{1-\sigma}$ anymore. $\square$

- *Hybrid* $\mathcal{H}_5$. In this hybrid game, the challenger samples $\mathbf{y}_{1-\sigma} \leftarrow \mathcal{R}^{n_y}$.

*Claim.* $\mathcal{H}_5 \approx_s \mathcal{H}_4$.

*Proof.* Observe that the probability of any two inputs $\mathbf{x}$ to $H$ colliding is negligible, hence this hybrid is statistically indistinguishable from $\mathcal{H}_4$. $\square$

At this point, it suffices to note that $E_{\mathcal{A},N,1}^{\text{pksec}}$ uses the natural reverse-sampling algorithm for additive correlations. This concludes the proof.

*Remark 8 (On strong PK-PCFs).* We note that because we use a standard PRF in our construction, our PK-PCF can be shown to be a *strong* PCF. Alternatively, we can substitute the PRF for a *weak* PRF and follow the same proof.

## 6.3 Multi-party computation with silent preprocessing

Building upon the PK-PCF introduced in Section 6.2, we introduce a *multi-party* PK-PCF for generating Beaver triple correlations, and discuss the direct implications to secure computation. We note that we can only support degree-2 correlations (e.g., Beaver triples) in the multi-party setting when using two-party PCFs as a building block. The same limitation applies to prior constructions of multi-party correlation generators from two-party building blocks [BCG+19b].

**Defining multi-party PK-PCFs.** We start by introducing the notion of multi-party PK-PCF (Definition 15). Our definition generalizes the notion of PK-PCF to more than two parties in a natural way. Note that for simplicity, we “absorb” the key derivation procedure into MKHSS.Eval. That is, in our formal definition, MKHSS.Eval directly takes as input the secret key $\mathbf{s}_k$ of a party and the public keys $(\mathbf{pk}_j)_{j \neq i}$ of the other parties. This is without loss of generality, as we can always define KeyDer to output $\mathbf{s}_k := (\mathbf{s}_k, (\mathbf{pk}_j)_{j \neq i})$. Indeed, we note that this is exactly what our MKHSS-based PK-PCF construction in Figure 14 does.

**Definition 15 (Multi-Party Public-Key Pseudorandom Correlation Function).** A *multi-party* PK-PCF for a *p-party* correlation $\mathcal{Y}$ is defined by a tuple of algorithms mpkPCF = (Setup, KeyGen, Eval), with the following template:

- mpkPCF Gibbings $\lambda \to \text{crs}$. The randomized setup algorithm takes as input the security parameter and outputs a common reference string (CRS) $\text{crs}$.

- mpkPCF. KeyGen($\text{crs}, i$) $\to (\mathbf{pk}_i, \mathbf{s}_k)$. The randomized key generation algorithm takes as input the CRS and an index $i \in [p]$, outputs a pair $(\mathbf{pk}_i, \mathbf{s}_k)$ of public and private mpkPCF keys.

- mpkPCF. Eval($\text{crs}, i, \mathbf{s}_k, (\mathbf{pk}_j)_{j \neq i}, x$) $\to y_i$. The deterministic evaluation algorithm takes as input an index $i$, the secret key $\mathbf{s}_k$, the public keys $(\mathbf{pk}_j)_{j \neq i}$, and an input $x \in \{0, 1\}^n$. It outputs a string $y_i$.

A *multi-party* PK-PCF must satisfy the following *pseudorandomness and security properties*:

*Correctness / Pseudorandom Y-correlated Outputs.* For all efficient adversaries $\mathcal{A}$, and all $N = N(\lambda) \in \text{poly}(\lambda)$, there exists a negligible function $\text{negl}$ such that for all sufficiently large $\lambda$,

$$ \text{Adv}_{\mathcal{A},N}^{\text{mpkpr}}(\lambda) := \left| \text{Pr}[\text{E}_{\mathcal{A},N,0}^{\text{mpkpr}}(\lambda) = 1] - \text{Pr}[\text{E}_{\mathcal{A},N,1}^{\text{mpkpr}}(\lambda) = 1] \right| \le \text{negl}(\lambda), $$

where $E_{\mathcal{A},N,b}^{\text{mpkpr}}(\lambda)$, for $b \in \{0, 1\}$, is as defined in Figure 15.
<figure><img src="image_7.png" /><figcaption>Fig. 15: Pseudorandomness of a multi-party public-key PCF for a p-party correlation $\mathcal{Y}$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 16: Security of a multi-party public-key PCF for a p-party correlation $\mathcal{Y}$.</figcaption></figure>

Security. There exists an efficient algorithm $\text{RSample}$: $(1^{\lambda}, i^*), (y_i)_{i \neq i^*} \mapsto y_{i^*}$ such that for every efficient adversary $\mathcal{A}, N = N(\lambda) \in \text{poly}(\lambda)$, and every $i^* \in [p]$, there exists a negligible function negligible such that for all sufficiently large $\lambda$,

$$ \text{Adv}_{\mathcal{A},N}^{\text{mpkpr}}(\lambda, i^*) := \left| \Pr[\text{E}_{\mathcal{A},N,0}^{\text{mpkpr}}(\lambda, i^*) = 1] - \Pr[\text{E}_{\mathcal{A},N,1}^{\text{mpksec}}(\lambda, i^*) = 1] \right| \le \text{negl}(\lambda), $$

where $\text{E}_{\mathcal{A},N,b}^{\text{mpksec}}(\lambda, i^*)$, for $b \in \{0,1\}$, is as defined in Figure 16.

**Construction.** We construct a multi-party PK-PCF for the p-party Beaver triple correlation over a ring $\mathcal{R}$. Let $\mathcal{B}$ denote the p-party correlation that, on input $\lambda$, samples $p$ uniformly random triples $(a_i, b_i, c_i) \leftarrow \mathcal{R}^3$ conditioned on $(\sum_i a_i) \cdot (\sum_i b_i) = \sum_i c_i$. We represent our construction on Figure 17.

At a high level, the construction of Figure 17 is a direct extension of the PK-PCF construction from Figure 14. In particular, the generalization from two parties to p parties is fairly straightforward. In a little more detail, our multi-party PK-PCF is realized as follows:

- Each party $P_i$ generates an MKHSS keys pair $(\text{pk}_i^{\text{mkhss}}, \text{sk}_i^{\text{mkhss}})$, samples a PRF key $k_i$, and shares $k_i$ into $(\llbracket k \rrbracket_0^\sigma, \llbracket k \rrbracket_1^\sigma)$ using MKHSS.Share, for each $\sigma \in \{0,1\}$. Then, $P_i$ sets: $\text{sk}_i := (\text{sk}, \llbracket k \rrbracket_1^0, \llbracket k \rrbracket_1^1, k)$ and $\text{pk}_i := (\text{pk}, \llbracket k \rrbracket_0^0, \llbracket k \rrbracket_0^1)$.

- On input $\mathbf{x}$, each party $P_i$ defines $(a_i, b_i) := F_{k_i}(\mathbf{x})$.

- Finally, each pair of parties $P_i, P_j$, using their MKHSS shares of $k_i$ and $k_j$, computes additive shares of $F_{k_i}(\mathbf{x}) \cdot F_{k_j}(\mathbf{x})$. Each party $P_i$ aggregates all the shares computed in this way into $c_i$. By correctness of the MKHSS scheme, it holds that:

$$ \sum_i c_i = \sum_{i,j} F_{k_i}(\mathbf{x}) \cdot F_{k_j}(\mathbf{x}) = \left( \sum_i a_i \right) \cdot \left( \sum_i b_i \right). $$

**Theorem 5 (Security of multi-party PK-PCF).** Assuming the existence of an externally-secure MKHSS scheme MKHSS for polynomial-size RMS programs and a PRF in $\text{NC}^1$, the construction described in Figure 17 is a multi-party PK-PCF for Beaver triple correlations.
Proof (sketch). The proof is essentially identical to the proof of Theorem 4.

<figure><img src="image_9.png" /></figure>

**Application to secure computation.** A multi-party PK-PCF for the *p*-party Beaver triple correlation immediately implies a *p*-party semi-honest secure computation protocol for a general arithmetic circuit *C* over *R* in the *silent preprocessing model* (see Boyle et al. [BCGI18, BCG<sup>+</sup>19a, BCG<sup>+</sup>19b, BCG<sup>+</sup>20a] for discussions on this model):

**Preprocessing phase.** Each party $P_i$ runs $(pk_i, sk_i) \leftarrow mpkPCF.KeyGen(i)$ and broadcasts $pk_i$.

**Silent expansion.** For each multiplication gate in *C*, each party $P_i$ computes $(a_i, b_i, c_i) := pkPCF.Eval(crs, i, sk_i, (pk_j)_{j \neq i}, \mathbf{x})$, where $\mathbf{x}$ is a fresh common randomness.

**Online phase.** The parties run the information-theoretic GMW protocol, consuming one Beaver triple for each multiplication gate computed in the preprocessing phase.

The fact that GMW can be securely instantiated using the correlated pseudorandomness generated by a (multi-party, public key) PCF follows from the fact that the latter suffices to instantiate a *corruptible* functionality for generating correlated randomness, and GMW is provably secure given ideal access to a corruptible correlated randomness functionality. We refer the reader to Boyle et al. [BCG<sup>+</sup>19b] for more detailed discussion about this approach. Then, plugging in our construction of (statistically correct) MKHSS from DCR or class group assumptions, we get the following corollary:

**Corollary 4.** Assume either the DCR assumption or the DDH assumption over class groups. For any polynomial number of parties $p$, for any polynomial-size arithmetic circuit $C$ with $n$ inputs, $s$ multiplication gates, and $m$ outputs over a ring $\mathcal{R}$, there exists a $p$-party protocol securely computing $C$ in the preprocessing model against an adversary passively corrupting up to $p-1$ parties with the following communication:

- In the preprocessing phase, the parties communicate $p \cdot \text{poly}(\lambda)$ bits in a single round of broadcast.

- In the online phase, the parties communicate $p \cdot (2s + m)$ elements of $\mathcal{R}$.

Previously, the best-known multi-party protocols with silent preprocessing (under assumptions not known to imply spooky encryption) were constructed using either HSS (from DCR or DDH over class groups [OSY21, RS21, ADOS22]), programmable 2-party PCGs (from ring-LPN [BCG<sup>+</sup>20b], or quasi-abelian syndrome decoding [BCCD23]). All these approaches incurred a *quadratic* communication overhead $\tilde{\Omega}(p^2) \cdot \text{poly}(\lambda)$ in the number of parties $p$, in the preprocessing phase. Our construction is the first to achieve $p \cdot \text{poly}(\lambda)$ communication overhead in the preprocessing phase, which is quasi-optimal.

## Acknowledgments

We thank Srini Devadas for helpful comments on the introduction. We thank Kevin He for spotting typos and inconsistencies. We thank the anonymous reviewers for helpful comments and suggestions that improved the presentation and results in the paper. Geoffroy Couteau and Aditya Hegde acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grant ANR-20-CE39-0001 (project SCENE) and under the France 2030 ANR Project ANR-22-PECY-003 SecureCompute. This work is supported by ERC grant OBELiSC (101115790). Aditya Hegde and Abhishek Jain were supported by NSF CNS-1814919, NSF CAREER 1942789 and Johns Hopkins University Catalyst award. Abhishek Jain was additionally supported by JP Morgan Faculty Award, and research gifts from Ethereum, Stellar, and Cisco.
Bibliography

[ADOS22] D. Abram, I. Damgård, C. Orlandi, and P. Scholl. An algebraic framework for silent preprocessing with trustless setup and active security. In *CRYPTO 2022, Part IV*, LNCS 13510, pages 421–452. Springer, Cham, August 2022.

[AJJM20] P. Ananth, A. Jain, Z. Jin, and G. Malavolta. Multi-key fully-homomorphic encryption in the plain model. In *TCC 2020, Part I*, LNCS 12550, pages 28–57. Springer, Cham, November 2020.

[AJJM21] P. Ananth, A. Jain, Z. Jin, and G. Malavolta. Unbounded multi-party computation from learning with errors. In *EUROCRYPT 2021, Part II*, LNCS 12697, pages 754–781. Springer, Cham, October 2021.

[AJL$^{+12}$] G. Asharov, A. Jain, A. López-Alt, E. Tromer, V. Vaikuntanathan, and D. Wichs. Multi-party computation with low communication, computation and interaction via threshold FHE. In *EUROCRYPT 2012*, LNCS 7237, pages 483–501. Springer, Berlin, Heidelberg, April 2012.

[ARS24] D. Abram, L. Roy, and P. Scholl. Succinct homomorphic secret sharing. In *EUROCRYPT 2024, Part VI*, LNCS 14656, pages 301–330. Springer, Cham, May 2024.

[BBC$^{+24}$] M. Bombar, D. Bui, G. Couteau, A. Couvreur, C. Ducros, and S. Servan-Schreiber. FOLEAGE: $F_4$OLE-based multi-party computation for boolean circuits. In *ASIACRYPT 2024, Part VI*, LNCS 15489, pages 69–101. Springer, Singapore, 2024.

[BCCD23] M. Bombar, G. Couteau, A. Couvreur, and C. Ducros. Correlated pseudorandomness from the hardness of quasi-abelian decoding. In *CRYPTO 2023, Part IV*, LNCS 14084, pages 567–601. Springer, Cham, August 2023.

[BCCS24] A. Bondarchuk, O. Chakraborty, G. Couteau, and R. Sirdey. Downlink (t)FHE ciphers texts compression. Cryptology ePrint Archive, Paper 2024/1921, 2024.

[BCG$^{+17}$] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, and M. Orrù. Homomorphic secret sharing: Optimizations and applications. In *ACM CCS 2017*, pages 2105–2122. ACM Press, October / November 2017.

[BCG$^{+19a}$] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, P. Rindal, and P. Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In *ACM CCS 2019*, pages 291–308. ACM Press, November 2019.

[BCG$^{+19b}$] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In *CRYPTO 2019, Part III*, LNCS 11694, pages 489–518. Springer, Cham, August 2019.

[BCG$^{+20a}$] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Correlated pseudo-random functions from variable-density LPN. In *61st FOCS*, pages 1069–1080. IEEE Computer Society Press, November 2020.

[BCG$^{+20b}$] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Efficient pseudorandom correlation generators from ring-LPN. In *CRYPTO 2020, Part II*, LNCS 12171, pages 387–416. Springer, Cham, August 2020.

[BCGI18] E. Boyle, G. Couteau, N. Gilboa, and Y. Ishai. Compressing vector OLE. In *ACM CCS 2018*, pages 896–912. ACM Press, October 2018.

[BCM23] E. Boyle, G. Couteau, and P. Meyer. Sublinear-communication secure multiparty computation does not require FHE. In *EUROCRYPT 2023, Part II*, LNCS 14005, pages 159–189. Springer, Cham, April 2023.

[BCM$^{+24}$] D. Bui, G. Couteau, P. Meyer, A. Passelègue, and M. Riahinia. Fast public-key silent OT and more from constrained Naor-Reingold. In *EUROCRYPT 2024, Part VI*, LNCS 14656, pages 88–118. Springer, Cham, May 2024.

[BCP03] E. Bresson, D. Catalano, and D. Pointcheval. A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications. In *ASIACRYPT 2003*, LNCS 2894, pages 37–54. Springer, Berlin, Heidelberg, November / December 2003.

[BDSS25] E. Boyle, L. Devadas, and S. Servan-Schreiber. Non-interactive distributed point functions. Cryptology ePrint Archive, Paper 2025/095, 2025.

[Bea92] D. Beaver. Efficient multiparty protocols using circuit randomization. In *CRYPTO'91*, LNCS 576, pages 420–432. Springer, Berlin, Heidelberg, August 1992.
[Bea95] D. Beaver. Precomputing oblivious transfer. In *CRYPTO'95, LNCS* 963, pages 97–109. Springer, Berlin, Heidelberg, August 1995.

[BGI16] E. Boyle, N. Gilboa, and Y. Ishai. Breaking the circuit size barrier for secure computation under DDH. In *CRYPTO 2016, Part I, LNCS* 9814, pages 509–539. Springer, Berlin, Heidelberg, August 2016.

[BGI17] E. Boyle, N. Gilboa, and Y. Ishai. Group-based secure computation: Optimizing rounds, communication, and computation. In *EUROCRYPT 2017, Part II, LNCS* 10211, pages 163–193. Springer, Cham, April / May 2017.

[BGI+18] E. Boyle, N. Gilboa, Y. Ishai, H. Lin, and S. Tessaro. Foundations of homomorphic secret sharing. In *ITCS 2018*, pages 21:1–21:21. LIPIcs, January 2018.

[BGMM20] J. Bartusek, S. Garg, D. Masny, and P. Mukherjee. Reusable two-round MPC from DDH. In *TCC 2020, Part II, LNCS* 12551, pages 320–348. Springer, Cham, November 2020.

[BHHO08] D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky. Circular-secure encryption from decision Diffie-Hellman. In *CRYPTO 2008, LNCS* 5157, pages 108–125. Springer, Berlin, Heidelberg, August 2008.

[BJKL21] F. Benhamouda, A. Jain, I. Komargodski, and H. Lin. Multiparty reusable non-interactive secure computation from LWE. In *EUROCRYPT 2021, Part II, LNCS* 12697, pages 724–753. Springer, Cham, October 2021.

[BKS19] E. Boyle, L. Kohl, and P. Scholl. Homomorphic secret sharing from lattices without FHE. In *EUROCRYPT 2019, Part II, LNCS* 11477, pages 3–33. Springer, Cham, May 2019.

[BL20] F. Benhamouda and H. Lin. Mr NISC: Multiparty reusable non-interactive secure computation. In *TCC 2020, Part II, LNCS* 12551, pages 349–378. Springer, Cham, November 2020.

[BM90] M. Bellare and S. Micali. Non-interactive oblivious transfer and applications. In *CRYPTO'89, LNCS* 435, pages 547–557. Springer, New York, August 1990.

[CDD+24] G. Couteau, L. Devadas, S. Devadas, A. Koch, and S. Servan-Schreiber. QuietOT: Lightweight oblivious transfer with a public-key setup. In *ASIACRYPT 2024, Part II, LNCS* 15485, pages 197–231. Springer, Singapore, 2024.

[CK24] G. Couteau and N. Kumar. 10-party sublinear secure computation from standard assumptions. In *CRYPTO 2024, Part IX, LNCS* 14928, pages 39–73. Springer, Cham, August 2024.

[CKS08] D. Cash, E. Kiltz, and V. Shoup. The twin Diffie-Hellman problem and applications. In *EUROCRYPT 2008, LNCS* 4965, pages 127–145. Springer, Berlin, Heidelberg, April 2008.

[Cle90] R. Cleve. Towards optimal simulations of formulas by bounded-width programs. In *22nd ACM STOC*, pages 271–277. ACM Press, May 1990.

[CM21] G. Couteau and P. Meyer. Breaking the circuit size barrier for secure computation under quasi-polynomial LPN. In *EUROCRYPT 2021, Part II, LNCS* 12697, pages 842–870. Springer, Cham, October 2021.

[CMPR23] G. Couteau, P. Meyer, A. Passelègue, and M. Riahinia. Constrained pseudorandom functions from homomorphic secret sharing. In *EUROCRYPT 2023, Part III, LNCS* 14006, pages 194–224. Springer, Cham, April 2023.

[Cou19] G. Couteau. A note on the communication complexity of multiparty computation in the correlated randomness model. In *EUROCRYPT 2019, Part II, LNCS* 11477, pages 473–503. Springer, Cham, May 2019.

[CS02] R. Cramer and V. Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In *EUROCRYPT 2002, LNCS* 2332, pages 45–64. Springer, Berlin, Heidelberg, April / May 2002.

[CZ22] G. Couteau and M. Zarezadeh. Non-interactive secure computation of inner-product from LPN and LWE. In *ASIACRYPT 2022, Part I, LNCS* 13791, pages 474–503. Springer, Cham, December 2022.

[DH76] W. Diffie and M. E. Hellman. New directions in cryptography. *IEEE Transactions on Information Theory*, 22(6):644–654, 1976.

[DHRW16] Y. Dodis, S. Halevi, R. D. Rothblum, and D. Wichs. Spooky encryption and its applications. In *CRYPTO 2016, Part III, LNCS* 9816, pages 93–122. Springer, Berlin, Heidelberg, August 2016.
[DIJL23] Q. Dao, Y. Ishai, A. Jain, and H. Lin. Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN. In *CRYPTO 2023, Part II*, LNCS 14082, pages 315–348. Springer, Cham, August 2023.

[DJ01] I. Damgård and M. Jurik. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In *PKC 2001, LNCS* 1992, pages 119–136. Springer, Berlin, Heidelberg, February 2001.

[DJ03] I. Damgård and M. Jurik. A length-flexible threshold cryptosystem with applications. In *ACISP 03, LNCS* 2727, pages 350–364. Springer, Berlin, Heidelberg, July 2003.

[DKK18] I. Dinur, N. Keller, and O. Klein. An optimal distributed discrete log protocol with applications to homomorphic secret sharing. In *CRYPTO 2018, Part III, LNCS* 10993, pages 213–242. Springer, Cham, August 2018.

[DPSZ12] I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In *CRYPTO 2012, LNCS* 7417, pages 643–662. Springer, Berlin, Heidelberg, August 2012.

[FHKP13] E. S. V. Freire, D. Hofheinz, E. Kiltz, and K. G. Paterson. Non-interactive key exchange. In *PKC 2013, LNCS* 7778, pages 254–271. Springer, Berlin, Heidelberg, February / March 2013.

[Gen09] C. Gentry. Fully homomorphic encryption using ideal lattices. In *41st ACM STOC*, pages 169–178. ACM Press, May / June 2009.

[GI14] N. Gilboa and Y. Ishai. Distributed point functions and their applications. In *EURO-CRYPT 2014, LNCS* 8441, pages 640–658. Springer, Berlin, Heidelberg, May 2014.

[GMW87] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In *19th ACM STOC*, pages 218–229. ACM Press, May 1987.

[Gol06] O. Goldreich. *Foundations of Cryptography: Volume 1*. Cambridge University Press, USA, 2006.

[HLP11] S. Halevi, Y. Lindell, and B. Pinkas. Secure computation on the web: Computing without simultaneous interaction. In *CRYPTO 2011, LNCS* 6841, pages 132–150. Springer, Berlin, Heidelberg, August 2011.

[JRX24] J. Januzelli, L. Roy, and J. Xu. Under what conditions is encrypted key exchange actually secure? *Cryptology ePrint Archive*, Report 2024/324, 2024.

[KKL$^{+}$16] V. Kolesnikov, H. Krawczyk, Y. Lindell, A. J. Malozemoff, and T. Rabin. Attribute-based key exchange with general policies. In *ACM CCS 2016*, pages 1451–1463. ACM Press, October 2016.

[LTV12] A. López-Alt, E. Tromer, and V. Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In *44th ACM STOC*, pages 1219–1234. ACM Press, May 2012.

[Mel22] K. Melissaris. *Witness-Authenticated Key Exchange*. PhD thesis, City University of New York, 2022.

[MW16] P. Mukherjee and D. Wichs. Two round multiparty computation via multi-key FHE. In *EUROCRYPT 2016, Part II, LNCS* 9666, pages 735–763. Springer, Berlin, Heidelberg, May 2016.

[NS09] M. Naor and G. Segev. Public-key cryptosystems resilient to key leakage. In *CRYPTO 2009, LNCS* 5677, pages 18–35. Springer, Berlin, Heidelberg, August 2009.

[OSY21] C. Orlandi, P. Scholl, and S. Yakoubov. The rise of paillier: Homomorphic secret sharing and public-key silent OT. In *EUROCRYPT 2021, Part I, LNCS* 12696, pages 678–708. Springer, Cham, October 2021.

[Pai99] P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In *EUROCRYPT'99, LNCS* 1592, pages 223–238. Springer, Berlin, Heidelberg, May 1999.

[PS16] C. Peikert and S. Shiehian. Multi-key FHE from LWE, revisited. In *TCC 2016-B, Part II, LNCS* 9986, pages 217–238. Springer, Berlin, Heidelberg, October / November 2016.

[RS21] L. Roy and J. Singh. Large message homomorphic secret sharing from DCR and applications. In *CRYPTO 2021, Part III, LNCS* 12827, pages 687–717, Virtual Event, August 2021. Springer, Cham.

[XW23] P. Xu and L.-P. Wang. Multi-key homomorphic secret sharing from LWE without multi-key HE. In *ACISP 23, LNCS* 13915, pages 248–269. Springer, Cham, July 2023.
# Supplementary Material

## A Alternative Construction of Multi-Key HSS from DCR

In this section, we provide an alternative MKHSS for $NC^1$ computations from DCR. This alternative construction has the benefit of not needing the DDH assumption over the Paillier group and avoiding the short exponent assumption, and providing a different path to realizing MKHSS. In particular, unlike our construction in Section 4, this alternative construction does *not* require “expanding” the input shares and secret keys. Moreover, it provides a path to an implementable (albeit concretely slow) MKHSS construction, as we explain later. We note that the lack of ciphertext and key expansion is potentially of independent interest given that all known multi-key FHE scheme (and all our MKHSS scheme from Section 4) have a quadratic blowup in the number of parties. Our alternative construction thus proves that this expansion is not inherent to “multi-keyness.” However, we stress that our MKHSS construction still only works with two parties and still has a ciphertext size blowup relative to the non-multi-key HSS from DCR [OSY21]. Albeit this blowup comes from larger parameters and not from needing having more ciphertexts, in contrast to Section 4.3.

### A.1 Overview of the alternative approach

In this section, we provide a brief overview of the main ideas behind our alternative approach to realizing multi-key HSS from DCR. In particular, we describe how we overcome the synchronization barriers described in Section 2 when using the Paillier–ElGamal encryption scheme.

First, in Appendix A.2 we explain how the parties can derive a common public key via the Diffie–Hellman protocol, and subtractive shares of the corresponding secret key. In contrast to the construction in Section 4, this approach synchronizes both the ciphertexts and the keys (instead of simply expanding the secret keys).

Second, in Appendix A.3, we explain how the two parties can locally use their derived keys to synchronize their respective input shares under their joint public key. This turns out to be more challenging, requiring some careful modifications to the original DCR-based HSS construction. However, in contrast to our constructions from Section 4, the parties no longer need to encrypt the “junk term,” which reduces the number of ciphertexts in each input share.

### A.2 Synchronizing keys

One trivial way for the parties to obtain a joint public key is to just perform a Diffie–Hellman key exchange. That is, the parties derive the common key $f := g^{-s_A \cdot s_B}$, given only each others’ public keys $f_A := g^{-s_A}$ and $f_B := g^{-s_B}$. Here, $g$ is a generator for a hidden-order subgroup of $\mathbb{Z}_{N^2}^*$ (e.g., the subgroup of quadratic residues). But how can the parties then obtain secret shares of the resulting secret key?

In retrospect, generating subtractive shares of the joint secret key (defined by multiplying the individual secret keys) is straightforward to achieve using existing tools. We show that we can use a minimal form of “non-interactive computation” [BM90, OSY21, CZ22], formalized as non-interactive multiplication (NIM) by Boyle et al. [BDSS25], which allows two parties to locally obtain subtractive secret shares of $s_A \cdot s_B$ using only their respective public keys. In particular, NIM can be seen as multi-key HSS for multiplication (or constant-degrees polynomials), which we then “bootstrap” into a multi-key HSS scheme supporting the computation of RMS programs.

**Constructing NIM from DCR.** At a high level, a NIM scheme allows Alice and Bob to generate shares of the multiplication of their respective inputs by exchanging one simultaneous message (or making these messages part of their respective MKHSS public keys, for example). A NIM scheme from the DCR assumption can be realized by following the blueprint laid out in several recent works [OSY21, ARS24, BCM$^{+24}$] (we sketch the construction in Appendix A.4.1). Then, given a NIM scheme, Alice and Bob can locally derive subtractive shares of the joint secret key $s = s_A \cdot s_B$ (defined over the integers) using just the public key of the other party, which is exactly a share of the joint secret key they require.
### A.3 Synchronizing input shares

We now explain how we overcome the challenges associated with synchronizing the HSS input shares. We focus on explaining how Alice and Bob can synchronize an HSS input generated by Alice under her public key $pk_A$ (synchronizing Bob’s input follows by reversing roles).

Using Paillier–ElGamal along with the “flipped” encryption trick we described in Section 2, an input share of a message $x$ under Alice’s public key is of the form:

$$(( (N + 1)^x g^{r_A}, f_A^{r_A} ), (g^{r'_A}, (N + 1)^x f_A^{r'_A} )).$$

In particular, $(N + 1)$ is the generator of the subgroup of $Z_{N^2}^*$ in which computing the discrete logarithm is easy. This makes it possible to compute the DDLog efficiently base-$(N + 1)$.

Recall that the goal of synchronization in MKHSS is to take an HSS input share of $x$ generated under Alice’s public key and transform it into an HSS input share under the joint key derived by Alice and Bob. In this case, Alice and Bob need to locally obtain an input share of the form:

$$(( (N + 1)^x g^{r_A}, f_A^{r_A} ), (g^{r'_A}, (N + 1)^x f_A^{r'_A} )).$$

where $f := g^{-s}$ is the synchronized common public key and $s := s_A \cdot s_B$ is the joint secret key.

**Towards synchronization.** First, we note that Alice can trivially synchronize her own share by simply re-encrypting $x$ under the joint public key $f$ and reusing the same randomness $r_A, r'_A$ she used to generate the original share. By doing so, Alice obtains a new HSS input share of the form:

$$[x]_A := (( (N + 1)^x \cdot g^{r_A}, f_A^{r_A} ), (g^{r'_A}, (N + 1)^x f_A^{r'_A} )), \quad (6)$$

which is distributed exactly as an input share under the joint public key $f$.

Now, we try and let Bob synchronize by computing

$$(( (N + 1)^x \cdot g^{r_A}, (f_A^{r_A})^{s_B} ), (g^{r'_A}, ((N + 1)^x f_A^{r'_A})^{s_B} ) \\ = (( (N + 1)^x \cdot g^{r_A}, f_A^{r_A} ), (g^{r'_A}, (N + 1)^{x \cdot s_B} f_A^{r'_A} )).$$

As already pointed out in Section 2, this “natural” approach to synchronization does not yield the desired encryption of $x$ (the second component is an encryption of $x \cdot s_B$ and not an encryption of $x$). While we resolve this in our other constructions by expanding the secret keys and having Alice provide an additional encryption of the “junk term,” we find a much simpler approach for synchronizing when using Paillier–ElGamal.

Specifically, our idea is to change the space from which the secret keys are sampled. Rather than sampling $s_\sigma$ from the set $\{1, \dots, N\}$, we instead sample the secret keys from the set

$$\{N + 1, 2N + 1, 3N + 1, \dots, (N - 1)N + 1\},$$

which guarantees that all sampled secret keys satisfy $s_\sigma \equiv 1 \mod N$. Observe that because the secret keys are sampled over the integers, this requirement can be easily satisfied by first sampling $s'_\sigma \leftarrow \$ \{1, \dots, N - 1\}$ and then defining $s_\sigma := s'_\sigma \cdot N + 1 \in \mathbb{Z}$. While at first glance this may appear to be an odd choice for sampling the secret keys, it turns out to be just the trick for “automatically” canceling out the junk term created by Bob’s attempt at synchronization (and does not harm security, as we will show later).

Specifically, using the fact that the secret key is congruent to $1 \mod N$ and the fact that $(N + 1)$ has order $N$ in $Z_{N^2}^*$, we get that $(N + 1)^{s_B} = (N + 1) \in Z_{N^2}^*$. This property allows Bob to then synchronize the encryption of the message $x$ as above because $((N + 1)^x f_A^{r_A})^{s_B} = (N + 1)^x f_A^{r_A}$, which is a proper encryption of $x$ under public key $f$ with randomness $r_A$, and matches Alice’s synchronized encryption of $x$ computed in Equation (6).

The high level intuition for why sampling the key in this way does not impact security is the following. First, observe that the public key $g^{-s}$ in Paillier–ElGamal, computed with a secret key $s \leftarrow \$[N]$, is close to a random subgroup element generated by $g$. Then, because $g$ has order $\phi(N)/4$, a public key $g^{-s'}$ computed with $s' := N \cdot s$, is statistically close to $g^{-s}$, since $s$ mod $\phi(N)$ is statistically
close to $s \cdot N \bmod \phi(N)$. As such, the new sampling results in a public key that is statistically close to a standard Paillier–ElGamal public key.

**Achieving full synchronization.** We are now in a situation where, on the one hand, we need to sample the secret keys $s_A$ and $s_B$ such that $s_A \pmod N \equiv s_B \pmod N \equiv 1 \pmod N$ in order to allow Bob to locally synchronize the encryption of $x$. On the other hand, we wish to maintain the ability to compute multiplicative shares of $(N+1)^{x \cdot s}$, using the “flipped” decryption trick, without the secret key being canceled out by the order of the group.

Despite these two requirements appearing mutually exclusive, our next insight allows us to have our cake and eat it too. Instead of encrypting messages exclusively in $\mathbb{Z}_{N^2}^*$, we can encrypt them both in $\mathbb{Z}_{N^2}^*$ and in $\mathbb{Z}_{N^{w+1}}^*$, for some $w > 2$, by using the generalized Paillier–ElGamal encryption scheme of Damgård and Jurik [DJ03]. In $\mathbb{Z}_{N^{w+1}}^*$, the group element $(N+1)$ has order $N^w$, which allows us to encrypt $x$ separately in $\mathbb{Z}_{N^2}^*$ and then duplicate this in $\mathbb{Z}_{N^{w+1}}^*$, such that $(N+1)^{x \cdot s} \in \mathbb{Z}_{N^2}^* \equiv (N+1)^x$ and $(N+1)^{x \cdot s} \in \mathbb{Z}_{N^{w+1}}^* \equiv (N+1)^{x \cdot s} \pmod{N^w}$, for sufficiently large $w$ so that $x \cdot s$ does not exceed $N^w$. This allows us to satisfy both requirements. Additionally, we note that we are not limited to sampling a short secret key $s$, and so our construction does not necessitate making the short-exponent discrete logarithm assumption (in contrast to our constructions from the NIDLS framework in Section 4.3).

## A.4 Alternative construction of MKHSS from DCR

In this section, we present the full MKHSS construction from DCR. Our construction uses two building blocks: NIM and the Damgård–Jurik encryption scheme, which we describe in Appendix A.4.1.

### A.4.1 Building blocks
Here, we describe the two building blocks that we use in our construction.

**Damgård–Jurik–ElGamal encryption scheme.** We first recall the Damgård–Jurik “ElGamal” encryption scheme in Figure 18. The scheme is proven secure under the DCR assumption [DJ03] (see also [CS02, BCP03]). For convenience, we extend the scheme to support the “flipped” encryptions via a FlipEncrypt algorithm.

For completeness, we prove the security of the extended DJEG encryption scheme presented in Figure 18.

**Assumption 1** (Decisional Composite Residuosity (DCR) Assumption). Let GenPQ be a randomized algorithm that, on input the security parameter $\lambda$, outputs two distinct, sufficiently large, random safe primes $p$ and $q$. The DCR assumption states that:

$$ \left\{ (N, g_0) \left| \begin{array}{l} (p, q) \leftarrow \text{GenPQ}(1^{\lambda}) \\ N := pq \\ g_0 \leftarrow \$\mathbb{Z}_{N^2}^* \end{array} \right. \right\} \approx_c \left\{ (N, g_1) \left| \begin{array}{l} (p, q) \leftarrow \text{GenPQ}(1^{\lambda}) \\ N := pq \\ g_0 \leftarrow \$\mathbb{Z}_{N^2}^* \\ g_1 := g_0^N \end{array} \right. \right\}. $$

**Lemma 5.** Let $\lambda$ be a security parameter. If the DCR assumption holds, then the encryption scheme presented in Figure 18 satisfies the standard notion of semantic security (i.e., CPA-security).

*Proof.* The proof of semantic security follows a similar proof made in [BCCS24, Section 4.4] and proceeds with a simple hybrid argument. Here, we adapt the proof to the generalized Damgård–Jurik–ElGamal setting.

- *Hybrid $\mathcal{H}_0$.* This hybrid consists of a ciphertext $(c_0, c_1)$ as generated by DJEG.Encrypt in Figure 18.

- *Hybrid $\mathcal{H}_1$.* In this hybrid, we change how the randomness $r$ is sampled in DJEG.Encrypt, and sample $r$ uniformly from $\{0, 1, \dots, N^{w+1}\}$ instead of $\{0, 1, \dots, N\}$.

$$ \textit{Claim.} \quad \mathcal{H}_1 \approx_s \mathcal{H}_0. $$

*Proof.* This hybrid is statistically close to the previous one by the fact that $g$ and $f$ have order $\phi(N)/4$, which is coprime to $N$. We note that we implicitly use the fact that GenPQ outputs safe primes making $g$, as sampled in Figure 18, a generator for the subgroup of order $\phi(N)/4$ with overwhelming probability. $\square$
- *Hybrid* $\mathcal{H}_2$. In this hybrid, we change how the public key $f$ is sampled in DJEG.KeyGen by sampling $f$ as a uniformly random $2N^w$-th residue. That is, $f := (g')^{2N^w} \in \mathbb{Z}_{N^{w+1}}^*$, where $g' \leftarrow \$ \mathbb{Z}_{N^{w+1}}^*$.

Claim. $\mathcal{H}_2 \approx_s \mathcal{H}_1$.

*Proof.* By the definition of $g = (g_0)^{2N^w}$, it is a generator for the subgroup of the $2N^w$-th residues with overwhelming probability (again, using the fact that $N$ is a composite of safe primes). Then, it suffices to note that in $\mathcal{H}_1$ we have $f = g^s$, which is a uniformly random $2N^w$-th residue when $g$ is a generator for the subgroup of $2N^w$-th residues and $s$ is sampled uniformly from $\mathbb{Z}_N$. $\square$

- *Hybrid* $\mathcal{H}_3$. In this hybrid, we change how the public key $f$ is sampled in DJEG.KeyGen by sampling $f$ as a uniformly random square from $\mathbb{Z}_{N^{w+1}}^*$.

Claim. $\mathcal{H}_3 \approx_c \mathcal{H}_2$ assuming DCR.

*Proof.* The claim follows from a direct reduction to the DCR assumption. For simplicity, we focus on the $w=1$ case which generalizes to $w > 1$ via induction [DJ01, Theorem 1]. Notice that $f$ is sampled as a $2N$-th residue in $\mathcal{H}_2$ and a random square of $\mathbb{Z}_{N^2}^*$ in $\mathcal{H}_3$. The reduction thus has at most a factor of two loss in advantage in the DCR game. $\square$

*Remark 9.* We note that, thanks to CRT decomposition, $\mathbb{Z}_{N^w \cdot \phi(N)/4}$ is isomorphic to $\mathbb{Z}_{N^w} \times \mathbb{Z}_{\phi(N)/4}$ because $N$ is coprime to $\phi(N)$. Using this, any square $c$ in $\mathbb{Z}_{N^{w+1}}^*$ can be written as $c = (1+N)^a g^b \mod N^{w+1}$, for some $(a,b) \in \mathbb{Z}_{N^w} \times \mathbb{Z}_{\phi(N)/4}$, since all elements in $\mathbb{Z}_{N^w \cdot \phi(N)}^*$ can be decomposed into this form. Moreover, for a random $c$, with overwhelming probability $1 - \frac{p+q-1}{N}$, we have that $a \neq 0$ and coprime to $N$.

- *Hybrid* $\mathcal{H}_4$. In this hybrid, the ciphertext elements $c_0$ and $c_1$ are sampled as uniformly random elements of $\mathbb{Z}_{N^{w+1}}^*$.

Claim. $\mathcal{H}_4 \approx_s \mathcal{H}_3$.

*Proof.* We claim that, in hybrid $\mathcal{H}_3$, $(c_0, c_1)$ is already statistically close to the uniform distribution over $\mathbb{Z}_{N^{w+1}}^* \times \mathbb{Z}_{N^{w+1}}^*$. To see this, we first note that $g$ generates a subgroup of order $\phi(N)/4$ and, therefore, the element $c_0$ statistically reveals only the value $r_0 = r \mod \phi(N)/4$. Moreover, using Remark 9, $c_1$ can be rewritten as follows:

$$c_1 = (1 + N)^x \cdot f^r = (1 + N)^{ar_1+x} \mod N^w \cdot g^{b \cdot r_0} \mod \phi(N)/4 \mod N^{w+1},$$

where $r_0 = r \mod \phi(N)/4$ and $r_1 = r \mod N^w$. Then, conditioned on $r_0, r_1$ is statistically close to a uniformly random element by the fact that $N$ and $\phi(N)$ are coprime. By the above, we have that $ar_1 + x \mod N^w$ is statistically close to a uniformly random element of $\mathbb{Z}_{N^w}$ given $r_0$ (recall that $a$ is coprime to $N$, with overwhelming probability). Combined, we have that $(c_0, c_1)$ are statistically close to a uniformly random tuple of elements sampled from $\mathbb{Z}_{N^{w+1}}^*$. $\square$

We have now concluded the proof of semantic security for the DJEG scheme when the ciphertext is generated using DJEG.Encrypt. We note that a very similar hybrid argument applies to proving that ciphertexts output by the “flipped” encryption DJEG.FlipEncrypt are computationally indistinguishable from uniform under the DCR assumption. A little more formally, starting with $\mathcal{H}_3$, the element $f$ is distributed identically to $g$ (both are random squares in $\mathbb{Z}_{N^2}^*$) which enables interchanging them in $c_0$ and $c_1$. This concludes the proof. $\blacksquare$

**Non-interactive multiplication.** Here, we sketch non-interactive multiplication (NIM), as defined by Boyle, Devadas, and Servan-Schreiber [BDSS25]. We define the NIM syntax to be role-agnostic (following Remark 4), which simplifies the presentation in the MKHSS construction.
Damgård–Jurik–ElGamal Encryption Scheme [DJ03]

**Public Parameters.** An algorithm GenPQ as defined in Assumption 1, an exponent parameter $w \ge 1$, and an efficiently computable function $L_w$ that computes the discrete log base $N + 1$ [DJ01].

DJEG.setup(1^λ):

1: (p, q) ← GenPQ(1^λ)

2: N := pq

3: g₀ ← $g \mathbb{Z}^*_{N^{w+1}}$

4: g := (g₀)²$N^w$ ∈ $\mathbb{Z}^*_{N^{w+1}}$

5: return crs := (N, g)

DJEG.KeyGen(crs):

1: parse crs = (N, g)

2: s ← $s$ [N]

3: f := $g^s \in \mathbb{Z}^*_{N^{w+1}}$

4: (pk, sk) := (f, s)

5: return (pk, sk)

DJEG.Encrypt(crs, pk, x):

1: parse crs = (N, g)

2: parse pk = f

3: r ← $\{0, 1, \dots, N\}$

4: c₀ := $g^r \mod N^{w+1}$

5: c₁ := $(N + 1)^x f^r \mod N^{w+1}$

6: return ct := (c₀, c₁)

DJEG.FlipEncrypt(crs, pk, x):

1: parse crs = (N, g)

2: parse pk = f

3: r ← $\{0, 1, \dots, N\}$

4: c₀ := $(N + 1)^x g^r \mod N^{w+1}$

5: c₁ := $f^r \mod N^{w+1}$

6: return ct := (c₀, c₁)

DJEG.Decrypt(crs, sk, ct):

1: parse crs = (N, -)

2: parse ct = (c₀, c₁)

3: c' := $c_1/(c_0)^{sk}$

4: x := $L_w(c')$

5: return x

<caption>Fig. 18: The DJEG encryption scheme.</caption>

**Definition 16** (Non-Interactive Multiplication; Adapted from [BDSS25]). Let $\lambda$ be a security parameter, $\mathcal{R}$ be a finite ring. A non-interactive multiplication (NIM) scheme consists of three algorithms NIM = (Setup, Encode, Decode) with the following syntax:

- Setup(1^λ) → crs. The randomized setup algorithm takes as input the security parameter and outputs a common reference string crs.

- Encode(crs, x) → (pe_σ, st_σ). The randomized encoding algorithm takes as input the CRS crs and a ring element $x \in \mathcal{R}$. It outputs a public encoding pe_σ and secret state st_σ.

- Decode(crs, pe₁⁻_σ, st_σ) → ⟨z⟩_σ. The deterministic decoding algorithm takes as input the CRS crs, another party's public encoding pe₁⁻_σ, and secret state st_σ. It outputs a subtractive secret share of z.

The above functionality must satisfy correctness and security, which are defined as follows:

**Correctness.** For all security parameters $\lambda \in \mathbb{N}$ and every pair of elements $x, y \in \mathcal{R}$, a NIM scheme is said to be correct if there exists a negligible function negl(·) such that:

$$ \Pr \left[ \langle z \rangle_A - \langle z \rangle_B = xy : \begin{array}{l} \text{crs} \leftarrow \text{Setup}(1^\lambda) \\ (\text{pe}_A, \text{st}_A) \leftarrow \text{Encode}(\text{crs}, x) \\ (\text{pe}_B, \text{st}_B) \leftarrow \text{Encode}(\text{crs}, y) \end{array} \ge 1 - \text{negl}(\lambda). \right. $$
Security. A NIM scheme is said to be secure if for all efficient adversaries $\mathcal{A}$, there exists a negligible function $\text{negl}(\cdot)$ such that for all $\lambda \in \mathbb{N}$, and all $\sigma \in \{A, B\}$, we have that

$$ \Pr \left[ \begin{array}{l} \text{crs} \leftarrow \text{Setup}(1^{\lambda}) \\ (x_0, x_1, \text{st}) \leftarrow \mathcal{A}(\text{crs}) \\ b \leftarrow \$ \{0, 1\} \\ (\text{pe}_{\sigma}, \text{st}_{\sigma}) \leftarrow \text{Encode}(\text{crs}, x_b) \\ b' \leftarrow \mathcal{A}(\text{pe}_{\sigma}, \text{st}) \end{array} \right. \le \frac{1}{2} + \text{negl}(\lambda), $$

where $x_0, x_1 \in \mathbb{R}$.

**Sketch: Constructing NIM from DCR.** Here, we briefly sketch the construction of NIM from the DCR assumption from Boyle et al. The scheme is essentially a simplification of non-interactive VOLE [OSY21] from the DCR assumption. In a nutshell, the idea is to first compute the multiplication “in the exponent” of the group and then compute the DDLog to obtain subtractive shares over the integers.

**NIM from DCR.** Let $N$ be a suitable composite modulus and let $g$ and $h$ be random generators of $\mathbb{Z}_{N^2}^*$ that are part of the CRS. The protocol is instantiated over the ring $\mathcal{R} = \mathbb{Z}_\ell$, where for correctness we need $\ell < 2^{-\lambda} \cdot \sqrt{N}$. The high level idea behind the NIM construction is to have:

- Alice's public encoding consist of a Pedersen-like commitment $g^{r_A}h^x$ to her element $x$ and

- Bob's public encoding consist of an encryption $(g^{r_B}, (N+1)^{y'h^{r_B}})$ of his element $y$,

where $r_A$ and $r_B$ are random elements of $\mathbb{Z}_N$.

Then, given Alice's encoding $\text{pe}_A := g^{r_A}h^x$, Bob derives $Z_B := (g^{r_A}h^x)^{-r_B} = g^{-r_A r_B}h^{-x r_B}$. Similarly, given Bob's encoding $\text{pe}_B := (g^{r_B}, (N+1)^{y'h^{r_B}})$, Alice derives $Z_A := (g^{r_B})^{r_A} \cdot ((N+1)^{y'h^{r_B}})^x$. It's not hard to see that $Z_A$ and $Z_B$ form multiplicative shares of $(N+1)^{xy \bmod N}$ since:

$$ \begin{align*} Z_A \cdot Z_B &= ((g^{r_B})^{r_A} \cdot ((N+1)^{y'h^{r_B}})^x) \cdot (g^{r_A}h^x)^{-r_B} \\ &= (g^{r_A r_B} \cdot (N+1)^{xy'h^{x r_B}}) \cdot (g^{-r_A r_B}h^{-x r_B}) \\ &= (N+1)^{xy}. \end{align*} $$

Therefore, by applying the DDLog procedure to $Z_A$ and $Z_B$, the parties recover subtractive shares of $xy \bmod N$. Moreover, because $x, y < 2^{-\lambda} \cdot \sqrt{N}$, we have that, with all but negligible probability, the shares $\langle xy \rangle_A$ and $\langle xy \rangle_B$ are subtractive shares over the integers, by the correctness of the DDLog algorithm.

### A.4.2 Alternative MKHSS construction
We present the alternative MKHSS construction in Figure 19. Each party samples a secret key $s_\sigma \leftarrow \$ \{i \cdot N + 1 \mid 1 \le i \le N - 1\}$ such that $s_\sigma \equiv 1 \bmod N$. The public key $\text{pk}_\sigma$ of each party consists of the group element $f_\sigma := g^{-s_\sigma}$ and public NIM encoding of $s_\sigma$. Alice and Bob then synchronize their keys and respective input shares as described in the overview. In particular, because the input shares are nearly identical to the input shares in the Paillier–ElGamal constructions of (non-multi-key) HSS [OSY21, RS21], the correctness of evaluation for computing RMS programs is almost immediate. Moreover, security reduces to the semantic security of the Damgård–Jurik encryption scheme and the NIM scheme.

**Concrete performance estimates.** We note that the construction in Figure 19 is potentially implementable. Finding ways to further optimize it is an interesting direction for future work. As an immediate optimization, we make the short exponent assumption and sample the keys from a shorter space, allowing us to work in the group $\mathbb{Z}_{N^4}^*$ instead of $\mathbb{Z}_{N^6}^*$. Then, the main overhead of Figure 19 is exponentiation in $\mathbb{Z}_{N^4}^*$. Each RMS multiplication in our construction requires four exponentiations: two exponentiation in $\mathbb{Z}_{N^4}^*$ and two in $\mathbb{Z}_{N^2}^*$, which require roughly 60 milliseconds and 15 milliseconds on high-end hardware, respectively, when using a 3072-bit modulus $N$. Therefore, we can expect each multiplication to take between 150 and 200 milliseconds. This results in roughly 5 multiplications per second. In contrast, (non-multi-key) HSS can achieve upwards of 100 multiplications per second on high-end hardware [BCG$^{+17}$], making our construction an order of magnitude slower.
Alternative Construction of MKHSS from DCR

**Public Parameters.** Let $S_{sk} := \{i \cdot N + 1 \mid 1 \le i \le N - 1\}$ be the secret key space and let $B$ be a bound on the message space. Let $NIM = (\text{Setup}, \text{Encode}, \text{Decode})$ be a NIM scheme. We will use the algorithms $\text{ExpLinEncS}$ and $\text{ExpLinEncR}$ defined in Figure 20.

MKHSS. Setup(1<sup>λ</sup>, w):

1: (N, g) ← DJEG. Setup(1<sup>λ</sup>)

2: crs<sub>nim</sub> ← NIM. Setup(1<sup>λ</sup>)

3: k<sub>1</sub><sup>prf</sup>, k<sub>2</sub><sup>prf</sup> ← $\{0, 1\}^{\lambda}$

4: crs := (N, g, crs<sub>nim</sub>, k<sub>1</sub><sup>prf</sup>, k<sub>2</sub><sup>prf</sup>)

5: return crs

MKHSS. KeyGen(crs):

1: parse (N, g, crs<sub>nim</sub>) from crs

2: s ← $S_{sk}$, f := $g^{-s}$

3: (pe, st) ← NIM. Encode(crs<sub>nim</sub>, s)

4: pk := (pe, f)

5: sk := (st, s)

6: return (pk, sk)

MKHSS. Share(crs, σ, pk<sub>σ</sub>, x):

1: parse crs = (N, g, crs<sub>nim</sub>)

2: parse pk<sub>σ</sub> = (pe<sub>σ</sub>, f<sub>σ</sub>)

3: r, r' ← $\mathbb{Z}_N$

4: ct ← DJEG. FlipEncrypt(f<sub>σ</sub>, x, 5; r)

5: ct' ← DJEG. Encrypt(f<sub>σ</sub>, x, 1; r')

6: [[x]]<sup>σ</sup><sub>σ</sub> := ((x, r, r'), (ct, ct'))

7: [[x]]<sup>σ</sup><sub>1-σ</sub> := (ct, ct')

8: return ([[x]]<sup>σ</sup><sub>A</sub>, [[x]]<sup>σ</sup><sub>B</sub>)

MKHSS. Eval(crs, σ, sk<sub>σ</sub>, pk<sub>1-σ</sub>, [[x<sub>A</sub>]]<sup>A</sup><sub>σ</sub>, [[x<sub>B</sub>]]<sup>B</sup><sub>σ</sub>, P):

1: parse (crs<sub>nim</sub>, k<sub>1</sub><sup>prf</sup>, k<sub>2</sub><sup>prf</sup>) from crs

2: parse sk<sub>σ</sub> = (st<sub>σ</sub>, s<sub>σ</sub>)

3: parse pk<sub>1-σ</sub> = (pe<sub>1-σ</sub>, f<sub>1-σ</sub>)

4: f := (f<sub>1-σ</sub>)<sup>sσ</sup>

5: ⟨z⟩<sub>σ</sub> := NIM. Decode(crs<sub>nim</sub>, pe<sub>1-σ</sub>, st<sub>σ</sub>)

6: k<sub>σ</sub> := ⟨⟨z⟩<sub>σ</sub>, 1⟩ if σ = A else k<sub>σ</sub> := ⟨⟨z⟩<sub>σ</sub>, 0⟩

7: for i ∈ [m]:

8:   ⟨⟨x<sub>σ</sub><sup>(i)</sup>⟩⟩ := ExpLinEncS(sk<sub>σ</sub>, pk<sub>1-σ</sub>, [[x<sub>σ</sub><sup>(i)</sup>]]<sup>σ</sup><sub>σ</sub>)

9:   ⟨⟨x<sub>1-σ</sub><sup>(i)</sup>⟩⟩ := ExpLinEncR(sk<sub>σ</sub>, pk<sub>1-σ</sub>, [[x<sub>1-σ</sub><sup>(i)</sup>]]<sup>1-σ</sup><sub>σ</sub>)

10: ek<sub>σ</sub> := (k<sub>1</sub><sup>prf</sup>, k<sub>2</sub><sup>prf</sup>, k<sub>σ</sub>)

11: ⟨⟨x⟩⟩ := (⟨⟨x<sub>A</sub><sup>(1)</sup>⟩⟩, ..., ⟨⟨x<sub>A</sub><sup>(m)</sup>⟩⟩, ⟨⟨x<sub>B</sub><sup>(1)</sup>⟩⟩, ..., ⟨⟨x<sub>B</sub><sup>(m)</sup>⟩⟩)

12: return DEval(σ, ek<sub>σ</sub>, ⟨⟨x⟩⟩, P)

<caption>Fig. 19: Alternative Construction of MKHSS from DCR.</caption>

ExpLinEncS(sk<sub>σ</sub>, pk<sub>1-σ</sub>, [[x]]<sup>σ</sup><sub>σ</sub>):

1: parse [[x]]<sup>σ</sup><sub>σ</sub> = ((x, r, r'), (-, -))

2: parse sk<sub>σ</sub> := (-, s<sub>σ</sub>)

3: parse pk<sub>1-σ</sub> = (-, f<sub>1-σ</sub>)

4: (c<sub>0</sub>, c<sub>1</sub>) := DJEG. FlipEncrypt(f<sub>1-σ</sub>, x, w; r)

5: (c'<sub>0</sub>, c'<sub>1</sub>) := DJEG. Encrypt(f<sub>1-σ</sub>, x, 2; r')

6: ⟨⟨x⟩⟩ := ((c<sub>0</sub>, (c<sub>1</sub>)<sup>sσ</sup>), (c'<sub>0</sub>, (c'<sub>1</sub>)<sup>sσ</sup>))

7: return ⟨⟨x⟩⟩

ExpLinEncR(sk<sub>σ</sub>, pk<sub>1-σ</sub>, [[x]]<sup>1-σ</sup><sub>σ</sub>):

1: parse [[x]]<sup>1-σ</sup><sub>σ</sub> = ((c<sub>0</sub>, c<sub>1</sub>), (c'<sub>0</sub>, c'<sub>1</sub>))

2: parse sk<sub>σ</sub> := (-, s<sub>σ</sub>)

3: ⟨⟨x⟩⟩ := ((c<sub>0</sub>, (c<sub>1</sub>)<sup>sσ</sup>), (c'<sub>0</sub>, (c'<sub>1</sub>)<sup>sσ</sup>))

4: return ⟨⟨x⟩⟩

<caption>Fig. 20: Exponent-linear encoding algorithms used as subroutines in the DCR-based MKHSS construction.</caption>
**Theorem 6.** Let $\lambda$ is the security parameter and let $N = N(\lambda)$ be the output of GGen as defined in Figure 18. If the DCR assumption holds, then the construction described in Figure 19 is an MKHSS scheme for the class of polynomial sized RMS programs with bound $B < 2^{-\lambda} \cdot N$ and message space $\mathbb{Z}_B$.

*Proof.* We prove correctness and privacy in turn.

**Correctness.** Recall that the correctness property requires that parties obtain a subtractive sharing of the program output upon evaluation.

We first prove that the encoding $\{\{x\}\}$ derived by the parties in MKHSS.Eval is (1) the same for both parties and (2) exponent-linear decodable.

*Claim.* For all integers $x \in \mathbb{Z}_N$ and all $\sigma \in \{A, B\}$, we have

$$ \{\{x\}\} = \text{ExpLinEncS}(\text{sk}_{\sigma}, \text{pk}_{1-\sigma}, \llbracket x \rrbracket_{\sigma}^{\sigma}) = \text{ExpLinEncR}(\text{sk}_{1-\sigma}, \text{pk}_{\sigma}, \llbracket x \rrbracket_{1-\sigma}^{\sigma}), $$

where $(\llbracket x \rrbracket_A^{\sigma}, \llbracket x \rrbracket_B^{\sigma}) \leftarrow \text{MKHSS.Share}(\text{crs}, \sigma, \text{pk}_{\sigma}, x)$. Moreover, $\{\{x\}\}$ is base-$(N+1)$ exponent-linear decodable under the decoding key $\mathbf{k} = (s_A \cdot s_B, 1)$.

*Proof.* We consider the case where $\sigma = A$; a symmetric argument follows for the case where $\sigma = B$.

By inspecting MKHSS.Share, we have $\llbracket x \rrbracket_A^A = ((x, r, r'), (\text{ct}, \text{ct}'))$ and $\llbracket x \rrbracket_B^A = (\text{ct}, \text{ct}')$, where

$$ \text{ct} = ((N+1)^x \cdot g^r, f_A^r) \text{ and } \text{ct}' = (g^{r'}, (N+1)^x \cdot f_A^{r'}) $$

Party-A computes $\{\{x\}\}$ in ExpLinEncS as

$$ \begin{aligned} \{\{x\}\} &= ((N+1)^x \cdot g^r, (f_B^r)^{s_A}), (g^{r'}, ((N+1)^x \cdot f_B^{r'})^{s_A}) \in (\mathbb{Z}_{N^6}^*)^2 \times (\mathbb{Z}_{N^2}^*)^2 \\ &= ((N+1)^x \cdot g^r, f^r), (g^{r'}, (N+1)^{x \cdot s_A} \cdot f_B^{r' \cdot s_A}) \\ &= ((N+1)^x \cdot g^r, f^r), (g^{r'}, (N+1)^x \cdot f^{r'}) \end{aligned} $$

where the third equality follows from the fact that $s_A \equiv 1 \pmod N$ and $(N+1)$ has order $N$ in $\mathbb{Z}_{N^2}^*$.
Now, observe that party-B computes $\{\{x\}\}$ in ExpLinEncR as

$$ \begin{aligned} \{\{x\}\} &= ((N+1)^x \cdot g^r, (f_A^r)^{s_B}), (g^{r'}, ((N+1)^x \cdot f_A^{r'})^{s_B}) \in (\mathbb{Z}_{N^6}^*)^2 \times (\mathbb{Z}_{N^2}^*)^2 \\ &= ((N+1)^x \cdot g^r, f^r), (g^{r'}, (N+1)^{x \cdot s_B} \cdot f_A^{r' \cdot s_B}) \\ &= ((N+1)^x \cdot g^r, f^r), (g^{r'}, (N+1)^x \cdot f^{r'}) \end{aligned} $$

Therefore, both parties obtain the same encoding $\{\{x\}\}$.

We are left to show that $\{\{x\}\} = (\mathbf{c}_0, \mathbf{c}_1)$ is base-$(N+1)$ exponent-linear decodable under $\mathbf{k} = (k_1, k_2) = (s_A \cdot s_B, 1)$. Observe that

$$ \langle \mathbf{c}_0, \mathbf{k} \rangle = ((N+1)^x \cdot g^r)^{s_A \cdot s_B} \cdot f^r = (N+1)^{x \cdot s_A \cdot s_B} \cdot g^{r \cdot s_A \cdot s_B} \cdot g^{-s_A \cdot s_B \cdot r} = (N+1)^{x \cdot s_A \cdot s_B} \in \mathbb{Z}_{N^6}^* $$

$$ \langle \mathbf{c}_1, \mathbf{k} \rangle = ((g^{r'})^{s_A \cdot s_B} \cdot (N+1)^x \cdot f^{r'}) = g^{r \cdot s_A \cdot s_B} \cdot (N+1)^x \cdot g^{-s_A \cdot s_B \cdot r} = (N+1)^x \in \mathbb{Z}_{N^2}^* $$

which proves that $\{\{x\}\}$ is base-$(N+1)$ exponent-linear decodable. In particular, $s_A \cdot s_B \le ((N-1) \cdot N)^2 < N^4$. Furthermore, because $x \le N$, we have that $x \cdot s_A \cdot s_B$ does not overflow modulo $N^5$. $\square$

Finally, to complete the proof of correctness, it suffices to note that by the correctness of NIM, the parties obtain subtractive shares of $s_A \cdot s_B$, and so $\mathbf{k}_\sigma$ is a subtractive share of $\mathbf{k}$ as defined above.

In sum, it follows that parties run DEval with encodings of the input that are base-$(N+1)$ exponent-linear decodable. Finally, since $B < 2^{-\lambda} \cdot N$ and DDLog is a $B$-bounded (resp. $(B \cdot N^4)$-bounded) base-$(N+1)$ algorithm for distributed discrete logarithm with negligible correctness error in $\mathbb{Z}_{N^2}^*$ (resp. $\mathbb{Z}_{N^6}^*$), it follows from Lemma 3 that the MKHSS scheme satisfies the correctness property for all polynomial-size RMS programs P.

**Security.** Recall that the security property requires that the input share $\llbracket x \rrbracket_{1-\sigma}^{\sigma}$ of party-$(1-\sigma)$, ensures the privacy of an input $x$ shared using party-$\sigma$'s public key $\text{pk}_\sigma$.
Consider any efficient adversary $\mathcal{A}$ for the security experiment defined in Definition 6. Let the output of the security experiment be defined as 1 if $\mathcal{A}$'s output $b'$ is equal to the challenge bit $b$; else let the output of the experiment be defined as 0. We will use a hybrid argument to show that the output of the experiment is 1 with probability of at most $1/2 + \text{negl}(\lambda)$.

- *Hybrid* $\mathcal{H}_0$. This hybrid consists of the output of the experiment when run with adversary $\mathcal{A}$ when the challenge bit is $b=0$.

- *Hybrid* $\mathcal{H}_1$. This hybrid game is identical to the previous hybrid, except that the secret key $s_\sigma$ is sampled uniformly at random from $[N]$ in MKHSS.KeyGen, which matches the distribution of the secret key in the DJEG encryption scheme.

*Claim.* $\mathcal{H}_1 \approx_s \mathcal{H}_0$.

*Proof.* Note that in $\mathcal{H}_0$ the public key is computed as $f = g^{N \cdot i} g$ for some $i \in [N-1]$ while in $\mathcal{H}_1$ it is computed as $g^i$ for $i \in [N]$. Because $g$ has order $\phi(N)/4$, and for a random $i \in [N-1]$, $i$ (mod $\phi(N)/4$ is statistically close to $i \cdot N \mod \phi(N)/4$ (since $\phi(N)$ is co-prime to $N$), it follows that $g^i$ and $(g^N)^i$ are both statistically close to the uniform distribution. To conclude the proof, it suffices to note that $(g^N)^i \cdot g$ is also close to uniform. $\square$

- *Hybrid* $\mathcal{H}_2$. In this hybrid game, $\text{pe}$ is replaced with an encoding of zero. That is, $(\text{pe}_\sigma, -) \leftarrow \text{NIM Encode}(\text{crs}_{\text{nim}}, 0)$.

*Claim.* $\mathcal{H}_2 \approx_c \mathcal{H}_1$ assuming the security of NIM.

*Proof.* The claim follows immediately from the security of the NIM scheme. $\square$

- *Hybrid* $\mathcal{H}_3$. In this hybrid game, we replace the DJEG encryptions with encryptions of $x_1$.

*Claim.* $\mathcal{H}_3 \stackrel{\mathcal{S}}{\approx} \mathcal{H}_2$ by the semantic security of the DJEG encryption scheme.

*Proof.* The claim follows by a straightforward hybrid argument replacing the two encryptions of $x_0$ with encryptions of $x_1$ and invoking the semantic security of the DJEG scheme. $\square$

- *Hybrid* $\mathcal{H}_4$. In this hybrid game, we reverse the changes made in $\mathcal{H}_2$ and encode the secret key $s$ using the NIM scheme.

*Claim.* $\mathcal{H}_4 \approx_c \mathcal{H}_3$ assuming the security of NIM.

*Proof.* The claim follows immediately from the security of the NIM scheme. $\square$

- *Hybrid* $\mathcal{H}_5$. In this hybrid game, we reverse the changes made in $\mathcal{H}_1$ and sample the secret key as in the construction.

*Claim.* $\mathcal{H}_5 \approx_c \mathcal{H}_4$.

*Proof.* The proof follows the same argument used to prove that $\mathcal{H}_1 \approx_c \mathcal{H}_0$. $\square$

To complete the proof, observe that $\mathcal{H}_5$ is exactly the output of the experiment when the challenge bit $b=1$. Since we've shown that $\mathcal{H}_0 \approx_c \mathcal{H}_5$, it follows that $\mathcal{A}$ wins the MKHSS security game with probability of at most $1/2 + \text{negl}(\lambda)$. $\blacksquare$