# Pseudorandom Correlation Functions for Garbled Circuits

Geoffroy Couteau, Srinivas Devadas, Alexander Koch, Sacha Servan-Schreiber

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

To cite this version:

Geoffroy Couteau, Srinivas Devadas, Alexander Koch, Sacha Servan-Schreiber. Pseudorandom Correlation Functions for Garbled Circuits. TCC 2025, Dec 2025, Aarhus, Denmark. hal-05379130

HAL Id: hal-05379130

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

Submitted on 24 Nov 2025

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Pseudorandom Correlation Functions for
Garbled Circuits

Geoffroy Couteau¹, Srinivas Devadas²,
Alexander Koch³*, and Sacha Servan-Schreiber⁴**

¹ Université Paris Cité, CNRS, IRIF

² MIT

³ Secorvo Security Consulting GmbH

⁴ Tinfoil

**Abstract.** In this paper, we define the notion of pseudorandom correlation generators (PCGs) and functions (PCFs) for garbled circuit correlations. With a Garbling PCG or PCF, two parties can non-interactively generate a virtually unbounded number of secret-shared garbled circuits and corresponding secret-shared garbled inputs. With the shares of the garbled circuit and garbled input, anyone can recover the garbled circuit and evaluate it to obtain the result of the computation in the clear.

In the process of constructing Garbling PCFs, we introduce a new primitive that we call a *Topology-Adaptive PCF (TAPCF)*, which we construct from two different variants of the learning parity with noise (LPN) assumption. Informally, a TAPCF is a PCF that additionally allows the target correlation to be specified on-demand (i.e., at evaluation time). Using our TAPCF construction as a building block, we construct a Garbling PCF that allows the parties to specify the circuit they wish to garble on-the-fly. Under realistic parameter settings, we estimate that, with our construction, two parties can generate one garbled circuit per second, for garbled circuits with 10,000 AND gates.

Garbling PCFs have several applications: We provide constructions for (1) an efficient homomorphic secret-sharing scheme for specific high-depth circuits, (2) a zero-knowledge proof system over secret shares that supports checking unstructured languages, and (3) a semi-honest reusable two-round, two-party computation protocol supporting non-interactive public outputs.

# 1 Introduction

Cryptographic protocols often benefit from an access to a trusted source of cor-
related randomness. Traditional approaches for securely distributing correlated
randomness are based on oblivious transfer extension [49] or somewhat homo-
morphic encryption [35], and induce a large communication overhead. To address

<footnote>* Work done while the author was at Université Paris Cité, CNRS, IRIF</footnote>

<footnote>** Work done while the author was at MIT and visiting IRIF.</footnote>
this inefficiency, starting with the work of Boyle, Couteau, Gilboa, and Ishai [19], much research effort has been dedicated towards building primitives that allow parties to silently generate large amounts of correlated (pseudo)randomness from short seeds, i.e., without any interaction. These primitives are known as pseudo-random correlation generators (PCGs) [20, 22, 62] and pseudorandom correlation functions (PCFs) [23, 24, 33], and are designed for “simple” forms of correlated randomness. Specifically, the correlations considered in prior work target oblivious transfers and (vector) oblivious linear evaluations, which have already led to many applications, including efficient secure computation [25, 37, 48], threshold cryptography [1, 39, 54], private set intersection [27, 57, 60], zero-knowledge proofs [5–7, 38, 65, 66] and more.

Recently, primitives for silently generating correlated randomness were used to design improved protocols based on garbling schemes. A garbling scheme [10, 67] GC maps a Boolean circuit $C$ to a garbled circuit $\hat{C}$ and a set of labels $(L_{i,0}, L_{i,1})_{i \in [s]}$, such that, knowing $\hat{C}$ and the labels $L_{i,x_i}$ corresponding to an input $x = (x_1, \dots, x_s)$ allows anyone to recover $C(x)$, without learning anything else about $x$. Garbling schemes are at the heart of secure computation protocols with minimal interaction [37, 50, 52, 63, 64], and efficient protocols for generating garbled circuits have both theoretical and practical applications. The recent work of Dittmer, Ishai, Lu, and Ostrovsky [37] (Eurocrypt 2022) showed that the silent generation of correlated randomness could be used to improve the distributed generation of garbled circuits. Inspired, in part, by their approach, and motivated by the many applications of minimally-interactive secure computation, we ask a related but different question: Is it possible to silently generate garbled circuits directly? In other words, we ask:

*Can two parties non-interactively generate a large number of additive shares of pseudorandom garbled circuits from short seeds?*

In this work, we answer the question in the affirmative by constructing PCGs and PCFs for garbling correlations. Towards answering this question, we initiate the study of efficient generation for pseudorandom garbled circuit correlations, where two parties obtain secret-shares of the garbled circuit and labels. Moreover, our constructions are potentially implementable and we estimate them to be concretely practical using existing building blocks.

**Contributions.** Our main contributions are threefold:

- **New Definitions.** We introduce the notion of garbling pseudorandom correlation generators (GPCGs) and garbling pseudorandom correlation functions (GPCFs). Intuitively, a GPCG is parametrized by a garbled circuit scheme GC. Given GPCG keys $(k^A, k^B)$ for a circuit $C$, two parties can locally generate many pairs $(\hat{C}_i^A, \hat{C}_i^B)$ such that $\hat{C}_i^A + \hat{C}_i^B = \hat{C}_i$ is a pseudorandom garbling of $C$ under the garbling scheme GC. A GPCF strengthens a GPCG on two fronts: (1) it allows generating the pairs $(\hat{C}_i^A, \hat{C}_i^B)$ on-demand, rather than expanding all correlations in one monolithic expansion, and (2) it allows the parties to choose the circuit $C_i$ to garble on the fly. That is, the parties can
generate pseudorandom shares $(\hat{C}_i^A, \hat{C}_i^B)$ of the garbled circuit $\hat{C}_i$, encoding the circuit $C_i$ chosen by the parties at evaluation time.

- **New Constructions.** We provide constructions of GPCGs and GPCFs, for a suitable secret-sharing-friendly garbling scheme, that is essential a “BMR-style” multiparty garbling [9, 37, 63, 64]. Our construction of GPCG builds upon programmable PCGs for Beaver triple correlations,<fnref n="5" /> for which efficient and practical [62] constructions are known from various flavors of the LPN assumption [12, 22]. Towards constructing GPCFs, we introduce the notion of topology-adaptive PCFs (TAPCFs), which are, informally, PCFs where the correlation can be specified by the parties on the fly, at evaluation time. We show that previous constructions of PCFs from LPN variants [23, 24, 33] can actually be directly cast as TAPCFs, uncovering a useful property that has so-far not been exploited and is likely to be of independent interest. We build GPCFs for our secret-sharing-friendly garbling scheme GC from TAPCFs for degree-2 correlations.<fnref n="6" />

- **Applications.** We show that GPCGs and GPCFs, in combination with other cryptographic primitives, enable several new applications in the realm of low-interaction secure computation. We show that GPCGs and GPCFs:

1. Result in a new framework for non-interactively computing over databases that are secret-shared between two servers, which, for certain types of queries, is much more practical compared to homomorphic secret sharing (HSS) [15, 17, 21, 56];

2. Can be used to obtain zero-knowledge proofs over secret-shared statements, where two non-colluding designated verifiers can, given suitable shares of a witness, efficiently check the truth value of statement, in zero-knowledge; and

3. Provide a new approach for semi-honest reusable, two-sided non-interactive secure computation (NISC) protocol [51] with a “non-interactive public disclosure” property.

We provide an overview of our GPCG and GPCF applications in the following section.

## 1.1 Overview of applications

Here, we describe the three main applications for our constructions in more detail. The full constructions are available in the full version.

<footnote n="5">⁵ Programmable PCGs enable partially specifying the correlation.</footnote>

<footnote n="6">⁶ A degree-2 correlation consists of a triple $(a, b, P(a, b))$ where $P$ is a polynomial of degree-2 in two variables. Beaver triples [8] are an example of a degree-2 correlation.</footnote>
**Efficient HSS for T-shaped circuits.** Homomorphic secret sharing (HSS) [15] is a powerful distributed alternative to fully-homomorphic encryption, and has many uses in performing computations over secret-shared databases. However, existing HSS constructions only support low-depth computations, making them highly inefficient for computing complex functions over the database, or high-depth circuits more generally.

As a conceptual contribution, we identify a common computational pattern present in applications involving database queries: The computation can often be represented as a “T-shaped” circuit, where a low-degree pre-processing computation is applied to the entire database (the top of the T), followed by a high-depth post-processing computation over a small subset of items selected in the pre-processing phase (the leg of the T). This type of computation captures the case where queries first extract a number of matches from a database and then compute some potentially complex function on a selected subset of matches. Examples of such queries include threshold counting, fuzzy matching, queries to hash-based data structures, and more.

Existing HSS constructions require paying an exponential cost in the depth of the entire circuit. In contrast, we show that using our GPCG or GPCF construction, we can dramatically improve the efficiency of HSS applied to T-shaped computations. We achieve this by constructing a “compiler” that computes the low-degree pre-processing with the original HSS scheme, generates shares of a pseudorandom garbling $\tilde{C}$ of the post-processing using a GPCF, and “connects” the outputs of the HSS to the secret-shared labels of $\tilde{C}$. This yields a new type of HSS scheme that sacrifices additive output reconstruction, but confines the computational blowup to only being exponential in the depth of the pre-processing rather than the entire circuit. For database queries where a small subset of items is first selected and then a post-processing computation is applied over the selected items, our approach can exponentially improve the server-side efficiency over existing HSS techniques.

**Zero-knowledge proofs for HSS.** Zero-knowledge proofs on secret-shared data [13, 30, 32] provides a framework for parties to efficiently check properties over secret-shared data provided to them by an untrusted prover. While some existing techniques are practical [32] and generic (they can be applied to any P or NP statements), we identify two downsides that we address in the two-party context. Existing solutions are limited in that they:

(1) require two sequential messages between the parties to check the proof (or, alternatively, require working in the random oracle model);

(2) are tailored to languages that are efficiently verifiable using arithmetic circuits, which makes them cumbersome to use with Boolean circuits.

Using secret-shared garbled circuits, we construct a two-party proof system for HSS-shared statements (and witnesses) that (1) only requires sending one message between verifiers to check the proof, (2) works in the standard model (i.e., does not assume a random oracle), and (3) is tailored to languages with Boolean verification circuits. To the best of our knowledge, this results in the first zero-
knowledge proof system for HSS without assuming a random oracle and supporting general verification predicates.

**Semi-honest Two-party NISC with non-interactive disclosure.** Non-interactive Secure Computation (NISC) allows two parties, after committing to their inputs, to securely evaluate multiple functions on their committed input, while using only a single additional round of communication per function. It is known that two-party NISC in the semi-honest model can be constructed from garbled circuits and oblivious transfers [50]. We show that our GPCF construction gives rise to a new construction of two-sided, two-party NISC [51] where, following a setup phase, two parties can commit to their respective inputs $x$ and $y$ in the first round, and later compute functions $f(x, y)$ in a single round, for any function $f$ of their choice. We show that our protocol achieves a desirable "non-interactive disclosure" property: Two parties can compute $f(x, y)$ but also choose to reveal $f(x, y)$ to either of them or to any other party by making the result public in the second round.

# 2 Technical Overview

In this section, we give a technical overview of our results. We start by describing a natural strawman scheme that fails to meet the required security guarantees we are after but serves as an introduction to the technical notation and ideas. Afterwards, we show how to resolve the failures of the strawman scheme using degree-2 correlations which can be realized using a PCG. We then introduce the notion of a topology-adaptive PCF and overview the construction from the expand-accumulate LPN assumption [24].

## 2.1 A strawman approach

Let $f$ be a function computed by a Boolean circuit $C$ taking $s$ bits as input. A garbled circuit $\hat{C}$ is an encoding of the circuit $C$ that can be efficiently evaluated given a garbled input $\hat{X}$ (encoding the input $x$) to reveal $C(x)$. However, given $\hat{C}$ and $\hat{X}$, no other information beyond $C$ and $C(x)$ is revealed to the evaluator.

In garbled circuit constructions, the garbled input $\hat{X}$, encoding $x = x_1 \| \dots \| x_s$, consists of $s$ labels (which can be thought of as keys) that correspond to the input bits $x_1, \dots, x_s$. More concretely, the garbled circuit $\hat{C}$ is defined with $2s$ input labels:

$$ (L_{1,0}, L_{1,1}, \dots, L_{s,0}, L_{s,1}) \in (\mathbb{F}_{2^\lambda})^{2s}, $$

which are used to encrypt the input bits to the circuit $C$. The garbling of $x$ consists of the labels $(L_{1,x_1}, \dots, L_{s,x_s})$ selected by the bits of $x$. At a high level, given the labels selected by $x$, the evaluator can decrypt the corresponding truth table entries for a given garbled input and proceed to get a new set of labels. This process is then repeated for all layers of the circuit until the last layer is reached. The final truth table outputs the value $C(x)$. We provide a more in-depth overview of garbled circuits in the full version of this work.
Garbled circuits traditionally require one party (the garbler) to generate the garbled circuit and input labels. However, if two parties want to generate a garbled circuit and garble a secret-shared input, things become more challenging.

Suppose that the two parties holding additive shares of $x \in \{0,1\}^s$ would like to produce secret shares of a garbled circuit $\hat{C}$ and garbled input $\hat{X}$. Because the circuit $C$ is itself known and independent of the input $x$, the parties can easily generate the garbled circuit $\hat{C}$ “in the clear,” putting aside the fact that we would ultimately like to hide the labels of the circuit from both parties. However, even so, the parties still need a way to obtain secret shares of the labels that correspond to their secret-shared input $x$.

One way to achieve this trivially and non-interactively is by exploiting additive secret shares as follows. Denote the secret-shares of $x$ held by the two parties $A$ and $B$ as $\langle x \rangle^A$ and $\langle x \rangle^B$, such that $\langle x \rangle^A \oplus \langle x \rangle^B = x$. Each share $\langle x \rangle^\sigma$ (for $\sigma \in \{A, B\}$) can be viewed as $s$ shares $(\langle x_1 \rangle^\sigma, \dots, \langle x_s \rangle^\sigma)$ of the individual input bits. For each $i \in [s]$, both parties can obtain a secret share of $L_{i,x_i}$ by computing:

$$ \langle L_{i,x_i} \rangle^\sigma := L_{i,0} \cdot (\langle 1 \rangle^\sigma \oplus \langle x_i \rangle^\sigma) \oplus L_{i,1} \cdot \langle x_i \rangle^\sigma, \quad (1) $$

where $\cdot$ represents an element in $\mathbb{F}_{2^\lambda}$ multiplied by a scalar. Note that:

$$ \langle L_{i,x_i} \rangle^A \oplus \langle L_{i,x_i} \rangle^B = L_{i,0} \cdot \underbrace{(1 \oplus \langle x_i \rangle^A \oplus \langle x_i \rangle^B)}_{= \neg x_i} \oplus L_{i,1} \cdot \underbrace{(\langle x_i \rangle^A \oplus \langle x_i \rangle^B)}_{= x_i} = L_{i,x_i}. $$

From this, the parties obtain secret shares of $\hat{X}$ (the garbled input), since they have secret-shares of the input labels $L_{i,x_i}$, for all $i \in [s]$. While at first glance it appears that we have successfully constructed secret-shares of a garbling (by obtaining secret-shares of $\hat{X}$) this approach is unfortunately very limited.

**Limitation of the strawman approach.** In many cases, it is not sufficient to simply obtain secret-shares of $\hat{X}$. For example, consider the two-party computation application from Section 1, where parties $A$ and $B$ have inputs $a$ and $b$ and would like to privately compute $C(a, b)$ over their inputs. If they simply compute shares of $\hat{X}$ as in the strawman scheme, and swap their shares of $\hat{X}$ to learn $\hat{X}$, they would indeed be able to evaluate $\hat{C}$ and learn $C(a, b)$. However, this approach would be completely insecure: both parties know the entire set of 2s labels used to generate the garbling $\hat{X}$, which would reveal $(a, b)$ to both parties! The problem here is that both parties have the entire set of input labels in the clear, which immediately reveals the inputs. While the strawman solution could work in a three-party setting, where the two parties send the resulting garbled circuit $\hat{C}$ and shares of their garbled input $\hat{X}$ to a non-colluding third party, it does not naturally apply to other settings, and has limited applications.

With the above limitation in mind, we identify the following requirements for a secret-shared garbling scheme in a two-party setting.

**Requirement I: A secret-shared garbled circuit.** To effectively garble a secret-shared input in a way that would not reveal the input to either party (even in the presence of the garbled input $\hat{X}$), the labels need to be secret-shared between the two parties. Secret-sharing the labels ensures that neither
party has access to the labels in the clear when generating the garbling. However, if the labels are secret-shared, then the garbled circuit $\hat{C}$ also needs to be secret-shared. To wit, our first requirement is a way for the parties to non-interactively generate a secret-shared garbled circuit and select the labels corresponding to their secret-shared input *without* having the labels in the clear.

**Requirement II: A way to generate fresh garblings.** Even with a way to generate a secret-shared garbled circuit, the parties would only be able to use $\hat{C}$ for one computation, after which they would need to regenerate a fresh garbled circuit $\hat{C}$ (and the corresponding labels). While it was easy to do so in the strawman solution since the garbled circuit (and labels) were known by both parties, if the labels are secret-shared, then refreshing the labels becomes necessary. Thus, our second requirement is a way for the parties to generate “fresh” instances of the garbled circuit $\hat{C}$ that can be used with new inputs.

With the above requirements laid out for generating secret shared garbled circuits, we identify the following two roadblocks in achieving them efficiently.

**Challenge I: Efficiently refreshing garbled circuits.** The second challenge is that it is unclear how to generate “new” secret shares of a garbled circuit efficiently (and non-interactively). While similar problems have been faced in prior work [28, 64], their solutions resort to interaction between parties to generate each garbled circuit. Therefore, at first glance, it may appear impossible to have a (fully non-interactive) way to refresh secret-shared garbled circuits, without resorting to heavy machinery (e.g., reusable garbled circuits [43]).

**Challenge II: Secret-shared input garbling.** The first challenge is that if the parties only have secret-shares of the input labels, then “selecting” the labels corresponding to the input $x$ can no longer be done using Eq. (1), necessitating a different approach. (Computing the multiplication between two secret shared values would require interaction between parties, which we want to avoid.)

**Organization.** In the rest of this overview, we focus on the first challenge since it is the more difficult one to resolve. In Section 2.2 we overview our PCG-based approach and in Sections 2.3 to 2.5 we describe our TAPCF-based approach. We then overview a simple method for computing an input garbling using homomorphic secret sharing (HSS) in Section 2.6, a formal construction is presented in Section 6.1. This enables resolving the second challenge of connecting inputs to the pseudorandom garbled circuit instances.

## 2.2 Refreshing a secret-shared garbled circuit with a PCG

We now turn to explaining our first key idea and contribution: developing a PCG to generate many “disposable” secret-shared instances of the garbled circuit. Taking a step back, we will separate the random values that the parties can trivially generate themselves from the ones that require “structure” (and which we will generate using a PCG for a suitable correlation).

In modern garbled circuit schemes, labels are defined using the “free-xor” trick [53] which, roughly speaking, defines $L_1$ in terms of $L_0$ and a global offset
$\Delta$. In particular, $L_1 := L_0 \oplus \Delta$. Then, the $i$-th wire value in the garbled circuit is masked with a random bit $r_i \in \{0, 1\}$. Each AND gate taking as input wires $i$ and $j$ has an output wire mask $r_i \wedge r_j$ and output label $L_{k,0} \oplus (r_i \wedge r_j) \cdot \Delta$. The output wire masks must additionally be scaled by the free-xor offset $\Delta^\sigma$.

In a secret-shared garbled circuit [37, 63, 64], each party obtains its own global offset $\Delta^\sigma \in \{\Delta^A, \Delta^B\}$, which can be viewed as secret shares of an unknown $\Delta$. We point the reader to the full version for additional background on garbled circuits and secret-sharing friendly constructions. We will denote secrets known to party A in red and those known to B in blue.

Our first observation is that the parties can reuse the same free-xor offsets $\Delta^A$ and $\Delta^B$ each time they generate a new garbled circuit, since this value is independent of the circuit inputs and never revealed. Additionally, party $\sigma \in \{A, B\}$ can generate its labels $L_{i,0}^\sigma$, for all wires $i$, by sampling them locally. From that, each party can derive $L_{i,1}^\sigma := L_{i,0}^\sigma \oplus \Delta^\sigma$ using the sampled offset $\Delta^\sigma$. The non-trivial part is generating shares of the $i$-th wire label and output mask. Specifically, the parties need to generate “fresh” masks $r_i$ and $r_j$, and secret shares of

$$r_i, r_j, (r_i \wedge r_j), r_i \cdot \Delta^A, r_i \cdot \Delta^B, r_j \cdot \Delta^A, r_j \cdot \Delta^B, (r_i \wedge r_j) \cdot \Delta^A, (r_i \wedge r_j) \cdot \Delta^B,$$

which then allows them to compute shares of the output wire labels:

$$L_{k,r_i \wedge r_j} := L_{k,0} \oplus (r_i \wedge r_j) \cdot \Delta = L_{k,0}^A \oplus (r_i \wedge r_j) \cdot \Delta^A \oplus L_{k,0}^B \oplus (r_i \wedge r_j) \cdot \Delta^B.$$

Specifically, $(r_i \wedge r_j) \cdot \Delta^\sigma = \langle (r_i \wedge r_j) \cdot \Delta^\sigma \rangle^A \oplus \langle (r_i \wedge r_j) \cdot \Delta^\sigma \rangle^B$, for $\sigma \in \{A, B\}$, which allows the parties to derive secret shares of the above expression. Moreover, we can view the above equations as the output of a degree-2 polynomial $P$ in two variables $r_i, r_j$ with fixed, private global scaling constants $\Delta^A$ and $\Delta^B$. It is known how to construct PCGs for degree-2 correlations [19, 20, 22, 23, 33, 62], which immediately makes it possible for the dealer to distribute short seeds $s^A$ and $s^B$ such that each party can locally apply the PCG to derive secret shares of $r_i, r_j, r_i \wedge r_j$. However, degree-2 correlations do not enable computing a share of the degree-3 expression with the global scaling constants. Fortunately, however, nearly all existing PCG constructions can be adapted to output shares scaled by a (secret) global constant at a negligible performance cost, which we formalize in the full version. With that, in the full version of this work, we show how to construct a garbling PCG for generating secret-shared garbled circuits, from the Ring-LPN assumption by plugging in either the practical PCG construction of Boyle et al. [22] or Schoppmann et al. [62].

Finally, the output wire mask is defined as a linear function of the next gate, as follows: Given $r_i, r_j, (r_i \wedge r_j)$, the set of four possible output wire masks (corresponding to the four possible inputs to the AND gate) are computed as:

$$\rho_{00} := (r_i \wedge r_j) \oplus r_k, \quad \rho_{01} := \rho_{00} \oplus r_i, \quad \rho_{10} := \rho_{00} \oplus r_j, \quad \rho_{11} := \rho_{00} \oplus r_i \oplus r_j \oplus 1,$$

which are all linear functions of the shares held to both parties and the mask $r_k$ of the next gate. More details on this are provided in the full version.
<figure><img src="image_3.png" /><figcaption>**Fig. 1:** Example circuit and mask values in the case where several wires are duplicated across several gates.</figcaption></figure>

**Dealing with duplicate wires.** A subtle challenge we need to address is that the above method of secret sharing the garbled circuit implicitly assumes that no two gates in the circuit take the same inputs (i.e., that the circuit structure can be described as a binary tree). In the general case, circuits can have two or more gates that share the same input wire. A simple example is illustrated in Fig. 1. If the PCG outputs random and independent masks for each gate, then the same wire would have different masks at the two input gates it is a part of, violating correctness. To address this, we require a programmability property from the PCG, which, at a high level, allows the dealer to distribute PCG seeds that share a common random mask $r_i$. In the example of Fig. 1, the wire masks $r_2$ and $r_3$ are reused across two different gates. Therefore, the PCG seeds associated with those gates need to be defined so as to share the same seed, making the output consistent. In this way, we can “program” each wire mask into the gate PCG, so that all masks for the same wire are identical across gates, ensuring correctness.

**Limitations of the PCG approach.** With our Garbling PCG construction, the parties can efficiently generate many fresh instances of the same secret-shared garbled circuits that they can then use for computations involving different inputs. However, while the PCG approach is simple, it has some practical downsides:

(1) PCGs, by definition, generate all the correlations in one monolithic expansion. This requires the parties to expand the PCG seed into *all* secret-shared random instances of the garbled circuit they will ever need to use. This is only practical if the total number of instances required is small.

(2) Under the hood, our PCG-based construction for garbling correlations requires one PCG for degree-2 correlation *per* AND gate. This leads to a large concrete blowup in the size of the PCG seed given to the parties (e.g., a Garbling PCG for circuits with 10,000 AND gates has a seed size of 30 GB).

(3) The circuit topology (i.e., the function computed by the garbled circuit) must be fixed at setup time. The parties cannot “rewire” the circuit gates on-demand since all instances of the garbled circuit output by the PCG must
be identical. While this is sufficient for applications where the parties need
to garble the same function repeatedly, it is not a versatile solution and has
obvious limitations (e.g., it does not imply reusable two-party computation).

To address all three limitations simultaneously, we introduce the notion of a
*topology-adaptive* PCF (TAPCF), which is likely to have applications outside
of secret-shared garbled circuits and is a natural object of study. In a nutshell,
as already explained in Section 1, a TAPCF allows all *correlations* to be spec-
ified *on-the-fly* and depend on common randomness when evaluating the PCF,
which, among other things, makes it possible in our construction for the parties
to specify the garbling correlations on-demand and generate any secret-shared
garbled circuit of their choosing.

## 2.3 Rewiring a secret-shared garbled circuit with a TAPCF

Abstractly, a TAPCF is defined with respect to an (implicit) PRF $F_K$ and al-
lows the evaluators to efficiently compute secret shares of correlations of the form
$P(F_K(a_1), \dots, F_K(a_m))$, where $P$ is some correlation function and $(a_1, \dots, a_m)$
is a vector of PRF inputs. For example, if we choose $P$ to be a degree-2 multiplica-
tion correlation, i.e., $(a, b) \mapsto (a, b, ab)$, computing $P(F_K(a_1), F_K(a_2))$ produces
secret shares of a correlation with the form $(F_K(a_1), F_K(a_2), F_K(a_1) \cdot F_K(a_2))$—
i.e., a pseudorandom Beaver triple [8].

The power of the TAPCF abstraction is that the evaluators can specify which
inputs to the function they want to compute correlations of *at evaluation time*.
This stands in contrast to the standard PCF definition, where it is not possi-
ble to “mix-and-match” inputs to the correlation function *P*. Surprisingly, this
powerful feature of TAPCFs can be obtained from a simple yet—to the best
of our knowledge, overlooked—property implicit in several existing PCF con-
structions [23, 24], where the evaluation algorithm *already* allows specifying the
correlation on-demand, even if the standard definition of PCFs does not ex-
plicitly require this to be the case! We believe that by shining a light on this
surprising fact, and formally defining the notion of TAPCFs, new applications
will emerge.

In Section 5, we show that using a TAPCF, the parties can generate the
necessary garbling correlations by letting *P* be a suitable degree-2 correlation,
as described in Section 2.2. At a high level, the TAPCF is used to generate
pseudorandom masks for each wire in the circuit. Let $r_i$ and $r_j$ be two such
masks for wires *i* and *j*, respectively. Then, for an AND gate that takes as input
wires *i* and *j*, the TAPCF is used to generate a pseudorandom output mask
$r_k$ by specifying inputs *i* and *j*. Specifically, the parties compute shares of the
degree-2 correlation $P(F_K(i), F_K(j))$, which generates shares of the output wire
mask $r_k$. The TAPCF, guarantees that all gates that take as input wire *i* have
an output mask generated as $P(F_K(i), F_K(\cdot))$, which, at a high level, guarantees
consistency across all wire masks in the circuit. Using this idea, we obtain: (1)
on-demand garbled circuit generation, (2) practical key sizes of around 1 GB
that are essentially independent of the generated garbled circuit size, and (3)
efficient “on-the-fly” garbling, allowing the parties to specify which circuit they
wish to garble at evaluation time by appropriately specifying the wire topology.

## 2.4 How to define a TAPCF

The standard PCF definition specifies that each PCF evaluation appears indis-
tinguishable to a fresh sample from the target correlation. Similarly, a TAPCF
specifies that each evaluation should yield a random-looking sample from the
target correlation, except that (1) some of the random coins used to generate
one correlation can also be used to generate other correlations, and (2) the eval-
uators can specify a cross-sample correlation at evaluation time.

We provide a conceptually simple definition to capture this notion for cor-
relations defined over Abelian groups, which automatically makes the target
correlation reverse-sampleable. At a high level, a target correlation specified
by a function $P: \mathbb{G}_2^m \to \mathbb{G}_3$ outputs *additive shares* (in the output group
$\mathbb{G}_3$) of $P(F_K(a_1), \dots, F_K(a_m))$, for random inputs $(a_1, \dots, a_m) \in \mathbb{G}_1^m$, where
$F_K: \mathbb{G}_1 \to \mathbb{G}_2$ is the implicit (weak) PRF.

Our definition of TAPCF is much closer in spirit to the traditional notion
of pseudorandom functions: A TAPCF (TAPCF.Gen, TAPCF.Eval) is a pair of
algorithm where TAPCF.Gen generates a pair of keys ($k^A, k^B$), and TAPCF.Eval
takes as input a key, a function $P$ specifying the correlation, and a set of in-
puts $(a_1, \dots, a_m)$. Correctness states that evaluation shares, denoted $y^\sigma \leftarrow$
TAPCF.Eval($\sigma, k^\sigma, P, (a_1, \dots, a_m)$), are computationally indistinguishable from
shares $(y^A, y^B)$ of $P(R(a_1), \dots, R(a_m))$, where $R$ is a truly random function.
Similarly, security states that even given $k^\sigma$, evaluations $y^\sigma \leftarrow$ TAPCF.Eval($\sigma, k^\sigma$,
$P, (a_1, \dots, a_m)$) are computationally indistinguishable from $P(R(a_1), \dots, R(a_m))$—
$y^\sigma$. In particular, our notion of TAPCF recovers the standard definition PCFs
*when no two inputs* $a_i$ are reused across different evaluations. We find that our
definition of TAPCFs sidesteps some of the complexities present in the standard
PCF definition (e.g., the need for defining a reverse-sampler for the target cor-
relation), while also making it clear that all PCFs must contain a (weak/strong)
PRF “under the hood.”

## 2.5 How to build a TAPCF

A pseudorandom correlation function outputs pseudorandom samples of a cor-
relation, where a typical choice of correlation deals shares of a low-degree poly-
nomial. For example, a PCF for Beaver triples yields, on input $i$, shares of
$(a_i, b_i, a_i \cdot b_i)$ for pseudorandom values $a_i, b_i$. However, in general, the definition
of a PCF does not permit correlations *across* the samples generated using the
PCF key (for example, it does not permit generating triples that share a common
element, such as $(a_i, b_i, a_i \cdot b_i)$ and $(a_i, b_j, a_i \cdot b_j)$). The notion of *programmable*
PCFs [24] does not capture this feature either: a programmable PCF allows to
program *different* PCF keys such that evaluating both keys on the same input
yield correlated outputs. However, that results in the cross-output correlation
being fixed at key generation time, making the correlation hardcoded in the keys.
However, a closer look at existing constructions of PCFs reveals that they
are much more flexible than the generic notion allows: they typically permit
specifying, on the fly, a cross-output correlation between distinct PCF outputs
produced by the same key!

The general idea for how we can achieve this cross-correlation property in existing PCF constructions is the following. At a high level, the PCF constructions of Boyle et al. [23, 24] can be made to share pseudorandom, degree-$d$ monomials (in our Beaver triple example, $d=2$), by first “virtually” generating a $d$-dimensional hypercube of monomials $\mathbf{a}_1 \otimes \mathbf{a}_2 \otimes \cdots \otimes \mathbf{a}_d$, where $(\mathbf{a}_1, \dots, \mathbf{a}_d)$ are exponentially-long pseudorandom vectors, and “accessing” an entry $(i_1, \dots, i_d)$ of the hypercube using $O(c^d)$ evaluations of a suitable function secret sharing (FSS) scheme [14, 16], where $c$ is a sparsity parameter that depends on the code used by the underlying LPN variant. Because chosen positions $(i_1, \dots, i_d)$ can be accessed on-demand, these schemes allow specifying, at evaluation time, which pseudorandom monomials should be used when generating the correlation.

To illustrate, we focus on degree-2 correlations (sufficient for our applica-
tion), and use the construction of Boyle et al. [24] that is based on the expand-
accumulate LPN (EA-LPN) assumption (Definition 2), which can be restated as
follows.

**EA-LPN assumption (intuition).** Fix a length parameter $N$ (typically very large, e.g., $2^{40}$), a sparsity parameter $c$, and a noise parameter $t$ ($c, t$ are typically small, e.g., 80). Define the “threshold vector” as a vector of the form $(0, \dots, 0, 1, \dots, 1)$, where a length-$\ell$ threshold has the first “1” at some position $i$. Equivalently, we can view this vector as the truth-table of the greater-than predicate $g_i(x) = 0$, for $x < i$, and $g_i(x) = 1$, for $x \ge i$. Now, let $\mathbf{e}$ denote the vertical concatenation of $t$ random threshold vectors of length $5N/t$, and let $\mathbf{H}$ be a random $N \times 5N$ sparse matrix, whose entries are Bernoulli samples with parameter $c/5N$ (i.e., $\mathbf{H}$ has $c$ ones per row on average). Then, EALPN($N, t, c$) states that $\mathbf{H} \cdot \mathbf{e}$ is computationally indistinguishable from a random vector.

**TAPCF construction.** To build a topology-adaptive PCF for degree-2 correlations, we sample two vectors $e_a, e_b$ as the concatenation of $t$ random threshold vectors. Observe that under the EALPN assumption, $\mathbf{a} = \mathbf{H} \cdot e_a$ and $\mathbf{b} = \mathbf{H} \cdot e_b$ are pseudorandom. The 2-dimensional hypercube of monomials is then $\mathbf{a} \otimes \mathbf{b} = \mathbf{a} \cdot \mathbf{b}^{\top} = \mathbf{H} \cdot (e_a \cdot e_b^{\top}) \cdot \mathbf{H}^{\top}$. By construction, the matrix $e_a \cdot e_b^{\top}$ is divided into $t^2$ squares of side length $5N/t$, where each square is the truth-table of a 2-dimensional rectangle predicate (i.e., a predicate of the form $g_{i,j}(u,v) = 1$ if $u \ge i$ and $v \ge j$, and 0 else). Using FSS for 2-dimensional rectangle predicates [16] yields a way to provide “compressed” shares of such truth tables, where the shares of $g_{i,j}$ have size $O(\log^2(5N/t))$ when using the FSS scheme of Boyle et al. [16], and enable evaluating $g_{i,j}$ on any input $x$.

Hence, by distributing $t^2$ FSS keys for 2-dimensional rectangle predicates,
the parties can generate additive shares of any entry of the matrix $e_a \cdot e_b^{\top}$ from
$O(t^2 \cdot \log^2(5N/t))$-sized FSS keys. Now, since the rows of $\mathbf{H}$ are $c$-sparse (on
average), computing shares of $a_i \cdot b_j$ (the $(i,j)$-th entry of the hypercube $\mathbf{a} \otimes \mathbf{b}$)
can be done as follows. First, identify the $c^2$ entries of $e_a \cdot e_b^{\top}$ at all positions
<figure><img src="image_4.png" /><figcaption>**Fig. 2:** Computation of the monomial $a_i \cdot b_j$ using the EALPN-based PCF of Boyle et al. [24], where $\mathbf{a} = \mathbf{H} \cdot \mathbf{e}_a$ and $\mathbf{b} = \mathbf{H} \cdot \mathbf{e}_b$. The $c^2$ position of $\mathbf{e}_a \cdot \mathbf{e}_b^\top$ at the intersection of the red and blue lines can be computed using FSS for 2-dimensional rectangle predicates.</figcaption></figure>

($u, v$) where both the $u$-th entry of the $i$-th row of $\mathbf{H}$ and the $v$-th entry of the $j$-th row of $\mathbf{H}$ are equal to 1. Evaluate the FSS for 2-dimensional rectangles at all these positions, and sum the outcomes. See Fig. 2 for an illustration and Section 4 for the full construction.

## 2.6 How to garble secret shared inputs

At this point, we have two ways of producing pseudorandom secret shares of a pseudorandom garbled circuit. More concretely, the techniques described thus far produce a pair of offsets $\Delta^A$ and $\Delta^B$ and a set of input labels $L_{1,0}^A, \dots, L_{s,0}^A$ and $L_{1,0}^B, \dots, L_{s,0}^B$, which are distributed to each party. Additionally, both parties obtain secret shares of pseudorandom input masks $\mathbf{r}_1, \dots, \mathbf{r}_s$ (along with shares of the masks for each wire in the circuit, which we ignore for the time being).

The challenge now is having the parties obtain pseudorandom shares of their private inputs $x$ and $y$. For the purposes of this overview, we focus on a single party (possibly an external third party) sharing their input $x$. The main idea is to have the trusted setup (which generates the PCG seeds or TAPCF keys) additionally distribute the fixed global offsets $\Delta^A$ and $\Delta^B$ to the two parties in the form of input shares under a public-key HSS scheme.

In a nutshell, HSS enables evaluating low-degree polynomials over input shares between two parties. Therefore, to secret share an input, each party (or an external party) computes an HSS input encoding of its private input $x = (x_1, \dots, x_s)$, which are also distributed to the two parties. Each party then holds an HSS input share $\Delta^A, \Delta^B$, and $(x_1, \dots, x_s)$.

The two parties then compute the degree-2 HSS program that computes $\Delta^A \cdot x_i, \Delta^B \cdot x_i$, which allows them to compute shares of the labels as follows. First, the parties compute shares of $x_i \cdot \Delta^A$ and $x_i \cdot \Delta^B$ using the HSS homomorphic evaluation. Second, the parties use shares of $\mathbf{r}, \mathbf{r} \cdot \Delta^A, \mathbf{r} \cdot \Delta^B$ (which are part of the pseudorandom secret shared garbled circuit) to compute additive shares of

$$L_{i, \rho_i}^A := L_{i, 0}^A \oplus (x_i \oplus \mathbf{r}_i) \cdot \Delta^A \quad \text{and} \quad L_{i, \rho_i}^B := L_{i, 0}^A \oplus (x_i \oplus \mathbf{r}_i) \cdot \Delta^B.$$
These labels now correspond to the correct (masked) input bits, enabling the evaluation of the garbled circuit on input $x$. In particular, even though each party learns the value of the label (after recovering the share from the other party), it does not learn the input value $x_i$ because it does not learn $r_i$ (which masks the true value of the wire).

## 3 Preliminaries

Here, we describe notation and the background on pseudorandom correlations.

**Notation.** We let $\mathbb{N}$ denote the set of natural numbers and $\mathbb{F}_p$ denote a finite field of order $p$. We denote a vector as $\mathbf{v} = (v_1, \dots, v_n)$ and will sometimes write $(v_i)_{i=1}^n$ as a shorthand. We denote by $\text{poly}(\cdot)$ any polynomial and by $\text{negl}(\cdot)$ any negligible function. We let $x \leftarrow_S S$ denote a uniformly random sample drawn from $S$. We let $x \leftarrow \mathcal{A}$ denote assignment and $x := y$ denote initialization of $x$ to the value of $y$. By an efficient algorithm $\mathcal{A}$ we mean that $\mathcal{A}$ is modeled by a (possibly non-uniform) Turing Machine that runs in probabilistic polynomial time. We write $D_0 \approx_c D_1$ to mean that two distributions $D_0$ and $D_1$ are computationally indistinguishable to all efficient distinguishers $\mathcal{D}$ and $D_0 \approx_s D_1$ to mean that $D_0$ and $D_1$ are statistically indistinguishable.

**Secret sharing.** We denote two-party secret shares of a value $x$ as the tuple of shares $(\langle x \rangle^A, \langle x \rangle^B)$ such that $\langle x \rangle^A \oplus \langle x \rangle^B = x$.

### 3.1 Cryptographic assumptions

**Definition 1 (Ring-LPN, verbatim from [22]).** Let $\mathcal{R} = \mathbb{Z}_p[X]/F(X)$ for a prime $p$ and a degree-$N$ polynomial $F(X) \in \mathbb{Z}_p[X]$. For $t \in \mathbb{N}$ let $\mathcal{H}\mathcal{W}_{\mathcal{R},t}$ be the distribution of “sparse polynomials” over $\mathcal{R}$ obtained by sampling $t$ noise positions $\mathbf{A} \leftarrow [0, \dots, N)^t$ and $t$ payloads $\mathbf{b} \leftarrow (\mathbb{Z}_p^*)^t$ uniformly at random, and outputting $e(X) := \sum_{j=0}^{t-1} \mathbf{b}[j] \cdot X^{\mathbf{A}[j]}$. For $\mathcal{R} = \mathcal{R}(\lambda)$, $m = m(\lambda)$, $t = t(\lambda)$, we say that the ring-LPN problem $\mathcal{R}$-LPN$_{\mathcal{R},m,t}$ is hard if for every non-uniform polynomial-time distinguisher $\mathcal{A}$, it holds that

$$ \left| \Pr[\mathcal{A}((a^{(i)}, a^{(i)} \cdot e + f^{(i)})_{i=1}^m) = 1] - \Pr[\mathcal{A}((a^{(i)}, u^{(i)})_{i=1}^m) = 1] \right| \le \text{negl}(\lambda), $$

where the probabilities are taken over $a^{(1)}, \dots, a^{(m)}, u^{(1)}, \dots, u^{(i)} \leftarrow_R \mathcal{R}$ and $e, f^{(1)}, \dots, f^{(m)} \leftarrow \mathcal{H}\mathcal{W}_{\mathcal{R},t}$. Moreover, the regular ring-LPN problem $\mathcal{R}$-regLPN$_{m,t}$ is defined in the same way, except that it uses $\text{reg}\mathcal{H}\mathcal{W}_{\mathcal{R},t}$, the distribution obtained by sampling the $t$ noise positions $\mathbf{A} \leftarrow [0, \dots, N)^t$, such that each block of size $N/t$ contains exactly one position. (Here, we assume that $t$ divides $N$.)

**Definition 2 (EALPN($N, t, c$), cf. [24]).** The expand-accumulate syndrome assumption with noise weight $t$, matrix sparsity $c$, and number of samples $N$, denoted EALPN($N, t, c$), states that

$$ \left\{ (H, \mathbf{b}) \left| \begin{array}{l} H \leftarrow_R \mathcal{M}_{\text{ea}}(\text{pp}) \\ e \leftarrow_R \mathcal{N}_{\text{ea}}(\text{pp}) \\ \mathbf{b} := H \cdot e \end{array} \right. \right\} \approx_c \left\{ (H, \mathbf{b}) \left| \begin{array}{l} H \leftarrow_R \mathcal{M}_{\text{ea}}(\text{pp}) \\ \mathbf{b} \leftarrow_R \mathbb{F}_2^N \end{array} \right. \right\}. $$
## 3.2 Pseudorandom correlation functions

Here, we provide a slight generalization of the standard definition of PCFs. The standard definition requires the correlation of the PCF to be reverse sampleable, similarly to the definition of PCGs. This is a necessary technicality associated with the standard PCF (and PCG) definition, but abstracted away in our TAPCF definition. The generalization consists in allowing the correlation to take an additional public input in, with the corresponding changes to the pseudorandomness and security definitions (allowing the adversary to choose these inputs adaptively).

**Definition 3 (Reverse-sampleable correlation with setup).** Let $\lambda$ be a security parameter and $n = n(\lambda) \in \text{poly}(\lambda)$ be an output length. Let (Setup, $\mathcal{Y}$) be two probabilistic algorithms, where on input $1^{\lambda}$, Setup generates a random pair $yk = (yk^A, yk^B)$. Moreover, $\mathcal{Y}$ takes as input the security parameter, a correlation key $yk$ and an input in $\{0, 1\}^*$, returns a pair $(y^A, y^B) \in \{0, 1\}^n \times \{0, 1\}^n$, defining a correlation on the outputs. We say that $\mathcal{Y}$ defines a reverse-sampleable correlation with setup, if there exists a probabilistic polynomial time algorithm RSample that takes as input the security parameter, $yk^{\bar{\sigma}}$, in $\{0, 1\}^*$, $\sigma \in \{A, B\}$, and $y^{\sigma} \in \{0, 1\}^n$, and outputs $y^{\bar{\sigma}} \in \{0, 1\}^n$, such that for all in $\{0, 1\}^*$, all $yk = (yk^A, yk^B)$ in the image of Setup and all $\bar{\sigma} \in \{A, B\} \setminus \{\sigma\}$, it holds that:

$$ \{(y^A, y^B) \mid (y^A, y^B) \leftarrow \mathcal{Y}(1^{\lambda}, yk, \text{in})\} \\ \approx_s \left\{ \begin{array}{l} (y^A, y^B) \mid \begin{array}{l} (y'^A, y'^B) \leftarrow \mathcal{Y}(1^{\lambda}, yk, \text{in}) \\ y^{\sigma} := y'^{\sigma} \end{array} \\ y^{\bar{\sigma}} \leftarrow \text{RSample}(1^{\lambda}, yk^{\bar{\sigma}}, \text{in}, \sigma, y^{\sigma}) \end{array} \right\}. $$

<figure><img src="image_5.png" /><figcaption>**Fig. 3:** (Strong) Pseudorandom $\mathcal{Y}$-correlated outputs of a PCF. Here, valid adversaries choose the $x_i \in \{0, 1\}^n$ as nonces, i.e. pairwise distinct.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>**Fig. 4:** (Strong) Security of game for a PCF. Here, RSample is the algorithm for reverse sampling the correlation $\mathcal{Y}$, as defined in Definition 3. Moreover, valid adversaries choose the $x_i \in \{0, 1\}^n$ as nonces, i.e. pairwise distinct.</figcaption></figure>

**Definition 4 (Pseudorandom Correlation Function [23, 24]).** Let $\lambda$ be a security parameter, $\mathcal{Y}$ be a reverse-sampleable correlation with setup with output length $n(\lambda) \in \text{poly}(\lambda)$, and $\lambda \le m = m(\lambda) \in \text{poly}(\lambda)$ be an input length. A pseudorandom correlation function (PCF) for $\mathcal{Y}$ is defined by a pair of algorithms (PCF.Gen, PCF.Eval) with the following functionality:

- PCF.Gen($1^{\lambda}$, yk) $\rightarrow$ ($k^A, k^B$). The randomized generation algorithm takes as input the security parameter $\lambda$ and the correlation key yk. It outputs a pair of keys ($k^A, k^B$).

- PCF.Eval($\sigma, k^\sigma, \text{in}, x) \rightarrow y^\sigma$. The deterministic evaluation algorithm takes as input $\sigma \in \{A, B\}$, a key $k^\sigma$, a correlation input in $\{0, 1\}^*$ and a (PCF) input string $x \in \{0, 1\}^m$. It outputs a string $y^\sigma \in \{0, 1\}^n$.

A (strong) PCF for the correlation $\mathcal{Y}$ must the following properties:

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

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

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

- Security. For all distinct $\sigma, \bar{\sigma} \in \{A, B\}$, and all (valid) efficient adversaries $\mathcal{A}$, there is a negligible function $\text{negl}(\cdot)$ such that for all sufficiently large $\lambda$,

$$ \left| \Pr[\text{Exp}_{\mathcal{A},N,\sigma,\bar{\sigma},0}^{\text{sec}}(\lambda) = 1] - \Pr[\text{Exp}_{\mathcal{A},N,\sigma,\bar{\sigma},1}^{\text{sec}}(\lambda) = 1] \right| \le \text{negl}(\lambda), $$
where $\text{Exp}^{\text{sec}}_{A,N,\sigma,\bar{\sigma},b}(\lambda)$, for $b \in \{0,1\}$, is as defined in Figure 4 (again, with the adversary given $N(\lambda)$ samples).

**Remark 1 (Strong PCFs in the standard model).** Our PCF constructions assume that there is a mapping $H$ that maps any PCF input $a$ to a sample from $\text{Ber}^{5N}_{c/2N}$, i.e., a mapping to a random row of $M$ (as specified above). To get a weak PCF, it suffices to let $H$ be a sampler for $\text{Ber}^{5N}_{c/2N}$, which uses $a$ as randomness; in the strong PCF setting, one can model $H$ as a random oracle with outputs sampled from $\text{Ber}^{5N}_{c/2N}$. Alternatively, a recent work [26] showed how to instantiate $H$ in the standard model using extremely lossy functions [68], at the cost of assuming a strengthened EALPN assumption. While we describe our constructions assuming a strong PCF to simplify notation, in practice, for our applications, it is enough for the parties to have a shared source of randomness to avoid this requirement.

# 4 Topology-Adaptive PCFs

Here, we define the notion of a topology-adaptive PCF (TAPCF) and provide a construction from the EA-LPN assumption from [24], cf. Definition 2.

## 4.1 Definition

**Definition 5 (Topology-Adaptive PCF (TAPCF)).** Let $\lambda$ be a security parameter, let $m = m(\lambda)$, $n = n(\lambda) \in \text{poly}(\lambda)$, let $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_3$ be Abelian groups of order poly($\lambda$) and define a set of m-input functions $\mathcal{P}$ of type $P: \mathbb{G}_2^m \to \mathbb{G}_3$. A TAPCF consists of a tuple of efficient algorithms (TAPCF.Gen, TAPCF.Eval) with the following functionality:

- TAPCF.Gen($1^{\lambda}$) $\to$ ($k^A, k^B$). The randomized generation algorithm takes as input the security parameter $\lambda$ and outputs a pair of keys ($k^A, k^B$).

- TAPCF.Eval($\sigma, k^\sigma, P, (a_1, \dots, a_m)$) $\to$ $y^\sigma$. The deterministic evaluation algorithm takes as input $\sigma \in \{A, B\}$, a key $k^\sigma$, a description of a function $P \in \mathcal{P}$, and a vector $(a_1, \dots, a_m) \in \mathbb{G}_1^m$. It outputs an element $y^\sigma \in \mathbb{G}_3$.

Let $\mathcal{R} = \{R: \mathbb{G}_1 \to \mathbb{G}_2\}$ be the set of all functions from $\mathbb{G}_1$ to $\mathbb{G}_2$. Then, TAPCF is a (strong) TAPCF, if the following two properties hold:

- Correctness / Pseudorandom $\mathcal{P}$-correlated outputs. For every $\sigma \in \{A, B\}$, and all efficient adversaries $\mathcal{A}$, there exists a negligible function $\text{negl}$ such that for all sufficiently large $\lambda$,

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

where $\text{Exp}^{\text{pr}}_{\mathcal{A},b}(\lambda)$, for $b \in \{0,1\}$, is as defined in Figure 5.
<figure><img src="image_7.png" /><figcaption>Fig. 5: Pseudorandom *P*-correlated outputs for a TAPCF.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6: Security of game for a TAPCF.</figcaption></figure>

- Security. For all distinct $\sigma, \bar{\sigma} \in \{A, B\}$, and all efficient adversaries $\mathcal{A}$, there exists a negligible function $\text{negl}$ such that for all sufficiently large $\lambda$,

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

where $\text{Exp}_{\mathcal{A},\sigma,\bar{\sigma},b}^{\text{sec}}(\lambda)$, for $b \in \{0, 1\}$, is as defined in Figure 6.

*Remark 2.* Note that Definition 5 has an “implicit” PRF $F_K: \mathbb{G}_1 \to \mathbb{G}_2$ applied to each input before the correlation function $P$ is applied over the PRF outputs. Hence, we define security with respect to a truly random function $R: \mathbb{G}_1 \to \mathbb{G}_2$. Also, we remark on the choice of defining this PCF in the strong variant and how to obtain it in the standard model in Remark 1.

## 4.2 TAPCF construction

We briefly recall the construction of PCF for degree-$d$ correlations from [24], whose security reduces to the expand-accumulate LPN assumption (Definition 2). Let FSS = (FSS.Gen, FSS.Eval) be a function secret sharing scheme for $d$-dimensional rectangle predicates, defined as follows:
**Definition 6 (d-Dimensional Rectangle Predicate).** Let $\mathbb{G}$ be an Abelian group. A $d$-dimensional rectangle predicate $f_{(\alpha,\beta),m}$ for $\alpha, \beta \in (\{0,1\}^\nu)^d$, and $m \in \mathbb{G}$, is defined as the function $f(\boldsymbol{x}) = m$ iff $\alpha_i \le x_i \le \beta_i$ for all $i \in [d]$, and $f(\boldsymbol{x}) = 0$ otherwise. When $\beta_i = \mathbf{1}$ for all $i \in [d]$, we denote it as $f_{\alpha,m}$. A $d$-dimensional distributed rectangle function is an FSS scheme for the family of $d$-dimensional rectangle predicates with domain $(\{0,1\}^\nu)^d$ and range $\mathbb{G}$.

Fix parameters $pp = (N, t, c)$. $N$ is the number of samples, $c$ is a matrix sparsity parameter (typically $c = \Theta(\log N)$ or $\omega(\log N)$), and $t$ is the Hamming weight of the noise. Let $\Delta_N$ denote a $5N$-by-$5N$ lower triangular matrix filled with ones. We let $M_{\text{ea}}(pp)$ denote the distribution obtained by sampling an $N$-by-$5N$ matrix $M$ whose entries are independent Bernoulli sample equal to 1 with probability $c/2N$, and outputting $H = M \cdot \Delta_N$. Let $\text{Ber}_{c/2N}^{5N}$ denote the distribution of the rows of $M$. We denote by $N_{\text{ea}}(pp)$ the distribution obtained by concatenating $t$ random unit vectors of length $5N/t$.

The PCF construction of [24], which we restate here in the language of TAPCF, is given in Construction 1. As an independent contribution, in proving security of our TAPCF construction, we provide a proof of security for the $d$-dimensional generalization of the PCF construction of Boyle et al. [24], which was not present in their original work.

**Theorem 1.** Assume that the EALPN$(N, t, c)$ assumption holds, and that FSS $=$ (FSS.Gen, FSS.Eval) is a secure FSS for the class of $d$-dimensional rectangles. Then, Construction 1 is a TAPCF for the class of all degree-$d$, $m$-variate polynomials over $\mathbb{F}_2$. Using the FSS scheme for $d$-dimensional rectangles of Boyle et al. [16], the scheme has the following complexities:

- each party's key is of size $\approx 4\lambda(\log(5N/t)t)^d$ bits,

- the cost of TAPCF.Gen is dominated by $t^d$ invocations of FSS.Gen,

- the cost of TAPCF.Eval is dominated by $\approx (c \cdot \log(5N/t))^d$ invocations of a length-doubling pseudorandom generator.

*Proof.* The proof is given in the full version of this work. $\square$

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

In particular, when $d = 2$, the construction needs $t^2$ FSS keys for a 2-dimensional interval function on a $2\log(5N/t)$-bit domain, which gives a main storage cost of around $4(\log(5N/t) \cdot t)^2\lambda$ bits. The computation involves $c^2$ calls to FSS.Eval, which costs a total of $\approx (c \cdot \log(5N/t))^2$ PRG operations [16, 24, 45].

# 5 Garbling PCF from a TAPCF

In this section, we provide a construction for on-demand garbling correlations from TAPCFs. Our construction (presented in Construction 2) follows directly from our TAPCF abstraction. Specifically, the TAPCF allows the evaluators to specify which wire masks are used as input to the AND gates. We begin by defining the notion of a garbling correlation and subsequently that of a Garbling PCF.
**Construction 1 (Topology-Adaptive PCF).**

*Parameters.* Let (FSS.Gen, FSS.Eval) be an FSS scheme for the class of $d$-dimensional rectangle predicates (Definition 6). Let $\mathbf{pp} = (N, t, c)$ be the parameters of the EALPN-assumption. Let $H$ be a hash function, modeled as a random oracle, that outputs sparse vectors over $\{0, 1\}^{5N}$ sampled from the Bernoulli distribution with parameter $c/5N$ (resulting in vectors of Hamming weight approximately $c$).

TAPCF.Gen($1^{\lambda}$, aux):

1: $(\mathbf{e}_1, \dots, \mathbf{e}_d) \leftarrow_R \mathcal{N}_{\text{ea}}^d(\mathbf{pp}) \triangleright \text{Sample regular-LPN noise.}$

2: **foreach** $i \le d$ **and** $j \le t$:

3: Let $\alpha_j^{(i)} \in [5N/t]$ denote the position of the first 1 in the $j$-th block of $\mathbf{e}_i$.

4: **foreach** $i = (i_1, i_2, \dots, i_d) \in [t]^d$:

5: Let $\alpha_i$ denote the $d$-tuple $\alpha_i = (\alpha_{i1}^{(1)}, \dots, \alpha_{id}^{(d)})$

6: $(\kappa_i^A, \kappa_i^B) \leftarrow \text{FSS.Gen}(f_{\alpha_{i,1}}) \triangleright f_{\alpha_{i,1}}$ is a $d$-dimensional rectangle (Def. 6).

7: $(\mathbf{k}^A, \mathbf{k}^B) := ((\kappa_i^A)_{i \in [t]^d}, (\kappa_i^B)_{i \in [t]^d})$

8: **return** $(\mathbf{k}^A, \mathbf{k}^B)$

TAPCF.Eval($\sigma$, $\mathbf{k}^{\sigma}$, $P$, $(a_1, \dots, a_m)$):

1: **parse** $\mathbf{k}^{\sigma} = (\kappa_i^{\sigma})_{i \in [t]^d}$

2: Define $a_i$ as $(i, a_i)$ for each $a_i \in (a_1, \dots, a_m)$

3: **parse** $P$ as an $m$-variate sum of degree-$d$ monomials $\prod_{i \in \mathcal{I}} X_{a_i}$ where $\mathcal{I}$ is a subset of $d$ elements from $\{a_1, \dots, a_m\}$ defining the monomial.

4: $y^{\sigma} := 0$

5: **foreach** monomial $(\prod_{i \in \mathcal{I}} X_{a_i}) \in P$

6: **foreach** $i \le d$:

7: $\mathbf{h}_{a_i} \leftarrow H(a_i)$ and let $c_i$ denote the Hamming weight of $\mathbf{h}_{a_i}$
$\triangleright$ Note that $c_i \approx c$ due to sampling from the Bernoulli distribution.

8: **foreach** nonzero entry of $\mathbf{h}_{a_i}$:

9: Let $j_i^k \le t$ denote the index of the corresponding noise block and $\alpha_i^k$ denote the position of the $k$-th 1 within this block.
$\triangleright$ Note that each block is a unit vector because of the sampling from
$\triangleright$ the regular noise distribution.

10: **foreach** tuple $(k_1, \dots, k_d) \in [c_1] \times \dots \times [c_d]$:

11: $\mathbf{j} := (j_1^{k_1}, \dots, j_d^{k_d})$

12: $\alpha := (\alpha_1^{k_1}, \dots, \alpha_d^{k_d})$

13: $y^{\sigma} := y^{\sigma} + \text{FSS.Eval}(\sigma, \kappa_j^{\sigma}, \alpha)$

14: **return** $y^{\sigma}$

**Construction 1:** Topology Adaptive PCF construction.
**Definition 7 (Garbling Correlation).** Let $\lambda$ be a security parameter and let

$$GC = (GC.SampLabels_{\sigma}, GC.Garble, GC Encode, GC.Decode)$$

be a secret-sharing friendly garbled circuit scheme (see the full version of this work). We define the correlation with setup (Setup, $\mathcal{Y}_{GC}$), where Setup takes $\lambda$ as input and samples a correlation key $yk := (yk^A, yk^B) := (\Delta^A, \Delta^B) \in \mathbb{F}_{2^{\lambda}} \times \mathbb{F}_{2^{\lambda}}$. Then, $\mathcal{Y}_{GC}: (1^{\lambda}, yk, C) \mapsto (y^A, y^B)$ proceeds as:

1: Parse $yk = (\Delta^A, \Delta^B)$

2: $L^A \leftarrow GC.SampLabels_A(1^{\lambda}, C)$.

3: $L^B \leftarrow GC.SampLabels_B(1^{\lambda}, C)$.

4: $(\hat{C}, \mathbf{r}) \leftarrow GC.Garble(1^{\lambda}, C, \Delta^A, L^A, \Delta^B, L^B)$.

5: Secret share $\hat{C}$ as $(\langle\hat{C}\rangle^A, \langle\hat{C}\rangle^B)$, s.t. $\hat{C} = \langle\hat{C}\rangle^A \oplus \langle\hat{C}\rangle^B$.

6: Secret share $\mathbf{r}$ as $(\langle\mathbf{r}\rangle^A, \langle\mathbf{r}\rangle^B)$ s.t. $\mathbf{r} = \langle\mathbf{r}\rangle^A \oplus \langle\mathbf{r}\rangle^B$.

7: For $\sigma \in \{A, B\}$, secret share $\mathbf{r}\Delta^\sigma$ as $(\langle\mathbf{r}\Delta^\sigma\rangle^A, \langle\mathbf{r}\Delta^\sigma\rangle^B)$, s.t. $\mathbf{r}\Delta^\sigma = \langle\mathbf{r}\Delta^\sigma\rangle^A \oplus \langle\mathbf{r}\Delta^\sigma\rangle^B$.

8: Set $y^A = (\Delta^A, L^A, \langle\hat{C}\rangle^A, \langle\mathbf{r}\rangle^A, \langle\mathbf{r}\Delta^A\rangle^A, \langle\mathbf{r}\Delta^B\rangle^A)$.

9: Set $y^B = (\Delta^B, L^B, \langle\hat{C}\rangle^B, \langle\mathbf{r}\rangle^B, \langle\mathbf{r}\Delta^A\rangle^B, \langle\mathbf{r}\Delta^B\rangle^B)$.

10: Output $(y^A, y^B)$.

**Definition 8 (Garbling PCF).** Let $\lambda$ be a security parameter and let GC be a secret-sharing-friendly garbled circuit scheme. A Garbling PCF for GC is a PCF (Definition 4) for the garbling correlation (Definition 7) with respect to GC.

**Proposition 1.** Under the expand-accumulate LPN assumption (cf. Definition 2), Construction 2 satisfies the correctness and privacy properties required of a Garbling PCF, defined in Definition 8. The expand-accumulate LPN assumption can be replaced with the variable-density LPN assumption using ??.

*Proof.* See the full version of this work. □

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

## 5.1 Concrete parameters and efficiency estimates

We now give a rough estimate of concrete efficiency we can expect from Construction 2 when using the PCFs of Boyle et al. [24] based on expand-accumulate codes, (cf. Definition 2).

Parameters depend on the maximum number of correlations the parties might ever be expected to generate from their keys. We pick a very loose upper bound of $N = 2^{45}$ (roughly 35 trillion correlations, or four billion 10,000 gate circuits). Then, the PCF construction depends on two parameters: $t$ and $c$ which, respectively, determine the communication and computational efficiency of the resulting construction (see [24, Section 5.4 of the full version]).
**Construction 2 (Garbling PCF).**

*Parameters.* Let TAPCF = (TAPCF.Gen, TAPCF.Eval) be a TAPCF for bivariate, degree-2 correlations satisfying scalable outputs (see the full version for a formal definition) with two scalars $\Delta^A, \Delta^B \in \mathbb{F}_{2^\lambda}$, and $P(a, b) = (a, b, c)$, with $c = ab \in \mathbb{F}_2$. Note that the output of TAPCF.Eval will also contain shares of the scaled versions $\Delta^A \cdot P(a, b)$ and $\Delta^B \cdot P(a, b)$. Let $H: \{0, 1\}^* \times \{0, 1\}^* \to \mathbb{G}_1$ be a suitable hash function (see Remark 1), where $\mathbb{G}_1$ is the Abelian group as in Definition 5. Let the input wires of an s-input circuit $C$ be indexed by 1, ..., s. Finally, let PRF = (PRF.KeyGen, PRF.Eval) be a PRF with outputs in $\{0, 1\}^{\text{poly}(\lambda)}$.

**GPCF.Gen(1^λ, yk):**

1: **parse** yk = ($\Delta^A, \Delta^B$)

2: ($k_{\text{PCF}}^A, k_{\text{PCF}}^B$) ← TAPCF.Gen(1^λ, $\Delta^A, \Delta^B$)

3: $K^A \leftarrow \text{PRF.KeyGen}(1^\lambda)$, $K^B \leftarrow \text{PRF.KeyGen}(1^\lambda)$

4: $k^A := (k_{\text{PCF}}^A, K^A, \Delta^A)$, $k^B := (k_{\text{PCF}}^B, K^B, \Delta^B)$

5: **return** ($k^A, k^B$)

**GPCF.Eval(σ, k^σ, C, nonce):**

1: **parse** k^σ = ($k_{\text{PCF}}^σ, K^σ, \Delta^σ$)

2: **foreach** wire i ∈ C

3: **if** wire i is an output wire of C then $\langle r_i \rangle^\sigma := 0$

4: $L^\sigma \leftarrow \text{SampLabels}_\sigma(1^\lambda, C; \text{PRF.Eval}(K^\sigma, \text{nonce}))$

5: Let $S = \emptyset$ ▷ Set to collect input masks with Δ-factors

6: **foreach** AND gate $G_k = (i, j, k) \in C$ ▷ Expand all necessary correlations

7: masks<sub>k</sub> ← TAPCF.Eval(σ, $k_{\text{PCF}}^\sigma$, P, H(i||nonce), H(j||nonce)), where masks<sub>k</sub> = ($\langle r_i \rangle^\sigma, \langle r_j \rangle^\sigma, \langle r_i r_j \rangle^\sigma, \langle r_i \Delta^A \rangle^\sigma, \langle r_j \Delta^A \rangle^\sigma, \langle (r_i r_j) \Delta^A \rangle^\sigma, \langle r_i \Delta^B \rangle^\sigma, \langle r_j \Delta^B \rangle^\sigma, \langle (r_i r_j) \Delta^B \rangle^\sigma$)

8: **if** i is an input wire: $S := S \cup \{(i, \langle r_i \Delta^A \rangle^\sigma, \langle r_i \Delta^B \rangle^\sigma)\}$

9: **if** j is an input wire: $S := S \cup \{(j, \langle r_j \Delta^A \rangle^\sigma, \langle r_j \Delta^B \rangle^\sigma)\}$

10: **foreach** AND gate $G_k = (i, j, k) \in C$ ▷ Compute garbling

11: labels := ($L_{i,0}^\sigma, L_{j,0}^\sigma, L_{k,0}^\sigma$)

12: $\langle \hat{G}_k \rangle^\sigma \leftarrow \text{GarbleGate}(k, \text{labels}, \text{masks}_k, \langle r_k \rangle^\sigma, \langle r_k \Delta^A \rangle^\sigma, \langle r_k \Delta^B \rangle^\sigma, \Delta^\sigma)$

13: Let $\langle \hat{C} \rangle^\sigma := (\langle \hat{G}_k \rangle^\sigma)_{k \in [\nu]}$

14: Set $\langle \mathbf{r} \Delta^A \rangle^\sigma := (\langle r_i \Delta^A \rangle^\sigma)_{i \in [s]}$, $\langle \mathbf{r} \Delta^B \rangle^\sigma := (\langle r_i \Delta^B \rangle^\sigma)_{i \in [s]}$ with entries from S

15: **return** ($\Delta^\sigma, L^\sigma, \langle \hat{C} \rangle^\sigma, (\langle r_1 \rangle^\sigma, \dots, \langle r_s \rangle^\sigma), \langle \mathbf{r} \Delta^A \rangle^\sigma, \langle \mathbf{r} \Delta^B \rangle^\sigma$)

**Construction 2:** Garbling PCF construction using a TAPCF.
**On the security of EA-LPN.** We stress that the Expand-Accumulate assumption is a recent assumption that is yet to receive significant cryptanalytic attention, and any choice of concrete parameter should be taken with a grain of salt. In particular, since the original publication, two papers [46, 58] have identified issues with the original formulation of EA-LPN and its choice of parameters, and suggested tweaks to the definition and updated parameters. We will rely on the state-of-the-art analysis provided by these papers in our parameter selection.

Very recently, Guo et al. [46] provided an attack on the EA-LPN assumption together with a fix that, essentially, slightly tweaks the noise distribution (with no impact on our TAPCF construction) and increases the key size (the number $t$ of noisy coordinates) by a factor two. We note that [46] focuses only on the *aggressive* parameter sets from [24] (both in their attack and in their fix), while [24] also suggests more conservative parameters (backed up by more solid security arguments). For clarity, we state below the two possible key sizes when using the conservative parameters of [24], depending on whether the attack of [46] extends or not to these parameters.

**Communication costs.** The communication cost (in bits) is defined in terms of $N$, $t$, and $c$, and is given by $4\lambda(\log(5N/t)\cdot t)^2$ when using the state-of-the-art FSS schemes for 2-dimensional interval functions [16], where we will fix $\lambda = 128$ for the purposes of our estimates. Since we fix $N = 2^{45}$, we must carefully choose the parameters $c$ and $t$. Boyle et al. [24] give both provable and heuristic parameter regimes. In the provable security regime, we can set $t = 85$ and $c = 3\ln(5N)$. This results in a concrete key size of roughly 800 MB, or alternatively a noise parameter of $t = 170$ and a key size of 1.2 GB if the attack of [46] applies.

However, if we opt for heuristic parameters (optimized for concrete computation costs), we can set $t = 1328$ (updated from $t = 664$ in light of the attack and fix from [46]) and $c \in \{7, 9, 11\}$. These parameter choices are validated through simulation on the minimum distance of the code [24, 58]. We note that the more conservative choice of $c = 11$, compared to Boyle et al. [24], can be motivated in light of an improved minimum distance algorithm of Raghuraman et al. [58], affecting the security of the original heuristic parameters proposed in Boyle et al. [24].<fnref n="7" /> With these *compute-optimized* heuristic parameter choices, the key size grows to 80 GB, but this significantly improves the concrete computation time, as we will explain next. We stress that these parameters might change in light of future cryptanalysis.

**Computational costs.** Computation costs are dominated by AES operations used to instantiate the 2-dimensional DPF [24]. The number of AES calls required, defined in terms of $N$, $t$, and $c$, and is given by $2 \cdot (c \cdot \log(5N/t))^2$ when using the state-of-the-art FSS schemes for 2-dimensional interval functions [16]. Using the AES-NI instruction set available on almost all modern CPUs, one byte of AES-128 can be computed in approximately 1.3 CPU cycles [2]. Therefore, on

<footnote n="7">⁷ While the algorithm of Raghuraman et al. [58] does not directly result in an attack on the original parameter set of Boyle et al. [24], it invalidates the heuristic considerations on which they were based.</footnote>
a 3.5 GHz processor, we can expect to process roughly $1.6 \times 10^8$ AES calls per second. Using the conservative parameters described above ($t = 170, c = 98$) and assuming that other computational costs are roughly 30% the cost of AES (an estimate obtained by examining state-of-the-art DPF implementations), we obtain roughly 4 PCF evaluations per second. However, when using the aggressive compute-optimized parameters ($t = 1328, c \in \{7, 9, 11\}$), we obtain throughputs ranging from roughly 370 (for $c = 11$) to 914 (for $c = 7$) PCF evaluations per second. Since we need one PCF evaluation *per gate*, a circuit with 10,000 AND gates would require roughly 12 seconds to compute *on one core* for $c = 7$. With the conservative parameters, on the other hand, generating a garbled circuit of 10,000 AND gates would require roughly 40 minutes. However, because this computation is again massively parallelizable, a 64-core machine should be able to generate one garbled circuit in under one minute. In the aggressive parameter regime, a 64-core machine should be able to generate one garbled circuit in only 200 ms of compute time.

# 6 Secret-Shared Input Garbling

In this section, we provide a construction for garbling inputs using the labels output by a Garbling PCG or PCF. In Functionality 1, we describe the secret-shared input encoding functionality that we will instantiate later. While we define it to take inputs from two parties A and B, it can equivalently be defined to take the uploaded input $x$ from a third party C (e.g., a client), and this is compatible with our instantiation as well. In Definition 9, we define the syntax and interactive protocol structure that the parties run to instantiate Functionality 1, which we later instantiate in Section 6.1 using HSS.

**Definition 9 (A secret-shared input garbling scheme).** Let HSS be any HSS scheme. A secret-shared input garbling scheme is a triple of efficient algorithms $\text{GI} = (\text{GI}\text{.}\text{Setup}, \text{GI}\text{.}\text{Encode}, \text{GI}\text{.}\text{SelectLabels})$, having the following syntax:

- $\text{GI}\text{.}\text{Setup}(1^{\lambda}, \Delta^A, \Delta^B) \to (\text{pk}, \text{gik}^A, \text{gik}^B)$. The randomized setup algorithm takes as input the security parameter $\lambda$, and two elements $\Delta^A, \Delta^B \in \mathbb{F}_{2^{\lambda}}$. It outputs keys $(\text{pk}, (\text{gik}^A, \text{gik}^B))$.

- $\text{GI}\text{.}\text{Encode}(\text{pk}, x) \to (\llbracket x \rrbracket^A, \llbracket x \rrbracket^B)$. The randomized input encoding algorithm takes as input a key $\text{pk}$ and an input $x \in \mathcal{I}$. It outputs two input encodings of $x$ with respect to HSS.

- $\text{GI}\text{.}\text{SelectLabels}(\sigma, \text{gik}^\sigma, \llbracket x \rrbracket^\sigma, \mathbf{L}_0^\sigma, \langle \mathbf{r} \rangle^\sigma, \langle \mathbf{r} \Delta^A \rangle^\sigma, \langle \mathbf{r} \Delta^B \rangle^\sigma) \to \langle \hat{\mathbf{X}} \rangle^\sigma$. The deterministic label selection algorithm takes as input a party index $\sigma$, a key $\text{gik}^\sigma$, and $\sigma$'s encoding of input $x$, input labels $\mathbf{L}_0^\sigma$ and a share of masks $\langle \mathbf{r} \rangle^\sigma$, together with $\Delta$-scaled versions, $\langle \mathbf{r} \Delta^A \rangle^\sigma$, $\langle \mathbf{r} \Delta^B \rangle^\sigma$. It outputs additive secret shares of the garbled input corresponding to $x$.

$\text{GI}$ is correct and secure if it securely realizes Functionality 1.
**Functionality 1 (Secret-shared input garbling).**

*Parameters.* The functionality is parameterized by a security parameter $\lambda$, and two input lengths $s_A, s_B \in \mathbb{N}$ such that $s = s_A + s_B$. It interacts with two parties, denoted A and B, and an adversary $\mathcal{A}$. The functionality is split into **Setup**, **Encode** and **SelectLabels** procedures, defined as follows:

- Setup: Sample and store $(\Delta^A, \Delta^B) \leftarrow_R \mathbb{F}_{2\lambda} \times \mathbb{F}_{2\lambda}$.

- Encode:

1. On input $x_A \in \{0,1\}^{s_A}$ from party A and $x_B \in \{0,1\}^{s_B}$ from party B.

2. Store $x := x_A \| x_B = x_1 \| \dots \| x_s$ and output nothing.

- SelectLabels:

1. If both parties are honest:

2.1: Wait for $\ln = (\mathbf{L}_0^\sigma, \langle\mathbf{r}\rangle^\sigma, \langle\mathbf{r}\Delta^A\rangle^\sigma, \langle\mathbf{r}\Delta^B\rangle^\sigma)$ from $\sigma, \forall \sigma \in \{A, B\}$, where $\mathbf{L}_0^\sigma = (L_{1,0}^\sigma, \dots, L_{s,0}^\sigma), \mathbf{r} = \langle\mathbf{r}\rangle^A \oplus \langle\mathbf{r}\rangle^B, \mathbf{r}\Delta^\sigma = \langle\mathbf{r}\Delta^\sigma\rangle^A \oplus \langle\mathbf{r}\Delta^\sigma\rangle^B$.

2.2: Define $\rho_i := x_i \oplus \langle\mathbf{r}_i\rangle^A \oplus \langle\mathbf{r}_i\rangle^B$, for all $i \in [s]$.

2.3: Sample $\langle x\rangle^A, \langle x\rangle^B \leftarrow_R \{0,1\}^s$ subject to $\langle x\rangle^A \oplus \langle x\rangle^B = x$.

2.4: Sample $\langle x\Delta^\sigma\rangle^A, \langle x\Delta^\sigma\rangle^B \leftarrow_R \mathbb{F}_{2\lambda}^s$ subject to $\langle x\Delta^\sigma\rangle^A \oplus \langle x\Delta^\sigma\rangle^B = x\Delta^\sigma$, for all $\sigma \in \{A, B\}$.

2.5: Compute $\langle\rho_i\rangle^\sigma := \langle x_i\rangle^\sigma \oplus \langle\mathbf{r}_i\rangle^\sigma$, for all $\sigma \in \{A, B\}$.

2.6: Compute $\langle\rho_i\Delta^A\rangle^\sigma := \langle x_i\Delta^A\rangle^\sigma \oplus \langle\mathbf{r}_i\Delta^A\rangle^\sigma$, for all $\sigma \in \{A, B\}$.

2.7: Compute $\langle\rho_i\Delta^B\rangle^\sigma := \langle x_i\Delta^B\rangle^\sigma \oplus \langle\mathbf{r}_i\Delta^B\rangle^\sigma$, for all $\sigma \in \{A, B\}$.

2.8: For all $\sigma \neq \bar{\sigma} \in \{A, B\}$, compute:

2.8.1: $\langle L_{i,\rho_i}^\sigma \rangle^\sigma := L_{i,0}^\sigma \oplus \langle\rho_i\Delta^\sigma\rangle^\sigma, \langle L_{i,\rho_i}^{\bar{\sigma}} \rangle^\sigma := \langle\rho_i\Delta^{\bar{\sigma}}\rangle^\sigma$ for all $i \in [s]$.

2.8.2: $\langle \mathbf{L}_{\rho}^{\sigma} \rangle^{\sigma} := (\langle L_{1,\rho_1}^{\sigma} \rangle^{\sigma}, \dots, \langle L_{s,\rho_s}^{\sigma} \rangle^{\sigma}), \langle \mathbf{L}_{\rho}^{\bar{\sigma}} \rangle^{\bar{\sigma}} := (\langle L_{1,\rho_1}^{\bar{\sigma}} \rangle^{\bar{\sigma}}, \dots, \langle L_{s,\rho_s}^{\bar{\sigma}} \rangle^{\bar{\sigma}})$.

2. If party $\sigma$ is honest and $\bar{\sigma} \in \{A, B\} \setminus \{\sigma\}$ is corrupted:

3.1: Wait for $\ln = (\mathbf{L}_0^\sigma, \langle\mathbf{r}\rangle^\sigma, \langle\mathbf{r}\Delta^A\rangle^\sigma, \langle\mathbf{r}\Delta^B\rangle^\sigma)$ from party $\sigma$.

3.2: Wait for $(\ln, \text{Out})$ from $\mathcal{A}$, where:

$$ \ln = (\mathbf{L}_0^{\bar{\sigma}}, \langle\mathbf{r}\rangle^{\bar{\sigma}}, \langle\mathbf{r}\Delta^A\rangle^{\bar{\sigma}}, \langle\mathbf{r}\Delta^B\rangle^{\bar{\sigma}}), \quad \text{Out} = (\langle L_{\rho}^A \rangle^{\bar{\sigma}}, \langle L_{\rho}^B \rangle^{\bar{\sigma}}) \parallel (\langle \rho_1 \rangle^{\bar{\sigma}}, \dots, \langle \rho_s \rangle^{\bar{\sigma}}) \\ \text{where } \mathbf{L}_0^{\bar{\sigma}} = (L_{1,0}^{\bar{\sigma}}, \dots, L_{s,0}^{\bar{\sigma}}), \mathbf{r} = \langle\mathbf{r}\rangle^A \oplus \langle\mathbf{r}\rangle^B, \mathbf{r}\Delta^{\bar{\sigma}} = \langle\mathbf{r}\Delta^{\bar{\sigma}}\rangle^A \oplus \langle\mathbf{r}\Delta^{\bar{\sigma}}\rangle^B. $$

3.3: Define $\rho_i := x_i \oplus \langle\mathbf{r}_i\rangle^A \oplus \langle\mathbf{r}_i\rangle^B$, for all $i \in [s]$.

3.4: For all $i \in [s]$:

3.4.1: Compute $\langle x_i \rangle^{\bar{\sigma}} := \langle \rho_i \rangle^{\bar{\sigma}} \oplus \langle \mathbf{r}_i \rangle^{\bar{\sigma}}$ and $\langle x_i \rangle^{\sigma} := x_i \oplus \langle x_i \rangle^{\bar{\sigma}}$.

3.4.2: Compute $\langle \rho_i \rangle^{\sigma} := \langle x_i \rangle^{\sigma} \oplus \langle \mathbf{r}_i \rangle^{\sigma}$.

3.4.3: Compute $L_{i,\rho_i}^A = L_{i,0}^A \oplus \rho_i \Delta^A$, and $L_{i,\rho_i}^B = L_{i,0}^B \oplus \rho_i \Delta^B$.

3.4.4: Compute $\langle L_{i,\rho_i}^A \rangle^\sigma := L_{i,\rho_i}^A \oplus \langle L_{i,\rho_i}^A \rangle^{\bar{\sigma}}$ and $\langle L_{i,\rho_i}^B \rangle^\sigma := L_{i,\rho_i}^B \oplus \langle L_{i,\rho_i}^B \rangle^{\bar{\sigma}}$.

3.5: Let $\langle \mathbf{L}_{\rho}^{\sigma} \rangle^{\sigma} := (\langle L_{1,\rho_1}^{\sigma} \rangle^{\sigma}, \dots, \langle L_{s,\rho_s}^{\sigma} \rangle^{\sigma})$.

3. Output $(\langle L_{\rho}^A \rangle^A, \langle L_{\rho}^B \rangle^A) \parallel (\langle \rho_1 \rangle^A, \dots, \langle \rho_s \rangle^A)$ to party A.

4. Output $(\langle L_{\rho}^A \rangle^B, \langle L_{\rho}^B \rangle^B) \parallel (\langle \rho_1 \rangle^B, \dots, \langle \rho_s \rangle^B)$ to party B.

**Functionality 1:** Ideal functionality for secret shared input garbling.
## 6.1 Secret-shared input garbling with HSS

In Construction 3, we instantiate Functionality 1 using any public key HSS scheme [4, 15, 17, 21]. In this construction, the input $x$ and the pair of global masks $(\Delta^A, \Delta^B)$ are secret-shared via the public-key HSS scheme. Then, using the HSS scheme, the parties can non-interactively encode their inputs by multiplying the shares of $x$ with the shares of $\Delta^A$ and $\Delta^B$, inside HSS, to obtain additive secret shares of the resulting product.

**Proposition 2.** *Assuming the correctness and security of the homomorphic secret sharing scheme HSS, Construction 3 securely instantiates Functionality 1 using the interactive protocol defined in Definition 9.*

*Proof.* See the full version of this work. □

# 7 Applications

In this section, we present the first applications of our garbling PCF and PCG constructions. We describe additional applications in the full version of this work.

## 7.1 Efficient HSS for T-shaped circuits

HSS constructions [4, 15, 17, 18, 21, 36, 40, 41, 56, 61] enable computations over secret shares of a database held by a set of servers (typically two), where one server is assumed to not collude with the other. By distributing the database across multiple servers, many clients can query the database and obtain the query results, without requiring the servers to communicate.

<table><caption>**Table 1:** Communication and computation comparison between basic HSS and our HSS framework when computing T-shaped circuits with $n$ inputs in a constant-degree pre-processing phase and a degree-$d$ post-processing applied to $k$ inputs.</caption><thead><tr><th></th><th>Basic HSS</th><th>Our framework</th></tr></thead><tbody><tr><td>Comm.</td><td>O(k)</td><td>O(k · d)</td></tr><tr><td>Comp.</td><td>O(n · 2<sup>d</sup>)</td><td>O(n + k · d)</td></tr></tbody></table>

HSS constructions provide a compelling alternative to fully-homomorphic encryption, by providing concrete efficiency [4, 17, 21] and constructions from a diverse set of cryptographic assumptions [15, 34, 36, 40, 56, 61]. However, these constructions only work for computing low-degree polynomials, as the computational costs blow up exponentially in the degree. This limitation currently prevents HSS from being used in many natural and practical contexts.
**Construction 3** (Secret-shared input garbling with HSS).

*Parameters.* Let HSS = (HSS. Setup, HSS. Input, HSS. Eval) be any HSS scheme and let Mult and Convert be the auxiliary HSS functions (see the full version of this work for a formal definition).

GI. Setup(1<sup>λ</sup>, Δ<sup>A</sup>, Δ<sup>B</sup>):

1: (pk, (ek<sup>A</sup>, ek<sup>B</sup>)) ← HSS. Setup(1<sup>λ</sup>)

2: ([[Δ<sup>A</sup>]<sup>A</sup>, [[Δ<sup>A</sup>]<sup>B</sup>]) ← HSS. Input(pk, Δ<sup>A</sup>)

3: ([[Δ<sup>B</sup>]<sup>A</sup>, [[Δ<sup>B</sup>]<sup>B</sup>]) ← HSS. Input(pk, Δ<sup>B</sup>)

4: gik<sup>A</sup> := (ek<sup>A</sup>, [[Δ<sup>A</sup>]<sup>A</sup>, [[Δ<sup>B</sup>]<sup>A</sup>]), gik<sup>B</sup> := (ek<sup>B</sup>, [[Δ<sup>A</sup>]<sup>B</sup>, [[Δ<sup>B</sup>]<sup>B</sup>])

5: return (pk, gik<sup>A</sup>, gik<sup>B</sup>)

GI. Encode(pk, x):

1: return ([[x]<sup>A</sup>, [[x]<sup>B</sup>]) ← HSS. Input(pk, x)

▷ GI. SelectLabels when defined to take an HSS memory share of x.

GI. SelectLabels(σ, gik<sup>σ</sup>, ⟨x⟩<sup>σ</sup>, L<sub>0</sub><sup>σ</sup>, ⟨r⟩<sup>σ</sup>, ⟨Δ<sup>A</sup> · r⟩<sup>σ</sup>, ⟨Δ<sup>B</sup> · r⟩<sup>σ</sup>):

1: parse gik<sup>σ</sup> = (ek<sup>σ</sup>, [[Δ<sup>A</sup>]<sup>σ</sup>, [[Δ<sup>B</sup>]<sup>σ</sup>])

2: parse L<sub>0</sub><sup>σ</sup> = (L<sub>1,0</sub><sup>σ</sup>, ..., L<sub>s,0</sub><sup>σ</sup>) and ⟨r⟩<sup>σ</sup> = (⟨r<sub>1</sub>⟩<sup>σ</sup>, ..., ⟨r<sub>s</sub>⟩<sup>σ</sup>)

3: parse ⟨x⟩<sup>σ</sup> = (⟨x<sub>1</sub>⟩<sup>σ</sup>, ..., ⟨x<sub>s</sub>⟩<sup>σ</sup>)

4: foreach i ∈ [s]:

5: ⟨x<sub>i</sub>⟩<sup>σ</sup> ← Convert(ek<sup>σ</sup>, ⟨x<sub>i</sub>⟩<sup>σ</sup>)

6: ⟨y<sub>i</sub><sup>A</sup>⟩<sup>σ</sup> ← Mult(ek<sup>σ</sup>, [[Δ<sup>A</sup>]<sup>σ</sup>, ⟨x<sub>i</sub>⟩<sup>σ</sup>])

7: ⟨y<sub>i</sub><sup>B</sup>⟩<sup>σ</sup> ← Mult(ek<sup>σ</sup>, [[Δ<sup>B</sup>]<sup>σ</sup>, ⟨x<sub>i</sub>⟩<sup>σ</sup>])

8: ⟨z<sub>i</sub><sup>A</sup>⟩<sup>σ</sup> := ⟨y<sub>i</sub><sup>A</sup>⟩<sup>σ</sup> ⊕ ⟨Δ<sup>A</sup> · r<sub>i</sub>⟩<sup>σ</sup>, ⟨z<sub>i</sub><sup>B</sup>⟩<sup>σ</sup> := ⟨y<sub>i</sub><sup>B</sup>⟩<sup>σ</sup> ⊕ ⟨Δ<sup>B</sup> · r<sub>i</sub>⟩<sup>σ</sup>,

9: if σ = A: ⟨L<sub>i,ρ<sub>i</sub></sub><sup>A</sup>⟩<sup>A</sup> := L<sub>i,0</sub><sup>A</sup> ⊕ ⟨z<sub>i</sub><sup>A</sup>⟩<sup>A</sup>, ⟨L<sub>i,ρ<sub>i</sub></sub><sup>B</sup>⟩<sup>A</sup> := ⟨z<sub>i</sub><sup>B</sup>⟩<sup>A</sup>

10: if σ = B: ⟨L<sub>i,ρ<sub>i</sub></sub><sup>B</sup>⟩<sup>B</sup> := L<sub>i,0</sub><sup>B</sup> ⊕ ⟨z<sub>i</sub><sup>B</sup>⟩<sup>B</sup>, ⟨L<sub>i,ρ<sub>i</sub></sub><sup>A</sup>⟩<sup>B</sup> := ⟨z<sub>i</sub><sup>A</sup>⟩<sup>B</sup>

11: ⟨L<sub>ρ</sub><sup>A</sup>⟩<sup>σ</sup> := (⟨L<sub>1,x<sub>1</sub></sub><sup>A</sup>⟩<sup>σ</sup>, ..., ⟨L<sub>s,ρ<sub>s</sub></sub><sup>A</sup>⟩<sup>σ</sup>), ⟨L<sub>ρ</sub><sup>B</sup>⟩<sup>σ</sup> := (⟨L<sub>1,x<sub>1</sub></sub><sup>B</sup>⟩<sup>σ</sup>, ..., ⟨L<sub>s,ρ<sub>s</sub></sub><sup>B</sup>⟩<sup>σ</sup>)

12: ⟨X̂⟩<sup>σ</sup> := (⟨L<sub>ρ</sub><sup>A</sup>⟩<sup>σ</sup>, ⟨L<sub>ρ</sub><sup>B</sup>⟩<sup>σ</sup>) || (⟨x<sub>1</sub>⟩<sup>σ</sup> ⊕ ⟨r<sub>1</sub>⟩<sup>σ</sup>, ..., ⟨x<sub>s</sub>⟩<sup>σ</sup> ⊕ ⟨r<sub>s</sub>⟩<sup>σ</sup>)

13: return ⟨X̂⟩<sup>σ</sup>

▷ GI. SelectLabels when defined to take an HSS input share of x.

GI. SelectLabels(σ, gik<sup>σ</sup>, [[x]<sup>σ</sup>, L<sub>0</sub><sup>σ</sup>, ⟨r⟩<sup>σ</sup>, ⟨Δ<sup>A</sup> · r⟩<sup>σ</sup>, ⟨Δ<sup>B</sup> · r⟩<sup>σ</sup>):

1: parse gik<sup>σ</sup> = (ek<sup>σ</sup>, - , -)

2: ⟨x⟩<sup>σ</sup> ← HSS. Convert(ek<sup>σ</sup>, [[x]<sup>σ</sup>])

3: return GI. SelectLabels(σ, gik<sup>σ</sup>, ⟨x⟩<sup>σ</sup>, L<sub>0</sub><sup>σ</sup>, ⟨r⟩<sup>σ</sup>, ⟨Δ<sup>A</sup> · r⟩<sup>σ</sup>, ⟨Δ<sup>B</sup> · r⟩<sup>σ</sup>)

**Construction 3:** Secret-shared input garbling with HSS construction.
**T-shaped computations.** We make the observation that database and data structure queries are often represented by T-shaped circuits, where a wide-and-shallow pre-processing computation is applied to all items, followed by a narrow-and-deep post-processing computation applied to a small subset of selected items from the pre-processing step.

Examples of such T-shaped database computations include: threshold counting queries, approximate nearest neighbor search queries [3, 42], bloom filter membership testing [11], and hash-based data structure queries [29, 31, 44].

Our key insight is that we can build efficient HSS for T-shaped computations by combining (1) any HSS scheme for low-degree pre-processing with (2) a secret-shared garbled circuit to encode the post-processing. By "connecting" the HSS output with the garbled circuit, we guarantee the same level of privacy (the client cannot recover anything more than the output of the computation) while also gaining the best-of-both-worlds in terms of computational efficiency (see comparison in Table 1). We arrive at the following informal theorem.

**Theorem 2 (HSS for T-shaped computation (informal)).** For all T-shaped computations with a constant-degree pre-processing applied to $n$ inputs followed by a degree-$d$, width-$k$ post-processing computation, there exists an HSS scheme with a non-additive reconstruction algorithm, achieving a download communication cost (i.e., the response share size) of $O(k \cdot d)$ and server-side computation cost of $O(n + k \cdot d)$.

**Construction.** For a T-shaped computation (as in Theorem 2), let $P_0$ be an $n$-input, $k$-output computation with a multiplicative depth $d_0$ and $P_1$ be a $k$-input computation with a multiplicative depth $d_1$ and width $O(k)$. Because the computation is T-shaped, we have that $d_0 \ll d_1$ and $k \ll n$. The full construction is given in Construction 4. Here, we provide a high-level overview of the construction:

- **HSS computation:** Compute $P_0$ over the $n$ HSS input values, which produces $k$ HSS memory shares of the output bits $(y_1, \dots, y_k)$.

- **Garbled circuit:** Generate a secret-shared garbled circuit $\tilde{C}$ computing the function $P_1$.

- **Garbled inputs:** Garble input bits $(y_1, \dots, y_k)$ using Construction 3 to produce $\tilde{X}$.

- **Output:** $\mathcal{C}$ and the shares of $\tilde{C}$ and $\tilde{X}$.

The HSS computation of $P_0$ requires a computational cost of $O(n \cdot 2^{d_0})$, since the computational cost is exponential in the depth of $P_0$. Generating the garbled circuit requires a computational cost of $O(k \cdot d_1)$ (we assume the width of the circuit is $O(k)$). Finally, the communication cost is just the share size of the garbled circuit and garbled input, which is $O(k \cdot d_1)$. In all of the above uses, $O(\cdot)$ hides a linear factor in the security parameter.
**Construction 4 (HSS for T-Shaped Computation).**

*Parameters.* Let HSS = (HSS. Setup, HSS. Input, HSS. Eval) be a HSS scheme for a class of programs $\mathcal{P}$, where $P_0 \in \mathcal{P}$ is an $n$-input, $k$-output computation with a multiplicative depth $d_0$. Let GC = (GC. SampLabels$_\sigma$, GC. Garble, GC. Encode, GC. Decode) be a secret-sharing-friendly garbled circuit scheme, and GPCF = (GPCF. Gen, GPCF. Eval) be a Garbling PCF for GC. Let GI = (GI. Setup, GI. Encode, GI. SelectLabels) be the HSS-based secret-shared input garbling scheme from Construction 3, using HSS.

HSS$^T$.Setup(1$^\lambda$):

1: $\Delta^A, \Delta^B \leftarrow_R \mathbb{F}_{2^\lambda}$

2: $(k^A, k^B) \leftarrow \text{GPCF.Gen}(1^\lambda, (\Delta^A, \Delta^B))$

3: $(\text{pk}, \text{gik}^A, \text{gik}^B) \leftarrow \text{GI.setup}(1^\lambda, \Delta^A, \Delta^B)$

4: $ek^A := (k^A, \text{gik}^A)$, $ek^B := (k^B, \text{gik}^B)$

5: **return** $(\text{pk}, (ek^A, ek^B))$

HSS$^T$.Input(pk, x):

1: **return** $([x]^A, [x]^B) \leftarrow \text{HSS Input}(\text{pk}, x)$

HSS$^T$.Eval($\sigma$, $ek^\sigma$, $[x]^\sigma$, $P$):

1: **parse** $P := (P_0, P_1)$, $ek^\sigma := (k^\sigma, \text{gik}^\sigma)$, and $\text{gik}^\sigma := (ek_{\text{HSS}}^\sigma, [[\Delta^A]^\sigma, [[\Delta^B]^\sigma])$

2: $\langle\langle y_0 \rangle\rangle^\sigma \leftarrow \text{HSS.Eval}^*(\sigma, ek_{\text{HSS}}^\sigma, [[x]^\sigma, P_0])$

3: $(\Delta^\sigma, \mathbf{L}_0^\sigma, \langle\hat{C}\rangle^\sigma, \langle\hat{r}\rangle^\sigma, \langle\mathbf{r}\Delta^A\rangle^\sigma, \langle\mathbf{r}\Delta^B\rangle^\sigma) \leftarrow \text{GPCF.Eval}(\sigma, k^\sigma, C, \text{ctr})$, where $C$ is the circuit encoding $P_1$ and $\text{ctr}$ is a counter, incremented each time

4: $\langle\hat{X}\rangle^\sigma \leftarrow \text{GI>SelectLabels}(\sigma, \text{gik}^\sigma, \langle\langle y_0 \rangle\rangle^\sigma, \mathbf{L}_0^\sigma, \langle\hat{r}\rangle^\sigma, \langle\mathbf{r}\Delta^A\rangle^\sigma, \langle\mathbf{r}\Delta^B\rangle^\sigma)$

5: **return** $y^\sigma := (C, \langle\hat{C}\rangle^\sigma, \langle\hat{X}\rangle^\sigma)$

HSS$^T$.Recover($y^A, y^B$):

1: **parse** $y_A = (C, \langle\hat{C}\rangle^A, \langle\hat{X}\rangle^A)$, $y_B = (C', \langle\hat{C}\rangle^B, \langle\hat{X}\rangle^B) \triangleright \text{assert } C = C'$

2: $\hat{C} := \langle\hat{C}\rangle^A + \langle\hat{C}\rangle^B$, $\hat{X} := \langle\hat{X}\rangle^A + \langle\hat{X}\rangle^B$

3: **return** GC.Decode($C, \hat{C}, \hat{X}$)

**Construction 4:** HSS for T-shaped circuits via GPCFs.
**Remark 3 (Non-additive reconstruction).** The exponential improvement in the computational overhead of the HSS computation for T-shaped circuits using Theorem 2 comes at the cost of non-additive reconstruction. Additive reconstructions in HSS schemes provides two main benefits: (1) guaranteed function privacy and (2) optimal download rate [15, 18]. In database query applications, where a client obtains the output of the computation, additive reconstruction not particularly important and only modestly increases the download rate by a factor of $d$.

### 7.1.1 Applications of HSS for T-shaped circuits

Many database computations can be divided into two steps that can be viewed as being T-shaped computations. In the first step, a “filtering” function is applied over all database items to select a small subset of items. In the second step, a (typically, computationally expensive) function is applied to the filtered subset of items. For example, many hashing-based data structures [3, 10, 29, 30, 42, 44] work by first retrieving a subset of items from the data structure / database (using the hash function as the “filtering” function), and then applying a post-processing operation on this retrieved subset of items.

**A framework via syndrome decoding.** We can efficiently instantiate an HSS for T-shaped database computation described above by combining a linear sketch based on any suitable linear error-correcting code [47, 55, 59] with an HSS scheme for low-degree polynomials. For a database of size $n$, where we assume the post-processing is applied to at most $k \ll n$ matches, we let $H$ be an $\ell \times n$ parity-check matrix with an efficient syndrome decoder capable of decoding up to $k$ errors. Note that $\ell = O(k)$, which implies that the codeword $cw$ is of size $O(k)$. Following the pre-processing performed in HSS (i.e., the filtering step), the servers obtain $n$ additive secret shares, which we will write as the vector $\langle y \rangle^{\sigma} := (\langle y_1 \rangle^{\sigma} \dots \langle y_n \rangle^{\sigma})$, where $y$ is a sparse vector (since, by assumption, at most $k$ items are selected). Using the sketch, the parties can efficiently compute the codeword $cw := H \cdot (\langle y \rangle^{\sigma})^{\top}$ over the secret shares, as it is a linear operation. The codeword $cw$ can be efficiently decoded to the set of (up to) $k$ items using the syndrome decoder of the error-correcting code.

Our idea is to offload the syndrome decoding and post-processing into the garbled circuit. Specifically, the garbled circuit first reconstructs the shares of $cw$, then performs syndrome decoding over the codeword $cw$ to recover the vector of items, and finally performs the post-processing over the selected items.

This simple framework combines three ingredients: (1) an HSS scheme, (2) any linear sketch based on syndrome decoding, and (3) a secret-shared garbled circuit. It immediately applies to several practical applications. We provide the following two concrete examples:

- **Threshold counting.** For a count query $q$ specifying some predicate, the answer to the query is 0 if fewer than some threshold $k$ items match the predicate, and 1 if more than $k$ items match the predicate. Using our framework, we can easily instantiate a simple threshold counting scheme as follows. Let
$H$ be a parity check matrix for a linear code that corrects up to $k$ errors and detects (i.e., output $\perp$) if more than $k$ errors occur [55]. Then,

1. Using HSS, compute the predicate specified in the query over each item in the database to obtain a secret share of an indicator bit $b_i$ indicating whether the predicate was satisfied for the item or not.

2. Compute the share of the codeword $\langle cw \rangle^{\sigma} := H \cdot (\langle b_1 \rangle^{\sigma}, \dots, \langle b_n \rangle^{\sigma})$.

3. Output secret-shares of the garbled circuit that recovers the codeword $cw$, decodes $cw$, and outputs 0 if the decoding succeeds and 1 otherwise.

In this example, the garbled circuit outputs 1 if the syndrome decoding fails (indicating there were more than $k$ items that matched the predicate) and 0 if the decoding succeeds (indicating there were fewer than $k$ items that matched the predicate). The client learns nothing more than the output bit, thanks to the security property of the garbled circuit.

- **Hash-based data structures.** We can use our framework to query such hash-based data structures efficiently as follows:

1. Using HSS, compute an indicator bit $b_i$ for each item in the database that matches the hash-based filtering predicate for the query.

2. Compute the share of the codeword $\langle cw \rangle^{\sigma} := H \cdot (\langle b_1 \rangle^{\sigma}, \dots, \langle b_n \rangle^{\sigma})$.

3. Output secret-shares of the garbled circuit that recovers the codeword $cw$, decodes $cw$ to get a vector of candidate items, and output the result of the post-processing function applied to the filtered subset of items.

In this example, $H$ needs to be able to extract up to $k$ "errors" where $k$ is a bound on the number of items returned in the pre-processing step (e.g., in many applications, $k$ is a small constant, e.g., 5 [31]). Once more, the client learns nothing more than the $k$ decoded outputs, thanks to the security property of the garbled circuit.

## Acknowledgments

We thank the anonymous reviewers for being a significant help in improving the presentation and results in this paper. We thank Aditya Hegde for helpful comments and pointers. Geoffroy Couteau and Alexander Koch acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grant ANR-20-CE39-0001 (project SCENE) and under the France 2030 ANR Project ANR-22-PECY-003 SecureCompute. This work is supported by ERC grant OBELiSC (101115790), and NSF grant 2330065.
Bibliography

[1] Damiano Abram, Ariel Nof, Claudio Orlandi, Peter Scholl, and Omer Shlomivits. Low-bandwidth threshold ECDSA via pseudorandom correlation generators. In *2022 IEEE Symposium on Security and Privacy*, pages 2554–2572. IEEE Computer Society Press, May 2022. https://doi.org/10.1109/SP46214.2022.9833559.

[2] Kahraman Akdemir, Martin Dixon, Wajdi Feghali, Patrick Fay, Vinodh Gopal, Jim Guilford, Erdinc Ozturk, Gil Wolrich, and Ronen Zohar. Breakthrough AES performance with Intel AES new instructions. *White paper*, *June*, 12:217, 2010.

[3] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. *Communications of the ACM*, 51(1):117–122, 2008.

[4] Thomas Attema, Pedro Capitão, and Lisa Kohl. On homomorphic secret sharing from polynomial-modulus LWE. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, *PKC 2023: 26th International Conference on Theory and Practice of Public Key Cryptography, Part II*, volume 13941 of *Lecture Notes in Computer Science*, pages 3–32. Springer, Cham, May 2023. https://doi.org/10.1007/978-3-031-31371-4_1.

[5] Carsten Baum, Lennart Braun, Alexander Munch-Hansen, Benoît Razet, and Peter Scholl. Appenzeller to brie: Efficient zero-knowledge proofs for mixed-mode arithmetic and Z2k. In Giovanni Vigna and Elaine Shi, editors, *ACM CCS 2021: 28th Conference on Computer and Communications Security*, pages 192–211. ACM Press, November 2021. https://doi.org/10.1145/3460120.3484812.

[6] Carsten Baum, Alex J. Malozemoff, Marc B. Rosen, and Peter Scholl. Mac'n'cheese: Zero-knowledge proofs for boolean and arithmetic circuits with nested disjunctions. In Tal Malkin and Chris Peikert, editors, *Advances in Cryptology - CRYPTO 2021, Part IV*, volume 12828 of *Lecture Notes in Computer Science*, pages 92–122, Virtual Event, August 2021. Springer, Cham. https://doi.org/10.1007/978-3-030-84259-8_4.

[7] Carsten Baum, Lennart Braun, Alexander Munch-Hansen, and Peter Scholl. MozZ$_{2k}$arena: Efficient vector-OLE and zero-knowledge proofs over $Z_{2k}$. In Yevgeniy Dodis and Thomas Shrimpton, editors, *Advances in Cryptology - CRYPTO 2022, Part IV*, volume 13510 of *Lecture Notes in Computer Science*, pages 329–358. Springer, Cham, August 2022. https://doi.org/10.1007/978-3-031-15985-5_12.

[8] Donald Beaver. Efficient multiparty protocols using circuit randomization. In Joan Feigenbaum, editor, *Advances in Cryptology - CRYPTO'91*, volume 576 of *Lecture Notes in Computer Science*, pages 420–432. Springer, Berlin, Heidelberg, August 1992. https://doi.org/10.1007/3-540-46766-1_34.

[9] Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols (extended abstract). In *22nd Annual ACM Symposium*
on *Theory of Computing*, pages 503–513. ACM Press, May 1990. https://doi.org/10.1145/100216.100287.

[10] Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, *ACM CCS 2012: 19th Conference on Computer and Communications Security*, pages 784–796. ACM Press, October 2012. https://doi.org/10.1145/2382196.2382279.

[11] Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. *Communications of the ACM*, 13(7):422–426, 1970.

[12] Maxime Bombar, Geoffroy Couteau, Alain Couvreur, and Clément Ducros. Correlated pseudorandomness from the hardness of quasi-abelian decoding. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology – CRYPTO 2023, Part IV*, volume 14084 of *Lecture Notes in Computer Science*, pages 567–601. Springer, Cham, August 2023. https://doi.org/10.1007/978-3-031-38551-3_18.

[13] Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Zero-knowledge proofs on secret-shared data via fully linear PCPs. In Alexandra Boldyreva and Daniele Micciancio, editors, *Advances in Cryptology – CRYPTO 2019, Part III*, volume 11694 of *Lecture Notes in Computer Science*, pages 67–97. Springer, Cham, August 2019. https://doi.org/10.1007/978-3-030-26954-8_3.

[14] Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing. In Elisabeth Oswald and Marc Fischlin, editors, *Advances in Cryptology – EUROCRYPT 2015, Part II*, volume 9057 of *Lecture Notes in Computer Science*, pages 337–367. Springer, Berlin, Heidelberg, April 2015. https://doi.org/10.1007/978-3-662-46803-6_12.

[15] Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the circuit size barrier for secure computation under DDH. In Matthew Robshaw and Jonathan Katz, editors, *Advances in Cryptology – CRYPTO 2016, Part I*, volume 9814 of *Lecture Notes in Computer Science*, pages 509–539. Springer, Berlin, Heidelberg, August 2016. https://doi.org/10.1007/978-3-662-53018-4_19.

[16] Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, *ACM CCS 2016: 23rd Conference on Computer and Communications Security*, pages 1292–1303. ACM Press, October 2016. https://doi.org/10.1145/2976749.2978429.

[17] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Michele Orrù. Homomorphic secret sharing: Optimizations and applications. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, *ACM CCS 2017: 24th Conference on Computer and Communications Security*, pages 2105–2122. ACM Press, October / November 2017. https://doi.org/10.1145/3133956.3134107.
[18] Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro. Foundations of homomorphic secret sharing. Cryptology ePrint Archive, Report 2017/1248, 2017. URL https://eprint.iacr.org/2017/1248.

[19] Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, *ACM CCS 2018: 25th Conference on Computer and Communications Security*, pages 896–912. ACM Press, October 2018. https://doi.org/10.1145/3243734.3243868.

[20] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In Alexandra Boldyreva and Daniele Micciancio, editors, *Advances in Cryptology – CRYPTO 2019, Part III*, volume 11694 of *Lecture Notes in Computer Science*, pages 489–518. Springer, Cham, August 2019. https://doi.org/10.1007/978-3-030-26954-8_16.

[21] Elette Boyle, Lisa Kohl, and Peter Scholl. Homomorphic secret sharing from lattices without FHE. In Yuval Ishai and Vincent Rijmen, editors, *Advances in Cryptology – EUROCRYPT 2019, Part II*, volume 11477 of *Lecture Notes in Computer Science*, pages 3–33. Springer, Cham, May 2019. https://doi.org/10.1007/978-3-030-17656-3_1.

[22] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators from ring-LPN. In Daniele Micciancio and Thomas Ristenpart, editors, *Advances in Cryptology – CRYPTO 2020, Part II*, volume 12171 of *Lecture Notes in Computer Science*, pages 387–416. Springer, Cham, August 2020. https://doi.org/10.1007/978-3-030-56880-1_14.

[23] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Correlated pseudorandom functions from variable-density LPN. In *61st Annual Symposium on Foundations of Computer Science*, pages 1069–1080. IEEE Computer Society Press, November 2020. https://doi.org/10.1109/FOCS46700.2020.00103.

[24] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl. Correlated pseudorandomness from expand-accumulate codes. In Yevgeniy Dodis and Thomas Shrimpton, editors, *Advances in Cryptology – CRYPTO 2022, Part II*, volume 13508 of *Lecture Notes in Computer Science*, pages 603–633. Springer, Cham, August 2022. https://doi.org/10.1007/978-3-031-15979-4_21.

[25] Andreas Brüggemann, Robin Hundt, Thomas Schneider, Ajith Suresh, and Hossein Yalame. FLUTE: Fast and secure lookup table evaluations. In *2023 IEEE Symposium on Security and Privacy*, pages 515–533. IEEE Computer Society Press, May 2023. https://doi.org/10.1109/SP46215.2023.10179345.

[26] Chris Brzuska, Geoffroy Couteau, Christoph Egger, Pihla Karanko, and Pierre Meyer. Instantiating the hash-then-evaluate paradigm: Strengthening PRFs, PCFs, and OPRFs. In Clemente Galdi and Duong Hieu Phan, editors, *SCN 24: 14th International Conference on Security in Communication Networks, Part II*, volume 14974 of *Lecture Notes in Com-
*Computer Science*, pages 97–116. Springer, Cham, September 2024. https://doi.org/10.1007/978-3-031-71073-5_5.

[27] Dung Bui and Geoffroy Couteau. Improved private set intersection for sets with small entries. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, *PKC 2023: 26th International Conference on Theory and Practice of Public Key Cryptography, Part II*, volume 13941 of *Lecture Notes in Computer Science*, pages 190–220. Springer, Cham, May 2023. https://doi.org/10.1007/978-3-031-31371-4_7.

[28] Seung Geol Choi, Jonathan Katz, Alex J. Malozemoff, and Vassilis Zikas. Efficient three-party computation from cut-and-choose. In Juan A. Garay and Rosario Gennaro, editors, *Advances in Cryptology – CRYPTO 2014, Part II*, volume 8617 of *Lecture Notes in Computer Science*, pages 513–530. Springer, Berlin, Heidelberg, August 2014. https://doi.org/10.1007/978-3-662-44381-1_29.

[29] Benny Chor, Niv Gilboa, and Moni Naor. Private information retrieval by keywords. Cryptology ePrint Archive, Report 1998/003, 1998. URL https://eprint.iacr.org/1998/003.

[30] Arka Rai Choudhuri, Aarushi Goel, Aditya Hegde, and Abhishek Jain. Homomorphic secret sharing with verifiable evaluation. In Elette Boyle and Mohammad Mahmody, editors, *TCC 2024: 22nd Theory of Cryptography Conference, Part IV*, volume 15367 of *Lecture Notes in Computer Science*, pages 614–650. Springer, Cham, December 2024. https://doi.org/10.1007/978-3-031-78023-3_20.

[31] Graham Cormode and Shan Muthukrishnan. An improved data stream summary: The count-min sketch and its applications. In *LATIN 2004: Theoretical Informatics: 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004. Proceedings 6*, pages 29–38. Springer, 2004.

[32] Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In *14th USENIX symposium on networked systems design and implementation (NSDI 17)*, pages 259–282, 2017.

[33] Geoffroy Couteau and Clément Ducros. Pseudorandom correlation functions from variable-density LPN, revisited. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, *PKC 2023: 26th International Conference on Theory and Practice of Public Key Cryptography, Part II*, volume 13941 of *Lecture Notes in Computer Science*, pages 221–250. Springer, Cham, May 2023. https://doi.org/10.1007/978-3-031-31371-4_8.

[34] Geoffroy Couteau and Pierre Meyer. Breaking the circuit size barrier for secure computation under quasi-polynomial LPN. In Anne Canteaut and François-Xavier Standaert, editors, *Advances in Cryptology – EURO-CRYPT 2021, Part II*, volume 12697 of *Lecture Notes in Computer Science*, pages 842–870. Springer, Cham, October 2021. https://doi.org/10.1007/978-3-030-77886-6_29.

[35] Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Rei-haneh Safavi-Naini and Ran Canetti, editors, *Advances in Cryptology –
CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 643–662. Springer, Berlin, Heidelberg, August 2012. https://doi.org/10.1007/978-3-642-32009-5_38.

[36] Quang Dao, Yuval Ishai, Aayush Jain, and Huijia Lin. Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology – CRYPTO 2023, Part II*, volume 14082 of *Lecture Notes in Computer Science*, pages 315–348. Springer, Cham, August 2023. https://doi.org/10.1007/978-3-031-38545-2_11.

[37] Samuel Dittmer, Yuval Ishai, Steve Lu, and Rafail Ostrovsky. Authenticated garbling from simple correlations. In Yevgeniy Dodis and Thomas Shrimpton, editors, *Advances in Cryptology – CRYPTO 2022, Part IV*, volume 13510 of *Lecture Notes in Computer Science*, pages 57–87. Springer, Cham, August 2022. https://doi.org/10.1007/978-3-031-15985-5_3.

[38] Samuel Dittmer, Yuval Ishai, Steve Lu, and Rafail Ostrovsky. Improving line-point zero knowledge: Two multiplications for the price of one. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, *ACM CCS 2022: 29th Conference on Computer and Communications Security*, pages 829–841. ACM Press, November 2022. https://doi.org/10.1145/3548606.3559385.

[39] Sebastian Faust, Carmit Hazay, David Kretzler, Leandro Rometsch, and Benjamin Schlosser. Non-interactive threshold BBS+ from pseudorandom correlations. In Arpita Patra, editor, *CT-RSA 2025*, number 15598 in LNCS, pages 198–222. Springer, 2025. https://doi.org/10.1007/978-3-031-88661-4_9.

[40] Nelly Fazio, Rosario Gennaro, Tahereh Jafarikhah, and William E Skeith. Homomorphic secret sharing from Paillier encryption. In Tatsuaki Okamoto, Yong Yu, Man Ho Au, and Yannan Li, editors, *Provable Security, ProvSec 2017*, volume 10592 of *Lecture Notes in Computer Science*, pages 381–399. Springer, 2017. https://doi.org/10.1007/978-3-319-68637-0_23.

[41] Ingerid Fosli, Yuval Ishai, Victor I Kolobov, and Mary Wootters. On the download rate of homomorphic secret sharing. *arXiv preprint arXiv:2111.10126*, 2021.

[42] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. Similarity search in high dimensions via hashing. In *Vldb*, volume 99, pages 518–529, 1999.

[43] Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. Reusable garbled circuits and succinct functional encryption. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, *45th Annual ACM Symposium on Theory of Computing*, pages 555–564. ACM Press, June 2013. https://doi.org/10.1145/2488608.2488678.

[44] Daniel H. Greene, Michal Parnas, and F. Frances Yao. Multi-index hashing for information retrieval. In *35th Annual Symposium on Foundations of Computer Science*, pages 722–731. IEEE Computer Society Press, November 1994. https://doi.org/10.1109/SFCS.1994.365720.
[45] Xiaojie Guo, Kang Yang, Xiao Wang, Wenhao Zhang, Xiang Xie, Jiang Zhang, and Zheli Liu. Half-tree: Halving the cost of tree expansion in COT and DPF. In Carmit Hazay and Martijn Stam, editors, *Advances in Cryptology - EUROCRYPT 2023, Part I*, volume 14004 of *Lecture Notes in Computer Science*, pages 330-362. Springer, Cham, April 2023. https://doi.org/10.1007/978-3-031-30545-0_12.

[46] Xiaojie Guo, Hanlin Liu, Zhicong Huang, Hongrui Cui, Wenhao Zhang, Cheng Hong, Xiao Wang, Kang Yang, and Yu Yu. Dory: Streaming PCG with small memory. Cryptology ePrint Archive, Paper 2025/1660, 2025. URL https://eprint.iacr.org/2025/1660.

[47] Richard W Hamming. Error detecting and error correcting codes. *The Bell system technical journal*, 29(2):147-160, 1950.

[48] Zhicong Huang, Wen jie Lu, Cheng Hong, and Jiansheng Ding. Chee-tah: Lean and fast secure two-party deep neural network inference. In Kevin R. B. Butler and Kurt Thomas, editors, *USENIX Security 2022: 31st USENIX Security Symposium*, pages 809-826. USENIX Association, August 2022. URL https://www.usenix.org/conference/usenixsecurity22/presentation/huang-zhicong.

[49] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Dan Boneh, editor, *Advances in Cryptology - CRYPTO 2003*, volume 2729 of *Lecture Notes in Computer Science*, pages 145-161. Springer, Berlin, Heidelberg, August 2003. https://doi.org/10.1007/978-3-540-45146-4_9.

[50] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, and Amit Sahai. Efficient non-interactive secure computation. In Kenneth G. Paterson, editor, *Advances in Cryptology - EUROCRYPT 2011*, volume 6632 of *Lecture Notes in Computer Science*, pages 406-425. Springer, Berlin, Heidelberg, May 2011. https://doi.org/10.1007/978-3-642-20465-4_23.

[51] Yuval Ishai, Dakshita Khurana, Amit Sahai, and Akshayaram Srinivasan. Black-box reusable NISC with random oracles. In Carmit Hazay and Martijn Stam, editors, *Advances in Cryptology - EUROCRYPT 2023, Part II*, volume 14005 of *Lecture Notes in Computer Science*, pages 68-97. Springer, Cham, April 2023. https://doi.org/10.1007/978-3-031-30617-4_3.

[52] Vladimir Kolesnikov. Gate evaluation secret sharing and secure one-round two-party computation. In Bimal K. Roy, editor, *Advances in Cryptology - ASIACRYPT 2005*, volume 3788 of *Lecture Notes in Computer Science*, pages 136-155. Springer, Berlin, Heidelberg, December 2005. https://doi.org/10.1007/11593447_8.

[53] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, *ICALP 2008: 35th International Colloquium on Automata, Languages and Programming, Part II*, volume 5126 of *Lecture Notes in Computer Science*, pages 486-498. Springer, Berlin, Heidelberg, July 2008. https://doi.org/10.1007/978-3-540-70583-3_40.
[54] Yashvanth Kondi, Claudio Orlandi, and Lawrence Roy. Two-round stateless deterministic two-party Schnorr signatures from pseudorandom correlation functions. Cryptology ePrint Archive, Report 2023/216, 2023. URL https://eprint.iacr.org/2023/216.

[55] Todd K Moon. Error correction coding: mathematical methods and algorithms. John Wiley & Sons, 2020.

[56] Claudio Orlandi, Peter Scholl, and Sophia Yakoubov. The rise of paillier: Homomorphic secret sharing and public-key silent OT. In Anne Canteaut and François-Xavier Standaert, editors, *Advances in Cryptology – EUROCRYPT 2021, Part I*, volume 12696 of *Lecture Notes in Computer Science*, pages 678–708. Springer, Cham, October 2021. https://doi.org/10.1007/978-3-030-77870-5_24.

[57] Srinivasan Raghuraman and Peter Rindal. Blazing fast PSI from improved OKVS and subfield VOLE. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, *ACM CCS 2022: 29th Conference on Computer and Communications Security*, pages 2505–2517. ACM Press, November 2022. https://doi.org/10.1145/3548606.3560658.

[58] Srinivasan Raghuraman, Peter Rindal, and Titouan Tanguy. Expand-convolute codes for pseudorandom correlation generators from LPN. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology – CRYPTO 2023, Part IV*, volume 14084 of *Lecture Notes in Computer Science*, pages 602–632. Springer, Cham, August 2023. https://doi.org/10.1007/978-3-031-38551-3_19.

[59] Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. *Journal of the society for industrial and applied mathematics*, 8(2): 300–304, 1960.

[60] Peter Rindal and Philipp Schoppmann. VOLE-PSI: Fast OPRF and circuit-PSI from vector-OLE. In Anne Canteaut and François-Xavier Standaert, editors, *Advances in Cryptology – EUROCRYPT 2021, Part II*, volume 12697 of *Lecture Notes in Computer Science*, pages 901–930. Springer, Cham, October 2021. https://doi.org/10.1007/978-3-030-77886-6_31.

[61] Lawrence Roy and Jaspal Singh. Large message homomorphic secret sharing from DCR and applications. In Tal Malkin and Chris Peikert, editors, *Advances in Cryptology – CRYPTO 2021, Part III*, volume 12827 of *Lecture Notes in Computer Science*, pages 687–717, Virtual Event, August 2021. Springer, Cham. https://doi.org/10.1007/978-3-030-84252-9_23.

[62] Philipp Schoppmann, Adrià Gascón, Leonie Reichert, and Mariana Raykova. Distributed vector-OLE: Improved constructions and implementation. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, *ACM CCS 2019: 26th Conference on Computer and Communications Security*, pages 1055–1072. ACM Press, November 2019. https://doi.org/10.1145/3319535.3363228.

[63] Xiao Wang, Samuel Ranellucci, and Jonathan Katz. Authenticated garbling and efficient maliciously secure two-party computation. In Bha-vani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, *ACM CCS 2017: 24th Conference on Computer and Communications Security*.
*Security*, pages 21–37. ACM Press, October / November 2017. https://doi.org/10.1145/3133956.3134053.

[64] Xiao Wang, Samuel Ranellucci, and Jonathan Katz. Global-scale secure multiparty computation. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, *ACM CCS 2017: 24th Conference on Computer and Communications Security*, pages 39–56. ACM Press, October / November 2017. https://doi.org/10.1145/3133956.3133979.

[65] Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. Wolverine: Fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits. In *2021 IEEE Symposium on Security and Privacy*, pages 1074–1091. IEEE Computer Society Press, May 2021. https://doi.org/10.1109/SP40001.2021.00056.

[66] Chenkai Weng, Kang Yang, Zhaomin Yang, Xiang Xie, and Xiao Wang. AntMan: Interactive zero-knowledge proofs with sublinear communication. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, *ACM CCS 2022: 29th Conference on Computer and Communications Security*, pages 2901–2914. ACM Press, November 2022. https://doi.org/10.1145/3548606.3560667.

[67] Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In *27th Annual Symposium on Foundations of Computer Science*, pages 162–167. IEEE Computer Society Press, October 1986. https://doi.org/10.1109/SFCS.1986.25.

[68] Mark Zhandry. The magic of ELFs. *Journal of Cryptology*, 32(3):825–866, July 2019. https://doi.org/10.1007/s00145-018-9289-9.