# Fast Public-Key Silent OT and More from Constrained Naor-Reingold

Dung Bui, Geoffroy Couteau, Pierre Meyer, Alain Passelègue, Mahshid Riahinia

► To cite this version:

Dung Bui, Geoffroy Couteau, Pierre Meyer, Alain Passelègue, Mahshid Riahinia. Fast Public-Key Silent OT and More from Constrained Naor-Reingold. EUROCRYPT 2024, Aug 2024, Santa Barbara (CA), France. pp.88-118, 10.1007/978-3-031-58751-1_4 . hal-04770536

HAL Id: hal-04770536

https://hal.science/hal-04770536v1

Submitted on 6 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Fast Public-Key Silent OT and More
from Constrained Naor-Reingold

Dung Bui¹, Geoffroy Couteau¹, Pierre Meyer², Alain Passelègue³,⁴, and Mahshid Riahinia⁴

¹ Université Paris Cité, CNRS, IRIF, FRANCE. {bui,couteau}@irif.fr

² Aarhus Universitet, DENMARK. pierre.meyer@cs.au.dk

³ CryptoLab Inc., FRANCE. alain.passelegue@cryptolab.co.kr

⁴ ENS de Lyon, Laboratoire LIP (U. Lyon, CNRS, ENSL, Inria, UCBL), FRANCE.
mahshid.riahinia@ens-lyon.fr

**Abstract.** Pseudorandom Correlation Functions (PCFs) allow two parties, given correlated evaluation keys, to locally generate arbitrarily many pseudorandom correlated strings, e.g. Oblivious Transfer (OT) correlations, which can then be used by the two parties to jointly run secure computation protocols.

In this work, we provide a novel and simple approach for constructing PCFs for OT correlation, by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function (wPRF). We then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity pseudorandom functions allow us to instantiate our paradigm. We further extend our ideas to obtain efficient *public-key* PCFs, which allow the distribution of correlated keys between parties to be non-interactive: each party can generate a pair of public/secret keys, and any pair of parties can locally derive their correlated evaluation key by combining their secret key with the other party's public key.

In addition to these theoretical contributions, we detail various optimizations and provide concrete instantiations of our paradigm relying on the Boneh-Ishai-Passelègue-Sahai-Wu wPRF and the Goldreich-Applebaum-Raykov wPRF. Putting everything together, we obtain public-key PCFs with a throughput of 15k-40k OT/s, which is of a similar order of magnitude to the state-of-the-art *interactive* PCFs and about 4 orders of magnitude faster than state-of-the art *public-key* PCFs.

As a side result, we also show that public-key PCFs can serve as a building block to construct reusable designated-verifier non-interactive zero-knowledge proofs (DV-NIZK) for NP. Combined with our instantiations, this yields simple and efficient reusable DV-NIZKs for NP in pairing-free groups.
Table of Contents

<table><tr><td>Fast Public-Key Silent OT and More from Constrained Naor-Reingold</td><td>1</td></tr><tr><td>Dung Bui, Geoffroy Couteau, Pierre Meyer, Alain Passelègue, and Mahshid Riahinia</td><td></td></tr><tr><td>1 Introduction</td><td>3</td></tr><tr><td>2 Technical Overview</td><td>5</td></tr><tr><td>2.1 A PCF for OT from Pseudorandomly Constrained PRFs</td><td>5</td></tr><tr><td>2.2 A CPRF for Inner-Product Membership from the Naor-Reingold PRF</td><td>6</td></tr><tr><td>2.3 Inner-Product Membership Weak Pseudorandom Functions</td><td>8</td></tr><tr><td>2.4 Optimizations</td><td>10</td></tr><tr><td>2.5 Final PCF Construction</td><td>11</td></tr><tr><td>2.6 Concrete Parameters</td><td>12</td></tr><tr><td>2.7 Public Key PCF</td><td>14</td></tr><tr><td>2.8 Application: A simple reusable DV-NIZK reusable</td><td>16</td></tr><tr><td>3 Preliminaries</td><td>17</td></tr><tr><td>3.1 Pseudorandom Functions</td><td>17</td></tr><tr><td>3.2 Constrained Pseudorandom Functions</td><td>17</td></tr><tr><td>3.3 Reverse-Sampleable Correlations</td><td>18</td></tr><tr><td>3.4 Pseudorandom Correlation Functions</td><td>19</td></tr><tr><td>3.5 NIZKs</td><td>22</td></tr><tr><td>3.6 Variants of Power-DDH</td><td>24</td></tr><tr><td>3.7 Decision Composite Residuosity Assumption</td><td>24</td></tr><tr><td>3.8 Pedersen Commitment Scheme</td><td>25</td></tr><tr><td>4 Constraining the Naor-Reingold PRF</td><td>25</td></tr><tr><td>4.1 Inner Product Membership CPRF from Naor-Reingold</td><td>25</td></tr><tr><td>4.2 Compressing the keys</td><td>27</td></tr><tr><td>4.3 Application: A Puncturable PRF in NC<sup>1</sup></td><td>29</td></tr><tr><td>5 Fast PCFs for OTs from Pseudorandomly Constrained PRFs</td><td>31</td></tr><tr><td>5.1 General Template</td><td>31</td></tr><tr><td>5.2 Pseudorandom Constraints Expressed as IPM</td><td>37</td></tr><tr><td>5.3 Candidate IPM-wPRF</td><td>38</td></tr><tr><td>5.4 Distributed Interactive Key Generation via MPC</td><td>40</td></tr><tr><td>6 Public-Key PCF for OT Correlations</td><td>42</td></tr><tr><td>6.1 Formal Definition</td><td>42</td></tr><tr><td>6.2 A Public-Key PCF via Bellare-Micali Non-Interactive OT</td><td>44</td></tr><tr><td>6.3 A Better Construction from Paillier-ElGamal</td><td>45</td></tr><tr><td>6.4 Reducing The Public Keys Size to O(n<sup>2/3</sup>)</td><td>51</td></tr><tr><td>7 DV-NIZKs from PK-PCFs</td><td>53</td></tr><tr><td>7.1 Construction of reusable DVNIZK</td><td>53</td></tr><tr><td>7.2 Concrete Instantiation</td><td>58</td></tr></table>
# 1 Introduction

Efficient procedures to generate correlated randomness are at the heart of modern secure computation. Starting with the seminal work of Beaver [Bea95], many protocols achieving impressive performances have been designed in a model where the parties are given access to a trusted source of correlated randomness [NNOB12, DPSZ12, FKOS15, LPSY15, DNNR17, WRK17, HSS20, DILO22]. As an example, $O(n)$ instances of a random oblivious transfer suffice to evaluate any size-$n$ circuit using the seminal GMW protocol [GMW87], using as little as four bits of communication per AND gate.

Due to the efficiency of protocols in the correlated randomness model, a popular paradigm in secure computation is to divide the protocol into two phases: in the *preprocessing* phase, which is independent of the inputs (and can be executed ahead of time), long correlated random strings are securely generated using a dedicated protocol. Then, in the *online* phase, this correlated randomness is consumed by a fast and lightweight protocol. Traditional approaches for generating the correlated randomness were based on oblivious transfer extension [IKNP03] or somewhat homomorphic encryption [DPSZ12]. They incur a large $\Omega(\lambda \cdot n)$ communication overhead for $n$-gate circuits and typically form the main efficiency bottleneck of the protocol.

**Generating pseudorandom correlations.** Recently, a new paradigm has emerged which enables the *silent* generation of long correlated *pseudorandom* strings [BCGI18, BCG$^{+}$19b, BCG$^{+}$19a], removing essentially all of the communication in the preprocessing phase. Concretely, this is made possible by the mean of cryptographic primitives, such as *pseudorandom correlation generators* (PCG) [BCG$^{+}$19b] and *pseudorandom correlated functions* (PCFs) [BCG$^{+}$20].

A PCG is a pair of algorithms (PCG.Gen, PCG.Expand) where PCG.Gen produces two short keys ($k_0, k_1$), and PCG.Expand($\sigma, k_\sigma$) produces a long string $y_\sigma$ such that ($y_0, y_1$) form pseudorandom samples from the target correlation. PCGs enable silent secure computation as follows: using a small distributed protocol to securely generate the keys ($k_0, k_1$), two parties can afterwards locally expand them into long correlated pseudorandom strings without any further communication. The online phase proceeds as before.

PCGs suffer from a considerable limitation: after distributing the keys, the parties are bound to generate *all at once* a priori *fixed amount* of correlated randomness. PCFs overcome this issue: a PCF is a pair of algorithms (PCF.Gen, PCF.Eval) where PCF.Gen produces two short keys ($k_0, k_1$), and PCF.Eval($\sigma, k_\sigma, x$) outputs $y_\sigma^x$ where for each new input $x$, ($y_0^x, y_1^x$) appears like a fresh sample from the target correlation. Hence, after distributively generating the keys ($k_0, k_1$) once and for all, two parties can generate on-the-fly any amount of target correlations in all their future secure computations.

The line of work on PCGs and PCFs has been fairly successful: modern PCG protocols for the oblivious transfer (OT) correlation (often called *silent OT extension*) can stretch up to 10M OT/s on one core of a standard laptop [CRR21, BCG$^{+}$22, RRT23] from keys in the 10$\sim$20kB range, and the fastest PCFs for OT [BCG$^{+}$22] can generate up to 100k OT/s on one core of a standard laptop.

**Public-key silent OT.** The silent generation of correlated randomness from PCGs or PCFs requires two parties to engage in an interactive protocol to securely generate the PCG/PCF keys. *Public-key* PCFs reduce this interactive phase to a bare minimum, by replacing it with a public-key setup. More precisely, after publishing their public keys online, any pair of parties on a network can start generating correlated randomness, without *any interaction* beyond the initial PKI. Public-key silent correlated randomness generation is somewhat of a holy grail in this line of work: it would represent a major step towards bridging the usability gap between secure communication (since PKI suffices to enable efficient pairwise secure communication) and secure computation, but public-key PCFs for OTs have so far proven considerably harder to achieve than standard PCG and PCFs. Until recently, we simply had no public key silent OT construction, beyond heavy-hammer constructions from obfuscation or threshold multikey FHE.

This changed recently with the result of [OSY21], which achieved the first practical public-key silent OT, assuming the quadratic residuosity assumption and the existence of correlation-robust hash functions. However, the efficiency of the new construction of [OSY21] still lags way behind that of state-of-the-art PCFs for OTs. Concretely, their construction relies on a new distributed discrete logarithm protocol that allows two parties, given multiplicative shares of a value $G^x$ (where $G$ generates a suitable DLog-easy group), to non-interactively compute additive shares of $x$. The
public-key silent OT construction of [OSY21] has public keys of size around 1kB for one of the parties, and about 50kB for the other. In terms of computational efficiency, the cost of generating a single OT correlation is dominated by $\lambda$ exponentiations with an exponent in $Z_{N·2^\lambda}$, where N is an RSA modulus. Using $\lambda = 128$ and $\log N = 3072$, this translates to 128 exponentiations with 3200-bit exponents and takes about one second on one core of a standard laptop, which is between four and five orders of magnitude slower than the state-of-the-art PCF of [BCG+22]. In summary, as of today, the fundamental goal of obtaining concretely efficient and usable public-key silent OTs remains wide open.

**Our Results.** As our main contribution, we construct the first concretely efficient public-key PCF for oblivious transfers. Our approach departs significantly from all previous works, and we obtain several additional contributions. Our new public-key PCF features public key sizes in the 30kB range, and the cost of generating each OT is dominated by a single exponentiation over a standard 256-bit elliptic curve. Using fast curves such as Curve25519 [Ber06] or FourQ [CL15], we estimate a throughput of 15k to 40k OT/s on one core of a standard laptop, about four orders of magnitude faster than the best previous public-key PCF, and approaching the efficiency of the best PCF overall. Our results enable for the first time all users of a network, after a simple PKI setup, to efficiently generate arbitrary amounts of pairwise OT correlations without any interaction. The security of our construction reduces to four assumptions: the Decisional Composite Residuosity assumption, the sparse power-DDH assumption (a new —static, falsifiable, secure in the GGM— variant of DDH that we introduce), correlation-robust hash function, and a suitable weak pseudorandom function (which we instantiate using either the Goldreich-Applebaum-Raykov weak PRF [Gol00, AR16] or the Boneh-Ishai-Passelègue-Sahai-Wu weak PRF [BIP$^{+18}$]).$^5$

At the heart of our result is a new construction of efficient constrained pseudorandom functions from the Naor-Reingold PRF [NR97], for a class of constraints we term inner-product membership (IPM) constraints. Informally, CPRFs are pseudorandom functions where given a constrained key $K_C$ for some predicate $C$, one can locally evaluate the PRF at all points $x$ where $C(x) = 0$, while the output of the function still looks random on inputs $x$ where $C(x) = 1$. A constrained key for the class IPM is associated to a vector $z$ and a set $S$, and allows evaluating the PRF on an input $x$ if and only $\langle x, z \rangle \in S$. Along the way to our efficient public-key PCF, we achieve several results of independent interest:

- We show how a simple tweak to the Naor-Reingold PRF yields a constrained PRF (CPRF) for IPM constraints, in the random oracle model. IPM constraints capture several predicates of interest, and in particular, we obtain the first puncturable pseudorandom function (CPRF for the class of point functions) in the complexity class $NC^1$.

- Observing that several low-complexity PRFs can be expressed as IPM constraints, we obtain a pseudorandomly constrained PRF: a constrained key is associated to a (low-complexity) PRF, and allows evaluating the CPRF on inputs $x$ for which the low-complexity PRF evaluates to 0.

- We then show that pseudorandomly constrained PRFs yield precomputable PCFs. The notion of precomputability for PCFs was recently introduced in [CMPR23] together with a proof-of-concept (inefficient) construction from DCR. In a precomputable PCF, one of the parties can locally generate a PCF key and precompute its entire share of the correlated randomness even before knowing the identity of the other party. This pushes to an extreme the possibility of preparing secure computation protocols ahead of time, by allowing one party to execute the entire preprocessing before knowing its input, the function, and the identity of its opponent. Combining these results, we obtain the first concretely efficient precomputable PCF, from the sparse DDH assumption, in the random oracle model. While the resulting construction is not a public-key PCF, distributing the key generation of our precomputable PCF is also very simple, requiring only $n$ parallel calls to an oblivious transfer protocol (with $n = 256$ in our most efficient instantiation).

Eventually, we explore an application of public-key PCF to designated-verifier zero-knowledge proofs (DV-NIZKs). A DV-NIZK allows any prover to demonstrate the truth of a statement using a single message, such that the proof can be verified using a secret verification key. DV-NIZKs are

<footnote>$^5$ The DCR assumption in our construction can be replaced by the DDH assumption over subgroups of finite fields, but at the cost of a less efficient construction.</footnote>
believed to be easier to obtain than standard NIZKs, in the following sense: they are known to exist under the plain CDH assumption in pairing-free groups [CH19, QRW19, KNYY19], while NIZKs are only known in pairing groups, or using subexponential hardness assumptions [JJ21, CJJQ23]. Yet, efficiency-wise, we do not know of any concretely efficient construction of DV-NIZKs in pairing-free groups (efficient NIZKs are known in pairing groups [GS08, KW15, CH20], and known DV-NIZKs in pairing-free groups rely on the hidden bit model, for which no concretely efficient instantiation is known). We show how, using a public-key PCF, one can compile any $\Sigma$-protocol with binary challenge into a DV-NIZK. Plugging our construction of public-key PCF, we obtain a new DV-NIZK from polynomial assumptions over pairing-free groups for all languages that admit a bit $\Sigma$-protocol, with communication comparable to that of the $\Sigma$-protocol. Conceptually, our result can be seen as observing that a public-key PCF suffices to upgrade *non-reusable* DV-NIZKs (which exist from public key encryption [CHH$^+$07]) into *reusable* DV-NIZKs.

# 2 Technical Overview

In this section, we provide a detailed overview of our results. We start by describing our main paradigm about constructing PCF for OT correlations from Pseudorandomly Constrained PRFs in Section 2.1. Then, in Section 2.2, we explain how to modify the Naor-Reingold PRF in order to obtain a CPRF for the class of inner-product membership predicates, and show that various weak PRF constructions can be expressed as such predicates in Section 2.3, leading to instantiations of pseudorandomly constrained PRFs and therefore of PCFs.

Next, we focus on optimizing the resulting PCFs. In Sections 2.4 and 2.5, we provide several optimizations which benefit the most efficient instantiations of our paradigm and detail our optimized PCF construction. Concrete parameters are provided in Section 2.6.

We then describe in Section 2.7 how our PCF can be turned into an efficient public-key PCF by relying on ideas borrowed from [OSY21], and how to optimize the resulting construction.

Finally, in Section 2.8, we explain how our public-key PCF can be used to construct reusable designated-verifier NIZKs.

## 2.1 A PCF for OT from Pseudorandomly Constrained PRFs

Let $F = (F.KeyGen, F.Eval)$ be a (weak, strong) PRF with key space $\mathcal{K}$ and binary outputs. For a key $K \in \mathcal{K}$, let $F_K : x \mapsto F.Eval(K, x)$. Also, let CPRF = (CPRF.KeyGen, CPRF.Eval, CPRF.Constrain, CPRF.CEval) denote a constrained PRF for the class $\mathcal{F} = \{F_K\}_{K \in \mathcal{K}} \cup \{1 - F_K\}_{K \in \mathcal{K}}$, i.e., $\mathcal{F}$ contains all predicates "$F.Eval(K, x)$ evaluates to $b$" for $b \in \{0, 1\}$ and $K \in \mathcal{K}$. Then, we construct a (weak, strong) pseudorandom correlation function for oblivious transfer correlation as follows:

- The sender gets two independent master secret keys ($msk_0, msk_1$) of the CPRF. On an input $x$, this party evaluates the CPRF on $x$ using both keys to obtain two pseudorandom outputs $(y_0, y_1)$.

- The receiver gets a random (weak) PRF key $K \leftarrow \mathcal{K}$, and two constrained keys: $ck_0$ that is $msk_0$ constrained at "$F_K(x) = 0$", and $ck_1$ that is $msk_1$ constrained at "$F_K(x) = 1$". On an input $x$, this party computes $b \leftarrow F_K(x)$, and sets $y_b \leftarrow \text{CPRF.CEval}(ck_b, x)$. It then outputs $(b, y_b)$.

*Correctness* is straightforward: for any $x$, the predicate $F_K(x) = b$ is satisfied for some $b \in \{0, 1\}$, hence the constrained key $ck_b$ yields the correct output $y_b$ by the correctness of the CPRF. *Sender security* follows from the fact that the two constrained keys are constrained at $F_K$ and $1 - F_K$, respectively, hence both constrains can never be satisfied at the same time. Thus, by the security of the CPRF, when $F_K(x) = b$, the value $y_{1-b}$ is indistinguishable from random for the receiver. *Receiver security* follows from the (weak) pseudorandomness of $F$, which entails that $b = F_K(x)$ is pseudorandom from the sender's perspective.

We sketch the full construction below (we omit the public parameters $\mathit{pp}$ output by the CPRF for simplicity):

- $\mathit{PCF.Gen}(1^\lambda)$:

- For $b \in \{0, 1\}$, run $\mathit{msk}_b \leftarrow \mathit{CPRF.KeyGen}(1^\lambda)$.
* Sample $K \leftarrow F.\text{KeyGen}(1^{\lambda})$, and compute $ck_0 \leftarrow \text{CPRF.Constrain}(\text{msk}_0, F_K)$ and $ck_1 \leftarrow \text{CPRF.Constrain}(\text{msk}_1, 1 - F_K)$.

* Output $k_0 \leftarrow (\text{msk}_0, \text{msk}_1)$ and $k_1 \leftarrow (K, ck_0, ck_1)$.

* **PCF.Eval($\sigma, k_\sigma, x$):**

* If $\sigma = 0$, parse $k_0 = (\text{msk}_0, \text{msk}_1)$, and compute $y_b \leftarrow \text{CPRF.Eval}(\text{msk}_0, x)$ for $b \in \{0, 1\}$, and output $(y_0, y_1)$.

* If $\sigma = 1$, parse $k_1 = (K, ck_0, ck_1)$, and compute $b \leftarrow F_K(x)$. Set $y_b \leftarrow \text{CPRF.CEval}(ck_b, x)$, and output $(b, y_b)$.

We further observe that the resulting PCF is *precomputable* as recently defined in [CMPR23]. Informally, it allows one of the parties to locally generate its own PCF key and compute its correlated randomness entirely, before even knowing the identity of the other party. In the above construction, the sender can precompute all pairs $(y_0, y_1)$ ahead of time, and it is therefore precomputable.

We note that the fact that CPRFs for a class containing a PRF yield a PCF is not entirely new; for example, a similar observation was briefly mentioned in [BGMM20]. However, the few known constructions of sufficiently expressive CPRFs [BV15, AMN$^{+}$18, CMPR23] are too expensive, and using them within the above transformation yields PCFs that are much less flexible than generic constructions based on homomorphic secret sharing or threshold FHE (that are not restricted to the OT correlation), and much less efficient than state-of-the-art PCFs [BCG$^{+}$20, BCG$^{+}$22]. Our key contribution is identifying that a simple tweak to the Naor-Reingold PRF [NR97] yields an extremely efficient pseudorandomly constrained PRF as we explain below.

## 2.2 A CPRF for Inner-Product Membership from the Naor-Reingold PRF

Let us first recall the Naor-Reingold PRF [NR97], whose input domain is $\mathcal{X} = \{0, 1\}^n$. Let $\mathbb{G} = \mathbb{G}(\lambda)$ be a family of cyclic groups of prime order $p = p(\lambda)$.

* $F.\text{KeyGen}(1^{\lambda})$: Sample $g \stackrel{\$}{\leftarrow} \mathbb{G}$ and $a_1, a_2, \dots, a_n \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$. Output $\text{msk} \leftarrow (g, a_1, \dots, a_n)$.

* $F.\text{Eval}(\text{msk}, x)$: On input $x = (x_1, \dots, x_n) \in \{0, 1\}^n$, output $g \prod_{i=1}^n a_i^{x_i}$.

Evaluating the Naor-Reingold PRF requires a few multiplications, followed by a single exponentiation. Its security reduces to the Decisional Diffie-Hellman assumption over $\mathbb{G}$.

**A no-evaluation-secure CPRF for inner-product.** As a warm-up, we define the class of predicates

$$C_z : x \rightarrow \begin{cases} 0 & \text{if } \langle x, z \rangle = 0 \\ 1 & \text{otherwise.} \end{cases}$$

That is, a constrained key for $z$ allows to evaluate the PRF on all inputs $x$ satisfying $\langle x, z \rangle = 0$. Now, consider the following extension of the Naor-Reingold PRF:

* $F.\text{Constrain}(\text{msk}, z)$: Sample $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$ and define $(\alpha_1, \dots, \alpha_n) \leftarrow (r^{-z_1} \cdot a_1, \dots, r^{-z_n} \cdot a_n)$, and output $ck = (g, \alpha_1, \dots, \alpha_n)$.

* $F.\text{CEval}(ck, x)$: On input $x = (x_1, \dots, x_n) \in \{0, 1\}^n$, output $g \prod_{i=1}^n \alpha_i^{x_i}$.

Here, each key $a_i$ is *blinded* by a term $r^{-z_i}$, and the outputs of the Eval and CEval algorithms coincide when the blinding terms cancel out which happens precisely when the inner product $\langle x, z \rangle$ is equal to 0 modulo the order of $r$. For a safe prime $p$ with $p-1 = 2q$, the order of $r$ is $q$ or $2q$ with overwhelming probability, so with $q \gg n$, $\langle x, z \rangle = 0 \mod q$ iff $\langle x, z \rangle = 0$ over the integers. More precisely, we have:

$$\begin{align*} F.CEval(ck, x) &= g \prod_{i=1}^{n} \alpha_i^{x_i} = g \prod_{i=1}^{n} (r^{-z_i} \cdot a_i)^{x_i} = g^{r - \sum_{i=1}^{n} x_i z_i} \prod_{i=1}^{n} a_i^{x_i} \\ &= (g \prod_{i=1}^{n} a_i^{x_i})^{r^{-\langle x, z \rangle}} = (F.Eval(\text{msk}, x))^{r^{-\langle x, z \rangle}} \\ &= F.Eval(\text{msk}, x) \text{ iff } \langle x, z \rangle = 0. \end{align*}$$

Furthermore, when the adversary makes no query to the evaluation oracle, it can be shown that the pseudorandomness of the above construction on a challenge input $x$ where $\langle x, z \rangle \neq 0$ holds as long as $g^{r(x,z)}$ looks random for a uniformly random $r \in \mathbb{Z}_p^*$. Indeed, the constrained key owner can compute $r^{-\langle x, z \rangle} \prod_{i=1}^n a_i^{x_i}$ and knows $g, x, z$. The actual evaluation is $g \prod_{i=1}^n a_i^{x_i}$ and the constrained key reveals no information about $r$ since $a_i$ are uniformly random in $\mathbb{Z}_p^*$.

Before we move on, we make the following observations:
1. The algorithm F.CEval does not need to know z. Hence, our CPRF for inner products is also constraint-hiding.

2. We described the construction for an input and a constrain $x, z \in \{0, 1\}^n$ for simplicity, and to match with the original construction of Naor and Reingold. However, the construction extends immediately to the setting where $x, z \in [\pm B]^n$, where B is some polynomial-size bound (the security of the original Naor-Reingold construction for general inputs of this form was shown in [ABP15] to reduce to a variant of the Diffie-Hellman assumption). We then have $|\langle x, z \rangle| \le n \cdot B^2$ and assuming $n \cdot B^2 \ll q$, the inner product is again computed over the integers.

3. Eventually, we also consider a straightforward modification of the construction where both parties apply an arbitrary public preprocessing function $p(\cdot)$ on the input $x$ before feeding it into Eval or CEval. This allows to force the input $x$ to have a specific format.

**From no-evaluation security to full security.** While the above construction can be attacked if the adversary can make an evaluation query, we recall that any no-evaluation secure CPRF can be turned into an adaptively secure CPRF (with any number of evaluation queries) in the random oracle model by hashing the output, as explained [AMN$^{+18}$]. Hence, proving no-evaluation security is sufficient for our purpose.

In fact, an even simpler construction exists in the random oracle model by simply removing the group and considering only the exponents. Precisely, define the PRF output as $H(\prod_{i=1}^n a_i^{x_i})$ where $H$ is a hash function modeled as a random oracle. Next, define the constrained key as $(\alpha_1, \dots, \alpha_n)$, as in the construction above. For this CPRF, security holds unconditionally in the ROM, since the evaluation is uniform unless the adversary can compute $r^{(x,z)}$, which is hard since the adversary has no information about $r$ and it has high min-entropy (and its order is at least $q \gg n$).

While we do hash the output to obtain full security, we still rely on the above construction, instantiated with a group $\mathbb{G}$, as it comes with benefits. Indeed, we can add elements of the form $g^{r^t}$ in the constrained key which turns out to be extremely useful, as we describe below.

**From inner product to inner product membership.** Previously, we showed how the Naor-Reingold PRF can be turned into a CPRF for inner-product predicates. Yet, this class of predicates is too restricted for instantiating the PCF construction explained in Section 2.1. Our next observation is that this class can be significantly expanded by adding elements of the form $g^{r^t}$ to the constrained key to help the evaluator cancel out some $r^{-t}$ terms. Indeed, if the evaluator uses $g^{r^t}$ instead of $g$ as the basis for exponentiation, the computation of $F.CEval(ck, x)$ becomes

$$ 
\begin{aligned}
F.CEval(ck, x) &= (g^{r^t}) \prod_{i=1}^{n} (r^{-z_i} \cdot a_i)^{x_i} \\
&= (g^{r^{t-(x,z)}}) \prod_{i=1}^{n} a_i^{x_i} \\
&= (F.Eval(msk, x))^{r^{t-(x,z)}},
\end{aligned}
$$

which is the same as $F.Eval(msk, x)$ if and only if $t = \langle x, z \rangle$. What makes this observation particularly powerful is that the evaluator can be given terms of the form $g^{r^t}$ for multiple values of $t$, and choose upon evaluation the term $g^{r^t}$ where $t = \langle x, z \rangle$. This yields a CPRF for the class of predicates

$$ C_{z,S}: x \rightarrow \begin{cases} 0 & \text{if } \langle x, z \rangle \in S \\ 1 & \text{otherwise} \end{cases} $$

where $S \subseteq \mathbb{Z}_{p-1}$ is a polynomial size subset. The full construction is given below:

- $F.Constrain(msk, z, S)$ : Sample $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$. For every $t \in S$, define $g_t \leftarrow g^{r^t}$, and let $(\alpha_1, \dots, \alpha_n) \leftarrow (r^{-z_1} \cdot a_1, \dots, r^{-z_n} \cdot a_n)$. Output $ck = ((g_t)_{t \in S}, \alpha_1, \dots, \alpha_n)$.

- $F.CEval(ck, x)$ : On input $x = (x_1, \dots, x_n) \in [\pm B]^n$, let $t \leftarrow \langle x, z \rangle$. Output $g_t \prod_{i=1}^n \alpha_i^{x_i}$.

Note that our prior claim that the constrained key contains no information about $r$ does not longer hold as it now contains the extra elements $g^{r^t}$ for all $t \in S$, hence no-evaluation security is no longer unconditional. We show that this construction is (no-evaluation) secure under a variant of the Diffie-Hellman assumption which we call *sparse power-DDH assumption*. The sparse power-DDH assumption states that for a subset $S \subseteq [\ell]$, where $\ell \in \mathbb{N}$ is polynomially-bounded, given $g^{r^t}$ for various $t \in S$, it is infeasible to distinguish $g^{r^t}$ for $t \in [\ell] \setminus S$ from uniformly random group elements.
The sparse power-DDH assumption is a static falsifiable assumption (which holds unconditionally in the generic group model), and it can be viewed as a natural generalization of the power-DDH assumption (which states that given $g^{r_i}$ for $i \in \{1, \dots, n\}$, it is infeasible to distinguish $g^{r_{i+1}}$ from random).

**On IPM predicates.** The inner product membership predicate captures several predicates of interest. We already mentioned inner-product equality (in which case our CPRF is constraint-hiding), and it also captures inner-product inequality. Moreover, this class captures puncturing, which, to our knowledge, yields the first candidate puncturable pseudorandom function in the complexity class $\mathbb{NC}^1$ (assuming that the hash function is instantiated with an $\mathbb{NC}^1$ function).$^6$ Since puncturable PRFs have independent applications, for instance in the context of indistinguishability obfuscation (which is typically first built for $\mathbb{NC}^1$ before being bootstrapped to $\mathbb{P}$), we expect that this result could have other applications. Furthermore, the IPM predicates capture several variants of puncturing, such as puncturing a Hamming ball, and many more. Most importantly, and as we explain in the following section, this class of predicates captures several candidate weak pseudorandom functions from the literature, which makes it powerful enough to instantiate the PCF for OT correlation outlined in Section 2.1.

## 2.3 Inner-Product Membership Weak Pseudorandom Functions

It turns out that several candidate weak PRFs from the literature can be expressed as IPM predicates. In this section, we provide a non-exhaustive list of such constructions. Notably, we show that the BIPSW [BIP$^{+18}$] as well as the XOR-MAJ [Gol00, AL16] candidate weak PRFs fall into this category and lead to efficient instantiations of our paradigm. We write IPM-wPRF to denote a weak PRF expressed as an IPM predicate.

**The Learning-with-Rounding wPRF.** Given a modulus $q$ and a smaller modulus $q' \ll q$, the well-known candidate wPRF of [BPR12] is given by $F_z(x) = \lceil\langle x, z \rangle\rceil_{q'}$, where $x, z \in \mathbb{Z}_{q'}^n$, and $\cdot \cdot \cdot \cdot q'$ denotes an appropriate procedure for rounding to an element of $\mathbb{Z}_{q'}$. This candidate was shown in [BPR12] to be a secure wPRF under the standard LWE assumption, provided that $q, q'$ are superpolynomial. This proof was further refined in [AKPW13] to show that a polynomial-size modulus suffices for the reduction. While the proof does not extend to the case $q' = 2$, no known efficient attack is known, and the learning-with-rounding (LWR) assumption is now widely conjectured to hold even outside of the regime where it reduces to LWE. When $q$ is polynomial and $q' = 2$, we observe that it suffices to define $S$ as $S = \{s \in \mathbb{Z}_{n \cdot q^2} : \lceil(s \bmod q)\rceil_2 = 0\}$ to rewrite this wPRF as an IPM-wPRF (with $|S| \approx n \cdot q^2/2$). Due to the $q^2$ overhead in the size of $S$, for standard choices of the modulus $q$, our construction with this candidate does not yield a very efficient instantiation. However, it forms a basis for our next candidate.

**The BIPSW wPRF.** In [BIP$^{+18}$], the authors introduced several new low-complexity wPRF candidates, together with some preliminary analysis to back up the security claims. Five years later, these candidates have received some attention, both by cryptanalysts [CCKK21, JMN23] and in the context of a range of applications, from secure computation to side-channel security [DGH$^{+21}$, ADDG23, DMMS21]. As the authors observed, one of their candidates (that we denote as BIPSW) can be rephrased as an LWR-style wPRF: $F_z(x) = \lceil\langle x, z \rangle \bmod 6\rceil$, with $x, z \in \{0, 1\}^n$, and with the rounding function defined as $\lceil s \rceil = 0$ if $(s \bmod 6) \in \{0, 1, 2\}$, and $\lceil s \rceil = 1$ if $(s \bmod 6) \in \{3, 4, 5\}$. The authors initially suggested a key length $n = 384$ as a conservative choice for security. Several attacks were later shown, in [CCKK21] and very recently in [JMN23], suggesting that the key length should be increased to $n = 770$. We note that the BIPSW candidate fits particularly well in our framework: it can be written as an IPM-wPRF by defining $S = \{s \le n : \exists k \le n/6, i \in \{0, 1, 2\}, s = 6k + i\}$. The size of $S$ is $n/2$, which is as low as $|S| = 385$ for $n = 770$.

**The Goldreich-Applebaum-Raykov wPRF.** In [Gol00], Goldreich suggested an approach for building one-way functions by evaluating a fixed low-arity predicate on fixed random small subsets of the input bits (i.e., $f(x) = (P(x[S_1]), \dots, P(x[S_n]))$, where $P$ is a predicate and $S_1, \dots, S_n$ are

<footnote>$^6$ It is not too hard to build a PPRF in $\mathbb{NC}^1$ by following the blueprint of the GGM PRF [GGM84b] but using a $\lambda$-ary tree instead of a binary tree and instantiating the PRG with an $\mathbb{NC}^0$ PRG with polynomial stretch. However, such constructions are inherently limited to superpolynomial-size domains, while our construction can handle subexponential-size domains.</footnote>
fixed random subsets, also $x[S_i]$ denotes the substring of the bits of $x$ indexed by $S_i$). Later works suggested that for a suitable choice of $P$, these random local functions can also be conjectured to be a pseudorandom generator when $m > |x|$. The construction of Goldreich has ever since been featured extensively in cryptography, both by cryptanalysts [CM01, MST03, BQ09, OW14, CEMT14, ABR16, AL16, LV17, CDM$^{+}$18, AK19, OST19, Méa, YGJL21, Méa22, Üna23b, DMR23, Üna23a] and in numerous cryptographic applications such as low-complexity cryptography, secure computation, obfuscation, and many more [App12, AR16, BCG$^{+}$17, App17, JLS21] (see [App15] for a survey from 2015). In [AR16], Applebaum and Raykov showed how Goldreich's random local functions can also yield plausible candidate wPRFs for suitable choices of $P$, when $|S_i| = \Omega(\log n)$. We denote this candidate wPRF as Goldreich-Applebaum-Raykov(GAR) wPRF.

We outline how the GAR wPRF can be expressed as an IPM-wPRF. The core idea is to view the random input $x$ as an encoding of a subset $S_x \subset [n]$ of size $|S_x| = \Omega(\log n)$, and to preprocess $x$ using some fixed preprocessing function $g$ such that $\langle g(x), z \rangle = z[S_x]$. To do so, we let $|x| = \log^2(n)$ and parse $x$ as a $k = \Omega(\log(n))$-tuple of distinct indices $j_1, \dots, j_k \in [n]$ by keeping only the distinct $j$'s from the $\log(n)$ strings $j \in \{0, 1\}^{\log(n)}$ (viewed as elements of $[n]$). Then, we let $g(x)$ be the length-$n$ vector defined as follows: the vector $g(x)$ is 0 everywhere, except that it has the entry $2^{\ell-1}$ at position $j_\ell$ for $\ell = 1, \dots, k$. Observe that with this encoding, computing $\langle g(x), z \rangle$ returns $\sum_{\ell=1}^k z_{j_\ell} \cdot 2^{\ell-1}$, which is exactly the integer whose binary representation encodes the subset $S_x$ of the bits of $z$. Now, for any choice of $\log(n)$-ary predicate $P$, we define $S = \{s \in [2^k] : P(s) = 0\}$. Observe that checking whether $\langle g(x), z \rangle \in S$ is equivalent to computing $P(z[S_x])$, where $S_x$ is the $\Omega(\log n)$-sized subset defined by $x$. Hence, up to the preprocessing of the input $x$ (which is for free in our construction), the GAR wPRF can be expressed as an IPM-wPRF. As long as the arity of $P$ is $k = O(\log(n))$, we have $|S| = O(2^k) = \text{poly}(n)$.

This yields a generic construction that works for any choice of predicate with sufficiently low arity. Directly instantiating this construction does not yield a very competitive PCF. However, our next observation is that for the most standard and well-studied choices of predicate $P$, the generic construction can be considerably improved.

**The XOR-MAJ wPRF.** The previous construction works for arbitrary predicates $P$, provided that $P$ takes at most $O(\log n)$ bits as input. In this section, we observe that when $P$ is of the form $P(x_0, x_1) = \text{SYM}_0(x_0) \oplus \text{SYM}_1(x_1)$, where $\text{SYM}_0, \text{SYM}_1$ are arbitrary symmetric functions, then there exists an improved construction that handles predicates of arbitrary locality. This capture in particular the XOR-MAJ predicate, which computes the XOR between the parity of the $x_0$ input and the majority of the $x_1$ input. XOR-MAJ is probably the most common choice of predicate for the GAR wPRF, and its properties have been studied extensively [AL16, CDM$^{+}$18, Méa, YGJL21, Méa22, Üna23b, DMR23].

We briefly outline how to express the GAR wPRF with the XOR-MAJ predicate as an IPM-wPRF (the generalization to other symmetric functions is immediate). Assume that the predicate is $P = \text{XOR}_k$-MAJ$_\ell$, which takes as input a $(k + \ell)$-bit subset $z$ of the bits of the secret key, and outputs XOR$(z_1, \dots, z_k) \oplus \text{MAJ}(z_{k+1}, \dots, z_{k+\ell})$. Similarly to before, we parse a random input $x$ as an encoding of two random disjoint subsets $(S_{0,x}, S_{1,x})$ of $[n]$, of size $k$ and $\ell$ respectively. Then, we let $\text{p}(x)$ denote the length-$n$ vector with 1's at all entries indexed by $S_{1,x}$, value $\ell + 1$ at all entries indexed by $S_{0,x}$, and 0's everywhere else. Observe that this encodings yields

$$ \langle \text{p}(x), z \rangle = \text{HW}((z_i)_{i \in S_{1,x}}) + (\ell + 1) \cdot \text{HW}((z_i)_{i \in S_{0,x}}), $$

where $\text{HW}(\cdot)$ denotes the Hamming weight. Furthermore, since $|S_{1,x}| = \ell$, every integer $\langle \text{p}(x), z \rangle$ computed as above uniquely determines the pair $(\text{HW}((z_i)_{i \in S_{1,x}}), \text{HW}((z_i)_{i \in S_{0,x}}))$. In turn, symmetric functions such as XOR and MAJ are uniquely determined by the Hamming weight of their inputs (in particular, XOR($z$) returns $\text{HW}(z) \bmod 2$ and MAJ($z$) returns 1 iff $\text{HW}(z) > \ell/2$). Then, using the fact that $A \oplus B = 0$ iff $A = B$, we define $S$ as follows:

$$ S = \{s = s_1 + (\ell + 1)s_0 \in [\ell + (\ell + 1) \cdot k] : [\text{HW}(s_1) \bmod 2] = [\text{HW}(s_0) > \ell/2]\}. $$

Compared to the previous construction, this new construction is tailored to XOR-MAJ (or more generally to predicates of the form $P(x_0, x_1) = \text{SYM}_0(x_0) \oplus \text{SYM}_1(x_1)^7$). However, for a predicate of

<footnote>$^7$ even more generally, the construction can be adapted to handle the XOR of any number $N$ of symmetric predicates with respective locality $\ell_1, \dots, \ell_N$, with $|S| = O(\prod_{i=1}^N \ell_i)$</footnote>
locality $l+k$, the size of $S$ scales as $O(l \cdot k)$, which is an exponential improvement over the $2^{l+k}$ cost of the generic construction. While the GAR wPRF is typically considered in the low-locality setting, our construction allows simultaneously relying on a particularly conservative parameter setting, using XOR-MAJ with locality $O(\sqrt{n})$ (in this parameter regime, the GAR wPRF is generally conjectured to provide subexponential security $2^{O(\sqrt{n})}$), and keeping $S$ to a small size $|S| = O(n)$. Together with the BIPSW wPRF candidate, this instantiation yields the most efficient concrete instantiations of our framework. To give a single data point, using the state-of-the-art cryptanalysis on Goldreich-style local wPRFs, we can set the key length $n$ to 256 and use the XOR$_{10}$-MAJ$_{64}$ predicate to achieve 128 bits of security for up to $2^{40}$ queries to the wPRF, and have $|S| = 357$.

**Other candidates.** Before moving on, we note that several other candidate wPRFs can be shown to fit in the IPM-wPRF framework: candidates based on sparse LPN or variable-density LPN [BCG$^{+20}$], and the BFLK candidate $f_{A,B}: x \mapsto (\bigoplus_{i \in A} x_i) \oplus \text{MAJ}((x_i)_{i \in B})$ from [BFKL94]. These candidates yield less competitive instantiations of our framework, and we do not discuss them further here. However, this suggests two interesting open questions for future work:

- Finding the best-possible IPM-wPRF (i.e. the one achieving the best possible tradeoffs between security and key size + size of $S$), and

- All candidates considered in this work are weak PRFs. Whether there exists strong IPM-PRFs remains an interesting open question (though we note that any IPM-wPRF can be generically upgraded to a strong PRF when instantiating the preprocessing function $p$ with a random oracle).

## 2.4 Optimizations

The above framework can be largely improve by various optimizations. In this section, we sketch several optimizations that allow improving the performance of our PCF.

**Halving the key size.** When we instantiate the framework of Section 2.1 using our Naor-Reingold CPRF, the sender key consists of two master secret keys $(g, a_1, \dots, a_n)$ and $(h, a'_1, \dots, a'_n)$, and the receiver key for the predicate $F_{z,S}: x \mapsto \langle x, z \rangle \in? S$ consists of $(r^{-z_i} \cdot a_i)_{i \in [n]}$, $(r'^{-z_i} \cdot a'_i)_{i \in [n]}$, $(g^{r'})_{t \in S}$, and $(h^{r't})_{t \in [\pm n \cdot B^2] \setminus S}$ (where $r, r'$ are random elements of $Z_p^*$ and $B$ is a bound on the entries of $x, z$). Thanks to the random self-reducibility of DDH, the two master secret keys can actually use the same elements $(a_1, \dots, a_n)$ provided that they use different bases $g, h$. For the same reason, we can also set $r = r'$ without any security loss. This reduces the sender key size by a factor two, and significantly compresses the receiver key size as well. Concretely, we can use the following keys:

- Sender key: $(g, h, a_1, \dots, a_n)$,

- Receiver key: $(r^{-z_i} \cdot a_i)_{i \le n}, (g_t)_{t \in [\pm n \cdot B^2]}$,

where $g_t \leftarrow g^{r't}$, for $t \in S$, and $g_t \leftarrow h^{r't}$, for $t \in [\pm n \cdot B^2] \setminus S$. The resulting construction can be proven secure under the same assumptions as the basic construction.

**Reusing the $g_t$'s.** We observe that the value $z$ (which depends on the underlying PRF key used by the receiver) is only known to the receiver, while the set $S$ is public and is related to the definition of the PRF. In a multiparty setting where the sender wants to compute PCF keys with multiple receivers, we can exploit this observation to define the $g_t$'s once for all, and pass them as common parameters to be used by all receivers. This requires adding two additional terms $(a_{0,j}, a'_{0,j})$ in the sender key for each receiver $R_j$, to re-randomize the bases $g, h$. That is, the sender now computes its pseudorandom OT messages as

$$y_{0,j}^{(x)} \leftarrow g^{a_{0,j} \cdot \prod_{i=1}^{n} a_i^{x_i}}$$

$$y_{1,j}^{(x)} \leftarrow h^{a'_{0,j} \cdot \prod_{i=1}^{n} (a_i)^{x_i}},$$

where $g^{a_{0,j}}$ and $h^{a'_{0,j}}$ will play the role of fresh new bases for each receiver $R_j$ (the receiver CEval have to be adapted accordingly). With this modification, the $g_t$'s can be thought of as public parameters or rather as a kind of public key associated to the sender.

**Compressing the $a_i$'s.** When instantiating the group with a suitable elliptic curve, the size of the $a_i$'s is typically $2\lambda$ bits (to achieve $\lambda$ bits of security against generic discrete log attacks). To further reduce the key size, the $a_i$'s can be generated from a pseudorandom generator in a two-step fashion: first, the sender receives a $\lambda$-bit seed seed and computes $(g, h, \text{seed}_1, \dots, \text{seed}_n) \leftarrow \text{PRG}(\text{seed})$, where
PRG : {0, 1}^λ ↦→ {0, 1}^{(4+n)·λ} (each seed_i is in {0, 1}^λ). Second, define a_i ← PRG'(seed_i), where PRG' : {0, 1}^λ ↦→ {0, 1}^{2λ}. The advantage of this approach is that it enables compressing both the sender key and the receiver key:

- The sender key is now simply the λ-bit seed seed.

- The receiver key is still (r^{-z_i} · a_i)_{i≤n} (together with the public g_t terms), except for the indices i where z_i = 0, where it holds that r^{-z_i} · a_i = a_i. For such indices, we can send simply send seed_i, which is twice smaller. When z_i is a bit-string (which is the case for the BIPSW and XOR-MAJ wPRFs), this reduces the size of about half of the r^{z_i} · a_i to that of seed_i, resulting in a 25% reduction of the key length.

**Exploiting the structure in S.** Assume that S contains all integers s (from some bounded range {0, ..., m · R}) such that (s mod m) < m/2, where m is some fixed value; we say that S is m-antiperiodic. Then we almost get the following equivalence:

$$s \notin S \iff (s - m) \in S,$$

where the almost stems from the fact that the equivalence breaks down at the extremities: for example, s = m/2 + 1 ∉ S, yet s - m ∉ S because s - m is outside of the bounded range {0, ..., m · R}. Nevertheless, we can recover the equivalence by slightly extending S into S' = S ∪ {-m/2, ..., -1} (the equivalence becomes: for every s ∈ {0, ..., R · m}, s ∉ S' ⇐⇒ (s - m) ∈ S').

In this case, we observe that it is not necessary to include in the receiver key both (g_t)_{t∈S} and (g_t)_{t∈S}. Indeed, as we are constraining before a key msk_0 with respect to the predicate “⟨x, z⟩ ∈ S”, and a second key msk_1 with respect to the predicate “⟨x, z⟩ ∉ S”, we can then rewrite the second constraint as “⟨x, z⟩ - m ∈ S”. Concretely, we now deal a single key msk to the sender, but we add an (n + 1)-th element a_{n+1} to act as a shift. The keys become:

- Sender key: msk = (g, a_1, ..., a_n, a_{n+1})

- Receiver key: ck = (g, r^{-z_1} · a_1, ..., r^{-z_n} · a_n, r^m · a_{n+1}), (g_t)_{t∈S'}.

Given msk, on input x the sender computes their two OT inputs as y_b ← CPRF.Eval(msk, x|b) for b = 0, 1. That is, we have:

$$y_b \leftarrow g \prod_{i=1}^{n} a_i^{x_i} \cdot a_{n+1}^b \quad \text{for } b=0,1.$$

Now, thanks to the term r^{-m} · a_{n+1} in the receiver key, for every input x, there is only a single b ∈ {0, 1}^l such that ⟨x|b, z| - m⟩ ∈ S, i.e. such that ⟨x, z⟩ - b · m ∈ S'. Compared to the previous construction, this (almost) halves the number of group elements g_t in the receiver key, going from m · R to (m/2) · (R + 1).

The BIPSW wPRF and the XOR-MAJ wPRF satisfy this property: the set S is m-antiperiodic with m = 6 for BIPSW, and m = 49 for our parameter choice with XOR-MAJ. Hence, this optimization can also be applied to these two instantiations.

## 2.5 Final PCF Construction

We are now fully equipped to describe our final PCF construction. Concrete parameters for both instantiations based on the BIPSW and the XOR-MAJ are provided in the next section. Let the input domain be {0, 1}^l. Let F be an IPM-wPRF with preprocessing function p : {0, 1}^l ↦→ [0, B]^n (for some polynomial bound B), key space {0, 1}^n and associated set S; that is, given a key z ↦→ {0, 1}^n and an input x ∈ {0, 1}^l, F_z(x) outputs 1 iff ⟨p(x), z⟩ ∈ S. We assume that S is m-antiperiodic for some integer m (i.e. S = {s ∈ {0, ..., R} : s mod m < m/2} for some polynomial bound R). Define S' ← S ∪ {-m/2, ..., -1}. Fix a family of cyclic groups G = G(λ) of order p = p(λ). Let G_0 : {0, 1}^λ ↦→ Z_p^* × {0, 1}^{n·λ}, G_1 : {0, 1}^λ ↦→ Z_p^*, and G_2 : {0, 1}^λ ↦→ {0, 1}^n be three pseudorandom generators. Let H : G ↦→ {0, 1}^λ be a hash function.

- **PCF.Gen(1^λ)**: sample seed ↦→ {0, 1}^λ. let (g, seed_1, ..., seed_{n+1}) ← G_0(seed) and a_i ← G_1(seed_i) for i = 1 to n + 1. Sample seed_z ∈ {0, 1}^λ, r ↦→ Z_p^*, and let z ← G_2(seed_z). For i = 1 to n, set v_i ← seed_i if z_i = 0, and v_i ← r^{-1} · a_i, otherwise. Set v_{n+1} ↦→ r^m · a_{n+1}. Define g_t ← g^t for every t ∈ S'. Output k_0 ← seed and k_1 ← (seed_z, v_1, ..., v_{n+1}, (g_t)_{t∈S'}).
- PCF.Eval(0, $k_0$, $x$) : recompute $(g, \mathbf{seed}_1, \dots, \mathbf{seed}_{n+1}) \leftarrow G_0(k_0)$ and $a_i \leftarrow \mathbb{G}_1(\mathbf{seed}_i)$ for $i = 1$ to $n+1$. Let $(s_1, \dots, s_n) \leftarrow \mathbf{p}(x)$. Define

$$y_b \leftarrow H \left( g \prod_{i=1}^{n} a_i^{s_i} \cdot a_{n+1}^{b} \right) \text{ for } b = 0, 1.$$

Output $(y_0, y_1)$.

- PCF.Eval(1, $k_1$, $x$) : parse $k_1$ as $(\mathbf{seed}_z, v_1, \dots, v_{n+1}, (g_t)_{t \in S'})$. Let $(s_1, \dots, s_n) \leftarrow \mathbf{p}(x)$. Recompute $z \leftarrow G_2(\mathbf{seed}_z)$. For $i = 1, \dots, n+1$, set $\alpha_i \leftarrow G_1(v_i)$ if $z_i = 0$ or $i = n+1$, and $\alpha_i \leftarrow v_i$ else. Let $b \leftarrow F_z(x)$ and $t \leftarrow \langle \mathbf{p}(x), z \rangle - b \cdot m$. Note that by definition, this means that $t \in S'$. Define

$$y_b \leftarrow H \left( g \prod_{t=1}^{n} \alpha_t^{s_t} \cdot \alpha_{n+1}^{b} \right).$$

Output $(b, y_b)$.

To state our main theorem, we define the sparse power-DDH assumption with respect to $S'$. For a group $\mathbb{G}_\lambda = \langle g \rangle$ of prime order $p$, the sparse power-DDH assumption with respect to $S'$ over a support $[0, R]$ states that

$$(g, (g^{r \cdot a^i})_{i \in S'}, (g^{r \cdot a^i})_{i \in [0, R] \setminus S'}) \stackrel{c}{\approx} (g, (g^{r \cdot a^i})_{i \in S'}, (g^{t_i})_{i \in [0, R] \setminus S'}),$$

where $\stackrel{c}{\approx}$ denotes computational indistinguishability, $a, r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$, and $t_i \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$ for all $i \in [0, R] \setminus S'$. Note that the bound $R$ and the set $S'$ are fixed parameters of the construction; hence, this assumption is a static, falsifiable variant of the power-DDH assumption used in several previous works (e.g. [AMN$^{+18}$]). It can be shown to hold in the generic group model. We obtain the following theorem:

**Theorem 1 (informal).** Assuming that the sparse power-DDH assumption with respect to $S'$ holds, that $(G_0, G_1, G_2)$ are pseudorandom generators, that $F$ is a secure IPM-wPRF, and modeling $H$ as a random oracle, then the above construction is a weak pseudorandom correlation function for the oblivious transfer correlation.

Note that, in the random oracle model, the construction can be upgraded to a strong PCF by first hashing the inputs [BCG$^{+20}$] and can also be proven secure under a weaker search version of the sparse power-DH assumption.

**Distributed key generation.** A useful feature of our PCF is that it admits a very efficient two-round distributed key generation algorithm. Concretely, and borrowing the notations from the construction above, the OT sender can simply generate seed and $r$ themself, and send $(g_t)_{t \in S'}$ to the OT receiver directly, together with $v_{n+1} = r^m \cdot a_i$. Then, the OT receiver samples seed$_z$. Eventually, to obtain the missing $v_i$'s, observe that $v_i = \mathbf{seed}_i$ if $z_i = 0$, and $v_i = r^{-1} \cdot a_i$ otherwise. Therefore, the sender and the receiver simply run $n$ parallel instances of an oblivious transfer protocol, where the sender input pairs $(\mathbf{seed}_i, r \cdot a_i)$, and the receiver uses selection bits $z_i$. Security follows immediately from the security of the oblivious transfer protocol. Using a two-round OT protocol, the entire distributed key generation can be done in two rounds, and the communication boils down to $n$ parallel OTs plus sending $|S'|$ group elements.

## 2.6 Concrete Parameters

With all the above optimizations in mind, we provide two concrete instantiations of PCF for the OT correlation, using either the BIPSW wPRF candidate, or the XOR-MAJ wPRF candidate.

**Curve and exponentiations.** To estimate the runtime of our constructions, we rely mainly on the website zka.lc, which provides an extensive list of benchmarks for standard operations on various curves and over various platforms. According to the benchmarks of zka.lc, computing one exponentiation represents about 50µs of computation on one core of an AWS platform using curve25519 [Ber06]. Note that in our construction, the sender must compute two exponentiations (to compute $(y_0, y_1)$) while the receiver computes a single exponentiation. However, the two sender exponentiations use a fixed basis $g$. Hence, the exponentiations can be significantly sped up with
precomputation (in contrast, the receiver does an exponentiation with a basis $g_t$ which is chosen based on the input). In our instantiations, exponentiations will generally dominate the runtime. Using more efficient curves, such as Microsoft's FourQ curve [CL15], the exponentiation time can be reduced to about $15\mu$s on a Haswell architecture (note that the curve offers slightly less security compared to curve25519, about 122 bits instead of 128).

**Parameters with BIPSW.** For BIPSW, we used the state-of-the-art cryptanalysis from the works of [CCKK21, JMN23], and set the key length to $n = 770$, which achieves 128 bits of security according to these attacks. We note that this parameter choice ignores some significant polynomial factors in the cost estimation (that come from a nearest neighbor search), hence our parameter choice takes a bit of margin. Furthermore, the recent attack of [JMN23] has a much higher memory requirement compared to previous attack. On the other hand, we warn the reader that the BIPSW candidate is a relatively young wPRF and while a total break would be surprising at this point, the state of cryptanalysis is likely to improve over the years. With $n = 770$, $S$ is 6-antiperiodic and we have $|S'| = 388$ With this parameter choice, the precomputable PCF has the following efficiency features:

- Key size: the receiver key size is 30.2kB (and the sender key size is 16 Bytes). Out of that, 12.1kB are public parameters $(g_t)_{t \in S'}$, which the sender can reuse with other receivers.

- Computation: computing $s_b$ involves 385 multiplications over $\mathbb{Z}_p^*$, one exponentiation, and one hash. This translates to about 10k OT/s per core using curve25519 on an AWS platform, or about 15k OT/s per core using a curve such as FourQ on a Haswell architecture.

**Parameters with XOR-MAJ.** For the GAR wPRF instantiated with the XOR-MAJ predicate, we rely on the state-of-the-art cryptanalysis results from [AL16, CDM$^+$18, YGJL21, Üna23a]. Specifically, according to Table 1 of [Üna23a], for a candidate to achieve $\lambda$ bits of security with a key of length $n = \lambda^\delta$ and a bound $n^{1+e}$ on the number of queries, the underlying predicate $P$ must have

- rational degree at least $\frac{\delta}{\delta-1} \cdot e + 1$, and

- resiliency at least $2e + 1$.

A $k$-variable Boolean function $P$ has rational degree $d$ if it is the smallest integer for which there exist degree $d$ polynomials $g$ and $h$, not both zero, such that $P \cdot g = h$.<fnref n="8" /> A $k$-variate boolean function is $t$-resilient if it has no nontrivial correlation with any linear combination of at most $t$ of its inputs. We note that Table 1 of [Üna23a] ignores the guess-and-decode attack of [YGJL21], because their attack does not have a closed-form formula. However, Both the guess-and-determine attack of [CDM$^+$18] and the guess-and-decode attack of [YGJL21] are specifically targeted at predicates with a very small locality (the papers consider localities from 5 to 8), and their complexity scales very poorly for predicates with a larger locality. As we will see shortly, our candidates have considerably higher locality (e.g. 74 in our main instantiation) and after selecting them, we verified individually that they yield concrete instances which are (way) out of reach of the guess-and-determine and the guess-and-decode attacks. In the following, we therefore use the two criteria above to select our candidates.

The algebraic immunity and resiliency of the XOR-MAJ predicate have been studied in several papers. To match the above two constraints, it suffices to use the XOR$_{\ell_1}$-MAJ$_{\ell_2}$ predicate with $\ell_1 = 2 \cdot (e+1)$ and $\ell_2 = 2\delta e/(\delta-1)$. We outline below a concrete choice of parameters for illustration: set $\delta = 1.143$. This yields $\delta/(\delta-1) = 8$ and $n = \lambda^\delta = 256$ using $\lambda = 128$. We get $\ell_2 = 16e$, and $|S'| = 16e^2+33e+2$. Setting $e = 4$, the parties can generate up to $n^{1+e} = 2^{40}$ pseudorandom OTs and $|S'| = 390$. With this parameter choice, the precomputable PCF has the following efficiency features:

- Key size: the receiver key size is 18kB (and the sender key size is 16 Bytes). Out of that, 12.2kB are public parameters $(g_t)_{t \in S'}$, which the sender can reuse with other receivers.

- Computation: computing $s_b$ involves 74 multiplications over $\mathbb{Z}_p^*$, one exponentiation, and one hash. This translates to about 15k OT/s per core using curve25519 on an AWS platform, or about 40k OT/s per core using a curve such as FourQ on a Haswell architecture.

Note that other choices of parameters can yield different trade-offs, such as achieving slightly smaller key size, slightly more OTs, or slightly less computation. For example, using $\delta = 1.2858$ yields $n = 512$, $|S'| = 222$, a slightly larger key size 18.9kB, 46 multiplications instead of 74, and a bound of $2^{45}$ on the target number of OTs.

<footnote n="8">⁸ Table 1 of [Üna23a] mentions only the degree of the predicate, but strengthening the requirement to the rational degree is known to be necessary [AL16, DMR23].</footnote>
## 2.7 Public Key PCF

We finally describe a *public key PCF*. Informally, a public key PCF allows users to generate a pair of public/secret keys, and then to broadcast their public key using a single message, while storing their secret key locally. Then, any pair of users can *non-interactively* obtain a PCF key pair ($k_0, k_1$) by combining their secret key and the other party's public key.

While the distributed key generation protocol described in Section 2.5 is particularly efficient, it requires two rounds of interaction. The protocol we now describe uses a *single* round of interaction. A major advantage of such protocol is that they enable $n$ parties over a network to execute $\Omega(n^2)$ pairwise PCF key generations (to set up an OT channel between each pair of parties) using only $O(n)$ communication in total (this is similar to how non-interactive key exchange enable $n^2$ pairs of parties to agree on shared keys using $O(n)$ communication).

**A simple construction.** In our interactive protocol, sending $(g_t)_{t \in S'}$ does not require interaction: the interaction stems entirely from the OTs. We start with a protocol that replaces the two-round OT with the non-interactive OT protocol of Bellare and Micali [BM90]. The objective is, for the sender with input $r$, and the receiver with input $z_i$, to distributively generate keys $a_i \in \mathbb{Z}_p^*$ and $\alpha_i = r^{-z_i} \cdot a_i \in \mathbb{Z}_p^*$ respectively. These values can be viewed as multiplicative shares over $\mathbb{Z}_p^*$ of $r^{-z_i}$ (up to inverting $a_i$ locally). We observe that if DDH holds over (a suitable subgroup of) $\mathbb{Z}_p^*$, such multiplicative shares can be directly obtained via the Bellare-Micali protocol. Concretely, let $\mathcal{G}'$ be a suitable cyclic subgroup of $\mathbb{Z}_p^*$ where DDH is conjectured to hold, and let $(G, H)$ be two random generators of $\mathcal{G}'$. Assume that $r \in \mathcal{G}'$. The protocol simply consists in having the sender send an ElGamal encryption of $r$, while the receiver sends a Pedersen commitment to $z_i$:

- **Sender to receiver:** pick a random coin $\rho$, and sends the ElGamal ciphertext $(C_0, C_1) \leftarrow (G^{\rho}, H^{\rho} \cdot r)$.

- **Receiver to sender:** pick $n$ random coins $(\theta_1, \dots, \theta_n)$ and send the Pedersen commitments $(H_1, \dots, H_n) \leftarrow (H^{-z_i} \cdot G^{\theta_i})_{i \le n}$.

- **Output:** for $i=1$ to $n$, the sender outputs $a_i \leftarrow H_i^{\rho}$, and the receiver outputs $\alpha_i \leftarrow C_1^{-z_i} \cdot C_0^{\theta_i}$.

Observe that

$$ \alpha_i = C_1^{-z_i} \cdot C_0^{\theta_i} = G^{\rho\theta_i} \cdot H^{-\rho z_i} r^{-z_i} = a_i \cdot r^{-z_i}. $$

Furthermore, $r$ is computationally indistinguishable from a random element of $\mathcal{G}'$ under the DDH assumption over $\mathcal{G}'$, and the protocol statistically hides $z_i$.

A first downside of this protocol is that we cannot set $\mathbb{Z}_p^* = \mathcal{G}'$, since DDH is easy over $\mathbb{Z}_p^*$ (it can be broken by computing the Legendre symbol). However, assuming that $p = 2q + 1$ is a safe prime ($q$ is prime), we can set $\mathcal{G}'$ to be the subgroup $\mathbb{Q}R_p$ of quadratic residues modulo $p$, where DDH is widely conjectured to hold (for a sufficiently large $p$). This implies that the protocol generates a (pseudo)random square $r$, instead of a random element of $\mathbb{Z}_p^*$. This does not harm the security of the CPRF but changes slightly the underlying sparse power-DDH variant: using $r$ of the form $w^2$ for a (pseudo)random element $w$ when computing $g_t \leftarrow g^{r^t} = g^{w^{2t}}$ for $t \in S'$ amounts exactly to relying on the sparse power-DDH assumption with respect to the set $2 \cdot S' = \{2 \cdot t : t \in S'\}$.

A second, more concerning, downside is the size of $p$: due to subexponential-time algorithms for discrete logarithm over finite fields, $p$ should be taken much larger than 256 bits, at the very least 1024 bits. But in turn, this implies that the group $\mathcal{G}$ over which we instantiate our PCF should have order $p \ge 2^{1024}$, which considerably harms efficiency (both for key size and computation), and prevents us in particular to rely on efficient 256-bit elliptic curves. We circumvent this issue by setting $p$ to a smaller value (e.g. a 256-bit prime), and relying on Paillier encryption.

**A more efficient variant.** Assume for simplicity that $p = 2q+1$ for a prime $q$ (the construction also works fine with any large prime factor of $p-1$). At a high level, we perform the Bellare-Micali-style non-interactive protocol over a Paillier group (similarly as in [OSY21]) followed by a post-processing operation which:

- converts the multiplicative shares over the Paillier group to subtractive shares modulo $N$ (where $N$ is an RSA modulus) using a distributed discrete log algorithm,

- converts the shares modulo $N$ to shares modulo $q$ using the fact that subtractive shares modulo $N$ are with very high probability shares over $\mathbb{Z}$ when the shared value is sufficiently smaller than the modulus,
- converts the additive shares modulo $q$ into multiplicative shares over $\mathbb{Z}_p^*$ via exponentiation.

Let $QR_p$ denote the set of quadratic residues modulo $p$, which has order $q$. Let $G$ be a basis of $QR_p$. Instead of sampling $r \stackrel{\$}{\leftarrow} QR_p$ directly, Alice samples $\Delta \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and sets $r \leftarrow G^\Delta \mod p$ (this yields the same distribution). Let $N$ be a public RSA modulus, whose factorization is unknown to both parties. The protocol proceeds almost as the previous protocol, except that Alice sends a Paillier-ElGamal encryption of $\Delta$ (viewed as an integer in $\{0, \dots, q-1\}$) instead of an ElGamal encryption of $r$. Let $(G, H)$ be two random elements of $\mathbb{Z}_{N^2}$. Our protocol borrows ideas from [OSY21]. It builds upon a distributed discrete logarithm algorithm DDLOG over $\mathbb{Z}_{N^2}$, which has the following features: given respective multiplicative shares $(S^{\text{send}}, S^{\text{rec}})$ of a value $(1+N)^m$ modulo $N^2$, the sender and the receiver can locally compute $v^{\text{send}} \leftarrow \text{DDLOG}(\text{send}, S^{\text{send}})$ and $v^{\text{rec}} \leftarrow \text{DDLOG}(\text{rec}, S^{\text{rec}})$ which form subtractive shares of $m$ over $\mathbb{Z}_N$ (i.e. $v^{\text{send}} - v^{\text{rec}} = m \mod N$). Furthermore, if $m < N/2^\lambda$ (when viewed as an integer in $\{0, \dots, N-1\}$), it holds with probability at least $1-2^{-\lambda}$ that $v^{\text{send}} - v^{\text{rec}} = m \mod N$ over the integers. The work of [OSY21] described an efficient implementation of DDLOG, whose cost boils down to one inversion and one multiplication over $\mathbb{Z}_N$. Given this procedure, our protocol proceeds as follows:

- **Sender to receiver:** pick a random coin $\rho$, and sends the Paillier-ElGamal ciphertext $(C_0, C_1) \leftarrow (G^\rho \mod N, H^\rho \cdot (1+N)^\Delta \mod N^2)$.

- **Receiver to sender:** pick $n$ random coins $(\theta_1, \dots, \theta_n)$ and send the Pedersen commitments $(H_1, \dots, H_n) \leftarrow (H^{z_i} \cdot G^{\theta_i} \mod N^2)_{i \le n}$.

- **Output:** for $i=1$ to $n$, the sender computes $G_i^{\text{send}} \leftarrow H_i^\rho$, and the receiver computes $G_i^{\text{rec}} \leftarrow C_1^{z_i} \cdot C_0^{\theta_i}$. Observe that

$$G_i^{\text{rec}} = C_1^{z_i} \cdot C_0^{\theta_i} = G^{\rho\theta_i} \cdot H^{\rho z_i} (1+N)^{\Delta z_i} = G_i^{\text{send}} \cdot (1+N)^{\Delta z_i} \mod N^2.$$

Using DDLOG, both parties locally compute values $(v_i^{\text{send}}, v_i^{\text{rec}})$ such that $v_i^{\text{send}} - v_i^{\text{rec}} = b \cdot \Delta \mod N$. Furthermore, assuming that $q < N/2^\lambda$,<fnref n="9" /> it holds that $v_i^{\text{send}} - v_i^{\text{rec}} = b \cdot \Delta$ over $\mathbb{Z}$ with probability at least $1-1/2^\lambda$. Eventually, the sender outputs $a_i \leftarrow G^{v_i^{\text{send}}}$ and the receiver outputs $\alpha_i \leftarrow G^{v_i^{\text{rec}}}$. Observe that

$$a_i = G^{v_i^{\text{send}}} = G^{v_i^{\text{rec}} + b \cdot \Delta} = \alpha_i \cdot r^b \mod p.$$

**A balancing optimization.** We note that in the above protocol, the size of the public keys is quite unbalanced: the sender public key contains a single Paillier-ElGamal ciphertext (in addition to $(g_t)_{t \in S'}$), while the receiver public key contains $n$ Pedersen commitments over $\mathbb{Z}_{N^2}$ (where $n$ is the wPRF key length, e.g. $n=256$ for our XOR-MAJ candidate, or $n=770$ for our BIPSW candidate). We now describe an optimization which reduces the receiver key size by a factor $k$, at the cost of increasing the Paillier-ElGamal ciphertext by a factor $k^2$. Taking $k = O(n^{1/3})$, this yields a variant in which both public keys contain $O(n^{2/3})$ elements of $\mathbb{Z}_{N^2}$. We note that our balancing optimization also applies to the public key PCF of [OSY21], thus enables reducing their public key size to $O(n^{2/3})$.

The main idea of the optimization is to compress the receiver public key by replacing the Pedersen commitments with a multi-Pedersen commitment. Fix a compression parameter $k$ (which we assume to divide $n$ for simplicity) and public random elements $(G, H_1, \dots, H_k) \in \mathbb{Z}_{N^2}^{k+1}$. We let the sender commits to $z$ by batches of $k$ values $z_i$ at once, as follows:

- **Receiver to sender:** pick $n/k$ random coins $(\theta_1, \dots, \theta_{n/k})$ and send the Pedersen commitments $(H_1, \dots, H_{n/k}) \leftarrow (G^{\theta_{i+1}} \cdot \prod_{j=1}^k H_j^{z_{j+1}} \mod N^2)_{0 \le i < n/k}$.

Suppose the parties want to retrieve multiplicative shares of $(1+N)^{\Delta \cdot z_i} \mod N^2$. The main observation is that this can be done using the randomness-reuse variant of Paillier-ElGamal, putting $(1+N)^\Delta$ in the first “slot”: the sender picks a random coin $\rho_1$ and computes

$$(C_0, (C_1^j)_{j \le k}) \leftarrow (G^{\rho_1} \mod N, H_1^{\rho_1} \cdot (1+N)^\Delta, H_2^{\rho_1}, \dots, H_k^{\rho_1} \mod N^2).$$

Then, given this extended ciphertext and $H_1 = G^{\theta_1} \cdot \prod_{j=1}^k H_j^{z_j} \mod N^2$, the parties retrieve multiplicative shares of $(1+N)^{\Delta \cdot z_1}$ by computing

$$G_1^{\text{send}} \leftarrow H_1^{\rho_1},$$

$$G_1^{\text{rec}} \leftarrow C_0^{\theta_1} \cdot \prod_{j \le k} (C_1^j)^{z_j}.$$

<footnote n="9">⁹ In practice, we take $\log q = 256$ and $\log N = 3072$.</footnote>
The above only yields shares of $(1+N)^{\Delta \cdot z_1}$. To extract shares of $(1+N)^{\Delta \cdot z_j}$ for $j = 2, \dots, k$, the sender must proceed similarly as above, using extended Paillier-ElGamal ciphertexts, but this time placing $(1+N)^\Delta$ in the $j$-th slot. In total, the sender computes $k$ length-$(k+1)$ extended ciphertexts, for a total of $k$ elements of $\mathbb{Z}_N$ and $k^2$ elements of $\mathbb{Z}_{N^2}$ (these $k + k^2$ elements can be reused across all $n/k$ batches). The full sender public key is given below:

- **Sender to receiver:** pick random coins $\rho_j$ for $j = 1$ to $k$, and constructs the extended Paillier-ElGamal ciphertexts as follows for $j = 1$ to $k$:

$$C_0^j \leftarrow \mathbf{G}^{\rho_j} \bmod N \\ (C_1^{j,1}, \dots, C_1^{j,k}) \leftarrow (\mathbf{H}_1^{\rho_j}, \dots, \mathbf{H}_j^{\rho_j} \cdot (1+N)^\Delta, \dots, \mathbf{H}_k^{\rho_j}) \bmod N^2$$

**Efficiency.** Without the balancing optimization, the public key of the sender consists in $|S'|$ elements of $\mathbb{G}$, one element of $\mathbb{Z}_N$, and one element of $\mathbb{Z}_{N^2}$, and the public key of the receiver consists in $n$ elements of $\mathbb{Z}_{N^2}$. To provide concrete estimates, we use our XOR-MAJ parameter set with $n = 256$ and $|S'| = 390$. We set $\lambda = 128$, $\log |\mathbb{G}| = 2\lambda$, and $\log N = 3072$. With these parameters, the sender public key size is 13.3kB, and the receiver public key size is 192kB. Using the balancing optimization, the public key of the sender consists in $|S'|$ elements of $\mathbb{G}$, $k$ element of $\mathbb{Z}_N$, and $k^2$ element of $\mathbb{Z}_{N^2}$, and the public key of the receiver consists in $n/k$ elements of $\mathbb{Z}_{N^2}$. With the XOR-MAJ parameter set and using $k = 5$, the sender key increases to 32.8kB while the receiver key is reduced to 38.4kB.

Regarding computation, the cost of deriving the PCF keys from the public and secret keys is dominated by $n+1$ exponentiations modulo $N^2$ and $n$ exponentiations modulo $p$ for the sender, and $2n$ exponentiations modulo $N^2$ and $n$ exponentiations modulo $p$ for the receiver. Using the balancing optimization, the number of exponentiations modulo $N^2$ increases to $n+k^2$ for the sender, and decreases to $n \cdot (1+1/k)$ for the receiver. Using $n = 256$ and $k = 5$, this translates to respectively 281 and 307 exponentiations over $\mathbb{Z}_{N^2}$.

Using $\log N = 3072$, an exponentiation modulo $N^2$ takes of the order of 5ms on one core a standard laptop, which translates to $1 \sim 2$ seconds of computation (note that this is a rough back-of-the-envelope estimation, true estimates may vary). Observe that this can be easily sped up using multiple cores, and that this is a one-time preprocessing phase to generate the shared PCF keys. After generating the PCF keys once for all, the parties can directly start generating OT correlations. Furthermore, the computational efficiency can be significantly improved by sampling $\rho$ and the $\theta_i$'s as 256-bit integers. This improves computation by one to two orders of magnitude, at the (reasonable) cost of having to assume the security of the small-exponent indistinguishability assumption (see e.g. [CC18, CKLR21] for discussions on this assumption and relations to other assumptions).

## 2.8 Application: A simple reusable DV-NIZK reusable

As a final contribution, we provide a way to use our PK-PCF in order to construct *reusable DV-NIZKs* from three ingredients: (1) A $\Sigma$-protocol [CDS94] with 1-bit challenges for an NP-complete language $\mathcal{L}$, for example Blum's protocol for graph Hamiltonicity [Blu86], (2) a public key PCF for OT correlation where the key evaluation of each party can be *silently* obtained from their own secret key and public key of the other, and (3) a *non-reusable DV-NIZK* with computational adaptive soundness knowledge and adaptive zero-knowledge properties. Note that this last ingredient can be constructed from public-key encryption and $\lambda$ invocations of $\Sigma$-protocol [PsV06].

The main idea behind our construction is the following. The designated verifier samples a PCF key pair $(\mathbf{sk}_V, \mathbf{pk}_V)$ and outputs a CRS containing their public key. A prover with statement $x$ and witness $w$ can then sample their own PCF key pair $(\mathbf{sk}_P, \mathbf{pk}_P)$ to produce a shared evaluation key with the designated prover. It then runs the $\Sigma$-protocol by computing a first message $a$. The challenge being binary, there are 2 possible third message for a transcript starting with $a$. We let $z_b$ the third message for challenge $b \in \{0,1\}$. Doing this $\lambda$-times lead to $2\lambda$ triplets $(a_i, b, z_{i,b})_{i \in [\lambda], b \in \{0,1\}}$. The prover then uses their PCF evaluation key to compute $2\lambda$ pseudorandom masks $r_{i,b}$ by evaluating the PCF on input $x|a|b$ (or $H(x|a|b)$ if the PCF is only weakly-secure). The prover finally outputs $\mathbf{pk}_P$, $(a_i, z_{i,0} \oplus r_{i,0}, z_{i,1} \oplus r_{i,1})$ as their proof.

The correctness of the PCF and $\Sigma$-protocol guarantee that the designated verifier can recover 1 mask out of each pair $(r_{i,0}, r_{i,1})$ and then can verify $\lambda$-transcripts, while security guarantees that the prover cannot predict which of the two is recovered by the verifier and that the non-revealed
$r_{i,b}$ is pseudorandom, therefore providing soundness and zero-knowledge. A minor issue remains: one needs to prevent the prover to sample maliciously their PCF key pair such that it can predict the challenge bit. We show that it is sufficient to require the prover to additionally provide a proof (using a non-reusable DV-NIZK) that their PCF public key was generated from a honest execution of the PCF key generation algorithm (with possibly bad randomness).

## 3 Preliminaries

We use $\lambda$ to denote the security parameter. For a natural integer $n \in \mathbb{N}$, the set $\{1, \dots, n\}$ is denoted by $[n]$. We mostly use bold lowercase letters (e.g., $\mathbf{r}$) to denote vectors. For a vector $\mathbf{r} = (r_1, \dots, r_n)$, the vector $(g^{r_1}, \dots, g^{r_n})$ is sometimes denoted by $g^{\mathbf{r}}$. We write $\text{poly}(\lambda)$ to denote an arbitrary polynomial function. We denote by $\text{negl}(\lambda)$ a negligible function in $\lambda$, and PPT stands for probabilistic polynomial-time. For a finite set $S$, we write $x \stackrel{\$}{\leftarrow} S$ to denote that $x$ is sampled uniformly at random from $S$. For an algorithm $\mathcal{A}$, we denote by $y \leftarrow \mathcal{A}(x)$ the output $y$ after running $\mathcal{A}$ on input $x$. We consider $\text{GenPar}$ as a PPT algorithm that on input $1^{\lambda}$ for $\lambda \in \mathbb{N}$, outputs $(\mathbb{G}, g, p)$, where $\mathbb{G}$ is a cyclic group of prime order $p$ generated by $g$.

### 3.1 Pseudorandom Functions

**Definition 1 (Weak) Pseudorandom Function (wPRF, PRF), [GGM84a, NR95]**. Let $\lambda \in \mathbb{N}$ be a security parameter. A (weak) pseudorandom function with domain $\mathcal{X} = \{\mathcal{X}_{\lambda}\}_{\lambda \in \mathbb{N}}$, key space $\mathcal{K} = \{\mathcal{K}_{\lambda}\}_{\lambda \in \mathbb{N}}$, and range $\mathcal{Y} = \{\mathcal{Y}_{\lambda}\}_{\lambda \in \mathbb{N}}$, consists of the following two polynomial-time algorithms:

* $\text{KeyGen}(1^{\lambda}) \to (\text{msk})$: A probabilistic algorithm that on input the security parameter $\lambda$, outputs a master secret key $\text{msk} \in \mathcal{K}$.

* $\text{Eval}(\text{msk}, x) \to y$: A deterministic algorithm that on input the master secret key $\text{msk}$, and an input value $x \in \mathcal{X}$, outputs a value $y \in \mathcal{Y}$.

We say that the pair $(\text{KeyGen}, \text{Eval})$ is a

- **pseudorandom function (PRF)** if for any PPT adversary $\mathcal{A}$, it holds that

$$ \left| \Pr \left[ \mathcal{A}^{\text{Eval}(\text{msk}, \cdot)}(1^{\lambda}) = 1 \middle| \text{msk} \stackrel{\$}{\leftarrow} \text{KeyGen}(1^{\lambda}) \right] - \Pr \left[ \mathcal{A}^{\text{RF}(\cdot)}(1^{\lambda}) = 1 \middle| \text{RF} \stackrel{\$}{\leftarrow} \mathcal{F} \right] \right| = \text{negl}(\lambda), $$

where $\mathcal{F}$ is the set of all functions with domain $\mathcal{X}$ and range $\mathcal{Y}$.

- **weak pseudorandom function (wPRF)** if for any PPT adversary $\mathcal{A}$ and any polynomially bounded number $Q \in \mathbb{N}$, it holds that

$$ \left\{ \left( (x_i, \text{Eval}(\text{msk}, x_i))_{i \in [Q]} \right) \middle| \begin{array}{l} \text{msk} \stackrel{\$}{\leftarrow} \text{KeyGen}(1^{\lambda}) \\ \forall i \in [Q] : x_i \stackrel{\$}{\leftarrow} \mathcal{X} \end{array} \right\} \approx_c \left\{ \left( (x_i, y_i)_{i \in [Q]} \right) \middle| \begin{array}{l} \forall i \in [Q] : \\ x_i \stackrel{\$}{\leftarrow} \mathcal{X}, y_i \stackrel{\$}{\leftarrow} \mathcal{Y} \end{array} \right\}. $$

### 3.2 Constrained Pseudorandom Functions

**Definition 2 (Constrained Pseudorandom Functions).** Let $\lambda$ be a security parameter. A Constrained Pseudorandom Function (CPRF) with domain $\mathcal{X} = \{\mathcal{X}_{\lambda}\}_{\lambda \in \mathbb{N}}$, key space $\mathcal{K} = \{\mathcal{K}_{\lambda}\}_{\lambda \in \mathbb{N}}$, and range $\mathcal{Y} = \{\mathcal{Y}_{\lambda}\}_{\lambda \in \mathbb{N}}$, that supports a class of circuits $\mathcal{C} = \{\mathcal{C}_{\lambda}\}_{\lambda \in \mathbb{N}}$, where each $\mathcal{C}_{\lambda} \in \mathcal{C}_{\lambda}$ has domain $\mathcal{X}_{\lambda}$ and range $\{0, 1\}$, consists of the following four polynomial-time algorithms:<fnref n="10" />

* $\text{KeyGen}(1^{\lambda}) \to (\text{pp}, \text{msk})$: The master key generation algorithm is a probabilistic algorithm that on input the security parameter $\lambda$, outputs a public parameter $\text{pp}$ and a master secret key $\text{msk} \in \mathcal{K}$.

* $\text{Eval}(\text{pp}, \text{msk}, x) \to y$: The evaluation algorithm is a deterministic algorithm that on input the public parameter $\text{pp}$, the master secret key $\text{msk}$, and an input $x \in \mathcal{X}$, outputs a value $y \in \mathcal{Y}$.

<footnote n="10">¹⁰ In the rest of the paper, we drop the subscript $\lambda$ when it is clear from context.</footnote>
*   **Constrain(msk, C) → ck<sub>C</sub>:** The constrained key generation algorithm is a probabilistic algorithm that on input the master secret key msk, and a circuit C ∈ C, outputs a constrained key ck<sub>C</sub>.

*   **CEval(pp, ck<sub>C</sub>, x) → y:** The constrained evaluation algorithm is a deterministic algorithm that on input the public parameter pp, a constrained key ck<sub>C</sub>, and an input x ∈ X, outputs a value y ∈ Y.

**Correctness.** For any security parameter λ, any constrain C ∈ C, and any input x ∈ X such that C(x) = 0, we have:

$$ \Pr \left[ \begin{array}{l} \text{Eval(pp, msk, x)} \neq \text{CEval(pp, ck}_C, x): \begin{array}{l} \text{msk} \leftarrow \text{KeyGen(pp)} \\ \text{ck}_C \leftarrow \text{Constrain(msk, C)} \end{array} \right] \leq \text{negl}(\lambda). \end{array} \right. $$

**1-Key Selective Security.** We say that a CPRF is 1-key selectively secure if the advantage of any PPT adversary A in the following game is negligible:

- **Setup:** The challenger runs (pp, msk) ← KeyGen(1<sup>λ</sup>), initializes a set S<sub>eval</sub> = ∅, and chooses a random bit b <sub>0</sub> = {0, 1}. It then sends pp to A.

- **Selective Choice of Constraint:** The adversary chooses a (single) circuit C ∈ C and sends it to the challenger.

- **Constrained Key Generation:** The challenger computes ck<sub>C</sub> ← Constrain(msk, C) and returns the constrained key ck<sub>C</sub> to A.

- **Pre-Challenge Evaluation Queries:** A can adaptively send arbitrary input values x ∈ X to the challenger. The challenger computes y ← Eval(pp, msk, x) and returns y to A. It also updates S<sub>eval</sub> ← S<sub>eval</sub> ∪ {x}.

- **Challenge Phase:** A sends an input x* ∈ X as its challenge query to the challenger with the restriction that x* /∈ S<sub>eval</sub> and C(x*) ≠ 0. If it holds that b = 0, then the challenger computes y* ← Eval(pp, msk, x*). Otherwise, if b = 1, the challenger samples a random value y* <sub>Y</sub> = Y. Finally, the challenger returns y* to A.

- **Post-Challenge Evaluation Queries:** A continues the queries as before, with the restriction that it cannot query x* as an evaluation query.

- **Guess:** A outputs a bit b' ∈ {0, 1}.

**1-Key Selective Constraint-Hiding.** We say that a CPRF is selectively 1-key constraint-hiding if the advantage of any PPT adversary A in the following game is negligible:

- **Setup:** The challenger runs (pp, msk) ← KeyGen(1<sup>λ</sup>), and chooses a random bit b <sub>0</sub> = {0, 1}. It then sends pp to A.

- **Selective Choice of Constraint:** The adversary chooses a (single) pair of circuits (C<sub>0</sub>, C<sub>1</sub>) ∈ C and sends the pair to the challenger.

- **Constrained Key Generation:** The challenger computes ck<sub>b</sub> ← Constrain(msk, C<sub>b</sub>), and returns ck<sub>b</sub> to A.

- **Evaluation Queries:** A can query the output of the evaluation algorithm on arbitrary inputs x ∈ X, with the restriction that C<sub>0</sub>(x) = C<sub>1</sub>(x). On such inputs, the challenger computes and returns y ← Eval(pp, msk, x) to A.

- **Guess:** A outputs a bit b' ∈ {0, 1}.

In both of the games described above, A wins if b' = b. We also define the advantage of A in winning a game as |2 · Pr[A wins] − 1|, where the probability is over the internal coins of A and the challenger.

**No-Evaluation Security.** 1-key selective no-evaluation security (resp. 1-key selective no-evaluation constraint-hiding) is defined similarly with the extra restriction that the adversary cannot issue any pre-challenge or post-challenge query (resp. any evaluation query).

### 3.3 Reverse-Sampleable Correlations

**Definition 3 (Reverse-Sampleable Correlation).** Let 1 ≤ ℓ<sub>0</sub>(λ), ℓ<sub>1</sub>(λ) ≤ poly(λ) be output-length functions. Let Y be a probabilistic algorithm that, on input 1<sup>λ</sup>, returns a pair of outputs (y<sub>0</sub>, y<sub>1</sub>) ∈ {0, 1}<sup>ℓ<sub>0</sub>(λ) × {0, 1}<sup>ℓ<sub>1</sub>(λ)</sup> defining a correlation on the outputs.
We say that $\mathcal{Y}$ defines a reverse-sampleable correlation if there exists a probabilistic polynomial time algorithm RSample which takes as input $1^{\lambda}$, $\sigma \in \{0, 1\}$, and $y_{\sigma} \in \{0, 1\}^{\ell_{\sigma}(\lambda)}$, and outputs $y_{1-\lambda}^{\ell_{1-\sigma}(\lambda)}$, such that for all $\sigma \in \{0, 1\}$ the following distributions are statistically close:

$$ \{(y_0, y_1) : (y_0, y_1) \stackrel{\$}{\leftarrow} \mathcal{Y}(1^{\lambda})\} \text{ and } \{(y_0, y_1) : (y'_0, y'_1) \stackrel{\$}{\leftarrow} \mathcal{Y}(1^{\lambda}), y_{\sigma} \leftarrow y'_{\sigma}, y_{1-\sigma} \leftarrow \text{RSample}(1^{\lambda}, \sigma, y_{\sigma})\}. $$

**Definition 4 (OT Correlation).** A (1-out-of-2, bit) OT correlation can be defined as being sampled as a pair $((r_0, r_1), (b, r_b))$, where $r_0, r_1, b \stackrel{\$}{\leftarrow} \{0, 1\}$.

**Remark 1 (An OT Correlation is Reverse-Sampleable).** A (1-out-of-2, bit) OT correlation is reverse-sampleable. Indeed, observe that the reverse-sampling can be performed as follows. RSample(1$^{\sigma}$, $\sigma$, $y_{\sigma}$) : If $\sigma = 0$, parse $y_{\sigma}$ as $y_{\sigma} = (r_0, r_1)$, sample $b \stackrel{\$}{\leftarrow} \{0, 1\}$, and output $(b, r_b)$; otherwise (i.e. if $\sigma = 1$) parse $y_{\sigma}$ as $y_{\sigma} = (b, r)$, sample $r' \stackrel{\$}{\leftarrow} \{0, 1\}$, and output $((1-b) \cdot r + b \cdot r', b \cdot r + (1-b) \cdot r')$.

## 3.4 Pseudorandom Correlation Functions

At a high level, a pseudorandom correlation function (PCF) compresses, in short correlated keys, (superpolynomially large) correlated pseudorandom strings for some ideal correlation, e.g. strings of Beaver triples [Bea92]$^{11}$. For instance, a key owner can evaluate the PCF at position $i$ to recover its share of the $i^{th}$ Beaver triple.

We consider two different flavours of PCFs: weak PCFs (wPCF) and strong PCFs (sPCF). Analogously to PRFs, wPCFs guarantee security given access only to evaluations on uniformly random and independent inputs, while sPCFs guarantee security even for adaptively chosen inputs. Note that contrary to PRFs, the PCF literature treats weak PCFs as the default notion.

For technical reasons, and in order to provide a meaningful definition of PCF for infinite families of finite correlations, we only consider reverse sampleable correlations (Definition 3). We refer to [BCG$^{+}$20, Section 4] for more details.

**Weak Pseudorandom Correlation Functions (wPCF).** We start by defining the notion of a weak pseudorandom correlation function.

**Definition 5 (Weak) Pseudorandom Correlation Function (wPCF), [BCG$^{+}$20, Definition 4.3].** Let $\mathcal{Y}$ be a reverse-sampleable correlation with output length functions $\ell_0(\lambda)$, $\ell_1(\lambda)$ and let $\lambda \le n(\lambda) \le \text{poly}(\lambda)$ be an input length function. Let (wPCF.Gen, wPCF.Eval) be a pair of algorithms with the following syntax:

- wPCF.Gen(1$^{\lambda}$) is a probabilistic polynomial time algorithm that on input $1^{\lambda}$, outputs a pair of keys $(k_0, k_1)$; we assume that $\lambda$ can be inferred from the keys.

- wPCF.Eval($\sigma$, $k_{\sigma}$, $x$) is a deterministic polynomial time algorithm that on input $\sigma \in \{0, 1\}$, key $k_{\sigma}$ and input value $x \in \{0, 1\}^{n(\lambda)}$, outputs a value $y_{\sigma} \in \{0, 1\}^{\ell_{\sigma}(\lambda)}$.

We say that (wPCF.Gen, wPCF.Eval) is a pseudorandom correlation function (PCF) for $\mathcal{Y}$, if the following conditions hold:

- **(Weakly) pseudorandom $\mathcal{Y}$-correlated outputs.** For every non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$, it holds that for all sufficiently large $\lambda$,

$$ | \Pr[\text{Exp}_{A,N,0}^{w-pr}(\lambda) = 1] - \Pr[\text{Exp}_{A,N,1}^{w-pr}(\lambda) = 1] | \le \epsilon(\lambda) $$

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

<footnote>$^{11}$ Recall that a Beaver triple is a triplet additive shares ([a], [b], [c]) where $a, b \stackrel{\$}{\leftarrow} \mathcal{R}$ for some ring $\mathcal{R}$, and $c = ab$.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. (Weakly) Pseudorandom $\mathcal{Y}$-correlated outputs of a (w)PCF.</figcaption></figure>

- **Security.** For every $\sigma \in \{0, 1\}$ and every non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$, it holds that for all sufficiently large $\lambda$,

$$| \Pr[\mathrm{Exp}_{\mathcal{A},N,\sigma,0}^{\mathrm{w-sec}}(\lambda) = 1] - \Pr[\mathrm{Exp}_{\mathcal{A},N,\sigma,1}^{\mathrm{w-sec}}(\lambda) = 1] | \le \epsilon(\lambda)$$

where $\mathrm{Exp}_{\mathcal{A},N,\sigma,b}^{\mathrm{w-sec}}(b \in \{0,1\})$ is defined as in Figure 2. In particular, the adversary is given access to $N(\lambda)$ samples (or simply $N$ if there is no ambiguity).

<figure><img src="image_3.png" /><figcaption>Fig. 2. Security of a wPCF. $\mathrm{RSample}$ is the algorithm for reverse sampling $\mathcal{Y}$ as in Definition 3.</figcaption></figure>

**Strong Pseudorandom Correlation Functions.** A strong PCF is syntactically defined in the same way as a weak PCF, but it instead satisfies stronger notions of pseudorandom $\mathcal{Y}$-correlated outputs and PCF security. For simplicity, we only provide these modified properties.

We say that $(\mathrm{sPCF}.\mathrm{Gen}, \mathrm{sPCF}.\mathrm{Eval})$ is an $(N, B, \epsilon)$-secure strong pseudorandom correlation function $(\mathrm{sPCF})$ for $\mathcal{Y}$, if the following conditions hold:

- **Strongly pseudorandom $\mathcal{Y}$-correlated outputs.** For every non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$ asking at most $N(\lambda)$ queries to the oracle $\mathcal{O}_b(\cdot)$ (as defined in Figure 3), it holds that for all sufficiently large $\lambda$,

$$| \Pr[\mathrm{Exp}_{\mathcal{A},0}^{\mathrm{s-pr}}(\lambda) = 1] - \Pr[\mathrm{Exp}_{\mathcal{A},1}^{\mathrm{s-pr}}(\lambda) = 1] | \le \epsilon(\lambda)$$
where $\mathrm{Exp}_{\mathcal{A},b}^{s-pr}$ ($b \in \{0,1\}$) is defined as in Figure 3.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Strongly Pseudorandom $\mathcal{Y}$-correlated outputs of a sPCF.</figcaption></figure>

- **Strong Security.** For every $\sigma \in \{0,1\}$ and every non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$ asking at most $N(\lambda)$ queries to the oracle $\mathcal{O}_b(\cdot)$ (as defined in Figure 4), it holds that for all sufficiently large $\lambda$,

$$| \Pr[\mathrm{Exp}_{\mathcal{A},0,\sigma}^{s-sec}(\lambda) = 1] - \Pr[\mathrm{Exp}_{\mathcal{A},1,\sigma}^{s-sec}(\lambda) = 1] | \le \epsilon(\lambda)$$

where $\mathrm{Exp}_{\mathcal{A},\sigma}^{s-sec}$ is defined as in Figure 4.

<figure><img src="image_5.png" /><figcaption>Fig. 4. Security of a strong PCF. Here, $\mathrm{RSample}$ is the algorithm for reverse sampling $\mathcal{Y}$ as in Definition 3.</figcaption></figure>

At a high level, a PCF is *precomputable* if the first party's key can be generated first, and the second key can be derived from the first.

**Definition 6 (Precomputable Pseudorandom Correlation Function, [CMPR23]).** Let $\mathcal{Y}$ be a reverse-sampleable correlation with output lengths $\ell_0(\lambda)$, $\ell_1(\lambda)$ and let $\lambda \le n(\lambda) \le \mathrm{poly}(\lambda)$ be its input length. We say that a pseudorandom correlation function ($\mathrm{PCF}.\mathrm{Gen}$, $\mathrm{PCF}.\mathrm{Eval}$) is *precomputable* if the description of $\mathrm{PCF}.\mathrm{Gen}$ contains the descriptions of two algorithms ($\mathrm{PCF}.\mathrm{Gen}_0$, $\mathrm{PCF}.\mathrm{Gen}_1$) such that
* PCF.Gen<sub>0</sub>(1<sup>λ</sup>): On input the security parameter λ, returns a key k<sub>0</sub> and auxiliary output aux.

* PCF.Gen<sub>1</sub>(1<sup>λ</sup>, aux): On input the security parameter λ and an auxiliary input aux, outputs a key k<sub>1</sub>.

We also require the following property to hold:

**Precomputability.** For any security parameter λ ∈ $\mathbb{N}$, the two following distributions are computationally indistinguishable:

$$ \{(k_0, k_1) : (k_0, k_1) \leftarrow \text{PCF.Gen}(1^\lambda)\} \stackrel{c}{\approx} \{(k_0, k_1) : \begin{array}{l} (k_0, \text{aux}) \leftarrow \text{PCF.Gen}_0(1^\lambda) \\ k_1 \leftarrow \text{PCF.Gen}_1(1^\lambda, \text{aux}) \end{array} \}. $$

## 3.5 NIZKs

A non-interactive argument for $\mathcal{R}$ is a tuple of three probabilistic polynomial time interactive algorithms $\Pi = (\text{Setup}, \text{P}, \text{V})$ called the common reference string generator, the prover, and the verifier with the following properties:

- $\text{Setup}(1^\lambda)$. On input 1<sup>λ</sup> generates public parameters par (such as group parameters), a crs, and a trapdoor $\mathcal{T}$. For simplicity of notation, we assume that any group parameters are implicitly included in the crs.

- $\text{P}(\text{crs}, x, w)$. On input of a crs, a statement x with witness w, outputs a proof π for x ∈ $\mathcal{L}$.

- $\text{V}(\text{crs}, x, \pi, \mathcal{T})$. On input of a crs, a statement, a proof, and a trapdoor, accepts or rejects the proof.

which satisfies the completeness, soundness, and zero-knowledge properties defined below.

If the trapdoor $\mathcal{T}$ of the non-interactive proof system is set to ⊥ (or, alternatively, if it is included in the crs), we call the argument system *publicly verifiable*. Otherwise, we call it a *designated-verifier* non-interactive argument system. If the soundness guarantee holds with respect to a computationally unbounded adversary, we have a NIZK-proof system.

**Definition 7 (Perfect completeness).** A proof system $\Pi = (\text{Gen}, \text{P}, \text{V})$ for $\mathcal{R}$ is perfectly complete, if

$$ \Pr \left[ V(\text{crs}, x, \pi, \mathcal{T}) = 1 \mid \begin{array}{l} (\text{crs}, \mathcal{T}) \leftarrow \text{Setup}(1^{\lambda}) \\ (x, w) \in \mathcal{R}, \pi \stackrel{\$}{\leftarrow} \text{P}(\text{crs}, x, w) \end{array} \right] = 1 $$

The soundness notion can be divided into *non-adaptive* and *adaptive*; it is non-adaptive if the malicious prover needs to choose the statement x before generating the crs while it is adaptive if the adversary can dynamically choose the statement after generating crs. We consider a strong variant of adaptive soundness, denoted *unbounded adaptive soundness*, where the adversary is given oracle access to a verification oracle. Note that in the publicly-verifiable setting, this is equivalent to the standard soundness notion (computational soundness), where the adversary must forge valid proof on an incorrect statement without the help of any oracle. However, in the designated-verifier setting, the standard soundness notion only guarantees that the argument system remains sound as long as the prover receives at most logarithmically responses on previous proofs. On the other hand, if the argument system satisfies unbounded soundness (*reusable soundness*), its soundness is maintained even if the adversary receives an arbitrary (polynomial) number of responses on previous proofs.

**Definition 8 (Unbounded adaptive soundness).** A proof system $\Pi$ is unbounded adaptive soundness if for every PPT adversary $\mathcal{A}$

$$ \Pr \left[ \begin{array}{l} V(\text{crs}, x, \pi, \mathcal{T}) = 1 \\ x \notin \mathcal{L} \end{array} \mid \begin{array}{l} (\text{crs}, \mathcal{T}) \leftarrow \text{Setup}(1^{\lambda}) \\ (x, \pi) \leftarrow \mathcal{A}^{\mathcal{O}(\text{crs}, \dots, \mathcal{T})}(\text{crs}) \end{array} \right] = \text{negl}(\lambda) $$

where $\mathcal{A}$ can make polynomially many queries to an oracle $\mathcal{O}(\text{crs}, \dots, \mathcal{T})$ which, on input $(x, \pi)$, outputs $V(\text{crs}, x, \pi, \mathcal{T})$.

Knowledge extractability (soundness) is a strengthening of the soundness property which guarantees that if the prover produces an accepting proof then there exists an efficient simulator can actually *extract* a witness for the statement. So the extractor is defined by $\text{Ext}(\pi, x, \mathcal{T}) \to w$ where $(x, w) \in \mathcal{R}$.
**Definition 9 (Unbounded adaptive knowledge soundness).** A proof system $\Pi$ is unbounded adaptive knowledge extractability if for every PPT adversary $\mathcal{A}$, there exists an efficient extractor $\text{Ext}$ such that

$$ \Pr \left[ \begin{array}{l} (\text{crs}, \mathcal{T}) \leftarrow \text{Setup}(1^{\lambda}) \\ (x, \pi) \leftarrow \mathcal{A}^{\mathcal{O}(\text{crs}, \dots, \mathcal{T})}(\text{crs}) : (x, w) \in \mathcal{R} \text{ iff } \text{V}(\text{crs}, x, \pi, \mathcal{T}) = 1 \\ w \leftarrow \text{Ext}(\pi, x, \mathcal{T}) \end{array} \right] \approx 1 $$

where $\mathcal{A}$ can make polynomially many queries to an oracle $\mathcal{O}(\text{crs}, \dots, \mathcal{T})$ which, on input $(x, \pi)$, outputs $\text{V}(\text{crs}, x, \pi, \mathcal{T})$.

We consider the notion of adaptive zero-knowledge where the adversary can choose the statement after seeing the crs. The definition of ZK below is often referred to as “single-theorem ZK” in which the prover generates a single proof (and the length of the common reference string can be larger than the length of the statement to prove) and multi-theorem zero-knowledge (where the adversary can adaptively ask for polynomially many proofs on arbitrary pairs $(x, w)$ for the same common reference string). Note that, there is a generic compiler from single-theorem ZK to multi-theorem ZK where zero-knowledge holds polynomially many statements via the “OR trick”. The same transformation directly applies to both the selective and adaptive ZK setting and also both the publicly verifiable and the designated verifier setting.

**Definition 10 (Adaptive Zero-Knowledge).** We say a non-interactive argument $\Pi$ is Adaptive Single-Theorem (Multi-Theorem) Zero-Knowledge if there exists a polynomial time simulator $\text{SimProver} = (S_1, S_2)$ where $(\text{crs}, \mathcal{T}) \leftarrow S_1(1^{\lambda})$ outputs a simulated common reference string and a simulation trapdoor and $\pi \leftarrow S_2(\text{crs}, \mathcal{T}, x)$ produces a simulated argument such that

**Adaptive Single-Theorem Zero-Knowledge.** For all interactive adversaries PPT $\mathcal{A}$, we require

$$ \Pr \left[ \begin{array}{l} \mathcal{A}(\pi) = 1 \\ (x, w) \in \mathcal{R} \end{array} \middle| \begin{array}{l} (\text{crs}, \mathcal{T}) \leftarrow \text{Setup}(1^{\lambda}) \\ (x, w) \leftarrow \mathcal{A}(1^{\lambda}, \text{crs}) \\ \pi \stackrel{\$}{\leftarrow} \text{P}(\text{crs}, x, w) \end{array} \right] - \Pr \left[ \begin{array}{l} \mathcal{A}(\pi) = 1 \\ (x, w) \in \mathcal{R} \end{array} \middle| \begin{array}{l} (\text{crs}, \mathcal{T}) \leftarrow S_1(1^{\lambda}) \\ (x, w) \leftarrow \mathcal{A}(1^{\lambda}, \text{crs}) \\ \pi \leftarrow S_2(\text{crs}, \mathcal{T}, x) \end{array} \right] = \text{negl}(\lambda) $$

**Adaptive Multi-Theorem Zero-Knowledge.** A PPT $\mathcal{A}$ has a negligible advantage in distinguishing the experiments $\text{Exp}_{\mathcal{A}}^{\text{zk},0}(1^{\lambda})$ and $\text{Exp}_{\mathcal{A}}^{\text{zk},1}(1^{\lambda})$ given in fig. 5.

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** $\text{Exp}_{\mathcal{A}}^{\text{zk},0}(1^{\lambda})$ and $\text{Exp}_{\mathcal{A}}^{\text{zk},1}(1^{\lambda})$ and oracles $\mathcal{O}_{\text{prove}}(\text{crs}, x, w)$ and $\mathcal{O}_{\text{sim}}(\text{crs}, \mathcal{T}, x, w)$, for the (adaptive) multi-theorem zero-knowledge property of a non-interactive argument system. $\mathcal{A}$ outputs $b \in \{0, 1\}$.</figcaption></figure>
## 3.6 Variants of Power-DDH

**Assumption 1 (Power-DDH, [CNs07, AHI11])**

The power-DDH assumption states that for a group $G_λ = ⟨g⟩$ of prime order $p$, for any polynomially-bounded $ℓ ∈ N$, it holds that

$$ (g, g^r, g^{r^2}, \dots, g^{r^{ℓ-1}}, g^{r^ℓ}) \stackrel{c}{\approx} (g, g^r, g^{r^2}, \dots, g^{r^{ℓ-1}}, g^t), $$

where $r, t \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$.

**Assumption 2 (Sparse Power-DDH)** The sparse power-DDH assumption states that for a group $G_λ = ⟨g⟩$ of prime order $p$, for any polynomially-bounded $ℓ ∈ N$ and $S ⊂ [ℓ]$, it holds that

$$ (g, (g^{r^i})_{i \in S}, (g^{r^i})_{i \in [ℓ] \setminus S}) \stackrel{c}{\approx} (g, (g^{r^i})_{i \in S}, (g^{t_i})_{i \in [ℓ] \setminus S}), $$

where $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$, and $t_i \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$ for all $i \in [ℓ] \setminus S$.

## 3.7 Decision Composite Residuosity Assumption

Let SampleModulus be a polynomial-time algorithm that on input the security parameter $λ$, outputs $(N, P, Q)$, where $N = PQ$ for $λ$-bit primes $P$ and $Q$.

**Assumption 3 (Decision Composite Residuosity assumption, [Pai99])** Let $λ$ be the security parameter. We say that the Decision Composite Residuosity (DCR) problem is hard relative to SampleModulus if $(N, x) \approx_c (N, x^N)$ where $(N, P, Q) \stackrel{\$}{\leftarrow}$ SampleModulus$(1^λ)$, $x \stackrel{\$}{\leftarrow} \mathbb{Z}_{N^2}^*$, and $x^N$ is computed modulo $N^2$.

Note that $\mathbb{Z}_{N^2}^*$ can be written as a product of subgroups $H \times \mathbb{N}\mathbb{R}_N$, where $H = \{(1+N)^i : i \in [N]\}$ is of order $N$, and $\mathbb{N}\mathbb{R}_N = \{x^N : x \in \mathbb{Z}_{N^2}^*\}$ is the subgroup of $N$-th residues that has order $\phi(N)$.

### Paillier-ElGamal Cryptosystem.

The Paillier-ElGamal cryptosystem [CS02, DGS03, BCP03] is defined by a triple (PaillierEG.Gen, PaillierEG.Enc, PaillierEG.Dec), and boils down to using the ElGamal cryptosystem over the group $(\mathbb{Z}_{N^2}, \times)$ where $N$ is a Blum integer of the form $N = PQ$, where $P$ and $Q$ are primes:

**PaillierEG.Gen(1^λ):**

1. Sample $g' \stackrel{\$}{\leftarrow} [N^2]$

2. Set $g \leftarrow (g')^{2N} \mod N^2$

3. Sample $d \stackrel{\$}{\leftarrow} [N^2]$

4. Output $(pk = g^d \mod N^2, sk = d)$

**PaillierEG.Enc(pk, x):**

1. Sample $r \stackrel{\$}{\leftarrow} [N]$

2. Output $ct = (g^r, pk^r \cdot (1+N)^x)$

**PaillierEG.Dec(sk, ct = (ct_0, ct_1)):**

1. Set $ct' \leftarrow ct_1 \cdot (ct_0)^{-d} \mod N^2$

2. Output $x = \frac{ct'-1}{N}$

Assuming the DCR assumption (Assumption 3), the Paillier-ElGamal cryptosystem is semantically secure.
## 3.8 Pedersen Commitment Scheme

Let $p, q$ be large prime numbers such that $q|p-1$. The Pedersen commitment scheme [Ped92] works over the subgroup of quadratic residues of $p$, denoted by $QR_p$ as follows:

**Pedersen. Setup(1^λ):**

1. Sample a $\leftarrow \mathbb{Z}_q$, and set $h := g^a \pmod p$.

2. Sample $a \leftarrow \mathbb{Z}_q$, and set $h := g^a \pmod p$.

3. Output $pp = (g, h, p, q)$

**Pedersen. Com(pp, m ∈ Z_q):**

1. Sample $r \leftarrow \mathbb{Z}_q$.

2. Output $com = g^r \cdot h^m \pmod p$, and $aux = (m, r)$.

**Pedersen. Open(pp, com, aux):**

1. Output $\pi = (m, r)$.

**Pedersen. Verify(pp, com, \pi = (m, r)):**

1. Output 1 if $com = g^r \cdot h^m$.

Pedersen commitments are perfectly hiding, and computationally binding assuming the hardness of DLog over $\mathbb{Z}_p$.

# 4 Constraining the Naor-Reingold PRF

In this section, we first describe how to obtain a constrained PRF in the ROM from the Naor-Reingold PRF for the class of inner-product membership constraints, defined below. Then, we detail several optimizations and provide some simple applications for the resulting CPRF.

## 4.1 Inner Product Membership CPRF from Naor-Reingold

We define the class of inner-product membership (IPM) constraints as $IPM = \{C_z^S | z \in \mathbb{R}^n, S \subseteq \mathcal{I}\}$, for some sets $\mathcal{R}$ and $\mathcal{I}$, and $n > 0$, where $C_z^S : \mathbb{R}^n \to \{0, 1\}$ is defined as $C_z^S(x) = 0$ iff $\langle z, x \rangle \in S$ for an input $x \in \mathbb{R}^n$. In the following, we first consider binary inputs, i.e., $\mathcal{R} = \{0, 1\}$, and later in the section, we explain how we can operate over non-binary inputs, e.g., considering $\mathcal{R} = \{0, 1, \dots, p-1\}$ for a prime $p$.

In Figure 6, we describe our construction for constraining the Naor-Reingold PRF for the class of inner-product membership constraints.

### Naor-Reingold CPRF for IPM (Binary Inputs)

**Requires:**

- $p$ is a safe prime, i.e., $p = 2q + 1$ for some prime $q$.

- The input and constraint space is $\{0, 1\}^n$.

- The inner-product space is $\mathcal{I} = \{0, 1, \dots, n\}$.

**CPRF.KeyGen(1^λ):**

- Run $(\mathbb{G}, g, p) \stackrel{\$}{\rightleftharpoons} \text{GenPar}(1^\lambda)$.

- Sample $\mathbf{a} = (a_0, \dots, a_n) \stackrel{\$}{\rightleftharpoons} \mathbb{Z}_p^{n+1}$.

- Set and output $\mathbf{msk} = \mathbf{a}$ and $\mathbf{pp} = (\mathbb{G}, g, p)$.

**CPRF.Eval(pp, msk, x ∈ \{0, 1\}^n):**

- Parse $pp = (\mathbb{G}, g, p)$ and $\mathbf{msk} = \mathbf{a}$.

- Output $y = g^{a_0 \cdot \prod_{i=1}^{n} a_i^{x_i}}$.
CPRF.Constrain(pp, msk, (z, S)):

- Parse pp = (G, g, p),
  and msk = a.

- Sample $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$.

- For $i \in [n]$, set $\alpha_i := a_i \cdot r^{-z_i}$.

- Let $\alpha = (\alpha_1, \dots, \alpha_n)$.

- For $s \in S$, compute $g_s := g^{a_0 \cdot r^s}$.

- Output $ck = (\alpha, (g_s)_{s \in S}, \mathbf{z})$.

CPRF.CEval(pp, ck, $\mathbf{x} \in \{0, 1\}^n$):

- Parse $pp = (\mathbb{G}, g, p)$,
  and $ck = (\alpha, (g_s)_{s \in S}, \mathbf{z})$.

- Let $s_x := \langle \mathbf{z}, \mathbf{x} \rangle$.

- If $\langle \mathbf{z}, \mathbf{x} \rangle \in S$,
  output $y = (g_{s_x}) \prod_{i=1}^{n} \alpha_i^{x_i}$.

- Otherwise, return $\perp$.

<caption>**Fig. 6.** Naor-Reingold CPRF for IPM constraints over binary inputs.</caption>

We first show that, our construction is no-evaluation secure under the sparse power-DDH assumption (Assumption 2).

**Theorem 2 (No-Evaluation Security).** *Assuming the hardness of sparse power-DDH (Assumption 2), the construction in Figure 6 is a single-key, no-evaluation secure CPRF for the class of IPM constraints.*

*Proof. We now prove correctness and no-evaluation security of the construction provided in Figure 6.*

**Correctness.** Correctness follows by inspection after replacing each $\alpha_i$ by $r^{z_i}a_i$ in the output of the CEval algorithm.

**No Evaluation Pseudorandomness.** Let $\mathcal{A}$ denote a 1-key no-evaluation adversary against the pseudorandomness of the above construction. Consider the following sequence of hybrid games:

**Hybrid $\mathcal{H}_0$:** This is the standard CPRF security game where the challenge query is answered by returning the output of the CPRF evaluation algorithm. Here the view of the adversary is as follows:

$$ \text{View}_{0}^{\mathcal{A}} = (\text{pp}, (\mathbf{z}, S), \text{ck}_{(\mathbf{z},S)}, \mathbf{x}^{*}, y^{*}), $$

$$ \text{where } \text{pp} = (\mathbb{G}, g, p), \text{ck}_{(\mathbf{z},S)} = (\alpha, (g_s)_{s \in S}, \mathbf{z}), \text{ and } y^* = g^{a_0 \cdot \prod_{i=1}^{n} a_i^{x_i^*}}. $$

**Hybrid $\mathcal{H}_1$:** In this game, the challenger modifies the way it computes the constrained key. It sets the constrained key to be $\text{ck} = (\alpha, (g_s)_{s \in S}, \mathbf{z})$, where $g_s = g^{a_0 \cdot r^s}$ for each $s \in S$, same as in $\mathcal{H}_0$, but differently, for $\alpha$, it samples a uniform vector $\alpha \stackrel{\$}{\leftarrow} \mathbb{Z}_p^n$.

Note that in $\mathcal{H}_0$ we have $\alpha_i = r^{-z_i}a_i$, where $a_i$ is uniformly sampled from $\mathbb{Z}_p$ for each $i \in [n]$. Therefore, the distribution of $\alpha$ is identical in both games.

**Hybrid $\mathcal{H}_2$:** In this game, the challenger replies to the challenge query by returning $g^t$ for a random element $t \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$. We claim that assuming the sparse power-DDH assumption (Assumption 2), $\mathcal{H}_2$ and $\mathcal{H}_1$ are computationally indistinguishable. Suppose $\mathcal{A}$ succeeds in distinguishing these two hybrid games. We construct an adversary $\mathcal{B}$ that breaks Assumption 2 with respect to the set $S$ and $\ell = n$.

$\mathcal{B}$ is given the group $\mathbb{G} = \langle g \rangle$ of order $p$ and sets $\text{pp} := (\mathbb{G}, g, p)$ which it sends to $\mathcal{A}$. Then, after receiving a constraint query $(\mathbf{z}, S)$ from $\mathcal{A}$, $\mathcal{B}$ asks its challenger for a challenge distribution with respect to the set $S$ and $\ell = n$. It receives a tuple of the form:

$$ (g, p, (g^{a \cdot r^s})_{s \in S}, (g^{t_s})_{s \in [n] \setminus S}), $$

$$ \text{where } a, r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*, \text{ and for each } g^{t_s}, \text{ where } s \in [n] \setminus S, \text{ it either holds that } t_s = a \cdot r^s \text{ or } t_s \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*. $$

$\mathcal{B}$ then selects a random vector $\alpha \stackrel{\$}{\leftarrow} \mathbb{Z}_p^n$, sets the constrained key $\text{ck} = (\alpha, (g^{a \cdot r^s})_{s \in S}, \mathbf{z})$, and returns it to $\mathcal{A}$.
To answer the challenge query $\mathbf{x}^*$ made by $\mathcal{A}$ which satisfies $\langle \mathbf{x}^*, \mathbf{z} \rangle \notin S$, it selects the $g^{t_{s^*}}$ corresponding to $s^* = \langle \mathbf{x}^*, \mathbf{z} \rangle$ (mod $p$) and outputs $(g^{t_{s^*}})_{i=1}^n \alpha_i^{x_i^*}$.

If $t_{s^*} = a \cdot r(\mathbf{x}^*, \mathbf{z})$, then $\mathcal{B}$ simulates the view of $\mathcal{A}$ as in Hybrid $\mathcal{H}_1$, and otherwise, if $t_{s^*} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$, it simulates $\mathcal{H}_2$. Therefore, distinguishing these two hybrids implies breaking Assumption 2 which proves our claim.

The rest of the proof proceeds by reversing the sequence of hybrid games while leaving the challenge query answered by a uniformly random value. □

While the construction described in Figure 6 is no-evaluation secure, a simple attack can be mounted as soon as 1 evaluation query is allowed, as we remark below. Fortunately, no-evaluation secure CPRFs can be turned into standard secure CPRFs by known techniques [AMN+18], e.g. in the ROM. We provide more details below.

**Remark 2 (A single query attack).** Let $(\mathbf{z}, S)$ be the constraint selected by the adversary. For any input $\mathbf{x}$, let us define $s_{\mathbf{x}} = \langle \mathbf{z}, \mathbf{x} \rangle$ and $u_{\mathbf{x}} = \prod_{i=1}^n \alpha_i^{x_i}$, where $\alpha = (\alpha_1, \dots, \alpha_n)$ is part of the constrained key obtained by the adversary. Then, remark that the output of the CPRF on any input $\mathbf{x}$ can be written as

$$ \mathrm{Eval}(\mathbf{x}) = g^{a_0 \cdot r^{s^*} \cdot u_{\mathbf{x}}} $$

where $g^{a_0 \cdot r^{s^*}}$ is part of the constrained key if and only if $s_{\mathbf{x}} \in S$.

Since $u_{\mathbf{x}}$ is computable for any $\mathbf{x}$ from the constrained key, an adversary $\mathcal{A}$ with access to the evaluation oracle, can ask for the output of the CPRF on any input $\mathbf{x}$ such that $s_{\mathbf{x}} \notin S$ and recover $g^{a_0 \cdot r^{s^*}}$ by raising the evaluation to the power $1/u_{\mathbf{x}}$. Given $g^{a_0 \cdot r^{s^*}}$, $\mathcal{A}$ can now evaluate the CPRF on any input $\mathbf{x}'$ such that $s_{\mathbf{x}} = s_{\mathbf{x}'}$ (mod $p$), and therefore break the security by finding any input $\mathbf{x}^* \neq \mathbf{x}$ such that $s_{\mathbf{x}} = s_{\mathbf{x}^*}$ (mod $p$).

**Achieving Selective and Adaptive Security.** As shown in [AMN+18], our no-evaluation secure CPRF for IPM constraints (Figure 6) can be modified to achieve adaptive security using a hash function modeled as a random oracle. In order to prevent the attack explained above, we can simply hash the output of our no-evaluation secure CPRF. Modeling the hash function as a random oracle, the output of the evaluation function is perfectly random as long as an adversary cannot efficiently find the hash input, i.e., as explain in our attack, cannot find two values $\mathbf{x} \neq \mathbf{x}' \in \mathbb{Z}_p^n$ for which it holds that $s_{\mathbf{x}} = s_{\mathbf{x}'} \notin S$ and $u_{\mathbf{x}} = u_{\mathbf{x}'}$. Since each $a_i$ (therefore each $\alpha_i$) is a random element of $\mathbb{Z}_p$, the probability that $u_{\mathbf{x}} = u_{\mathbf{x}'}$ for any $\mathbf{x} \neq \mathbf{x}' \in \mathbb{Z}_p^n$ is $1/p$. Therefore, the probability of finding a collision is negligible. The proof of adaptive security proceeds in the same way as in [AMN+18] (Section 4.3). Looking more closely, we can replace the random oracle by a correlation-robust hash function and achieve selective security. Variants of correlation-robust hash have been used in many previous works, see [IKNP03, KKRT16, AMN+18] for a small sample. As in these works, we note that this is a simple standard-model assumption that is likely to hold for classical hash functions such as SHA3.

**Non-Binary Inputs.** Extending the input domain of our CPRF construction to support non-binary inputs can be simply done by considering the construction presented in Figure 6 for the class of IPM constraints for a larger set $\mathcal{I}$ as the inner-product space. In other words, one can consider $\mathrm{IPM} = \{C_{\mathbf{z}}^S | \mathbf{z} \in \mathcal{R}^n, S \subset \mathcal{I}\}$, with $\mathcal{R} = \mathbb{Z}_p$ for a large (safe) prime $p$ and $\mathcal{I} = \{0, 1, \dots, \ell\}$, with $\ell = \mathrm{poly}(\lambda)$, $\ell \ll p$. The no-evaluation security then follows from Theorem 2 assuming the hardness of sparse power-DDH assumption for the set $S \subset [\ell]$.

## 4.2 Compressing the keys

We now show how to generate the elements of a master secret key in our Naor-Reingold CPRF by evaluating pseudorandom generators on short seeds. We can thus store a shorter master secret key and communicate a shorter constrained key (for some indices of the constraint vector).

Due to the works of Nechaev [Nec94] and Shoup [Sho97], generic algorithms that solve the DLog problem over $\mathbb{F}_p$, for a prime $p$, run in $\sqrt{p}$ steps. Therefore, in order to achieve $\lambda$ bits of security against such algorithms, it should hold that $\log(p) = 2\lambda$. As a result, we can choose the seeds of our PRGs (that generate the master secret key) as short as $\log(p)/2$ bits without any security loss.
**Compressing msk.** Using a pseudorandom generator (PRG) $\mathbf{G}: \{0,1\}^{\lambda} \to \{0,1\}^{(n+1)\cdot2^{\lambda}}$, we can generate the vector msk = $(a_0, a_1, \dots, a_n)$ as the output of $\mathbf{G}$ on a random $\lambda$-bit seed. Doing so, the size of the stored master secret key is reduced from $(n+1)\cdot2^{\lambda}$ bits to $\lambda$ bits.

**Compressing ck.** Recall that for a constraint vector $\mathbf{z}$ and a set $S$, a constrained key generated in the CPRF construction of Figure 6 is of the form $\text{ck}_{(\mathbf{z},S)} = (\alpha, (g_s)_{s \in S}, \mathbf{z})$, where $\alpha_i = r^{-z_i} a_i$ for all $i \in [n]$. In the case of binary inputs, for each index $i \in [n]$, it holds that $\alpha_i = a_i$, if $z_i = 0$, and $\alpha_i = r^{-1} \cdot a_i$, if $z_i = 1$. In other words, for all the indices $i \in [n]$, where $z_i = 0$, the master secret key element $a_i$ is included in the constrained key and given to the adversary in plain.
Here, we propose an alternative way of generating the master key elements $(a_1, \dots, a_n) \in \mathbb{Z}_p^n$ which results in including shorter elements in the constrained key and thus reducing the constrained key size. The idea is to use a pseudorandom generator (PRG) $\mathbf{G}' : \{0,1\}^{\lambda} \to \{0,1\}^{2^{\lambda}}$ and to generate each $a_i$ as the image of $\mathbf{G}'$ on a randomly sampled short seed $\text{seed}_i \stackrel{\$}{\leftarrow} \{0,1\}^{\lambda}$, for all $i \in [n]$. Doing so, when generating a constrained key for a constraint vector $\mathbf{z}$, for all the indices $i \in [n]$ where $z_i = 0$, we can include the $\lambda$-bit $\text{seed}_i$ instead of the $2^{\lambda}$-bit master secret key element $a_i$.

Combining the two above solutions for reducing the msk and ck sizes, we can first use a PRG $\mathbf{G}: \{0,1\}^{\lambda} \to \{0,1\}^{(2+n)^{\lambda}}$ to generate a vector $(a_0, \text{seed}_1, \dots, \text{seed}_n)$ from a random $\lambda$-bit seed, and afterwards, use another PRG $\mathbf{G}': \{0,1\}^{\lambda} \to \{0,1\}^{2^{\lambda}}$ to generate $a_i \leftarrow \mathbf{G}'(\text{seed}_i)$ for all $i \in [n]$.

Figure 7 presents the modified construction with reduced key size. The steps that are different from the original construction (Figure 6) are marked by the symbol $\sqsupset$.

## Naor-Reingold CPRF with Compressed Keys

Requires:

- $p$ is a safe prime, i.e., $p = 2q + 1$ for some prime $q$.

- The input and constraint space is $\{0,1\}^n$.

- The inner-product space $\mathcal{I} = \{0,1,\dots,n\}$.

- $\mathbf{G}: \{0,1\}^{\lambda} \to \{0,1\}^{(n+2)^{\lambda}}$, and $\mathbf{G}': \{0,1\}^{\lambda} \to \{0,1\}^{2^{\lambda}}$ are PRGs.

**CPRF.KeyGen(1^{\lambda}):**

- Run $(\mathbb{G}, g, p) \stackrel{\$}{\leftarrow} \text{GenPar}(1^{\lambda})$.

$\sqsupset$ Sample $\text{seed} \stackrel{\$}{\leftarrow} \{0,1\}^{\lambda}$.

$\sqsupset$ Output msk = seed, and $\text{pp} = (\mathbb{G}, g, p)$.

**CPRF.Constrain(pp, msk, (z, S)):**

$\sqsupset$ Parse $\text{pp} = (\mathbb{G}, g, p)$, and msk = seed.

$\sqsupset$ $(a_0, (\text{seed}_i)_{i=1}^n) \leftarrow \mathbf{G}(\text{seed})$.

- Sample $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$.

$\sqsupset$ For $i \in [n]$:

1. If $z_i = 0$, set $\tilde{\alpha}_i := \text{seed}_i$.

2. If $z_i = 1$, set $\tilde{\alpha}_i := r^{-1} \cdot \mathbf{G}'(\text{seed}_i)$.

$\sqsupset$ Let $\tilde{\alpha} = (\tilde{\alpha}_1, \dots, \tilde{\alpha}_n)$.

- For $s \in S$, set $g_s := g^{a_0 \cdot r^s}$.

$\sqsupset$ Output $\text{ck} = (\tilde{\alpha}, (g_s)_{s \in S}, \mathbf{z})$.

**CPRF.Eval(pp, msk, x \in \{0,1\}^n):**

$\sqsupset$ Parse $\text{pp} = (\mathbb{G}, g, p)$, and msk = seed.

$\sqsupset$ $(a_0, \text{seed}_1, \dots, \text{seed}_n) \leftarrow \mathbf{G}(\text{seed})$.

$\sqsupset$ For all $i \in [n]$:
  compute $a_i \leftarrow \mathbf{G}'(\text{seed}_i)$.
  Output $y = g^{a_0 \cdot \prod_{i=1}^n a_i^x}$.

**CPRF.CEval(pp, ck, x \in \{0,1\}^n):**

$\sqsupset$ Parse $\text{pp} = (\mathbb{G}, g, p)$, and $\text{ck} = (\tilde{\alpha}, (g_s)_{s \in S}, \mathbf{z})$.

$\sqsupset$ For $i \in [n]$:
1. If $z_i = 0$, set $\alpha_i := \mathbf{G}'(\tilde{\alpha}_i)$.
2. If $z_i = 1$, set $\alpha_i := \tilde{\alpha}_i$.

- Let $s_x := \langle \mathbf{z}, \mathbf{x} \rangle$.

- If $\langle \mathbf{z}, \mathbf{x} \rangle \in S$, output $y = (g_{s_x})_{i=1}^n \prod_i \alpha_i^{x_i}$.

- Otherwise, output $\perp$.
<caption>**Fig. 7.** Naor-Reingold CPRF for IPM with Compressed Keys.</caption>

**Security Analysis.** We observe that computing the elements of the master secret as outputs of a pseudorandom generator on short seeds does not affect the no-evaluation security of the resulting CPRF except for imposing a negligible loss in the security reduction. More precisely, the proof of the no-evaluation security of the CPRF with optimized constrained key size follows from a sequence of hybrid games similar to the proof of Theorem 2 with an adaptation in Hybrid $\mathcal{H}_1$. We break this hybrid into the two following parts:

**Hybrid $\mathcal{H}_1^0$:** In this game, the challenger modifies the way it computes some elements of the vector $\alpha$ of the constrained key. To generate a constrained key, the challenger first parses $\mathbf{msk} = \mathbf{seed}$ and computes $(a_0, \mathbf{seed}_1, \dots, \mathbf{seed}_n) \leftarrow \mathcal{G}(\mathbf{seed})$. It then sets $\tilde{\alpha}_i := \mathbf{seed}_i$, for all $i \in [n]$ such that $z_i = 0$. And differently from $\mathcal{H}_0$, it samples random elements $\tilde{\alpha}_i \stackrel{\$}{\leftarrow} \mathbb{Z}_p$, for all $i \in [n]$ such that $z_i = 1$. It then sets the constrained key to be $\mathbf{ck} = (\tilde{\alpha}, (g_s)_{s \in S}, \mathbf{z})$, where $g_s = g^{a_0 \cdot r^s}$, for all $s \in S$.

Note that Hybrid $\mathcal{H}_1^0$ remains computationally indistinguishable from Hybrid $\mathcal{H}_0$. This is because the only difference between the two hybrids is that for all indices $i \in [n]$ where $z_i = 1$, the element $\tilde{\alpha}_i$ is sampled as a random element in $\mathcal{H}_1$, rather than being computed as $\tilde{\alpha}_i = r^{-1} \cdot \mathcal{G}'(\mathbf{seed}_i)$ in $\mathcal{H}_0$. Therefore, if a PPT adversary can distinguish between these two hybrids, there must exist an index $i$ such that a random element $\tilde{\alpha}_i \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ is distinguished from an element of the form $\tilde{\alpha}_i = r^{-1} \cdot \mathcal{G}'(\mathbf{seed}_i)$. Such an adversary can be leveraged to distinguish between the outputs of the pseudorandom generator $\mathcal{G}'$ with random elements of $\mathbb{Z}_p$.

**Hybrid $\mathcal{H}_1^1$:** In this game, the challenger samples the master secret key without using the PRG $\mathcal{G}$ anymore. In other words, the challenger samples $a_0 \stackrel{\$}{\leftarrow} \mathbb{Z}_p$, and $\mathbf{seed}_i \stackrel{\$}{\leftarrow} \{0, 1\}^\lambda$ for all $i \in [n]$, and sets $\mathbf{msk} = (a_0, \mathbf{seed}_1, \dots, \mathbf{seed}_n)$. As a result, when generating a constrained key, it no longer uses $\mathcal{G}$. Here again, Hybrid $\mathcal{H}_1^1$ remains indistinguishable to $\mathcal{H}_1^0$ due to the security of the PRG $\mathcal{G}$.

The rest of the proof is done exactly as in the proof of Theorem 2 with an adaptation that the constrained key element $\alpha$ is now set as in $\mathcal{H}_1^1$.

## 4.3 Application: A Puncturable PRF in $\mathbf{NC}^1$

A puncturable PRF is a pseudorandom function that allows the generation of a constrained key $\mathbf{ck}$ which enables one to evaluate the output of the PRF on all inputs but one. The well-known construction of [GGM84a] from one-way functions offers a puncturable PRF that is computable by a linear-depth circuit in the size of the input. Noticing that the IPM class contains puncturing constraints (for certain parameters), our CPRF construction (Figure 6) which is essentially constrained Naor-Reingold PRF and can be evaluated by a log-depth circuit, offers a puncturable PRF in $\mathbf{NC}^1$.

**Construction.** For this construction, we consider the input space to be $\{-1, 1\}^n$. Suppose that we want to puncture the Naor-Reingold PRF on an input $\mathbf{x}^* \in \{-1, 1\}^n$. In what follows, we show that this can be done using the Naor-Reingold CPRF construction of Figure 6 that supports the class of IPM constraints. Note that for a vector $\mathbf{x}^* \in \{-1, 1\}^n$ and any vector $\mathbf{x} \in \{-1, 1\}^n$, the inner-product $\langle \mathbf{x}, \mathbf{x}^* \rangle = n$ iff $\mathbf{x} = \mathbf{x}^*$. Also, all possible values of the inner-product between vectors in $\{-1, 1\}^n$ lie in the set $\mathcal{I} = \{-n, -n+2, -n+4, \dots, n-2, n\}$. Therefore, setting the constraint set $S = \mathcal{I} \setminus \{n\}$, a CPRF supporting inner-product membership constraints for the set $S$, can be viewed as a puncturable PRF for any vector $\mathbf{x}^* \in \{-1, 1\}^n$. Parameters of the IPM constraints for this application is presented in Figure 8.

### Naor-Reingold Puncturable PRF

Setting the parameters of IPM = {$C_z^S | z \in \mathcal{R}^n, S \subset \mathcal{I}$}:

- Input and constraint vectors space: $\mathcal{R} = \{-1, 1\}^n$.
- Inner-product space: $\mathcal{I} = \{-n, -n+2, -n+4, \dots, n-2, n\}$.

- Inner-product constraint set: $S = \mathcal{I} \setminus \{n\}$.

<caption>**Fig. 8.** Parameters of IPM for puncturing constraints.</caption>

**Security.** The 1-key selective no-evaluation security of the scheme is implied by the sparse power-DDH assumption. Importantly, we note that in the case of puncturing constraints, the 1-key selective no-evaluation security becomes equivalent to the standard selective security notion where an adversary is allowed to query the evaluation oracle. This is because the challenge query can only be issued on the punctured point $\mathbf{x}^*$. Therefore, in the selective setting, the challenger can compute the constrained key $ck_{\mathbf{x}^*}$ in the beginning of the security game, and consequently, can answer evaluation queries for inputs $\mathbf{x} \neq \mathbf{x}^*$ by computing and returning the output of $CEval(pp, ck_{\mathbf{x}^*}, \mathbf{x})$ to the adversary. In the following, we briefly go over the security proof:

**Hybrid $\mathcal{H}_0$:** This is the 1-key selective CPRF security game where the evaluation and challenge queries are answered by returning the output of the CPRF evaluation algorithm on the queried inputs. The view of the adversary in this game is as follows:

$$ \text{View}_{0}^{\mathcal{A}} = (\text{pp}, \{\mathbf{x}_i, y_i\}_{i \in [Q]}, \text{ck}, \mathbf{x}^*, y^*), $$

where $\text{pp} = (\mathbb{G}, g, p)$, $\text{ck} = (\alpha, (g_s)_{s \in S})$, and $y = g^{a_0 \cdot \prod_{i=1}^{n} a_i^*}$ for all $(x, y) \in \{(x_i, y_i)_{i \in [Q]}, (\mathbf{x}^*, y^*)\}$.

**Hybrid $\mathcal{H}_1$:** In this game, we change how the evaluation oracle queries are answered. As we consider the selective setting, the challenger knows the punctured point $\mathbf{x}^*$ from the beginning. It can therefore compute the constrained key $ck$ from the start, and answer an evaluation query on any input $\mathbf{x} \neq \mathbf{x}^*$ by computing $y \leftarrow CEval(pp, ck, \mathbf{x})$. The view of the adversary remains identical to its view in $\mathcal{H}_0$ by the correctness of the CPRF.

**Hybrid $\mathcal{H}_2$:** In this game, the challenger sets the vector $\alpha$ in the constrained key $ck$ to be a random vector from $\mathbb{Z}_p^*$. Hybrids $\mathcal{H}_1$ and $\mathcal{H}_2$ remain statistically indistinguishable.

**Hybrid $\mathcal{H}_3$:** In this hybrid, the challenger replies to the challenge query by returning $g^t$ for a random element $t \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$. Assuming the sparse power-DDH assumption (Assumption 2), hybrids $\mathcal{H}_2$ and $\mathcal{H}_3$ are computationally indistinguishable. Let $\mathcal{A}$ be an adversary that distinguishes $\mathcal{H}_2$ and $\mathcal{H}_3$. In what follows, we construct an adversary $\mathcal{B}$ that breaks Assumption 2 with respect to the set $S' = \{0, 2, 4, \dots, 2n-2\}$ and $\ell = 2n$.

Knowing the group $\mathbb{G} = \langle g \rangle$ of order $p$, $\mathcal{B}$ sets $pp := (\mathbb{G}, g, p)$ and sends it to $\mathcal{A}$.

Then, after receiving a punctured point $\mathbf{x}^*$ from $\mathcal{A}$, adversary $\mathcal{B}$ asks the assumption oracle for a challenge distribution with respect to the set $S' = \{0, 2, 4, \dots, 2n-2\}$ and $\ell = 2n$ and receives a tuple of the following form:

$$ (g, p, (g_s)_{s \in S'}, (g_s)_{s \in [2n] \setminus S'}), $$

where for all $s \in S'$ it holds that $g_s = g^{a \cdot r^s}$ for some $a, r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$, and for all $s \in [2n] \setminus S'$ it either holds that $g_s = g^{a \cdot r^s}$ or $g_s = g^{t_s}$ for some $t_s \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$.

$\mathcal{B}$ then selects a random vector $\alpha \stackrel{\$}{\leftarrow} \mathbb{Z}_p^n$ and sets the constrained key $ck = (\alpha, (g^{a \cdot r^s})_{s \in S'}, \mathbf{z})$. Note that with overwhelming probability, $a$ can be written as $a = r^{-n} \cdot \beta$, for a random element $\beta \in \mathbb{Z}_p^*$. Therefore we can rewrite $g^{a \cdot r^s} = g^{\beta \cdot r^{s-n}}$ for all $s \in S'$. As a result, the tuple $(g^{a \cdot r^s})_{s \in S'}$ for the set $S' = \{0, 2, 4, \dots, 2n-2\}$ simulates $(g^{\beta \cdot r^s})_{s \in S}$, where $S = \{-n, -n+2, \dots, n-4, n-2\}$.

Finally, to answer the challenge query on the punctured input $\mathbf{x}^*$ which satisfies $\langle \mathbf{x}^*, \mathbf{x}^* \rangle = n$, $\mathcal{B}$ selects the $g_{2n}$ and outputs $y^* = (g_{2n})^{\prod_{i=1}^{n} \alpha_i^{x_i^*}}$. If $\mathcal{A}$ can distinguish between hybrids $\mathcal{H}_3$ and $\mathcal{H}_2$, the adversary $\mathcal{B}$ can successfully break the sparse power-DDH assumption with respect to set $S'$ and $\ell = 2n$. □
# 5 Fast PCFs for OTs from Pseudorandomly Constrained PRFs

In this section, we provide a general framework for building programmable PCFs for OT correlations from CPRFs and show how it can be instantiated under standard assumptions, yielding a concretely efficient construction.

In section 5.1 we provide a general framework for building programmable PCFs from CPRFs supporting classes of “pseudorandom constraints”. In section 5.2 we introduce a more specific template, which uses an “inner product membership (weak) PRF” to ensure these pseudorandom constraints can be expressed as “inner-product membership” constraints (which is the class tolerated by the Naor-Reingold CPRF section 4). In section 5.3 we show that many weak PRFs based on LWR or random CSPs fit our framework of inner product membership (weak) PRF. Finally, we show in section 5.4 that, when instantiated with the Naor-Reingold CPRF, our PCF natively admits a 2-round low-communication protocol for securely distributing the PCF key generation.

## 5.1 General Template

In this section, we provide constructions of (weak/strong) PCF for OT correlations from various notions of CPRF supporting a “hardcoded-key (weakly/strongly) pseudorandom class of constraints”. While technically incomparable, our constructions can be seen as achieving increasingly “stronger” PCFs from increasively “stronger” assumptions on the CPRF.

1. We first show in section 5.1 how to obtain a [weak/strong] PCF for Rabin-OT correlations, given a CPRF supporting as constraint a [weak/strong] PRF family whose key is hardcoded.

2. We then show in fig. 9 how to obtain a (weak/strong) PCF for random-OT correlations, given a CPRF supporting as constraint a (weak/strong) PRF family whose key is hardcoded as well as its opposite.

A minor drawback of this construction as opposed to the previous one is that the PCF key is roughly twice as large (as it now contains two CPRF keys), but it achieves the more standard notion of “PCF for OT correlation”, without having to use the relatively costly generic transformation from Rabin-OT to random-OT. The assumption is strictly stronger however, as a CPRF for $\mathcal{C}$ may not necessarily imply the existence of a CPRF for $\mathcal{C} \cup \{1 - f: f \in \mathcal{C}\}$.

3. Finally—and as our main construction of this section—we show in section 10 how to obtain a PCF for random-OT correlations, given a CPRF supporting the class of “1-in-2 pseudorandom constraints”. That is, for every $x \in \{0,1\}^{n-1}$ (where $n$ is the input length), exactly one of $x|0$ or $x|1$ is constrained, and which one is pseudorandom (with respect to one hardcoded key). A formal definition is provided in definition 12.

The main difference with the previous construction is that the PCF key now contains a single CPRF key, at the cost of assuming a PCF for a more involved class of constraints. This is greatly mitigated by the fact that several low-complexity weak PRF candidates from the literature admit a low-complexity circuit for “1-in-2 pseudorandom selection”.

**PCF for Rabin-OT from CPRF supporting wPRF Constraints.** We start by showing how one can build a PCF for Rabin-OT correlations using a CPRF supporting (weak) PRF as constraint.

**Definition 11 (Oblivous Transfer Correlations).** We consider two flavours of Oblivious Transfer correlations (OT correlations).

- The Rabin OT correlation over message space $\mathcal{M}$ can be defined as being sampled as a pair $(m, m')$, where $m \stackrel{\$}{\leftarrow} \mathcal{M}$ is the OT sender's random message and $m' \stackrel{\$}{\leftarrow} \{m, \perp\}$ is the message given to the receiver, which is equal to $m$ with probability $1/2$ and to $\perp$ (a special symbol not in $\mathcal{M}$, signifying the receiver does not get the sender message) with probability $1/2$.

- The (random, 1-out-of-2) OT correlation over message space $\mathcal{M}$ can be defined as being sampled as a pair (of pairs) $(m_0, m_1)$ and $(\sigma, m_\sigma)$, where $(m_0, m_1) \stackrel{\$}{\leftarrow} \mathcal{M}^2$ is the OT sender's pair of random messages and $\sigma \stackrel{\$}{\leftarrow} \{0,1\}$ is the random selection bit given to the receiver.
Crépeau [Cré88] showed that the two flavours of OT considered in definition 11 are essentially equivalent. However, the transformation from Rabin-OT to 1-out-of-2 OT is interactive<fnref n="12" />, and expands $\lambda$ Rabin-OTs in order to perform a single 1-out-of-2 OT (which is the notion standardly used in MPC). Since the construction of fig. 9 is a PCF for Rabin-OT correlations, we view it as more of an introductory “proof of concept”.

PCF Pre-Computable weak/strong PCF for Rabin-OT Correlations
(with a single call to a CPRF)

Requires:

- $F: \mathcal{K}_{\lambda} \times \mathcal{X}_{\lambda} \rightarrow \{0, 1\}$ is a weak/strong PRF.

- CPRF = (KeyGen, Eval, Constrain, CEval) is a constrained PRF supporting as constraints $\{F(k, \cdot): k \in \mathcal{K}_{\lambda}\}$.

PCF.Gen<sub>0</sub>(1<sup>λ</sup>):

1. Run (pp, msk) ⇐ KeyGen(1<sup>λ</sup>).

2. Set $k_0 \leftarrow (\text{pp}, \text{msk})$.

3. Output $k_0$.

PCF.Eval(1<sup>λ</sup>, σ, k<sub>σ</sub>, x):

1. If $\sigma = 0$:

(a) Parse $k_0$ as $k_0 = (\text{pp}, \text{msk})$.

(b) Set $y_0 \leftarrow \text{Eval}(\text{pp}, \text{msk}, x)$.

(c) Output $y_0$.

PCF.Gen<sub>1</sub>(1<sup>λ</sup>, k<sub>0</sub>):

1. Sample $k \leftarrow \mathcal{K}_{\lambda}$.

2. Parse $k_0$ as $k_0 = (\text{pp}, \text{msk})$.

3. Run $\text{ck} \leftarrow \text{Constrain}(\text{msk}, F(k, \cdot))$.

4. Set $k_1 \leftarrow (\text{ck}, k, \text{pp})$.

5. Output $k_1$.

2. If $\sigma = 1$:

(a) Parse $k_1$ as $k_1 = (\text{ck}, k, \text{pp})$.

(b) Compute $b := F(k, x)$.

(c) If $b = 0$, $y_1 \leftarrow \text{CEval}(\text{pp}, \text{ck}, x)$.

(d) If $b = 1$, $y_1 \leftarrow \perp$.

(e) Output $y_1$.

<caption>**Fig. 9.** Pre-Computable wPCF/PCF for Rabin-OT from CPRF supporting (w)PRF constraints.</caption>

**Theorem 3** ((w/s)PCF for Rabin-OT from CPRF supporting (w/s)PRF Constraints).

Assume the existence of the following primitives:

- $F: \mathcal{K}_{\lambda} \times \mathcal{X}_{\lambda} \rightarrow \{0, 1\}$ is a weak (resp. strong) PRF.

- CPRF = (KeyGen, Eval, Constrain, CEval) is a secure CPRF supporting as constraints the class $\{F(k, \cdot): k \in \mathcal{K}_{\lambda}\}$.

Then the construction of fig. 10 is a secure weak (resp. strong) precomputable PCF for Rabin-OT correlations.

Because our main goal is building PCFs for 1-in-2 OT correlations (and the above is little more than a toy example), we forgo a full proof in this version of the paper and instead sketch the sequence of hybrids which can be used to formally prove theorem 3.

- *Weakly (resp. Strongly) Pseudorandom Rabin-OT Correlated Outputs.* By correctness of CPRF, whenever $F(k, x) = 0$ it holds that with all but negligible probability $\text{Eval}(\text{pp}, \text{msk}, x) = \text{CEval}(\text{pp}, \text{ck}, x)$ if $\text{ck}$ is a key constrained by $F(k, \cdot)$. It follows that in the experiment $\text{Exp}_{\mathcal{A},N,0}^{\text{pr}}(\lambda)$, $y_1$ can be generated as follows while only introducing a negligible security loss:

$$y_1 \leftarrow \begin{cases} y_0 & \text{If } b = 0 \\ \perp & \text{Else} \end{cases}.$$

<footnote n="12">¹² Crépeau’s transformation does not seem to yield a procedure allowing parties holding Rabin-OT-correlated shares to generate 1-out-of-2-OT-correlated shares locally.</footnote>
The next hybrid involves generating $y_0$ as $y_0 \stackrel{\$}{\leftarrow} \mathcal{M}$ (instead of $y_0 \leftarrow \text{Eval}(\text{pp}, \text{msk}, x)$). By CPRF security, the outputs of the master evaluation algorithm of a CPRF are pseudorandom from the point of view of an external adversary without knowledge of the master key (or any constrained key). It follows that this hybrid only introduces a negligible security loss. The final hybrid consists in sampling $b \stackrel{\$}{\leftarrow} \{0, 1\}$ instead of $b \leftarrow F(k, x)$. This step incurs a negligible security loss by (weak/strong) PRF security, as the outputs of a PRF are pseudorandom from the point of view of an external adversary.

- Weak (Resp. Strong) PCF Security. Security for $\sigma = 0$ (i.e. “secrecy of $y_1$ given $k_0$”) follows from the fact that $k_0$ contains no information about the PRF key $k$, and hence an internal adversary with knowledge of $k_0$ has only negligible advantage in determining on which values of $x$ $\text{Eval}(1, k_1, x) = \perp$. Security for $\sigma = 1$ follows from CPRF security: the constrained key $\text{ck}$ in $k_1$ does not allow for evaluation of points $x$ such that $F(k, x) = 1$.

The outputs of the master evaluation algorithm of a CPRF, as well as the outputs of a weak/strong PRF on random/arbitrary inputs, are pseudorandom from the point of view of an external adversary without knowledge of the keys. Furthermore,

**PCF for OT from CPRF supporting wPRF Constraints and their Opposite.** We now provide a construction of a PCF for 1-out-of-2 random OT correlations (which is the standard notion of “PCF for OT correlations”), which does not rely on the generic transformation from Rabin-OT. Our construction relies on a CPRF which can be constrained with respect to both a (weak) PRF and its opposite. More specifically, for a (weak) PRF $F$ with range $\{0, 1\}$, we require a CPRF supporting the class of constraints $\{F(k, \cdot) \mid k \in \mathcal{K}_{\lambda}\}$ as well as a CPRF supporting the class of constraints $\{1 - F(k, \cdot) \mid k \in \mathcal{K}_{\lambda}\}$. However the existence of CPRFs supporting $X$ and $Y$ generically implies the existence of a CPRF supporting $X \cup Y$.

PCF Pre-Computable weak/strong PCF for OT Correlations
(with two calls to a CPRF)

Requires:

- $F: \mathcal{K}_{\lambda} \times \mathcal{X}_{\lambda} \rightarrow \{0, 1\}$ is a weak/strong PRF; we denote $\bar{F}: \mathcal{K}_{\lambda} \times \mathcal{X}_{\lambda} \rightarrow \{0, 1\}$ the function defined by $\bar{F}(k, x) := 1 - F(k, x)$.

- **CPRF** = (KeyGen, Eval, Constrain, CEval) is a constrained PRF supporting as constraints $\{F(k, \cdot): k \in \mathcal{K}_{\lambda}\} \cup \{\bar{F}(k, \cdot): k \in \mathcal{K}_{\lambda}\}$.

PCF.Gen<sub>0</sub>(1<sup>λ</sup>):

1. Run (pp<sub>0</sub>, msk<sub>0</sub>) $\stackrel{\$}{\leftarrow}$ KeyGen(1<sup>λ</sup>).

2. Run (pp<sub>1</sub>, msk<sub>1</sub>) $\stackrel{\$}{\leftarrow}$ KeyGen(1<sup>λ</sup>).

3. Set $k_0 \leftarrow (pp_0, pp_1, msk_0, msk_1)$.

4. Output $k_0$.

PCF.Gen<sub>1</sub>(1<sup>λ</sup>, k<sub>0</sub>):

1. Sample $k \stackrel{\$}{\leftarrow} \mathcal{K}_{\lambda}$.

2. Parse $k_0$ as $k_0 = (pp_0, pp_1, msk_0, msk_1)$.

3. Run $\text{ck}_0 \leftarrow \text{Constrain}(\text{msk}_0, F(k, \cdot))$.
// For inputs $x$ such that $F(k, x) = 0$.

4. Run $\text{ck}_1 \leftarrow \text{Constrain}(\text{msk}_1, \bar{F}(k, \cdot))$.
// For inputs $x$ such that $F(k, x) = 1$.

5. Set $k_1 \leftarrow (\text{ck}_0, \text{ck}_1, k, pp_0, pp_1)$.

6. Output $k_1$.

PCF.Eval(1<sup>λ</sup>, σ, k<sub>σ</sub>, x):

1. If $\sigma = 0$:

(a) Parse $k_0$ as $k_0 = (pp_0, pp_1, msk_0, msk_1)$.

(b) Set $r_0 \leftarrow \text{Eval}(pp_0, msk_0, x)$.

(c) Set $r_1 \leftarrow \text{Eval}(pp_1, msk_1, x)$.

(d) Set $y_0 \leftarrow (r_0, r_1)$.

(e) Output $y_0$.

2. If $\sigma = 1$:

(a) Parse $k_1$ as $k_1 = (\text{ck}_0, \text{ck}_1, k, pp_0, pp_1)$.

(b) Compute $b := F(k, x)$.

(c) Compute $r \leftarrow \text{CEval}(pp_b, ck_b, x)$.

(d) Set $y_1 \leftarrow (b, r)$.

(e) Output $y_1$.
**Fig. 10.** Pre-Computable wPCF/PCF for OT from CPRF supporting (w)PRF constraints and their opposite.

**Theorem 4 (PCF from CPRF supporting (w)PRF constraints and their opposite).**

Assume the existence of the following primitives:

- $F: K_\lambda \times \mathcal{X}_\lambda \to \{0,1\}$ is a $(Q, T, \epsilon)$-secure weak (resp. strong) PRF; we denote $\bar{F}: K_\lambda \times \mathcal{X}_\lambda \to \{0,1\}$ the function defined by $\forall k \in K_\lambda, \forall x \in \mathcal{X}_\lambda, \bar{F}(k, x) := 1 - F(k, x)$;

- CPRF = (KeyGen, Eval, Constrain, CEval) is a $(Q', T', \epsilon')$-secure $\delta$-correct CPRF with output space $\mathcal{M}$ supporting the class of constraints $\{F(k, \cdot): k \in K_\lambda\} \cup \{\bar{F}(k, \cdot): k \in K_\lambda\} \cup \{\mathbf{1}\}$ (1 denotes here the constant circuit rejecting all points). Let $c \in \mathbb{N}$ be a constant such that KeyGen, Eval, Constrain, and CEval all run in time $n^c$.

Then the construction of fig. 10 is a $(\min\{Q, 2Q'\}, \min\{T - 2n^c, T' - Q''n^c\}, \epsilon + 2\epsilon' + \min\{Q, 2Q'\} \cdot \delta)$-secure weak (resp. strong) precomputable PCF for OT correlations. The message space of the OT correlations is the output space of CPRF.

*Proof.* We deal with the case where $F$ is only assumed to be a weak PRF (and consequently we only need to prove that Figure 10 is a weak PCF), but the case where $F$ is a strong PRF is completely analogous.

Let $(Q'', T'', \epsilon'') := (\min\{Q, 2Q'\}, \min\{T, T'\}, \epsilon + 2\epsilon' + \min\{Q, 2Q'\} \cdot \delta)$. Since the construction of Figure 10 provides PCF.Gen$_0$ and PCF.Gen$_1$ explicitly, precomputability follows from definition. It therefore suffices to show that (PCF.Gen, PCF.Eval) is a $(T'', Q'', \epsilon'')$-secure PCF, where PCF.Gen is defined as:

$$ \text{PCF.Gen}(1^{\lambda}) : (k_0, \text{aux}) \stackrel{\$}{\leftarrow} \text{PCF.Gen}_0(1^{\lambda}); k_1 \stackrel{\$}{\leftarrow} \text{PCF.Gen}_1(1^{\lambda}, k_0, \text{aux}); \text{Output } (k_0, k_1). $$

- Weakly Pseudorandom OT-Correlated Outputs. Let $\mathcal{A}$ be an adversary that runs in time $T''$. We prove that

$$ | \Pr[\text{Exp}_{\mathcal{A}, Q'', 0}^{w-pr}(\lambda) = 1] - \Pr[\text{Exp}_{\mathcal{A}, Q'', 1}^{w-pr}(\lambda) = 1] | \le \epsilon'', $$

where:

$\text{Exp}_{\mathcal{A}, Q'', 0}^{w-pr}(\lambda):$

For $i = 1, \dots, Q''(\lambda):$
$x^{(i)} \stackrel{\$}{\leftarrow} \mathcal{X}_{\lambda}$
$b^{(i)}, r_0^{(i)}, r_1^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}$
$y_0^{(i)} \leftarrow (r_0^{(i)}, r_1^{(i)}); y_1^{(i)} \leftarrow (b^{(i)}, r_{b^{(i)}}^{(i)})$
$b \leftarrow \mathcal{A}(1^{\lambda}, (x_0^{(i)}, y_0^{(i)}, y_1^{(i)})_{i \in [Q''(\lambda)]})$
Output $b$

$\text{Exp}_{\mathcal{A}, Q'', 1}^{w-pr}(\lambda):$

(k$_0$, k$_1$) $\leftarrow$ PCF.Gen(1$^{\lambda}$)
For $i = 1, \dots, Q''(\lambda):$
$x^{(i)} \stackrel{\$}{\leftarrow} \mathcal{X}_{\lambda}$
for $\sigma \in \{0, 1\}$, $y_{\sigma}^{(i)} \leftarrow$ PCF.Eval($\sigma, k_{\sigma}, x^{(i)}$)
$b \leftarrow \mathcal{A}(1^{\lambda}, (x^{(i)}, y_0^{(i)}, y_1^{(i)})_{i \in [Q''(\lambda)]})$
Output $b$

Consider the following sequence of hybrids:

* **Hybrid 1:** This is the real-world experiment $\text{Exp}_{\mathcal{A}, Q'', 1}^{w-pr}(\lambda)$.

* **Hybrid 2:** For all $i \in [Q''(\lambda)]$, replace "$y_1^{(i)} \leftarrow$ PCF.Eval(1, k$_1$, $x^{(i)}$)" with:

1. Parse $k_1 = (ck_0, ck_1, k, pp_0, pp_1)$

2. Compute $b^{(i)} := F(k, x^{(i)})$

3. Set $r^{(i)} \leftarrow y_0^{(i)}[b^{(i)}]$ (i.e. $r^{(i)} \leftarrow y_0^{(i)}$ first if $b^{(i)} = 0$, and $r^{(i)} \leftarrow y_0^{(i)}$ second if $b^{(i)} = 1$)

4. Set $y_1^{(i)} \leftarrow (b^{(i)}, r^{(i)})$

5. Output $y_1^{(i)}$

Observe that the only difference between hybrids 1 and 2 is whether $y_1^{(i)}$ is generated using CPRF.CEval (in hybrid 1) or CPRF.Eval (in hybrid 2). For $i \in [Q'']$, let $E_i$ denote the event "$y_0^{(i)}[b^{(i)}] = r^{(i)}$" (where the random variables $y_0^{(i)}$, $b^{(i)}$, and $r^{(i)}$ are those from hybrid 1). By the $\delta$-correctness of CPRF, $\forall i \in [Q''], \Pr[E_i] \ge 1 - \delta$, and further consider the event $E := \cap_{i \in [Q'']} E_i$. Observe that $\Pr[\text{Hyb}_1 = 1|E] = \Pr[\text{Hyb}_2 = 1]$. Finally, by the law of total
probability:

$$
\begin{align*}
| \Pr[\text{Hyb}_1 = 1] - \Pr[\text{Hyb}_2 = 1] | &= | \Pr[\text{Hyb}_1 = 1 | E] \cdot \Pr[E] + | \Pr[\text{Hyb}_1 = 1 | \bar{E}] \cdot \Pr[\bar{E}] \\
&\quad - \Pr[\text{Hyb}_2 = 1] | \\
&= | \Pr[\text{Hyb}_1 = 1 | \bar{E}] \cdot \Pr[\bar{E}] - \Pr[\text{Hyb}_2 = 1] \cdot (1 - \Pr[E]) | \\
&= | \Pr[\text{Hyb}_1 = 1 | \bar{E}] - \Pr[\text{Hyb}_2 = 1] | \cdot (1 - \Pr[E]) \\
&\le (1 - \Pr[E]) \le Q''\delta. \tag{1}
\end{align*}
$$

*   **Hybrid 3:** For all $i \in [Q'']$, replace $y_0^i \leftarrow \text{PCF.Eval}(0, k_0, x^{(i)})$ with:

1.  Parse $k_0 = (pp_0, pp_1, msk_0, msk_1)$

2.  Compute $b^{(i)} := F(k, x^{(i)})$

3.  Sample $r_{1-b^{(i)}}^{(i)} \stackrel{\$}{\leftarrow} \mathcal{M}$

4.  Set $r_{b^{(i)}}^{(i)} \leftarrow \text{Eval}(pp_{b^{(i)}}, \text{msk}_{b^{(i)}}, x)$

5.  Set $y_0 \leftarrow (r_0, r_1)$

6.  Output $y_0$

By the security of CPRF, evaluations of the master key msk<sub>1-b<sup>(i)</sup></sub> on constrained points are pseudorandom from the point of view of an adversary given a constrained key. It follows that |Pr[Hyb<sub>3</sub> = 1] - Pr[Hyb<sub>4</sub> = 1]| ≤ ε'.

*   **Hybrid 4:** For all $i \in [Q'']$, replace $r_{b^{(i)}} \leftarrow \text{Eval}(pp_{b^{(i)}}, \text{msk}_{b^{(i)}}, x)$ with $r_{b^{(i)}}^{(i)} \stackrel{\$}{\leftarrow} \mathcal{M}$.

Because **1** is in the constraint class, by CPRF security, the outputs of CPRF.Eval must be pseudorandom from the point of view of an external adversary who is not given any CPRF constrained key. It follows that $|\Pr[\text{Hyb}_3 = 1] - \Pr[\text{Hyb}_4 = 1]| \le \epsilon'$.

*   **Hybrid 5:** For all $i \in [Q'']$, replace $b^{(i)} := F(k, x^{(i)})$ with $b^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}$. Consider the following adversary B, whose goal is to attack the PRF F. $B((x_i, b_i)_{i \in [Q'']})$:

1.  $(k_0, k_1) \stackrel{\$}{\leftarrow} \text{PCF.Gen}_0$ (where PCF is the construction of fig. 10)

2.  For $i \in [Q'']$, Sample $r_0^{(i)}, r_1^{(i)} \leftarrow \{0, 1\}$

3.  Output $\mathcal{A}(1^{\lambda}, (x^{(i)}, r_0^{(i)}, r_1^{(i)})_{i \in [Q'']})$

Because $\mathcal{A}$ runs in time $T'' \le T - 2n^c$, $\mathcal{B}$ runs in time at most $T$ and therefore by $(Q, T, \epsilon)$-security if the wPRF F:

$$
\left| \Pr \left[ \mathcal{B}((x_i, b_i)_{i \in [Q'']}) = 1 : \begin{array}{l} x_i \stackrel{\$}{\leftarrow} \mathcal{X}_{\lambda} \\ b_i \stackrel{\$}{\leftarrow} \{0, 1\} \end{array} \right] - \Pr \left[ \mathcal{B}((x_i, b_i)_{i \in [Q'']}) = 1 : \begin{array}{l} x_i \stackrel{\$}{\leftarrow} \mathcal{X}_{\lambda} \\ b_i \leftarrow F(k, x_i) \end{array} \right] \right| \le \epsilon .
$$

This is exactly saying that $|\Pr[\text{Hyb}_4 = 1] - \Pr[\text{Hyb}_5 = 1]| \le \epsilon$.

*   **Hybrid 6:** This is the ideal-world experiment $\text{Exp}_{A,Q'',0}^{w-pr}(\lambda)$. Observe that hybrids 5 and 6 are code-equivalent.

By combining all of the above hybrids $|\Pr[\text{Exp}_{A,Q'',0}^{w-pr}(\lambda) = 1] - \Pr[\text{Exp}_{A,Q'',1}^{w-pr}(\lambda) = 1]| \le \epsilon''$.

-  Weak PCF Security: Let $\mathcal{A}$ be a time-$T''$ adversary. We need to show that $|\Pr[\text{Exp}_{A,Q'',\sigma,0}^{w-sec}(\lambda) = 1] - \Pr[\text{Exp}_{A,Q'',\sigma,1}^{w-sec}(\lambda) = 1]| \le \epsilon''$, where:

$\text{Exp}_{A,Q'',\sigma,0}^{w-sec}(\lambda):$

$$(k_0, k_1) \leftarrow \text{PCF.Gen}(1^{\lambda})$$

For $i = 1, \dots, N(\lambda)$:

$x^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}^{n(\lambda)}$

$y_{\sigma}^{(i)} \stackrel{\$}{\leftarrow} \text{wPCF.Eval}(\sigma, k_{\sigma}, x^{(i)})$

$y_{1-\sigma}^{(i)} \stackrel{\$}{\leftarrow} \text{RSample}(1^{\lambda}, \sigma, y_{\sigma}^{(i)})$

*

$b \leftarrow \mathcal{A}(1^{\lambda}, \sigma, k_{\sigma}, (x^{(i)}, y_{1-\sigma}^{(i)})_{i \in [N(\lambda)]})$

Output b

$\text{Exp}_{A,Q'',\sigma,1}^{w-sec}(\lambda):$

$$(k_0, k_1) \leftarrow \text{PCF.Gen}(1^{\lambda})$$

For $i = 1, \dots, Q''$:

$x^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}^{n(\lambda)}$

$y_{1-\sigma}^{(i)} \stackrel{\$}{\leftarrow} \text{wPCF.Eval}(1 - \sigma, k_{1-\sigma}, x^{(i)})$

$b \leftarrow \mathcal{A}(1^{\lambda}, \sigma, k_{\sigma}, (x^{(i)}, y_{1-\sigma}^{(i)})_{i \in [Q'']})$

Output b

Recall that for OT correlations (with message space $\mathcal{M}$), RSample is defined as follows.

RSample(1<sup>λ</sup>, σ, y<sub>σ</sub>) :
• If $\sigma = 0$:

* Sample $b \stackrel{\$}{\leftarrow} \{0, 1\}, r \stackrel{\$}{\leftarrow} \mathcal{M}$

* Output $y_{1-\sigma} = (b, r)$

• If $\sigma = 1$:

* Parse $y_{\sigma}$ as $y_{\sigma} = (b, r_b)$

* Sample $r_{1-b} \stackrel{\$}{\leftarrow} \mathcal{M}$

* Output $y_{1-\sigma} = (r_0, r_1)$

• If $\sigma = 0$: The only difference between $\text{Exp}_{A,Q'',0,0}^{\text{w-sec}}(\lambda)$ and $\text{Exp}_{A,Q'',0,1}^{\text{w-sec}}(\lambda)$ is whether the $(y_1^{(i)}, \text{first})_{i \in [Q'']}$ are sampled truly at random or using a PRF (whose key is unknown to $\mathcal{A}$). By security of the PRF $F$, we immediately get $|\text{Pr}[\text{Exp}_{A,Q'',0,0}^{\text{w-sec}}(\lambda) = 1] - \text{Pr}[\text{Exp}_{A,Q'',0,1}^{\text{w-sec}}(\lambda) = 1]| \le \epsilon$.

• If $\sigma = 1$: The only difference between the two experiments is whether $(y_0^{(i)}[1 - b^{(i)}])_{i \in [Q'']}$ are sampled uniformly at random from $\mathcal{M}$, or are computed as $y_0^{(i)}[1 - b^{(i)}] \leftarrow \text{CPRF.Eval}(\text{pp}_{1-b^{(i)}}, \text{msk}_{1-b^{(i)}}, x^{(i)})$. By design, for all $i \in [Q'']$, it holds that $F(k, x^{(i)}) = b^{(i)}$ (i.e. $\bar{F}(k, x^{(i)}) = 1 - b^{(i)}$). Therefore, whether $b^{(i)} = 0$ or $b^{(i)} = 1$, $x^{(i)}$ is unauthorised for the key $\text{ck}_{1-b^{(i)}}$. By invoking CPRF security twice (once with respect to $\text{msk}_0$ and one with respect to $\text{msk}_1$), $|\text{Pr}[\text{Exp}_{A,Q'',1,0}^{\text{w-sec}}(\lambda) = 1] - \text{Pr}[\text{Exp}_{A,Q'',1,1}^{\text{w-sec}}(\lambda) = 1]| \le 2\epsilon'$.

Therefore $\forall \sigma \in \{0, 1\}, |\text{Pr}[\text{Exp}_{A,Q'',\sigma,0}^{\text{w-sec}}(\lambda) = 1] - \text{Pr}[\text{Exp}_{A,Q'',\sigma,1}^{\text{w-sec}}(\lambda) = 1]| \le \epsilon''$.

□

## PCF for OT from 1-in-2 Pseudorandomly Constrained PRF.

### 1-in-2 Pseudorandomly Constrained PRF.

**Definition 12 (1-in-2 Pseudorandomly Constrained PRF).** A weakly/strongly pseudorandomly constrained PRF (PR-CPRF) is a constrained PRF with domain $\{0, 1\}^{n(\lambda)}$ that supports the class of constraints of the form:

$$ \mathcal{C}_{\lambda} = \left\{ \begin{array}{ll} C_k: \{0,1\}^{n(\lambda)} \rightarrow \{0,1\} & : k \in \mathcal{K}_{\lambda} \\ x_0 \dots x_{n-1} \mapsto F_{in}(k, x_0 \dots x_{n-2}) \oplus x_{n-1} & \end{array} \right\} $$

where $F_{in}: \mathcal{K}_{\lambda} \times \{0,1\}^{n(\lambda)-1} \rightarrow \{0,1\}$ is a weak/strong pseudorandom function.

When convenient, we will refer to the constrained PRF as the outer PRF and $F_{in}$ as the inner PRF.

### PCF for OT from 1-out-of-2 Pseudorandomly Constrained PRF.

**Theorem 5 (PCF for OT from PR-CPRF).** Assuming the existence of a weakly/strongly 1-in-2 pseudorandomly constrained PRF, the construction of fig. 11 is a pre-computable weak/strong PCF for OT correlations.

## PCF Precomputable PCF for OT from PR-CPRFs

**Requires:** PR-CPRF = (KeyGen, Eval, Constrain, CEval) is a weakly/strongly pseudorandomly constrained PRF with input space $\{0, 1\}^{n(\lambda)+1}$ and characterized by inner weak/strong PRF $F_{in}: \mathcal{K}_{\lambda} \times \{0, 1\}^{n(\lambda)} \rightarrow \{0, 1\}$.

PCF.Gen$_0(1^{\lambda})$:

1. Run (pp, msk) $\stackrel{\$}{\leftarrow}$ KeyGen(1$^{\lambda}$).

2. Set and output $k_0 = (\text{pp}, \text{msk})$.

PCF.Gen$_1(1^{\lambda}, k_0)$:

1. Sample $k \stackrel{\$}{\leftarrow} \mathcal{K}_{\lambda}$.

2. Parse $k_0 = (\text{pp}, \text{msk})$.

3. Run $\text{ck} \leftarrow \text{Constrain}(\text{msk}, C_k)$.

4. Set and output $k_1 = (\text{ck}, k, \text{pp})$.
PCF.Eval(1^λ, σ, k_σ, x = (x_0...x_{n-1})):

1. If $\sigma = 0$:

(a) Parse $k_0 = (\mathit{pp}, \mathit{msk})$.

(b) Compute $r_0 \leftarrow \text{Eval}(\mathit{pp}, \mathit{msk}, x_0 \dots x_{n-1})$.

(c) Compute $r_1 \leftarrow \text{Eval}(\mathit{pp}, \mathit{msk}, x_0 \dots x_{n-1})$.

(d) Set and output $y_0 \leftarrow (r_0, r_1)$.

2. If $\sigma = 1$:

(a) Parse $k_1 = (\mathit{ck}, k, \mathit{pp})$.

(b) Compute $b \leftarrow F_{\text{in}}(k, x_0 \dots x_{n-1})$.

(c) Compute $r \leftarrow \text{CEval}(\mathit{pp}, \mathit{ck}, x_0 \dots x_{n-1}b)$.

(d) Run and output $y_1 \leftarrow (b, r)$.

<caption>Fig. 11. Pre-Computable wPCF/PCF for OT from weakly/strongly PR-CPRF.</caption>

## 5.2 Pseudorandom Constraints Expressed as IPM

As discussed in section 4, the Naor-Reingold PRF can be adapted into a CPRF supporting inner-product membership constraints. In this section, we show that the class of “inner-product membership” is expressive enough to capture the various notions of pseudorandom constraints used in section 5.1. As a direct corollary, this yields PCFs for OT correlations from the Naor-Reingold CPRF.

**IPM-wPRF.** We define the notion of “inner-product membership (weak) PRF” (IPM-PRF) as a (weak) PRF whose evaluation is performed by checking whether the inner product between (some public function of) the key and (some public function of) the input belongs to some public set.

**Definition 13 (Inner-Product Membership weak PRF, IPMwPRF).** Let $\ell(\cdot) : \mathbb{N}^* \to \mathbb{N}^*$. Let $\langle \cdot, \cdot \rangle : \mathbb{Z}^{\ell(\lambda)} \times \mathbb{Z}^{\ell(\lambda)} \to \mathbb{Z}$ denote the usual inner-product over $\mathbb{Z}^{n(\lambda)}$. An *Inner-Product Membership weak Pseudorandom Function* (IPM-wPRF) $F_\lambda: \mathcal{K}_\lambda \times \mathcal{X}_\lambda \to \{0, 1\}$ is one parameterised by a collection $\{S_\lambda\}_{\lambda \in \mathbb{N}}$ of polynomial-size subsets of $\mathbb{Z}$, and two collections of functions $\{f_\lambda : \mathcal{X}_\lambda \to \mathbb{Z}^{\ell(\lambda)}\}_{\lambda \in \mathbb{N}}$ and $\{g_\lambda : \mathcal{K}_\lambda \to \mathbb{Z}^{\ell(\lambda)}\}_{\lambda \in \mathbb{N}}$ (where $M(\lambda)$ is some polynomial-size bound we assume to be included in the descriptions of the $f_\lambda$ and the $g_\lambda$) which define it semantically in the following way:

$$ \forall \lambda \in \mathbb{N}, \forall k \in \mathcal{K}_{\lambda}, \forall x \in \mathcal{X}_{\lambda}, F_{\lambda}(k, x) = \begin{cases} 0 & \text{if } \langle f_{\lambda}(x), g_{\lambda}(k) \rangle \in S_{\lambda} \\ 1 & \text{otherwise.} \end{cases} $$

We say that an IPM-wPRF is $(Q, T, \epsilon)$-secure if it is a $(Q, T, \epsilon)$-secure weak PRF.

**Remark 3 (The opposite of an IPM-wPRF is an IPM-wPRF).** The opposite of an IPM-wPRF $F_\lambda$ parameterised by $\{S_\lambda\}_{\lambda \in \mathbb{N}}$, $\{f_\lambda\}_{\lambda \in \mathbb{N}}$, and $\{g_\lambda\}_{\lambda \in \mathbb{N}}$ is the IPM-wPRF parameterised by $\{[0, \ell(\lambda) \cdot M^2(\lambda)] \setminus S_\lambda\}_{\lambda \in \mathbb{N}}$, $\{f_\lambda\}_{\lambda \in \mathbb{N}}$, and $\{g_\lambda\}_{\lambda \in \mathbb{N}}$. In particular, the existence of a CPRF supporting as constraint $\{F(k, \cdot) : k \in \mathcal{K}_\lambda\}$ is equivalent to that of a CPRF supporting as constraint $\{F(k, \cdot) : k \in \mathcal{K}_\lambda\} \cup \{1 - F(k, \cdot) : k \in \mathcal{K}_\lambda\}$.

One of the downsides of the PCF construction of fig. 9 is that it requires the ability to constrain a CPRF both with respect to a (w)PRF and its opposite. Remark 3 implies that a CPRF supporting the class of inner-product membership constraints can be used in conjunction with an IPM-wPRF to instantiate the template of fig. 9.

**Antiperiodic Optimization.** In this section we introduce a sufficient condition for a IPM-wPRFs to yield a “1-in-2 pseudorandom selection circuit” which can itself be expressed as inner-product membership. Such IPM-wPRFs are well-suited to instantiate the template of fig. 10.

**Definition 14 (Antiperiodic<fnref n="13" /> Set).** Let $\Delta \in \mathbb{N}^*$ and $q \in \mathbb{N}^*$. We say a bounded set of integers $S \subseteq \mathbb{Z}_q$ is $\Delta$-antiperiodic if for all $n \in \mathbb{Z}_q$, $n \in S \Leftrightarrow (n+\Delta) \notin S$. We say a set $S \subseteq \mathbb{Z}_q$ is antiperiodic if there exists $\delta \in \mathbb{N}^*$ such that $S$ is $\delta$-antiperiodic.

<footnote n="13">¹³ The rationale for the terminology is that a, up to defining booleans as $\{-1, +1\}$, a set is $(\Delta)$-antiperiodic if and only its indicator function is. Recall a function $f$ is $\Delta$-antiperiodic if $\forall x \in D_f, f(x + \Delta) \neq f(x)$.</footnote>
**Definition 15 (Antiperiodic IPM-wPRF).** Let $\Delta \in \mathbb{N}^*$. We say an IPM-wPRF $F$, parameterised by the collection of sets $\{S_\lambda\}_{\lambda \in \mathbb{N}^*}$, is $(\Delta)$-antiperiodic if for all $\lambda \in \mathbb{N}^*$, $S_\lambda$ is.

**Observation 1 (Antiperiodic Optimization)** Let $\Delta \in \mathbb{N}^*$. If $F$ is a $\Delta$-antiperiodic IPM-wPRF (parameterised by $f_\lambda, g_\lambda, S_\lambda$) then for all $k \in K_\lambda$, the circuit $C_k: \{0,1\}^{n(\lambda)} \to \{0,1\}$, $x_0 \dots x_{n-1} \mapsto F(k, x_0 \dots x_{n-2}) \oplus x_{n-1}$ satisfies:

$$C_k(x) = 0 \Leftrightarrow \langle (f_\lambda(x_0, \dots, x_{n-2}) \| x_{n-1}), (g_\lambda(k) \| \delta) \rangle \in S_\lambda.$$

In particular, assuming the existence of an antiperiodic IPM-wPRF and that of a CPRF supporting inner-product membership constraints, there exists a 1-in-2 pseudorandomly constrained PRF (definition 12).

*Proof.*

$$\begin{align*}
C_k(x) = 0 &\Leftrightarrow F(k, x_0 \dots x_{n-2}) = x_{n-1} \\
&\Leftrightarrow F(k, x_0 \dots x_{n-2}) = x_{n-1} = 0 \lor F(k, x_0 \dots x_{n-2}) = x_{n-1} = 1 \\
&\Leftrightarrow [\langle f_\lambda(x_0, \dots, x_{n-2}), g_\lambda(k) \rangle \in S_\lambda \land x_{n-1} = 0] \\
&\qquad \lor [\langle f_\lambda(x_0, \dots, x_{n-2}), g_\lambda(k) \rangle \notin S_\lambda \land x_{n-1} = 1] \\
&\Leftrightarrow \langle (f_\lambda(x_0, \dots, x_{n-2}) \| x_{n-1}), (g_\lambda(k) \| \delta) \rangle \in S_\lambda.
\end{align*}$$

The second part of the observation, regarding the existence of a PCF, is a direct corollary of theorem 5.

□

## 5.3 Candidate IPM-wPRF

LWR-based IPM-wPRF candidates. Banerjee, Peikert, and Rosen [BPR12] provided the following weak PRF candidate, whose security can be reduced to the LWR assumption:

$$F_k(x) := \lfloor \langle \mathbf{k}, x \rangle \rfloor_p, \text{ where } \mathbf{k}, x \in \mathbb{Z}_q^n \text{ and } q \gg p \ (\lfloor X \rfloor_p \text{ denotes the closest integer to } X \cdot p/q).$$

**Lemma 1 (IPM-wPRF from Poly-Modulus LWR).** Let $q$ be a polynomial-size modulus. Assuming LWR$_{q,2}$, there is an IPM-wPRF whose membership set $S_\lambda$ has size $\lceil q/2 \rceil$.

*Proof.* If $q$ is polynomial and $p = 2$, then the candidate wPRF can be cast as an IPM-wPRF parameterised by $\ell(\lambda) := n(\lambda)$, $S_\lambda := \mathbb{Z}_q \cap p\mathbb{Z}$ (which is indeed polynomial-size when $q$ is polynomial).

□

Boneh, Ishai, Passelègue, Sahai, and Wu [BIP$^+$18] introduced a candidate weak PRF which can be seen as a special instance of LWR with constant-size composite modulus. The BIPSW wPRF is defined as:

$$F_k(x) := \sum_{i \in [n]} k_i x_i \mod 2 + \sum_{i \in [n]} k_i x_i \mod 3 \ (\mod 2).$$

**Lemma 2 (The Boneh-Ishai-Passelègue-Sahai-Wu IPM-wPRF is Antiperiodic).** The BIPSW wPRF can be cast as a 3-antiperiodic IPM-wPRF whose membership set $S_\lambda$ has size $\lceil \frac{n}{2} \rceil$.

*Proof.* Observe that $F_k(x) = 0$ if and only if $\langle k, x \rangle \mod 6 \in \{3, 4, 5\}$, and therefore this can be cast as an IPM-wPRF where $\ell(\lambda) := n(\lambda)$, $S_\lambda := [0, n(\lambda)] \cap (6\mathbb{Z} + \{0, 1, 2\})$. □

IPM-wPRF based on random CSPs. Let $d = \Theta(\log n)$, and let $P: \{0,1\}^d \to \{0,1\}$ be an appropriately chosen balanced predicate. Let in $:= \lceil \log(n!/d!) \rceil$ (this will be the input length of the wPRF), and consider any polytime-computable function $I: \{0,1\}^{\mathrm{in}} \to A_{[n]}^d$, $x \mapsto I_x$, where $A_{[n]}^d \subseteq [n]^d$ denotes the set of all arrangements (i.e. ordered subsets taken without repetitions) of $d$ elements from $[n]$. We require that every element of $A_{[n]}^d$ admits a unique pre-image by $I$, but $I$ is allowed to be undefined for some elements of $\{0,1\}^{\mathrm{in}}$. Such a function exists, and will be viewed as input-preprocessing allowing us to interpret a bit string as arrangement of $d$ elements of $[n]$. The Goldreich-Applebaum-Raykov wPRF [Gol00, AR16] can be defined by:

$$F: \{0,1\}^n \times \{0,1\}^{\mathrm{in}} \to \{0,1\} \\ (k,x) \mapsto P(k_{I_x[0]}, \dots, k_{I_x[d-1]}).$$
A predicate of particular interest is the XOR-MAJ predicate [Gol00, AL16]. Define $MAJ_s: \{0,1\}^s \to \{0,1\}, (x_1, \dots, x_s) \mapsto (\sum_{i=1}^s x_i \ge s/2)$ and XOR-MAJ$_{s,t}$: $\{0,1\}^{s+t} \to \{0,1\}, (x_1, \dots, x_{s+t}) \mapsto x_1 \oplus \dots \oplus x_s \oplus MAJ_\ell(x_{s+1}, \dots, x_{s+t})$. The “Goldreich-Applebaum-Raykov wPRF with d-local XOR-MAJ$_{s,t}$ predicate” is defined as follows:

$$F: \{0,1\}^n \times \{0,1\}^\text{in} \to \{0,1\} \\ (k,x) \mapsto \text{XOR-MAJ}_{s,t}(k_{I_x[0]}, \dots, k_{I_x[s+t-1]})$$

**Lemma 3 (The Goldreich-Applebaum-Raykov wPRF is an IPM-wPRF).** *The following statements hold:*

1. Goldreich-Applebaum-Raykov wPRF (with any low-locality predicate). If $P$ is any $d$-local balanced predicate, the GAR wPRF can be cast as an IPM-wPRF parameterised by a membership set $S_\lambda$ of size $2^{d-1}$.

2. Goldreich-Applebaum-Raykov wPRF (optimized for the XOR-MAJ predicate). If $P$ is the XOR-MAJ$_{s,t}$ predicate, the GAR wPRF can be cast as an IPM-wPRF parameterised by a membership set $S_\lambda$ of size $2 \cdot [s/2] \cdot [t/2]$.

*Proof.*

1. Let $\text{Supp}(P) := \{v \in \mathbb{Z}_{2^d}: P(\text{IntToBitString}(v)) = 1\}$. Observe that:

$$ 
\begin{align} 
F(k, x) = 0 &\Leftrightarrow P(k_{I_x[1]}, \dots, k_{I_x[d]}) = 0 \nonumber \\ 
&\Leftrightarrow \text{BitStringToInt}(k_{I_x[0]}, \dots, k_{I_x[d-1]}) \notin \text{Supp}(P) \tag{2} \\ 
&\Leftrightarrow k_{I_x[0]} \cdot 1 + \dots + k_{I_x[d-1]} \cdot 2^{d-1} \notin \text{Supp}(P) \nonumber \\ 
&\Leftrightarrow \langle k, f(x) \rangle \in \mathbb{Z}_{2^d} \setminus \text{Supp}(P) \nonumber 
\end{align} 
$$

$$ \text{where } f: \{0,1\}^\text{in} \to \mathbb{Z}_{2^d}^n, x \mapsto \sum_{i=0}^{d-1} 2^i \cdot \mathbf{1}_{I_x[i]} . $$

The Goldreich-Applebaum-Raykov wPRF can therefore be cast as an IPM-wPRF parameterised by $\ell := n, S_\lambda := \mathbb{Z}_{2^d} \setminus \text{Supp}(P), f_\lambda := f$, and $g_\lambda := \text{Id}$. Note that because $P$ is a balanced predicate, $|\text{Supp}(P)| = 2^{d-1}$, and that because $d = \Theta(\log n)$, $|S_\lambda| = n^{\mathcal{O}(1)}$.

2. Observe that:

$$ 
\begin{align} 
F_k(x) = 0 &\Leftrightarrow \text{XOR}(k_{I_x[0]}, \dots, k_{I_x[s-1]}) = \text{MAJ}_t(k_{I_x[s]}, \dots, k_{I_x[s+t-1]}) \nonumber \\ 
&\Leftrightarrow [\text{XOR}(k_{I_x[0]}, \dots, k_{I_x[s-1]}) = 0 \land \text{MAJ}_t(k_{I_x[s]}, \dots, k_{I_x[s+t-1]}) = 0] \nonumber \\ 
&\lor [\text{XOR}(k_{I_x[0]}, \dots, k_{I_x[s-1]}) = 1 \land \text{MAJ}_t(k_{I_x[s]}, \dots, k_{I_x[s+t-1]}) = 1] . \tag{3} 
\end{align} 
$$

Further observe that:

$$ 
\begin{align} 
\text{XOR}(k_{I_x[0]}, \dots, k_{I_x[s-1]}) &= [<1^s, (k_{I_x[0]}, \dots, k_{I_x[s-1]})> \bmod 2] \tag{4} \\ 
&= [<\mathbf{1}_{I_x[0, s-1]}, k> \bmod 2] \nonumber 
\end{align} 
$$

and that

$$ 
\begin{align} 
\text{MAJ}_t(k_{I_x[s]}, \dots, k_{I_x[s+t-1]}) &= [(<1^t, (k_{I_x[s]}, \dots, k_{I_x[s+t-1]})> \ge t/2] \tag{5} \\ 
&= [<\mathbf{1}_{I_x[s, s+t-1]}, k> \ge t/2] . \nonumber 
\end{align} 
$$

By combining eqs. (3) to (5), we obtain:

$$ 
\begin{align} 
F_k(x) = 1 &\Leftrightarrow [<k, \mathbf{1}_{I_x[0, s-1]}> \equiv 0 \bmod 2 \land <k, \mathbf{1}_{I_x[s, s+t-1]}> <t/2] \nonumber \\ 
&\lor [<k, \mathbf{1}_{I_x[0, s-1]}> \equiv 1 \bmod 2 \land <k, \mathbf{1}_{I_x[s, s+t-1]}> \ge t/2] \nonumber \\ 
&\Leftrightarrow [<\mathbf{1}_{I_x[0, s-1]} + (t+1) \cdot \mathbf{1}_{I_x[s, s+t-1]}, k> \in S_{\text{XOR-MAJ}}] \nonumber 
\end{align} 
$$

$$ \text{where } S_{\text{XOR-MAJ}} := \{r + (t+1) \cdot q : (q,r) \in (Q_0 \times R_0) \cup (Q_1 \times R_1)\} $$

$$ \text{with } Q_0 := [0, [s/2] - 1], Q_1 := [[s/2], s - 1], $$

$$ \text{and } R_b := \{r \in [0, t-1] : r \equiv b \bmod 2\} \text{ (for } b \in \{0,1\}). $$
The Goldreich-Applebaum-Raykov wPRF with XOR-MAJ predicate can therefore be cast as an IPM-wPRF parameterised by $\ell := n$, $S_\lambda := S_{\text{XOR-MAJ}}$, $f_\lambda: \{0,1\}^n \to \{0,1\}^n$, $x \mapsto \mathbf{1}_{x[0,s-1]} + (t+1) \cdot \mathbf{1}_{x[s,s+t-1]}$ (in other words, $f_\lambda$ maps $x$ to the length-$n$ vector with $1$ in positions $I_x[0], \dots, I_x[s-1]$, with $(t+1)$ in positions $I_x[s], \dots, I_x[s+t-1]$, and with $0$ everywhere else), and $g_\lambda := \text{Id}$. Finally, note that $|S_{\text{XOR-MAJ}}| = |Q_0| \cdot |R_0| + |Q_1| \cdot |R_1| \le 2 \cdot \lfloor \frac{s}{2} \rfloor \cdot \lfloor \frac{t}{2} \rfloor$.

□

As described in the proof of lemma 3, the Goldreich-Applebaum-Raykov IPM-wPRF with XOR-MAJ$_{s,t}$ predicate is almost $(t+1)$-antiperiodic. The set $S_{\text{XOR-MAJ}}$ is represented in fig. 12.

<figure><img src="image_7.png" /><figcaption>Fig. 12. Representation of the (inner-product) membership set of the GAR IPM-wPRF with XOR-MAJ predicate. Considering the membership set $[-\lfloor \frac{t}{2} \rfloor, 0] \cup S_{\text{XOR-MAJ}} \cup [(t+1) \cdot (s+1), (t+1) \cdot (s+1) + \lfloor \frac{t}{2} \rfloor]$ yields a $\delta$-antiperiodic IPM-wPRF.</figcaption></figure>

**Lemma 4 (The XOR-MAJ Goldreich-Applebaum-Raykov IPM-wPRF is Antiperiodic).**

The Goldreich-Applebaum-Raykov IPM-wPRF with predicate: XOR-MAJ$_{s,t}$ can be cast as a $(t+1)$-antiperiodic IPM-wPRF parameterised by a membership set of size $2 \cdot \lfloor s/2 \rfloor \cdot \lfloor t/2 \rfloor + (t+1)$.

## 5.4 Distributed Interactive Key Generation via MPC

In this section, we show that our PCF for OT correlations based on the Naor-Reingold PRF admits an efficient protocol for securely distributing the key-generation phase.

**Definitions.** We start by introducing in figs. 13 and 14 the ideal functionalities for the distributed key-generation and for 1-in-2 oblivious transfer.

**Functionality** PCF Distributed Key-Generation $\mathcal{F}_{\text{DKG}}$

**Parameters:** The ideal functionality Fsd is parameterised by a number of parties $N \ge 2$, and an $N$-party PCF PCF = (PCF.Gen, PCF.Eval) (for some correlation).

$\mathcal{F}_{\text{DKG}}$ interacts with parties $P_1, \dots, P_N$ in the following manner.

**Output:** Run $(k_1, \dots, k_N) \stackrel{\$}{\leftarrow} \text{PCF.Gen}(1^\lambda)$; Output $k_i$ to each party $P_i$ (for $1 \le i \le N$).

<caption>Fig. 13. Ideal functionality $\mathcal{F}_{\text{DKG}}$ for the distributed generation of PCF keys.</caption>
## Functionality Oblivious Transfer $\mathcal{F}_{\text{OT}}$

The functionality $\mathcal{F}_{\text{OT}}$ for 1-out-of-2 oblivious transfer is parameterised by a message space $\mathcal{M}$, and interacts with two parties $S$ (the sender) and $R$ (the receiver).

**Input:** Wait to receive (**sender**, **sid**, $m_0$, $m_1$) (where $m_0, m_1 \in \mathcal{M}$) from $S$ and (**receiver**, **sid**, $b$) (where $b \in \{0, 1\}$) from $R$.

**Output:** Send (**sid**, $m_b$) to $R$ and (**sid**) to $S$, then halt.

<caption>**Fig. 14.** Ideal functionality $\mathcal{F}_{\text{OT}}$ for 1-out-of-2 oblivious transfer.</caption>

**The Protocol.** The protocol, provided in fig. 15, revolves around the following observation. The key difficulty in generating the keys is that $P_1$, holding $z \in \{0,1\}^n$, must retrieve $(r^{-z_i} \cdot \alpha_i)_{i \in [n]}$ from $P_0$, without learning $(r^{-(1-z_i)} \cdot \alpha_i)_{i \in [n]}$. Our observation is that this can be performed efficiently using 1-out-of-2 OT, where $P_0$ acts as sender with messages $(\alpha_i, r^{-z_i}\alpha_i)$ and $P_1$ acts as receiver with selection bit $z_i$.

**Protocol** PCF Distributed Key-Generation $\Pi_{\text{DKG}}$ for the PCF of fig. 11 (parameterised by the CPRF of fig. 7)

**Parties:** $P_0, P_1$.

**Parameters:**

- $\text{sid}_1, \dots, \text{sid}_n$ are $n$ distinct session ids.

- Parameters for the CPRF (fig. 11): $G: \{0,1\}^{\lambda} \to \{0,1\}^{(n+2)\lambda}$ and $G': \{0,1\}^{\lambda} \to \{0,1\}^{2\lambda}$ are PRGs.

- Parameters for the PCF (fig. 7): $F := K_{\lambda} \times \mathcal{X}_{\lambda} \to \mathcal{M}_{\lambda}$ is a $\delta$-antiperiodic IPM-wPRF parameterised by membership set $S_{\lambda}$, input-preprocessing function $f_{\lambda}: \mathcal{X}_{\lambda} \to \{0,1\}^n$, and key-preprocessing function $g_{\lambda}: K_{\lambda} \to \{0,1\}^n$.

**Hybrid Model:** The protocol is defined in the $\mathcal{F}_{\text{OT}}$-hybrid model.

**The Protocol:**

1. Preprocessing Phase:

- $P_0$ does the following:

(a) Run $(\mathbb{G}, g, p) \stackrel{\$}{\leftarrow} \text{GenPar}(1^{\lambda})$.

(b) Sample seed $\stackrel{\$}{\leftarrow} \{0,1\}^{\lambda}$.

(c) Set msk $\leftarrow$ seed, $\text{pp} \leftarrow (\mathbb{G}, g, p)$, and $k_0 \leftarrow (\text{pp}, \text{msk})$.

(d) Compute $(a_0, \text{seed}_1, \dots, \text{seed}_{n+1}) \leftarrow G(\text{seed})$

(e) Sample $r \stackrel{\$}{\leftarrow} \mathbb{F}_p^*$

(f) For $s \in S$, compute $g_s \leftarrow g^{a_0 \cdot r^s}$

(g) For $i \in [n]$:

• Set $\tilde{\alpha}_i^{(0)} := \text{seed}_i$

• Set $\tilde{\alpha}_i^{(1)} := r^{-1} \cdot G'(\text{seed}_i)^a$

(h) Set $\tilde{\alpha}_{n+1}^{(1)} := r^{-\delta} \cdot G'(\text{seed}_{n+1})$

- $P_1$ does the following:

(a) Sample $k \stackrel{\$}{\leftarrow} K_{\lambda}$

(b) Set $z = (z_1, \dots, z_{n+1}) \leftarrow (g_{\lambda}(k), \delta)$

2. Interactive Phase:

- $P_0$ sends $(g_s)_{s \in S}$ to $P_1$
– For $i = 1...n$:

• $P_0$ sends ($\mathit{sender}, \mathit{sid}_i, \tilde{\alpha}_i^{(0)}, \tilde{\alpha}_i^{(1)}$) to $\mathcal{F}_{\mathit{OT}}$.

• $P_1$ sends ($\mathit{receiver}, \mathit{sid}_i, z_i$) to $\mathcal{F}_{\mathit{OT}}$ and waits to receive ($\mathit{sid}_i, m_i$).

– $P_0$ sends $\tilde{\alpha}_{n+1}^{(1)}$ to $P_1$

– $P_0$ sends $\mathit{pp}$ to $P_1$

3. **Output Phase:**

– $P_1$ sets $\mathit{ck} \leftarrow (m_1, \dots, m_n, \tilde{\alpha}_{n+1}^{(1)}, (g_s)_{s \in S}, \mathbf{z})$ and $k_1 \leftarrow (\mathit{ck}, k, \mathit{pp})$

– $P_0$ outputs $k_0$

– $P_1$ output $k_1$

**Fig. 15.** Two-party protocol for securely generating the keys of the PCF from fig. 11 (instantiated with the Naor-Reingold CPRF fig. 7).

**Theorem 6 (Secure PCF Key Generation).** The protocol of fig. 15 securely perfectly UC-securely realises the two-party functionality fig. 13 (as parameterised by the PCF of fig. 11, in turn instantiated with the CPRF of fig. 7) in the $\mathcal{F}_{\mathit{OT}}$-hybrid model, in the presence of a passive adversary statistically corrupting at most one of the parties. The protocol makes $n$ calls to the $\mathcal{F}_{\mathit{OT}}$ functionality and additionally uses $|S| \cdot \log|\mathbb{G}| + 2\lambda + \log|\mathit{pp}|$ bits of communication. The protocol requires a single round of communication (in the $\mathcal{F}_{\mathit{OT}}$-hybrid model).

*Proof.*

– Security against $P_0$. Perfect security against a corrupted $P_0$ follow from the fact they receive no messages (either from $P_1$ or from $\mathcal{F}_{\mathit{OT}}$) as well as the observation that the code defining $P_0$'s output $k_0$ can be parsed as being code-equivalent to $"k_0 \stackrel{\lambda}{\rightleftharpoons} \mathit{PCF}.\mathit{Gen}_0(1^\lambda)"$ (which is how the ideal functionality fig. 13 computes it). $P_0$'s view from the protocol can therefore be perfectly simulated.

– Security against $P_1$. To show perfect security against a corrupted $P_1$, let $\mathcal{A}$ be a semi-honest, static, adversary that interacts with parties $P_0, P_1$ running the protocol in the $\mathcal{F}_{\mathit{OT}}$-hybrid model. Consider the following simulator $S$, which runs internally a copy of $\mathcal{A}$.

• Simulating the communication with the environment $\mathcal{Z}$: $S$ writes every input value it receives from $\mathcal{Z}$ on $\mathcal{A}$'s input tape (as if coming from $\mathcal{A}$'s environment), and copies every value on $\mathcal{A}$'s output tape to $S$'s own output tape (to be read by $\mathcal{Z}$).

• Simulating the protocol's execution:

1. $S$ activates $\mathcal{A}$.

2. $S$ waits to receive $k_1$ from $\mathcal{F}_{\mathit{DKG}}$ (on behalf of $P_1$).

3. $S$ parses $k_1$ as $k_1 = (\mathit{ck}, k, \mathit{pp})$.

4. $S$ parses $\mathit{ck}$ as $\mathit{ck} = (m_1, \dots, m_n, \tilde{\alpha}_{n+1}^{(1)}, (g_s)_{s \in S}, \mathbf{z})$.

5. $S$ writes $(g_s)_{s \in S}$ on $\mathcal{A}$'s input tape (as if $P_0$ sent this to $P_1$).

6. $S$ waits to read on $\mathcal{A}$'s output tape the message that $\mathcal{A}$ would send to $\mathcal{F}_{\mathit{OT}}$ (on behalf of $P_1$), then writes $(\mathit{sid}_i, m_i)_{i \in [n]}$ on $\mathcal{A}$'s input tape (as if $\mathcal{F}_{\mathit{OT}}$ sent this to $P_1$).

7. $S$ writes $\tilde{\alpha}_{n+1}^{(1)}$ on $\mathcal{A}$'s input tape (as if $P_0$ sent this to $P_1$).

8. $S$ writes $\mathit{pp}$ on $\mathcal{A}$'s input tape (as if $P_0$ sent this to $P_1$).

– Protocol's efficiency. The total communication of the protocol is the following: $P_0$ sends $(g_s)_{s \in S}$ (each $g_s$ is a group element of $\mathbb{G}$), $\tilde{\alpha}_{n+1}^{(1)}$ (which is an element of $\mathbb{F}_p$, hence $2\lambda$-bit long), and $\mathit{pp}$.

□

# 6 Public-Key PCF for OT Correlations

## 6.1 Formal Definition

Here, we introduce and formalize the notion of public-key pseudorandom correlation function (PK-PCF). The main property of a public-key PCF is the non-interactive generation of evaluation

<footnote>a $G'(\mathit{seed}_i)$ is viewed as an element of $\mathbb{F}_p$; $p$ is chosen so that $\log p = 2\lambda$.</footnote>
keys. More precisely, in a PK-PCF, the generation of evaluation keys is done in two separate steps: public key generation PCF.Gen, and evaluation key derivation PCF.KeyDer. Let $\sigma \in \{0, 1\}$ denote the index of a party in a PK-PCF protocol. In the first step, each party locally runs PCF.Gen($\sigma$) to generate a key pair ($sk_{\sigma}, pk_{\sigma}$), and then broadcasts the public key $pk_{\sigma}$. In the second step, each party uses the secret key $sk_{\sigma}$ and the public key of the other party $pk_{1-\sigma}$ and runs the PCF.KeyDer algorithm in order to derive the PCF evaluation key $k_{\sigma}$. After this step, similarly to an interactive PCF, parties can use their keys $k_{\sigma}$ and run the evaluation algorithm PCF.Eval($\sigma, k_{\sigma}, x$) to compute a correlated output $y_{\sigma}$ on an input $x$.

In the following, we state the formal definition and security requirements of a weak PK-PCF.

**Definition 16 (Public-Key Pseudorandom Correlation Function (PK-PCF)).** Let $\mathcal{Y}$ be a reverse-sampleable correlation with output length functions $\ell_0(\lambda)$, $\ell_1(\lambda)$ and let $\lambda \le n(\lambda) \le \text{poly}(\lambda)$ be an input length function. A PK-PCF consists of the following four polynomial algorithms:

- PCF Gibb's Setup(1$^{\lambda}$): A probabilistic algorithm that on input 1$^{\lambda}$, outputs a public parameter $pp$. For simplicity of notation, we assume that all other algorithms have access to $pp$.

- PCF Gen($\sigma$): A probabilistic algorithm that on input $\sigma \in \{0, 1\}$, outputs a pair of public key and secret key ($sk_{\sigma}, pk_{\sigma}$).

- PCF KeyDer($\sigma$, $sk_{\sigma}$, $pk_{1-\sigma}$): A deterministic algorithm that on input $\sigma \in \{0, 1\}$, a secret key $sk_{\sigma}$ and a public key $pk_{1-\sigma}$, outputs an evaluation key $k_{\sigma}$.

- PCF Eval($\sigma, k_{\sigma}, x$): A deterministic algorithm that on input $\sigma \in \{0, 1\}$, a key $k_{\sigma}$ and input value $x \in \{0, 1\}^{n(\lambda)}$, outputs $y_{\sigma} \in \{0, 1\}^{\ell_{\sigma}(\lambda)}$.

We say that a PK-PCF for a correlation $\mathcal{Y}$ is $(N, B, \epsilon)$-secure, if the following two conditions hold:

**Pseudorandom $\mathcal{Y}$-correlated outputs.** For every non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$, it holds that for all sufficiently large $\lambda$,

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

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

**Experiment Pseudorandom $\mathcal{Y}$-Correlated Outputs**

$\text{Exp}_{\mathcal{A},N,0}^{\text{pr}}(\lambda):$
pp $\leftarrow$ PCFSetup(1$^{\lambda}$)
For $\sigma = 0, 1$:
  ($sk_{\sigma}, pk_{\sigma}) \leftarrow$ PCF.Gen($\sigma$)
For $i = 1, \dots, N(\lambda)$:
  $x^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}^{n(\lambda)}$
  $(y_0^{(i)}, y_1^{(i)}) \leftarrow \mathcal{Y}(1^{\lambda})$
$b \leftarrow \mathcal{A}(1^{\lambda}, pk_0, pk_1, (x^{(i)}, y_0^{(i)}, y_1^{(i)})_{i \in [N(\lambda)]})$
Output $b$

$\text{Exp}_{\mathcal{A},N,1}^{\text{pr}}(\lambda):$
pp $\leftarrow$ PCFSetup(1$^{\lambda}$)
For $\sigma = 0, 1$:
  ($sk_{\sigma}, pk_{\sigma}) \leftarrow$ PCF.Gen(1$^{\lambda}$, pp, $\sigma$)
For $\sigma = 0, 1$:
  $k_{\sigma} \leftarrow$ PCF.KeyDer($\sigma$, $sk_{\sigma}$, $pk_{1-\sigma}$)
For $i = 1, \dots, N(\lambda)$:
  $x^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}^{n(\lambda)}$
  $y_0^{(i)} \leftarrow$ PCF.Eval(0, $k_0$, $x^{(i)}$)
  $y_1^{(i)} \leftarrow$ PCF.Eval(1, $k_1$, $x^{(i)}$)
$b \leftarrow \mathcal{A}(1^{\lambda}, pk_0, pk_1, (x^{(i)}, y_0^{(i)}, y_1^{(i)})_{i \in [N(\lambda)]})$
Output $b$

<caption>**Fig. 16.** Pseudorandom $\mathcal{Y}$-correlated outputs of a PK-PCF.</caption>

**Security.** For every $\sigma \in \{0, 1\}$ and every non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$, it holds that for all sufficiently large $\lambda$,

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

where $\text{Exp}_{\mathcal{A},N,\sigma,b}^{\text{sec}}$ ($b \in \{0, 1\}$) is defined as in Figure 17. In particular, the adversary is given access to $N(\lambda)$ samples
Experiment PCF Security

$\mathrm{Exp}^{\mathrm{sec}}_{A,N,\sigma,0}(\lambda):$

pp $\leftarrow$ PCF.setup(1$^{\lambda}$)

For $\hat{\sigma} = 0, 1:$

$(sk_{\hat{\sigma}}, pk_{\hat{\sigma}}) \leftarrow \mathrm{PCF}.\mathrm{Gen}(\hat{\sigma})$

$k_{1-\sigma} \leftarrow \mathrm{PCF}.\mathrm{KeyDer}(1 - \sigma, sk_{1-\sigma}, pk_{\sigma})$

For $i = 1, \dots, N(\lambda):$

$x^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}^{n(\lambda)}$

$y_{1-\sigma}^{(i)} \leftarrow \mathrm{PCF}.\mathrm{Eval}(1 - \sigma, k_{1-\sigma}, x^{(i)})$

Let $T = (x^{(i)}, y_{1-\sigma}^{(i)})_{i \in [N(\lambda)]}$

$b \leftarrow A(1^{\lambda}, pk_0, pk_1, \sigma, sk_{\sigma}, T)$

Output $b$

$\mathrm{Exp}^{\mathrm{sec}}_{A,N,\sigma,1}(\lambda):$

pp $\leftarrow$ PCF.setup(1$^{\lambda}$)

For $\hat{\sigma} = 0, 1:$

$(sk_{\hat{\sigma}}, pk_{\hat{\sigma}}) \leftarrow \mathrm{PCF}.\mathrm{Gen}(\hat{\sigma})$

$k_{\sigma} \leftarrow \mathrm{PCF}.\mathrm{KeyDer}(\sigma, sk_{\sigma}, pk_{1-\sigma})$

For $i = 1, \dots, N(\lambda):$

$x^{(i)} \stackrel{\$}{\leftarrow} \{0, 1\}^{n(\lambda)}$

$y_{\sigma}^{(i)} \leftarrow \mathrm{PCF}.\mathrm{Eval}(\sigma, k_{\sigma}, x^{(i)})$

$y_{1-\sigma}^{(i)} \leftarrow \mathrm{RSample}(1^{\lambda}, \sigma, y_{\sigma}^{(i)})$

Let $T = (x^{(i)}, y_{1-\sigma}^{(i)})_{i \in [N(\lambda)]}$

$b \leftarrow A(1^{\lambda}, pk_0, pk_1, \sigma, sk_{\sigma}, T)$

Output $b$

<caption>Fig. 17. Security of a PK-PCF. RSample is the algorithm for reverse sampling $\mathcal{Y}$.</caption>

## 6.2 A Public-Key PCF via Bellare-Micali Non-Interactive OT

In Section 5, we provided transformations from CPRFs supporting (w)PRF constraints and their opposite to PCFs for OT correlations. More specifically, Figure 10 presents a simple (unoptimized) instance of this transformation where in order to generate the PCF keys, two calls to the underlying CPRF are made. In this section, we discuss how to generate the resulting PCF keys of this transformation non-interactively when plugging in our Naor-Reingold CPRF.

Let $F: \mathcal{K} \times \mathcal{X} \to \{0, 1\}$ be an IPM-wPRF with respect to an IPM set $S$ and predicate functions $f, g$ (See Definition 13), and let us plug in our CPRF construction (Figure 6) in this transformation. The resulting PCF keys are:

$$k_0 = ((pp_0, msk_0), (pp_1, msk_1)), \quad k_1 = ((pp_0, ck_0), (pp_1, ck_1), g(\hat{k}))$$

where $msk_b \leftarrow \mathrm{CPRF}.\mathrm{KeyGen}(1^{\lambda})$, and $ck_b \leftarrow \mathrm{CPRF}.\mathrm{Constrain}(msk_b, C_b)$, where $C_0(x) = F_{\hat{k}}^r(x)$, and $C_1(x) = 1 - F_{\hat{k}}^r(x)$ for a random key $\hat{k} \stackrel{\$}{\leftarrow} \mathcal{K}$, and $b \in \{0, 1\}$.

We now take a closer look at the correlation between a master secret key and a constrained key in Naor-Reingold CPRF. When working over a group $\mathbb{G} = \langle g \rangle$ of prime order $p$, a master secret key is of the form $msk = (a_0, a_1, \dots, a_n) \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{n+1}$, and a constrained key for an IPM constraint $(k, S)$ is $ck = (\alpha, (g_s)_{s \in S}, k)$, where $\alpha_i = a_i \cdot r^{-k_i}$ for all $i \in [n]$, and $g_s = g^{a_0 \cdot r^s}$ for all $s \in S$. Here, $k = g(\hat{k})$, where $\hat{k}$ is the key of the wPRF $F$.

In order to generate the PCF keys non-interactively, we need to derive a valid pair of msk and ck non-interactively. Given that the set $S$ attributed with the IPM-wPRF is public, party 0 can sample a random element $a_0 \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and compute and publish the tuple $(g_s)_{s \in S}$. Party 1 can then use this tuple as a part of its PCF key.

The more correlated elements of msk and ck are the vectors $(a_1, \dots, a_n) \in \mathrm{msk}$ and $(\alpha_1, \dots, \alpha_n) \in \mathrm{ck}$ that satisfy the equation $\alpha_i = a_i \cdot r^{-g(k)_i}$ for all $i \in [n]$. Note that the wPRF key $k$ is only known to party 1 and the secret elements $(a_1, \dots, a_n)$ and $r$ are only known to party 0. In what follows, we discuss how to generate two pairs $(a, r)$ and $(\alpha, b)$ such that $\alpha = a \cdot r^b$, where $\alpha, a, r \in \mathbb{Z}_p$ and $b \in \{0, 1\}$. We can then extend the solution to generate all the elements of the two vectors $a$ and $\alpha$.

Bellare-Micali Non-interactive OT [BM90] provides a simple but costly solution by using ElGamal encryption and Pedersen commitment to generate two such correlated pairs $(a, r)$ and $(\alpha, b)$, for a bit $b \in \{0, 1\}$ and elements $a, r, \alpha \in \mathbb{QR}_p$, where $\mathbb{QR}_p$ denotes the subgroup of quadratic residues modulo $p$. The details of this protocol can be found in Figure 18.
<figure><img src="image_8.png" /><figcaption>**Fig. 18.** Bellare-Micali Non-Interactive OT [BM90]. Here, $p = 2q+1$ for primes $p$ and $q$. The public elements $g, h$ are randomly sampled from $QR_p$ and $DLog_g(h)$ is unknown to both parties.</figcaption></figure>

Note that in this protocol, the element $r$ should be a quadratic residue modulo $p$. Therefore, using this protocol for setting up a public key generation for our PCF protocol from the Naor-Reingold CPRF implies assuming the hardness of the sparse power-DDH problem for a quadratic residue $r \in QR_p$. This variant is implied by the sparse power-DDH assumption. However, for the security of this non-interactive protocol we have to assume the hardness of DDH problem over $QR_p$ which imposes choosing a large-enough prime $p$ due to subexponential-time attacks on DDH over finite fields. This makes the resulting public-key PCF inefficient in terms of both the size of public-key and evaluation keys and computation time.

In the next section, we propose an alternative efficient way of setting up the public keys.

## 6.3 A Better Construction from Paillier-ElGamal

In this section, we present an efficient public-key PCF construction where in order to derive a pair of OT-correlated evaluation keys, we perform the non-interactive OT protocol of Bellare-Micali [BM90] over a Paillier group. This is in essence the Non-interactive VOLE protocol of [OSY21], followed by additional steps in order to derive the correlated keys over $Z_p^*$.

Let $N = PQ$ be a Blum integer, meaning that $P$ and $Q$ are prime numbers of the form $P = 2P' + 1$ and $Q = 2Q' + 1$ for $\lambda$-bit prime numbers $P'$ and $Q'$. The key generation and derivation of our public-key PCF work over the group $Z_{N^2}^* \approx \mathbb{H} \times \mathbb{N}\mathbb{R}_N$, where $\mathbb{H} = \{(1+N)^i : i \in [N]\}$ is of order $N$, and $\mathbb{N}\mathbb{R}_N = \{x^N : x \in Z_{N^2}^*\}$ is of order $\varphi(N)$.

We first recall the following lemma due to [OSY21], where they introduce a distributed discrete logarithm algorithm for a subset of $Z_{N^2}^*$.

**Lemma 5 ([OSY21]).** There exists an algorithm $DDLog_N(g)$ for which the following holds: Let $g_0, g_1 \in Z_{N^2}^*$, such that $g_0 = g_1(1+N)^x (\text{mod } N^2)$. If $z_0 = DDLog_N(g_0)$ and $z_1 = DDLog_N(g_1)$, then $z_0 - z_1 = x (\text{mod } N)$.

More precisely, $DDLog_N(g)$ works as follows:

* $DDLog_N(g)$

- Write $g = h + h'N$, where $h, h' < N$, using the division algorithm.

- Output $z = h'h^{-1} (\text{mod } N)$.

Construction idea: Let $g_q$ be a generator of $QR_p$, and $G, H$ two random elements of $\mathbb{N}\mathbb{R}_{2N}$. Party 0 samples $r' \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and sets $r := g_q^{r'} (\text{mod } p)$. It then computes its public key as a Paillier-ElGamal encryption of $r'$, i.e., $pk_0 = (G^t, H^t \cdot (1+N)^{r'})$. Party 1 holding a bit $k \in \{0,1\}$ computes its public key as a Pedersen commitment of $k$ over $\mathbb{N}\mathbb{R}_{2N}$, i.e., $pk_1 = G^s \cdot H^k$. Following the same computations as in Figure 18, at the end of the protocol, the two parties derive two pairs $(A, r)$ and $(B, k)$, where $B = A \cdot (1+N)^{r' \cdot k}$. In other words, the parties derive multiplicative shares of $(1+N)^{r' \cdot k}$. We now use the $DDLog_N$ algorithm of Lemma 5 to locally convert these multiplicative shares to subtractive shares. More precisely, Party 0 and Party 1 respectively compute $\hat{a} \leftarrow DDLog_N(A)$ and $\hat{\alpha} \leftarrow DDLog_N(B)$,
where $\hat{a} - \hat{\alpha} = r' \cdot k \pmod N$. Note that we can furthermore view these elements as the shares of $r' \cdot k$ over the integers, if it holds that $r' \cdot k \ll N$. Therefore, setting $q < N/2^{\lambda}$, it is now possible for Party 0 and Party 1 to respectively compute $a = g_q^{\hat{a}}$ and $\alpha = g_q^{\hat{\alpha}}$ such that $\alpha = a \cdot r^{-k} \pmod p$. Recall that the goal of the protocol is to derive a pair of Naor-Reingold master secret key and constrained key for a constraint vector $k \in \{0,1\}^n$ that is a wPRF key. We need to therefore derive $n$ such correlated elements. To do so, it is enough for Party 1 to publish $n$ Pedersen commitments to each bit of its wPRF key $k$. The details of the construction are presented in Figure 19.

PK-PCF for OT Correlations from sparse power-DDH and DCR

Requires:

- Let $F: \mathcal{K} \times \mathcal{X} \to \{0,1\}$ be an IPM-wPRF with respect to an IPM set $S$ and predicate functions $f,g$ (See Definition 13). We assume that $S$ is $\Delta$-antiperiodic, and consider $S' = S \cup \{-\Delta/2, \dots, -1\}$.

- Let $p$ be a safe prime, i.e., $p = 2q + 1$ for a prime $q$, and $N = PQ$ for primes $P$ and $Q$.

- Let $\text{DDLog}_N$ be the distributed discrete logarithm algorithm described in Lemma 5.

- Let $\text{Hash}$ be a hash function modeled as a random oracle.

PCF. Setup($1^{\lambda}$):

1. $(\mathbb{G}, g, p) \stackrel{\$}{\leftarrow} \text{GenPar}(1^{\lambda})$.

2. Sample a generator $g_q$ of $\text{QR}_p$.

3. Sample $G' \stackrel{\$}{\leftarrow} \mathbb{Z}_{N^2}$, and set $G \leftarrow (G')^{2N} \pmod{N^2}$.

4. Sample $d \stackrel{\$}{\leftarrow} \mathbb{Z}_{N^2}$, and set $H \leftarrow G^d \pmod{N^2}$.

5. Output $\text{pp} = (\mathbb{G}, p, g_q, (G, H), F)$.

PCF. Gen$_0(1^{\lambda})$:

1. Sample $h \stackrel{\$}{\leftarrow} \mathbb{G}$.

2. Sample $r' \stackrel{\$}{\leftarrow} \mathbb{Z}_q$, and set $r := g_q^{r'} \pmod p$.

3. Compute $(c_0, c_1) = (G^t, H^t \cdot (1+N)^{r'})$, where $t \stackrel{\$}{\leftarrow} \mathbb{Z}_N$.
// Paillier-ElGamal encryption of $r'$.

4. For $s \in S'$, compute and set $h_s := h^{r^s}$.

5. Sample $a_{n+1} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$, and set $\alpha_{n+1} = a_{n+1} \cdot r^\Delta$.

6. Set $\text{sk}_0 = (h, r, t, a_{n+1})$.

7. Set $\text{pk}_0 = \{(c_0, c_1), (h_s)_{s \in S'}, \alpha_{n+1}\}$.

8. Output $(\text{sk}_0, \text{pk}_0)$.

PCF. Gen$_1(1^{\lambda})$:

1. Sample $\hat{k} \stackrel{\$}{\leftarrow} \mathcal{K}$.

2. Compute $k = (k_1, \dots, k_n) \leftarrow g(\hat{k})$.

3. For $i \in [n]$, compute $\text{com}_i = G^{s_i} \cdot H^{k_i} \pmod{N^2}$, where $s_i \stackrel{\$}{\leftarrow} \mathbb{Z}_N$.
// Pedersen commitments of $k_i$.

4. Set $\text{sk}_1 = (k, (s_i)_{i \in [n]})$.

5. Set $\text{pk}_1 = (\text{com}_1, \dots, \text{com}_n)$.

6. Output $(\text{sk}_1, \text{pk}_1)$.

PCF. KeyDer($\sigma$, $\text{sk}_{\sigma}$, $\text{pk}_{1-\sigma}$):

1. If $\sigma = 0$:

(a) Parse $\text{sk}_0 = (h, r, t, a_{n+1})$.

(b) Parse $\text{pk}_1 = (\text{com}_1, \dots, \text{com}_n)$.

(c) For $i \in [n]$:

i. compute $A_i = \text{com}_i^t \pmod{N^2}$.
// $A_i = G^{s_i \cdot t} \cdot H^{k_i \cdot t} \pmod{N^2}$.

ii. compute $\hat{a}_i \leftarrow \text{DDLog}_N(A_i)$.
// $\hat{a}_i = (r' \cdot k_i)_0$.

iii. set $a_i := g_q^{\hat{a}_i} \pmod p$.
// $a_i = g_q^{(r' \cdot k_i)_0}$.

(d) Set $\mathbf{a} = (a_1, \dots, a_{n+1})$.

(e) Set and output $k_0 = (h, \mathbf{a})$.

2. If $\sigma = 1$:

(a) Parse $\text{sk}_1 = (k, (s_i)_{i \in [n]})$.

(b) Parse $\text{pk}_0 = \{(c_0, c_1), (h_s)_{s \in S'}, \alpha_{n+1}\}$.

(c) For $i \in [n]$:

i. compute $B_i = c_0^{s_i} \cdot c_1^{k_i} \pmod{N^2}$.
// $B_i = G^{s_i \cdot t} \cdot H^{k_i \cdot t} \cdot (1+N)^{r' \cdot k_i}$.

ii. compute $\hat{a}_i = \text{DDLog}_N(B_i)$.
// $\hat{a}_i = (r' \cdot k_i)_1$.

iii. set $\alpha_i := g_q^{\hat{a}_i} \pmod p$.
// $\alpha_i = g_q^{(r' \cdot k_i)_1}$.

(d) Set $\alpha = (\alpha_1, \dots, \alpha_{n+1})$.

(e) Set and output $k_1 = (\alpha, (h_s)_{s \in S'}, \mathbf{k}, \Delta)$.
PCF.Eval(1^λ, σ, k_σ, ˆx = (ˆx_1, ..., ˆx_n)):

1. If $\sigma = 0$:

(a) Parse $k_0 = (h, \mathbf{a})$.

(b) Compute $\mathbf{x} = (x_1, \dots, x_n) \leftarrow f(\hat{x})$.

(c) Compute $r_0 = h_{i=1}^{\prod_{i=1}^{n} a_i^{x_i}}$.

(d) Compute $r_1 = h_{i=1}^{\prod_{i=1}^{n} a_i^{x_i} \cdot a_{n+1}}$.

(e) Set and output $y_0 \leftarrow (\text{Hash}(r_0), \text{Hash}(r_1))$.

2. If $\sigma = 1$:

(a) Parse $k_1 = (\alpha, (h_s)_{s \in S'}, \mathbf{k}, \Delta)$.

(b) Compute $\mathbf{x} = (x_1, \dots, x_n) \leftarrow f(\hat{x})$.

(c) Let $b = F_k(\hat{x})$, and $s = \langle \mathbf{x}, \mathbf{k} \rangle - b \cdot \Delta$.

(d) Compute $r = (h_s)_{i=1}^{\prod_{i=1}^{n} \alpha_i^{x_i} \cdot \alpha_{n+1}^b}$.

(e) Set and output $y_1 \leftarrow (b, \text{Hash}(r))$.

<caption>Fig. 19. Public-Key PCF for OT Correlations from Paillier-ElGamal</caption>

## Security Analysis

First we state the following lemma. We skip the proof and refer the reader to the construction idea explained in Section 6.3.

**Lemma 6 (Correlated Evaluation Keys).**

Let PCF.Gen and PCF.KeyDer be the algorithms described in Figure 19. And let $(\text{sk}_\sigma, \text{pk}_\sigma) \leftarrow \text{PCF.Gen}(\sigma)$, and $k_\sigma \leftarrow \text{PCF.KeyDer}(\sigma, \text{sk}_\sigma, \text{pk}_{1-\sigma})$ for $\sigma \in \{0, 1\}$. It holds that $k_0 = (h, \mathbf{a})$, $k_1 = (\alpha, (h_s)_{s \in S'}, \mathbf{k}, \Delta)$, where for a random element $r \in \mathbb{Z}_p$:

- $h_s = h^{r_s}$ for all $s \in S'$, and

- $\mathbf{a} = (a_1, \dots, a_{n+1})$ and $\alpha = (\alpha_1, \dots, \alpha_{n+1})$ such that $\alpha_i = a_i \cdot r^{-k} \pmod p$ for all $i \in [n]$, and $\alpha_{n+1} = a_{n+1} \cdot r^{-\Delta}$.

We also state the following remark regarding the randomness space of operations over $\mathbb{N}\mathbb{R}_{2N}$ in our construction:

**Remark 4.** The key generation and derivation phases of our PK-PCF protocol contain operations over the subgroup $\mathbb{N}\mathbb{R}_{2N}$ that is of order $P'Q'$. However, since the two parties should perform their computations obviously to the factorization of $N$, they sample their required randomness for computing commitments and encryptions from $\mathbb{Z}_N$ instead of $\mathbb{Z}_{P'Q'}$. This does not change the distribution of the resulting elements over $\mathbb{N}\mathbb{R}_{2N}$, since

$$ \Delta(\{r \pmod{P'Q'} : r \stackrel{\$}{\leftarrow} \mathbb{Z}_N\}, \mathcal{U}(\mathbb{Z}_{P'Q'})) = \frac{N \pmod{P'Q'}}{N} = \frac{2P' + 2Q' + 1}{4P'Q' + 2P' + 2Q' + 1} \le \frac{1}{2^\lambda}, $$

where $\Delta(D_1, D_2)$ denotes the statistical distance between the distributions $D_1$ and $D_2$.

We now prove the security of our PK-PCF construction.

**Theorem 7 (PCF Security).** Assuming the hardness of sparse power-DDH (Assumption 2) and DCR (Assumption 3), the construction provided in Figure 19 is a secure public-key pseudorandom correlated function for OT correlations.

*Proof.* We prove that our construction satisfies the properties of a PK-PCF.

**Pseudorandom OT-Correlated Outputs.** We consider the following sequence of hybrid games:

**Hybrid $H_0$:** This is the game $\text{Exp}_{\lambda,N,1}^{\text{pr}}(\lambda)$, where the view of an adversary consists of $(1^{\lambda}, \text{pk}_0, \text{pk}_1, (x^{(i)}, y_0^{(i)}, y_1^{(i)})_{i \in [N(\lambda)]})$, where each tuple $(x^{(i)}, y_0^{(i)}, y_1^{(i)})$ is generated by running the PCF evaluation algorithms of both parties on $x^{(i)}$ for $i \in [N(\lambda)]$.

**Hybrid $H_1$:** In this hybrid, we replace the key generation and key derivation steps of Hybrid $H_0$ by the following:
1. Sample $h \stackrel{\$}{\leftarrow} \mathbb{G}$.

2. Sample $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p$. // PCF.Gen0: $r = g_q^{r'}$, where $r' \stackrel{\$}{\leftarrow} \mathbb{Z}_q$. 
→ $r$ has the same distribution in both cases.

3. For $s \in S'$, compute and set $h_s := h^{r_s}$.

4. Compute $(c_0, c_1) = (G^t, H^t \cdot (1+N)^0)$, where $t \stackrel{\$}{\leftarrow} \mathbb{Z}_N$. 
// PCF.Gen0: $(c_0, c_1) = (G^t, H^t \cdot (1+N)^{r'})$.

→ due to the semantic security of Paillier-ElGamal under the DCR assumption.

5. Sample $a_{n+1} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$, and set $\alpha_{n+1} = a_{n+1} \cdot r^{-\Delta}$.

6. Set $\text{pk}_0 = \{(c_0, c_1), (h_s)_{s \in S'}, \alpha_{n+1}\}$.

7. For $i \in [n]$, compute $\text{com}_i = G^{s_i} \cdot H^0 \pmod{N^2}$. 
// PCF.Gen1: $\text{com}_i = G^{s_i} \cdot H^{k_i}$.

→ due to the perfectly hiding property of Pedersen commitments over $\mathbb{NR}_{2N}$.

8. Set $\text{pk}_1 = (\text{com}_1, \dots, \text{com}_n)$.

// Instead of running PCF.KeyDer($\sigma, \text{sk}_\sigma, \text{pk}_{1-\sigma}$) for $\sigma = 0, 1$:

9. Sample $(a_1, \dots, a_n) \stackrel{\$}{\leftarrow} \mathbb{Z}_p^n$, and set $\mathbf{a} = (a_1, \dots, a_{n+1})$.

10. Sample $\hat{k} \stackrel{\$}{\leftarrow} \mathcal{K}$, and compute $\mathbf{k} \leftarrow g(\hat{k})$.

11. For $i \in [n]$, compute and set $\alpha_i = a_i \cdot r^{-k_i}$.

12. Set $k_0 = (h, \mathbf{a})$, and $k_1 = (\alpha, (h_s)_{s \in S}, \mathbf{k}, \Delta)$.

→ due to the correctness of the key derivation (see Lemma 6).

Hybrid $\mathcal{H}_1$ differs from Hybrid $\mathcal{H}_0$ on the steps that are commented. Due to the highlighted arguments written for each step, $\mathcal{H}_1$ remains indistinguishable to $\mathcal{H}_0$. Note that in this hybrid, the view of the adversary contains simulated public keys $\text{pk}_0$ and $\text{pk}_1$ that are independent of any secrets.

Hybrid $\mathcal{H}_2$: This is the same as Hybrid $\mathcal{H}_1$ except that here, we replace

For $\sigma = 0, 1$: $y_\sigma \leftarrow \text{PCF.Eval}(\sigma, \text{sk}_\sigma, \text{pk}_{1-\sigma})$

with

$$ (y_0^{(i)}, y_1^{(i)}) \stackrel{\$}{\leftarrow} \text{OT}(1^\lambda). $$

Regarding the security of the Naor-Reingold CPRF and Theorems 4 and 5, hybrids $\mathcal{H}_2$ and $\mathcal{H}_1$ are indistinguishable.

Hybrid $\mathcal{H}_3$: This is the same as Hybrid $\mathcal{H}_2$ except that here, we undo the changes from hybrid $\mathcal{H}_1$ and replace the whole batch of modified steps with

$$ \text{For } \sigma = 0, 1: (\text{sk}_\sigma, \text{pk}_\sigma) \leftarrow \text{PCF.Gen}(1^\lambda, \text{pp}, \sigma). $$

This Hybrid remains indistinguishable to Hybrid $\mathcal{H}_2$ due to the same reasons explained in Hybrid $\mathcal{H}_1$ for the steps that simulated the two public keys. The evaluation keys are not used in $\mathcal{H}_2$ anymore, and therefore, it does not change the view of the adversary that we do not generate them in this hybrid.

Note that hybrid $\mathcal{H}_3$ has the same distribution as $\text{Exp}_{\mathcal{A},N,0}^{\text{sec}}(\lambda)$. This concludes the proof of pseudorandom OT-correlated output of the construction.

Security. We prove the security for each $\sigma \in \{0, 1\}$.

* For $\sigma = 0$, consider the following sequence of hybrid games:

Hybrid $\mathcal{H}_0$: This is the game $\text{Exp}_{\mathcal{A},N,\sigma=0,0}^{\text{sec}}(\lambda)$, where the view of party 0 considered as the adversary consists of

$$ (1^\lambda, \text{pk}_0, \text{pk}_1, \text{sk}_0, (x^{(i)}, y_0^{(i)}, y_1^{(i)})_{i \in [N(\lambda)]}), $$

where $y_1^{(i)} \leftarrow \text{PCF.Eval}(1, k_1, x^{(i)})$ for all $i \in [N(\lambda)]$.