owned this note
owned this note
Published
Linked with GitHub
# (1/2) A Pragmatic Introduction to Secure Multi-Party Computation
###### tags: `Tag(HashCloak - DC Net Readings)`
Author(s): David Evans, Vladimir Kolesnikov and Mike Rosulek
Paper: [https://securecomputation.org/docs/pragmaticmpc.pdf](https://securecomputation.org/docs/pragmaticmpc.pdf)
### Table of Contents
[toc]
:::info
>Abstract: Secure multi-party computation (MPC) has evolved from a theoretical curiosity in the 1980s to a tool for building real systems today. Over the past decade, MPC has been one of the most active research areas in both theoretical and applied cryptography. This book introduces several important MPC protocols, and surveys methods for improving the efficiency of privacy-preserving applications built using MPC. Besides giving a broad overview of the field and the insights of the main constructions, we overview the most currently active areas of MPC research and aim to give readers insights into what problems are practically solvable using MPC today and how different threat models and assumptions impact the practicality of different approaches.
:::
### 1 Introduction
Secure multi-party computation (MPC) enable a group to jointly perform a computation without disclosing any participant’s private inputs.
* The participants agree on a function to compute, and then can use an MPC protocol to jointly compute the output of that function on their secret inputs without revealing them.
* Since its introduction by Andrew Yao in the 1980s, multi-party computation has developed from a theoretical curiosity to an important tool for building large-scale privacy-preserving applications.
### 1.1 Outsourced Computation
In an outsourced computation:
* One party:
* Owns the data.
* And wants to be able to obtain the result of computation on that data.
* The second party:
* Receives and stores the data in an encrypted form.
* Performs computation on the encrypted data.
* And provides the encrypted results to the data owner without learning anything about the input data, intermediate values, or final result.
* The data owner can then decrypt the returned results to obtain the output.
### 1.2 Multi-Party Computation
The goal of secure multi-party computation (MPC) is to enable a group of independent data owners who do not trust each other or any common third party to jointly compute a function that depends on all of their private inputs. MPC differs from outsourced computation in that all of the protocol participants are data owners who participate in executing a protocol.
### 1.3 MPC Applications
MPC enables privacy-preserving applications where multiple mutually distrusting data owners cooperate to compute a function.
* Here, we highlight a few illustrative examples of privacy-preserving applications that can be built using MPC. This list is far from exhaustive, and is meant merely to give an idea of the range and scale of MPC applications.
**Yao’s Millionaires Problem:** : “Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth.”
* That is, the goal is to compute the Boolean result of $x_1 ≤ x_2$ where $x_1$ is the first party’s private input and $x_2$ is the second party’s private input.
**Secure auctions:** it is crucial for all participants, both bidders and sellers, to be able to rely on the privacy and non-malleability of bids.
* Bid privacy requires that no player may learn any other player’s bid (other than perhaps revealing the winning bid upon the completion of the auction).
* Bid non-malleability means that a player’s bid may not be manipulated to generate a related bid.
**Voting:** Secure electronic voting, in a simple form, is simply computation of the addition function which tallies the vote. Privacy and non-malleability of the vote (properties discussed above in the context of auctions) are essential for similar technical reasons. Additionally, because voting is a fundamental civil process, these properties are often asserted by legislation.
* The property of coercion resistance is not standard in MPC (but can be formally expressed and achieved (Küsters et al., 2012)).
* The issue here is the ability of voters to prove to a third party how they voted.
**Secure machine learning:** MPC can be used to enable privacy in both the inference and training phases of machine learning systems.
## 2 Defining Multi-Party Computation
The protocols we discuss in later chapters have been proven secure based on these definitions.
### 2.1 Notations and Conventions
*Secure Multi-Party Computation:* We will abbreviate as MPC.
* Denotes secure computation among two or more participants.
* *Secure function evaluation (SFE):* We will use 2PC to emphasize this setting when needed.
We denote encryption and decryption of a message $m$ under key $k$ as $Enc_k(m)$ and $Dec_k(m)$.
* We will refer to protocol participants interchangeably also as parties or players, and will usually denote them as P1, P2, etc.
* We will denote the adversary by $\mathcal{A}$.
A negligible function $ν : \mathbb{N} → \mathbb{R}$ is any function that approaches zero asymptotically faster than any inverse polynomial.
* In other words, for any polynomial $p, ν(n) < 1/p(n)$ for all but finitely many $n$.
We will denote computational and statistical security parameters by $κ$ and $σ$ respectively.
* The computational security parameter $κ$ governs the hardness of problems that can be broken by an adversary’s offline computation — e.g., breaking an encryption scheme.
* In practice $κ$ is typically set to a value like 128 or 256.
* The statistical security parameter σ governs the hardness of these attacks
* In practice, $σ$ is typically set to a smaller value like 40 or 80.
* The correct way to interpret the presence of two security parameters is that security is violated only with probability $2^−σ + ν(κ)$, where $ν$ is a negligible function that depends on the resources of the adversary.
* When we consider computationally unbounded adversaries, we omit $κ$ and require $ν$ = 0.
We will use symbol $∈_R$ to denote uniformly random sampling from a distribution.
* For example we write “choose $k ∈_R \{0, 1\}^κ$ ” to mean that $k$ is a uniformly chosen $κ$-bit long string.
* More generally, we write “$v ∈_R D$” to denote sampling according to a probability distribution D.
* We write “$v ∈_R A(x)$” to denote that $v$ is the result of running randomized algorithm $A$ on input $x$.
Let $D1$ and $D2$ be two probability distributions indexed by a security parameter, or equivalently two algorithms that each take a security parameter as input.
* We say that $D1$ and $D2$ are indistinguishable if, for all algorithms $A$ there exists a negligible function $ν$ such that:
![](https://i.imgur.com/lOEsAGO.png)
* In other words, no algorithm behaves more than negligibly differently when given inputs sampled according to $D1$ vs $D2$.
* When we consider only *non-uniform, polynomial-time* algorithms $A$, the definition results in *computational indistinguishability*.
* When we consider *all* algorithms without regard to their computational complexity, we get a definition of *statistical indistinguishability*.
* In that case, the probability above is bounded by the statistical distance (also known as total variation distance) of the two distributions, which is defined as:
![](https://i.imgur.com/Zuf0A8L.png)
Throughout this work, we use *computational security* to refer to security against adversaries implemented by non-uniform, polynomial-time algorithms. We use *information-theoretic security* (also known as unconditional or statistical security) to mean security against arbitrary adversaries (even those with unbounded computational resources).
### 2.2 Basic Primitives
Here, we provide definitions of a few basic primitives we use in our presentation.
**Secret Sharing:** Secret sharing is an essential primitive, that is at the core of many MPC approaches.
* Informally, a ($t, n$)-secret sharing scheme splits the secret $s$ into $n$ shares, such that any $t$ − 1 of the shares reveal no information about $s$, while any $t$ shares allow complete reconstruction of the secret $s$.
#### Secret Sharing Definition 2.1.
We provide one definition, adapted from Beimel and Chor (1993):
* Let $D$ be the domain of secrets and $D_1$ be the domain of shares.
* Let $Shr : D → D^n_1$ be a (possibly randomized) sharing algorithm, and $Rec : D^k_1 → D$ be a reconstruction algorithm.
* A ($t, n$)-secret sharing scheme is a pair of algorithms ($Shr, Rec$) that satisfies these two properties:
![](https://i.imgur.com/TNVFzvo.png)
**Random Oracle:** Random Oracle (RO) is a heuristic model for the security of hash functions, introduced by Bellare and Rogaway (1993).
* The idea is to treat the hash function as a public, idealized random function.
* In the random oracle model, all parties have access to the public function $H : \{0, 1\}^∗ → \{0, 1\}^κ$, implemented as a stateful oracle.
* On input string $x ∈ \{0, 1\}^∗$ , $H$ looks up its history of calls.
* If $H(x)$ had never been called, $H$ chooses a random $r_x ∈ \{0, 1\}^κ$, remembers the pair $x,r_x$ and returns $r_x$.
* If $H(x)$ had been called before, $H$ returns $r_x$.
* In this way, the oracle realizes a randomly-chosen function $\{0, 1\}^∗ → \{0, 1\}^κ$.
### 2.3 Security of Multi-Party Computation
Informally, the goal of MPC is for a group of participants to learn the correct output of some agreed-upon function applied to their private inputs without revealing anything else. We now provide a more formal definition to clarify the security properties MPC aims to provide.
#### 2.3.1 Real-Ideal Paradigm
Although they used different terminology, the definition of probabilistic encryption by Goldwasser and Micali (1984) is widely considered to be the first instance of using this approach to define and prove security.
**Ideal World:** In the ideal world, the parties securely compute the function $\mathcal{F}$ by privately sending their inputs to a completely trusted party $\mathcal{T}$, referred to as the *functionality*.
**Real World:**
In the real world, there is no trusted party. Instead, all parties communicate with each other using a protocol.
* The protocol $π$ specifies for each party $P_i$ a “next-message” function $π_i$.
* This function takes as input:
* a security parameter.
* The party’s private input $x_i$.
* A random tape.
* And the list of messages $P_i$ has received so far.
* Then, $π_i$ outputs either a next message to send along with its destination, or else instructs the party to terminate with some specific output.
#### 2.3.2 Semi-Honest Security
A semi-honest adversary is one who corrupts parties but follows the protocol as specified.
* In other words, the corrupt parties run the protocol honestly but they may try to learn as much as possible from the messages they receive from other parties.
* The view of a party consists of its private input, its random tape, and the list of all messages received during the protocol.
* The view of an adversary consists of the combined views of all corrupt parties.
* Semi-honest adversaries are also considered passive in that they cannot take any actions other than attempting to learn private information by observing a view of a protocol execution.
Anything an adversary learns from running the protocol must be an efficiently computable function of its view.
* That is, without loss of generality we need only consider an “attack” in which the adversary simply outputs its entire view.
* For a protocol to be secure, it must be possible in the ideal world to generate something indistinguishable from the real world adversary’s view.
More formally:
* Let $π$ be a protocol and $\mathcal{F}$ be a functionality.
* Let $C$ be the set of parties that are corrupted, and let $Sim$ denote a simulator algorithm.
* We define the following distributions of random variables:
![](https://i.imgur.com/aEYKuXN.png)
>A protocol is secure against semi-honest adversaries if the corrupted parties in the real world have views that are indistinguishable from their views in the ideal world:
![](https://i.imgur.com/C8Cv7xq.png)
![](https://i.imgur.com/4AaDifW.png)
#### 2.3.3 Malicious Security
A *malicious* (also known as *active*) may instead cause corrupted parties to deviate arbitrarily from the prescribed protocol in an attempt to violate security.
* A malicious adversary has all the powers of a semi-honest one in analyzing the protocol execution, but may also take any actions it wants during protocol execution.
**Effect on honest outputs:** When the corrupt parties deviate from the protocol, there is now the possibility that honest parties’ outputs will be affected.
* We can/should make no guarantees on the final outputs of corrupt parties, only of the honest parties, since a malicious party can output whatever it likes.
**Extraction:** The input of a malicious party is not well-defined in the real world, which leads to the question of what input should be given to $\mathcal{T}$ in the ideal world.
* We leave it to the simulator to choose inputs for the corrupt parties.
* This aspect of simulation is called extraction, since the simulator extracts an effective ideal-world input from the real-world adversary that “explains” the input’s real-world effect.
* In most constructions, it is sufficient to consider black-box simulation, where the simulator is given access only to the oracle implementing the real-world adversary, and not its code.
When $\mathcal{A}$ denotes the adversary program, we write $corrupt(\mathcal{A})$ to denote the set of parties that are corrupted, and use $corrupt(Sim)$ for the set of parties that are corrupted by the ideal adversary, Sim.
We define distributions for the real world and ideal world, and define a secure protocol as one that makes those distributions indistinguishable:
* $Real_{π,\mathcal{A}}(κ; \{x_i | i \notin < corrupt(\mathcal{A})\}):$
* Run the protocol on security parameter $κ$.
* Where each honest party P$_i$ (for $i < corrupt(\mathcal{A})$) runs the protocol honestly using given private input $x_i$.
* And the messages of corrupt parties are chosen according to $\mathcal{A}$.
* Thinking of $\mathcal{A}$ as a protocol next-message function for a collection of parties.
* Let $y_i$ denote the output of each honest party P$_i$
* And let $V_i$ denote the final view of party P$_i$.
* ![](https://i.imgur.com/t6nGwX9.png)
* $Ideal_{F,Sim}(κ; \{x_i | i \notin corrupt(\mathcal{A})\}):$
* Run $Sim$ until it outputs a set of inputs $\{x_i | i ∈ corrupt(\mathcal{A})\}$.
* Compute $(y_1, . . ., y_n) ← F (x-1, . . ., x_n)$.
* Then, give $\{y_i | i ∈ corrupt(\mathcal{A})\}$ to $Sim$.
* Let $V^∗$ denote the final output of $Sim$ (a set of simulated views).
* Output $(V^∗ , \{y_i \space | \space i \notin corrupt(Sim)\})$.
![](https://i.imgur.com/VPMtyHR.png)
**Security with abort:** In any message-based two-party protocol, one party will learn the final output before the other. If that party is corrupt and malicious, they may simply refuse to send the last message to the honest party and thereby prevent the honest party from learning the output.
Typical results in the malicious setting provide a weaker property known as *security with abort*, which requires slightly modifying the ideal functionality as follows:
* First, the functionality is allowed to know the identities of the corrupt parties.
* The functionality’s behavior is modified to be slightly reactive:
* After all parties have provided input, the functionality computes outputs and delivers the outputs to the corrupt parties only.
* Then the functionality awaits either a “deliver” or “abort” command from the corrupted parties.
* Upon receiving “deliver”, the functionality delivers the outputs to all the honest parties.
* Upon receiving “abort”, the functionality delivers an abort output (⊥) to all the honest parties.
> It is generally understood that when discussing security against malicious adversaries, the adversary has control over output delivery to honest parties and output fairness is not expected.
### 2.4 Specific Functionalities of Interest
Here, we define several functionalities that have been identified as particularly useful building blocks for building MPC protocols.
**Oblivious Transfer:** (OT) is an essential building block for secure computation protocols. It is theoretically equivalent to MPC as shown by Kilian (1988): given OT, one can build MPC without any additional assumptions, and, similarly, one can directly obtain OT from MPC.
![](https://i.imgur.com/q0dQ46j.png)
**Commitment:** Commitment is a fundamental primitive in many cryptographic protocols. A commitment scheme allows a sender to commit to a secret value, and reveal it at some later time to a receiver.
![](https://i.imgur.com/E2iFAFJ.png)
**Zero-Knowledge Proof:** A zero-knowledge (ZK) proof allows a prover to convince a verifier that it knows x such that $C(x) = 1$, without revealing any further information about $x$.
* Here $C$ is a public predicate.
![](https://i.imgur.com/stuf6YE.png)
As a simple example:
* Suppose $G$ is a graph and that Alice knows a 3- coloring $χ$ for $G$.
* Then Alice can use a ZK proof to convince Bob that $G$ is 3-colorable.
* She constructs a circuit $C_G$ that interprets its input as an encoding of a 3-coloring and checks whether it is a legal 3-coloring of $G$.
* She uses $(C_G, χ)$ as input to the ZK proof.
* From Bob’s point of view, he receives output (**proven**, $C_G$) if and only if Alice was able to provide a valid 3-coloring of $G$.
* At the same time, Alice knows that Bob learned nothing about her 3-coloring $χ$ other than the fact that some legal $χ$ exists.
### 2.5 Further Reading
The definition of security that we have sketched in this book is the Universal Composition (UC) framework of Canetti (2001).
* Protocols proven secure in the UC framework have the important composition property described in Section 2.3.4, which in particular guarantees security of a protocol instance no matter what other protocols are executing concurrently.
* While the UC framework is the most popular model with this property, there are other models with similar guarantees (Pfitzmann and Waidner, 2000; Hofheinz and Shoup, 2011).
* However, a significantly simpler model is presented by Canetti et al. (2015), which is equivalent to the full UC model for the vast majority of cases.
## 3 Fundamental MPC Protocols
In this chapter we survey several important MPC approaches, covering the main protocols and presenting the intuition behind each approach.
All of the approaches discussed can be viewed as a form of computing under encryption, or, more specifically, as secret-sharing the input data and computing on the shares.
* For example: An encryption $Enc_k(m)$ of a message $m$ with a key $k$ can be seen as secret-sharing $m$, where one share is $k$ and the other is $Enc_k(m)$.
We present several fundamental protocols illustrating a variety of generic approaches to secure computation, as summarized in Table 3.1:
![](https://i.imgur.com/CXXlolA.png)
> All of the protocols of this section target the semi-honest adversary model (Section 2.3.2). We discuss malicious-secure variants in Chapter 6. All of these protocols build on oblivious transfer, which we discuss how to implement efficiently in Section 3.7.
### 3.1 Yao’s Garbled Circuits Protocol
Yao’s Garbled Circuits protocol (GC) is the most widely known and celebrated MPC technique. It is usually seen as best-performing, and many of the protocols we cover build on Yao’s GC.
* While not having the best known communication complexity, it runs in constant rounds and avoids the costly latency associated with approaches, such as GMW (described in Section 3.2), where the number of communication rounds scales with the circuit depth.
#### 3.1.1 GC Intuition
The main idea behind Yao’s GC approach is quite natural. Recall, we wish to evaluate a given function $\mathcal{F} (x, y)$ where party P$_1$ holds $x ∈ X$ and P$_2$ holds $y ∈ Y$.
* Here $X$ and $Y$ are the respective domains for the inputs of P$_1$ and P$_2$.
**Function as a look-up table:**
1. First, let’s consider a function $\mathcal{F}$ for which the input domain is small and we can efficiently enumerate all possible input pairs, $(x, y)$.
* The function $\mathcal{F}$ can be represented as a look-up table $T$, consisting of $|X| · |Y |$ rows, $T_{x,y} = \langle \mathcal{F} (x, y) \rangle$.
* The output of $\mathcal{F} (x, y)$ is obtained simply by retrieving $T_{x,y}$ from the corresponding row.
* Evaluating a look-up table can be done as follows:
* P$_1$ will encrypt $T$ by assigning a randomly-chosen strong key to *each* possible input $x$ and $y$.
* That is, for each $x ∈ X$ and each $y ∈ Y$, P$_1$ will choose $k_x ∈R \{0, 1\}^κ$ and $k_y ∈R \{0, 1\}^κ$ .
2. Now our task is to enable P$_2$ to decrypt (only) the entry $T_{x,y}$ corresponding to players’ inputs.
* This is done by having P$_1$ send to P$_2$ the keys $k_x$ and $k_y$.
* P$_1$ knows its input $x$, and hence simply sends key $k_x$ to P$_2$.
* The key $k_y$ is sent to P$_2$ using a 1-out-of-$|Y|$ Oblivious Transfer (Section 2.4).
* Once P$_2$ receives $k_x$ and $k_y$, it can obtain the output $F(x, y)$ by decrypting $T_{x,y} using those keys.
* Importantly, no other information is obtained by P$_2$.
* **Point-and-Permute:** A careful reader may wonder how P$_2$ knows which row of the table $T$ to decrypt, as this information is dependent on the inputs of both parties, and, as such, is sensitive. The simplest way to address this is to encode some additional information in the encrypted elements of $T$.
* For example, P$_1$ may append a string of σ zeros to each row of $T$.
* Decrypting the wrong row with high probability ($p$ = $1 \over 2^σ$) will produce an entry which will not end with $σ$ zeros, and hence will be rejected by P$_2$.
* While thisapproach works, it is inefficient for P$_2$, who expects to need to decrypt half of the rows of the table $T$.
* A much better approach, often called *point-and-permute*, was introduced by Beaver et al. (1990).
* The idea is to interpret part of the key (namely, the last $\lceil log |X| \rceil$ bits of the first key and the last $\lceil log |Y | \rceil$ bits of the second key) as a pointer to the permuted table $T$, where the encryption will be placed.
* To avoid collisions in table row allocation, P$_1$ must ensure that the pointer bits don’t collide within the space of keys $k_x$ or within the space of ky.
* This can be done in a number of ways.
3. Finally, strictly speaking, key size must be maintained to achieve the corresponding level of security.
* As a consequence, rather than viewing key bits as a pointer, players will append the pointer bits to the key and maintain the desired key length.
**Managing look-up table size:** Clearly, the above solution is inefficient as it scales linearly with the domain size of $F$. At the same time, for small functions, such as those defined by a single Boolean circuit gate, the domain has size 4, so using a look-up table is practical.
The next idea is to represent $\mathcal{F}$ as a Boolean circuit $\mathcal{C}$ and evaluate each gate using look-up tables of size 4.
* As before, P$_1$ generates keys and encrypts look-up tables, and P$_2$ applies decryption keys without knowing what each key corresponds to.
* However, in this setting, we cannot reveal the plaintext output of intermediate gates.
* This can be hidden by making the gate output also a key whose corresponding value is unknown to the evaluator, P$_2$.
* For each wire $w_i$ of $\mathcal{C}$, P$_1$ assigns two keys $k^0_i$ and $k^1_i$, corresponding to the two possible values on the wire.
* We will refer to these keys as *wire labels*, and to the plaintext wire values simply as *wire values*.
* During the execution, depending on the inputs to the computation, each wire will be associated with a specific plaintext value and a corresponding wire label, which we will call *active value* and *active label*.
* We stress that the evaluator can know only the active *label*, but not its corresponding *value*, and not the *inactive* label.
Then, going through $\mathcal{C}$, for each gate $G$ with input wires $w_i$ and $w_j$, and output wire $w_t$, P$_1$ builds the following encrypted look-up table:
![](https://i.imgur.com/UrY1722.png)
Each cell of the look-up table encrypts the label corresponding to the output computed by the gate. Crucially, this allows the evaluator P$_2$ to obtain the intermediate active labels on internal circuit wires and use them in the evaluation of $\mathcal{F}$ under encryption without ever learning their semantic value.
* P$_1$ permutes the entries in each of the look-up tables (usually called garbled tables or garbled gates), and sends all the tables to P$_2$.
* Additionally, P$_1$ sends (only) the active labels of all wires corresponding to the input values to P$_2$.
* For input wires belonging to P$_1$’s inputs to $\mathcal{F}$, this is done simply by sending the wire label keys.
* For wires belonging to P$_2$’s inputs, this is done via 1-out-of-2 Oblivious Transfer.
* Upon receiving the input keys and garbled tables, P$_2$ proceeds with the evaluation.
* In our case of a 4-row garbled table, the point-and-permute technique is particularly simple and efficient — one pointer bit is needed for each input, so there are two total pointer bits added to each entry in the garbled table.
* Ultimately, P$_2$ completes evaluation of the garbled circuit and obtains the keys corresponding to the output wires of the circuit.
* These could be sent to P$_1$ for decryption, thus completing the private evaluation of $\mathcal{F}$.
At an intuitive level, at least, it is easy to see that this circuit-based construction is secure in the semi-honest model.
* Security against a corrupt P$_1$ is easy, since (other than the OT, which we assume has been separately shown to satisfy the OT security definition) that party receives no messages in the protocol!
* For a corrupt P$_2$, security boils down to the observation that the evaluator P$_2$ never sees both labels for the same wire.
#### 3.1.2 Yao’s GC Protocol
Figure 3.1 formalizes Yao’s gate generation, and Figure 3.2 summarizes Yao’s GC protocol.
![](https://i.imgur.com/DtwDGwu.png)
![](https://i.imgur.com/0UcCkQm.png)
### 3.2 Goldreich-Micali-Wigderson (GMW) Protocol
In the GMW protocol (Goldreich et al., 1987; Goldreich, 2004), the secret-sharing of the wire value is more direct: the players hold additive shares of the active wire value.
* The GMW protocol (or just “GMW”) naturally generalizes to more than two parties, unlike Yao’s GC, which requires novel techniques to generalize to more than two parties (see Section 3.5).
#### 3.2.1 GMW Intuition
The GMW protocol can work both on Boolean and arithmetic circuits. We present the two-party Boolean version first, and then briefly explain how the protocol can be generalized to more than two parties. As with Yao’s protocol, we assume players P$_1$ with input $x$ and P$_2$ with input $y$ have agreed on the Boolean circuit $\mathcal{C}$ representing the computed function $F (x, y)$.
The GMW protocol proceeds as follows:
* For each input bit $x_i ∈ \{0, 1\}$ of $x ∈ \{0, 1\}^n, P$_1$ generates a random bit $r_i ∈R \{0, 1\}$ and sends all $r_i$ to $P_2$.
* Next, P$_1$ obtains a secret sharing of each $x_i$ among P$_1$ and P$_2$ by setting its share to be $x_i$ ⊕ $r_i$.
* Symmetrically, P$_2$ generates random bit masks for its inputs $y_i$ and sends the masks to P$_1$, secret sharing its input similarly.
* P$_1$ and P$_2$ proceed in evaluating $\mathcal{C}$ gate by gate.
Consider gate $G$ with input wires $w_i$ and $w_j$ and output wire $w_k$ .
* The input wires are split into two shares, such that $s^1_x ⊕ s^2_x = w_x$.
* Let P$_1$ holds shares $s 1 i$ and $s 1 j$ on $wi$ and $wj$.
* Let P$_2$ hold shares $s^2_i$ and $s^2_j$ on the two wires.
* Without loss of generality, assume $\mathcal{C}$ consists of **NOT**, **XOR** and **AND** gates.
* Both **NOT** and **XOR** gates can be evaluated without any interaction.
* A **NOT** gate is evaluated by P$_1$ flipping its share of the wire value, which flips the shared wire value.
* An **XOR** gate on wires $w_i$ and $w_j$ is evaluated by players xor-ing the shares they already hold.
* That is:
* P$_1$ computes its output share as $s^1_k = s^1_i ⊕ s^1_j$.
* And P$_2$ correspondingly computes its output share as $s^2_k = s^2_i ⊕ s^2_j$.
* The computed shares, $s^1_k , s^2_k$, indeed are shares of the active output value: $s^1_k ⊕ s^2_k = (s^1_i ⊕ s^1_j) ⊕ (s^2_i ⊕ s^2_j) = (s^1_i ⊕ s^2_i) ⊕ (s^1_j ⊕ s^2_j ) = v_1 ⊕ v_2$.
* Evaluating an **AND** gate requires interaction and uses 1-out-of-4 OT a basic primitive.
* From the point of view of P$_1$, its shares $s^1_i , s^1_j$ are fixed, and P$_2$ has two Boolean input shares, which means there are four possible options for P$_2$.
* If P$_1$ knew P$_2$’s shares, then evaluating the gate under encryption would be trivial:
* P$_1$ can just reconstruct the active input values, compute the active output value and secret-share it with P$_2$.
* While P$_1$ cannot do that, it can do the next best thing:
* Prepare such a secret share for each of P$_2$’s possible inputs, and run 1-out-of-4 OT to transfer the corresponding share.
* Specifically, let: $S = S_{s^1_i},_{s^1_j}(s^2_i, s^2_j) = (s^1_i ⊕ s^2_i) ∧ (s^1_j ⊕ s^2_j)$ be the function n computing the gate output value from the shared secrets on the two input wires.
* P$_1$ chooses a random mask bit $r ∈R \{0, 1\}$ and prepares a table of OT secrets:
![](https://i.imgur.com/rxnddpa.png)
* Then P$_1$ and P$_2$ run an 1-out-of-4 OT protocol, where P$_1$ plays the role of the sender, and P$_2$ plays the role of the receiver.
* P$_1$ uses table rows as each of the four input secrets,
* And P$_2$ uses its two bit shares as the selection to choose the corresponding row.
* P$_1$ keeps $r$ as its share of the gate output wire value,
* And P$_2$ uses the value it receives from the OT execution.
* Because of the way the OT inputs are constructed, the players obtain a secret sharing of the gate output wire.
* At the same time, it is intuitively clear that the players haven’t learned anything about the other player’s inputs or the intermediate values of the computation.
* This is because effectively only P$_2$ receives messages, and by the OT guarantee, it learns nothing about the three OT secrets it did not select.
* Likewise, P$_1$ learns nothing about the selection of P$_2$.
* After evaluating all gates, players reveal to each other the shares of the output wires to obtain the output of the computation.
**Generalization to more than two parties:**
We now sketch how to generalize this to the setting where $n$ players P$_1$, P$_2$, . . ., P$_n$ evaluate a boolean circuit $\mathcal{F}$. As before, player P$_j$ secret-shares its input by choosing $\forall i \neq j,r_i ∈_R \{0, 1\}$, and sending $r_i$ to each P$_i$. The parties P$_1$, P$_2$, . . ., P$_n$ proceed by evaluating $\mathcal{C}$ gate-by-gate.
They evaluate each gate G as follows:
* For an **XOR** gate, the players locally add their shares.
* Like the two-party case, no interaction is required and correctness and security are assured.
* For an **AND** gate $c = a ∧ b$, let $a_1, . . ., a_n, b1, . . ., b_n$ denote the shares of $a, b% respectively held by the players.
* Consider the identity: ![](https://i.imgur.com/V5RujfJ.png)
* Each player P$_j$ computes $a_j∧b_j$ locally to obtain a sharing of $\bigoplus ^n_{i=1} a_i∧b_i$.
* Further, each pair of players P$_i, P_j$ jointly computes the shares of $a_i ∧ b_j$ as described above in the two-party GMW.
* Finally, each player outputs the **XOR** of all obtained shares as the sharing of the result $a ∧ b$.
### 3.3 BGW protocol
One of the first multi-party protocols for secure computation is due to Ben-Or, Goldwasser, and Wigderson (Ben-Or et al., 1988), and is known as the “BGW” protocol.
> Another somewhat similar protocol of Chaum, Crépau, and Damgård was published concurrently (Chaum et al., 1988) with BGW, and the two protocols are often considered together. we present here the BGW protocol for n parties, which is somewhat simpler.
The BGW protocol can be used to evaluate an arithmetic circuit over a field $\mathbb{F}$, consisting of addition, multiplication, and multiplication-by-constant gates.
* The protocol is heavily based on Shamir secret sharing (Shamir, 1979), and it uses the fact that Shamir secret shares are homomorphic in a special way.
* The underlying shared value can be manipulated obliviously, by suitable manipulations to the individual shares.
* For $v ∈ F$ we write [v] to denote that the parties hold Shamir secret shares of a value $v$.
* More specifically, a dealer chooses a random polynomial $p4 of degree at most $t$, such that $p(0) = v$.
* Each party P$_i$ then holds value $p(i)$ as their share.
* We refer to $t$ as the threshold of the sharing, so that any collection of $t$ shares reveals no information about $v$.
> The invariant of the BGW protocol is that for every wire $w$ in the arithmetic circuit, the parties hold a secret-sharing [$v_w$] of the value $v_w$ on that wire.
**Input wires:** For an input wire belonging to party P$_i$, that party knows the value $v$ on that wire in the clear, and distributes shares of [$v$] to all the parties.
**Addition gate:** Consider an addition gate, with input wires $α, β$ and output wire $γ$.
* The parties collectively hold sharings of incoming wires [$v_α$] and [$v_β$], and the goal is to obtain a sharing of [$v_α + v_β$].
* Suppose the incoming sharings correspond to polynomials $p_α$ and $p_β$, respectively.
* If each party $P_i$ locally adds their shares $p_α(i) + p_β(i)$.
* Then the result is that each party holds a point on the polynomial $p_γ(x)$ def = $p_α(x) + p_β(x)$.
* Since $p_γ$ also has degree at most $t$, these new values comprise a valid sharing $p_γ(0) = p_α(0) + p_β(0) = v_α + v_β$.
> Note that addition gates require no communication among the parties. All steps are local computation. The same idea works to multiply a secret-shared value by a public constant — each party simply locally multiplies their share by the constant.
**Multiplication gate:** Consider a multiplication gate, with input wires $α, β$ and output wire $γ$.
* The parties collectively hold sharings of incoming wires [$v_α$] and [$v_β$], and the goal is to obtain a sharing of the product [$v_α · v_β$].
* As above, the parties can locally multiply their individual shares, resulting in each party holding a point on the polynomial $q(x) = p_α(x) · p_β(x)$.
* However, in this case the resulting polynomial may have degree as high as $2t$ which is too high.
* In order to fix the excessive degree of this secret sharing, the parties engage in a degree-reduction step:
* Each party P$_i$ holds a value $q(i)$, where $q$ is a polynomial of degree at most $2t$.
* The goal is to obtain a valid secret-sharing of $q(0)$, but with correct threshold.
* The main observation is that $q(0)$ can be written as a linear function of the party’s shares.
* In particular:
![](https://i.imgur.com/zIZfTyX.png)
* Where the $λ_i$ terms are the appropriate Lagrange coefficients.
Hence the degree-reduction step works as follows:
1. Each party P$_i$ generates and distributes a threshold-$t$ sharing of [q(i)].
* To simplify the notation, we do not give names to the polynomials that underly these shares.
* However, it is important to keep in mind that each party P$_i$ chooses a polynomial of degree at most $t$ whose constant coefficient is $q(i)$.
2. The parties compute [$q(0)$] = $\sum^{2t+1}_{i=1} λ_i[q(i)]$, using local computations.
* Note that the expression is in terms of addition and multiplication-byconstant applied to secret-shared values.
* Since the values [$q(i)$] were shared with threshold $t$, the final sharing of [$q(0)$] also has threshold $t$, as desired.
> Note that multiplication gates in the BGW protocol require communication/interaction, in the form of parties sending shares of [$q(i)$].
>
> Note also that we require $2t + 1 ≤ n$, since otherwise the $n$ parties do not collectively have enough information to determine the value $q(0)$, as $q$ may have degree $2t$.
>
> For that reason, the BGW protocol is secure against t corrupt parties, for 2t < n (i.e., an honest majority).
**Output wires:** For an output wire $α$, the parties will eventually hold shares of the value [$v_α$] on that wire.
* Each party can simply broadcast its share of this value, so that all parties can learn $v_α$.
### 3.4 MPC From Preprocessed Multiplication Triples
A convenient paradigm for constructing MPC protocols is to split the problem into a pre-processing phase (before the parties’ inputs are known) and an online phase (after the inputs are chosen). The pre-processing phase can produce correlated values for the parties, which they can later “consume” in the online phase
**Intuition:** To get an idea of how to defer some of the protocol effort to the pre-processing phase, recall the BGW protocol.
* The only real cost in the protocol is the communication that is required for every multiplication gate.
* However, it is not obvious how to move any of the related costs to a pre-processing phase, since the costs are due to manipulations of secret values that can only be determined in the online phase (i.e., they are based on the circuit inputs).
* Nonetheless, Beaver (1992) showed a clever way to move the majority of the communication to the pre-processing phase.
* A *Beaver triple* (or multiplication triple) refers to a triple of secret-shared values $[a], [b], [c]$ where $a$ and $b$ are randomly chosen from the appropriate field, and $c = ab$.
* In an offline phase, such Beaver triples can be generated in a variety of ways, such as by simply running the BGW multiplication subprotocol on random inputs.
* One Beaver triple is then “consumed” for each multiplication gate in the eventual protocol.
* Consider a multiplication gate with input wires $α, β$.
* The parties hold secret sharings of [$v_α$] and [$v_β$].
* To carry out the multiplication of $v_α$ and $v_β$ using a Beaver triple $[a], [b], [c]$, the parties do the following:
1. Using local computation, compute [$v_α −a$] and publicly open $d = v_α−a$ (i.e., all parties announce their shares).
* While this value depends on the secret value $v_α$, it is masked by the random value a and therefore reveals no information about $v_α$.
2. Using local computation, compute [$v_β − b$] and publicly open $e = v_β − b$.
3. Observe the following identity:
![](https://i.imgur.com/Mr5lbrO.png)
* Since $d$ and $e$ are public, and the parties hold sharings of $[a], [b], [c]$, they can compute a sharing of [$v_αv_β$] by local computation only:
![](https://i.imgur.com/8KbadUG.png)
> Using this technique, a multiplication can be performed using only two openings plus local computation. Overall, each party must broadcast two field elements per multiplication, compared to $n$ field elements (across private channels) in the plain BGW protocol. While this comparison ignores the cost of generating the Beaver triples in the first place, there are methods for generating triples in a batch where the amortized cost of each triple is a constant number of field elements per party (Beerliová-Trubíniová and Hirt, 2008).
**Abstraction:** While the BGW protocol (specifically, its degree-reduction step) deals with the details of Shamir secret shares, the Beaver-triples approach conveniently abstracts these away.
In fact, it works as long as the parties have an abstract “sharing mechanism” [$v$] with the following properties:
* *Additive homomorphism*: Given [$x$] and [$y$] and a public value $z$, parties can obtain any of [$x + y$], [$x + z$], [$xz$], without interaction.
* *Opening:* Given [$x$], parties can choose to reveal $x$ to all parties.
* *Privacy:* An adversary (from whatever class of adversaries is being considered) can get no information about $x$ from [$x$].
* *Beaver triples:* For each multiplication gate, the parties have a random triple [$a$], [$b$], [$c$] where $c = ab$.
* *Random input gadgets:* For each input wire belonging to party P$_i$, the parties have a random [$r$], where $r$ is known only to P$_i$.
* During the protocol, when P$_i$ chooses its input value $x$ for this wire, it can announce $δ = x − r$ to all parties (leaking nothing about $x$), and they can locally compute [$x$] = [$r$] + $δ$ from the homomorphic properties.
> As long as these properties are true of an abstract sharing mechanism, the Beaver-triples approach is secure. In fact, the paradigm is also secure in the presence of malicious adversaries, as long as the opening and privacy properties of the sharing mechanism hold against such adversaries. Specifically, a malicious adversary cannot falsify the opening of a shared value. We use this fact later in Section 6.6.
**Instantiations:** Clearly Shamir secret sharing gives rise to an abstract sharing scheme [$·$] that satisfies the above properties with respect to adversaries who corrupt at most $t < n/2$ parties.
* Another suitable method of sharing is simple additive sharing over a field $\mathbb{F}$.
* In additive sharing, [$v$] signifies that each party P$_i$ holds $v_i$ where $\sum^n_{i=1} v_i = v$.
* This mechanism satisfies the appropriate homomorphic properties, and is secure against $n$ − 1 corrupt parties.
* When using $\mathbb{F} = {0, 1}$, we obtain an offline-online variant of the GMW protocol (since the field operations in this case correspond to **AND** and **XOR**).
* Of course, an arbitrary $\mathbb{F}$ is possible as well, leading to a version of GMW for arithmetic circuits.
### 3.5 Constant-Round Multi-Party Computation: BMR
The Beaver-MicaliRogaway (BMR) protocol (Beaver et al., 1990) runs in a constant (in the depth of the circuit $\mathcal{C}$) number of rounds, while achieving security against any $t < n$ number of corruptions among the $n$ participating parties.
#### 3.5.1 BMR Intuition
The BMR protocols adapt the main idea of Yao’s GC to a multi-party setting. GC is chosen as a starting point due to its round-efficiency.
* However, a naïve attempt to port the GC protocol from the 2PC into the MPC setting gets stuck at the stage of sending the generated GC to the evaluators.
* The circuit generator knows all the secrets (wire label correspondences), and if it colludes with any of the evaluators, the two colluding parties can learn the intermediate wire values and violate the security guarantees of the protocol
The basic BMR idea is to perform a *distributed* GC generation, so that no single party (or even a proper subset of all parties) knows the GC generation secrets – the label assignment and correspondence.
* This GC generation can be done in parallel for all gates using MPC.
* This is possible by first generating (in parallel) all wire labels independently, and then independently and in parallel generating garbled gate tables.
* Because of parallel processing for all gates/wires, the GC generation is *independent* of the depth of the computed circuit $C$.
* As a result, the GC generation circuit $C_{GEN}$ is constant-depth for all computed circuits $\mathcal{C}$ (once the security parameter $κ$ is fixed).
* Even if the parties perform MPC evaluation of $C_{GEN}$ that depends on the depth of $C_{GEN}$, the overall BMR protocol will still have constant rounds overall.
* The MPC output, the GC produced by securely evaluating CGEN, may be delivered to a designated player, say P$_1$, who will then evaluate it similarly to Yao’s GC.
* The final technicality here is how to deliver the active input labels to P$_1$.
In concrete terms, the above approach is not appealing due to potentially high costs of distributed generation of encryption tables, requiring the garbled row encryption function (instantiated as a PRF or hash function) evaluation inside MPC.
* Several protocols were proposed, which allow the PRF/hash evaluation to be extracted from inside the MPC and instead be done locally by the parties while providing the output of PRF/hash into the MPC.
* The underlying idea of such an approach is to assign different portions of each label to be generated by different players.
* That is, a wire $w_a$’s labels $w^v_a$ are a concatenation of sublabels $w^v_{a,j}$ each generated by P$_j$.
* Then, for a gate G$_i$ with input labels $w^{v_a}_a, w^{vb}_b$ and the output label $w^{vc}_c.
* The garbled row corresponding to input values $v_a, v_b$ and output value $v_c$ can simply be:
![](https://i.imgur.com/OAqi9au.png)
* Where $F : {0, 1}^κ \mapsto {0, 1}^{n·κ}$ is a RPG extending $κ$ bits into $n · κ$ bits.
The generation of the garbled table row is almost entirely done locally by each party.
* Each P$_j$ computes $F(i, w^{v_a}_{a,j}) ⊕ F(i, w^{vb}_{b,j})$ and submits it to the MPC, which simply xors all the values to produce the garbled row.
* However, we are not quite done. Recall that the GC evaluator P$_1$ will reconstruct active labels.
* A careful reader would notice that knowledge of its own contributed sublabel will allow it to identify which plaintext value the active label corresponds to, violating the security guarantee.
* The solution is for each player P$_j$ to add a “flip” bit $f_{a,j}$ to each wire $w_a$.
The xor of the $n$ flip bits, $fa = \bigoplus _{j=1..n} f_{a,j}$, determines which plaintext bit corresponds to the wire label $w^v_a$.
* The flip bits will be an additional input into the garbling MPC.
* Now, with the addition of the flip bits, no subset of players will know the wire flip bit, and hence even the recognition and matching of the sublabel will not allow the evaluator to match the label to plaintext value, or to compute the inactive label in full.
We sketch a concrete example of an efficient BMR garbling in Figure 3.3; BMR evaluation is straightforward based on the garbling technique.
![](https://i.imgur.com/xlelvrl.png)
### 3.6 Information-Theoretic Garbled Circuits
In this section, we discuss a third flavor, where the secrets are shared not among players, but among wires. This construction is also interesting because it provides information-theoretic security in the OT-hybrid setting, meaning that no computational hardness assumptions are used in the protocol beyond what is used in the underlying OT.
An important practical reason to consider IT GC is that it presents a trade-off between communication bandwidth and latency:
* It needs to send less data than Yao GC at the cost of additional communication rounds.
![](https://i.imgur.com/jNQbTJG.png)
### 3.7 Oblivious Transfer
Oblivious Transfer, defined in Section 2.4, is an essential building block for secure computation protocols, and an inherently asymmetric primitive.
#### 3.7.1 Public Key-Based OT
We start with the basic public key-based OT in the semi-honest model. The construction, presented in Figure 3.6, is very simple indeed.
* The security of the construction assumes the existence of public-key encryption with the ability to sample a random public key without obtaining the corresponding secret key.
* The scheme is secure in the semi-honest model.
* The Sender $\mathcal{S}$ only sees the two public keys sent by $\mathcal{R}$, so cannot predict with probability better than $1\over2$ which key was generated without the knowledge of the secret key.
* Hence, the view of $\mathcal{S}$ can be simulated simply by sending two randomly-chosen public keys.
* The Receiver $\mathcal{R}$ sees two encryptions and has a secret key to decrypt only one of them.
* The view of $\mathcal{R}$ is also easily simulated, given $\mathcal{R}$’s input and output.
* Sim$_S$ will generate the public-private key pair and a random public key, and set the simulated received ciphertexts to be:
1. The encryption of the received secret under the generated keypair.
2. And the encryption of zero under the randomly chosen key.
* The simulation goes through since the difference with the real execution is only in the second encryption, and distinguisher will not be a tell apart the encryption of zero from another value due to the encryption security guarantees.
> Note that this semi-honest protocol provides no security against a malicious sender—the Sender $\mathcal{S}$ can simply generate two public-private key pairs, $(sk_0, pk_0)$ and $(sk_1, pk_1)$ and send $(pk_0, pk_1)$ to $\mathcal{R}$, and decrypt both received ciphertexts to learn both $x_1$ and $x_2$.
#### 3.7.2 Public Key Operations in OT
The simple protocol in Figure 3.6 requires one public key operation for both the sender and receiver for each selection bit. As used in a Boolean circuit-based MPC protocol such as Yao’s GC, it is necessary to perform an OT for each input bit of the party executing the circuit. For protocols like GMW, evaluating each AND gate requires an OT. Hence, several works have focused on reducing the number of public key operations to perform a large number of OTs.
### 3.8 Custom Protocols
Circuit-based protocols suffer from linear bandwidth cost in the size of the circuit, which can be prohibitive for large computations. There are significant overheads with circuit-based computation on large data structures, compared to, say, a RAM (Random Access Machine) representation.
Several specialized problems do benefit from tailored solutions and the performance gains possible with custom protocols may be substantial. In this work we briefly review one such practically important problem: *private set intersection.*
#### 3.8.1 Private Set Intersection (PSI)
The goal of private set intersection (PSI) is to enable a group of parties to jointly compute the intersection of their input sets, without revealing any other information about those sets (other than upper bounds on their sizes).
* Although protocols for PSI have been built upon generic MPC (Huang et al., 2012a), more efficient custom protocols can be achieved by taking advantage of the structure of the problem.
## 4 Implementation Techniques
### 4.1 Less Expensive Garbling
The main costs of executing a garbled circuits protocol are the bandwidth required to transmit the garbled gates and the computation required to generate and evaluate the garbled tables.
* In a typical setting (LAN or WAN and moderate computing resources such as smartphone or a laptop), bandwidth is the main cost of executing GC protocols.
* There have been many improvements to the traditional garbling method introduced in Section 3.1.2;
Table 4.1 summarizes the impact of garbing improvements on the bandwidth and computation required to generate and evaluate a garbled gate.
![](https://i.imgur.com/2GEhztq.png)
#### 4.1.1 Garbled Row Reduction
Naor et al. (1999) introduced garbled row reduction (GRR) as a way to reduce the number of ciphertexts transmitted per gate.
* The key insight is that it is not necessary for each ciphertext to be an (unpredictable) encryption of a wire label.
* Indeed, one of the entries in each garbled table can be fixed to a predetermined value (say $0^κ$), and hence need not be transmitted at all.
* For example, consider the garbled table below, where $a$ and $b$ are the input wires, and $c$ is the output:
![](https://i.imgur.com/D6BLD6p.png)
* Since $c^0$ and $c^1$ are just arbitrary wire labels, we can select $c^0 = H(a^1 \| b^0 )$.
* Thus, one of the four ciphertexts in each gate (say, the first one when it is sorted according point-and-permute order) will always be the all-zeroes string and does not need to be sent.
Pinkas et al. (2009) describe a way to further reduce each gate to two ciphertexts, applying a polynomial interpolation at each gate.
* Because this is not compatible with the FreeXOR technique described next, however, it was rarely used in practice.
* The later half-gates technique (Section 4.1.3) achieves two-ciphertext **AND** gates and is compatible with FreeXOR, so supersedes the interpolation technique of Pinkas et al. (2009).
#### 4.1.2 FreeXOR
One of the results of Kolesnikov (2005) was the observation that the GESS sharing for **XOR** gates can be done without any growth of the share sizes (Section 3.6).
* Kolesnikov (2005) found a lower bound for the minimum share sizes, explaining the necessity of the exponential growth for independent secrets.
* This bound, however, did not apply to **XOR** gates (or, more generally, to “even” gates whose truth table had two zeros and two ones).
As introduced in Section 3.6, XOR sharing for GESS can simply be done as follows:
* Let $s_0, s_1 ∈ \mathcal{D}_S$ be the output wire secrets.
* Choose $R ∈_R \mathcal{D}_S$ and set the shares $sh_{10} = R, sh_{11} = s_0 ⊕ s_1 ⊕ R, sh_{20} = s_0 ⊕ R, sh_{21} = s_1 ⊕ R$.
* The share reconstruction procedure on input $sh_{1i} , sh_{2j}$, outputs $sh_{1i} ⊕ sh_{2j}$.
* It is easy to verify that this allows the evaluator to reconstruct the correct gate output secret.
* e.g., $sh_{11} ⊕ sh_{21} = (s_0 ⊕ s_1 ⊕ R) ⊕ (s_1 ⊕ R) = s_0$.
* Denoting $s_0 ⊕ s_1 = ∆$, we observe that this offset $∆$ is preserved for the labels of each wire:
* $sh_{10} ⊕ sh_{11} = sh_{20} ⊕ sh_{21} = s_0 ⊕ s_1 = ∆$.
Because the shares on all of the gate’s wires have the same offset, the above GESS XOR gate construction cannot be directly plugged into Yao’s GC, since standard Yao’s GC requires wires to be independently random.
* This breaks both correctness and security of GC.
* Indeed, correctness is broken because GESS XOR will not produce the pre-generated output wire secrets.
* Standard GC security proofs fail since GESS XOR creates correlations across wire labels, which are encryption keys.
* Even more problematic with respect to security is the fact that keys and encrypted messages are related to each other, creating circular dependencies.
**FreeXOR: Integrating GESS XOR into GC:** FreeXOR is a GC technique introduced by Kolesnikov and Schneider (2008b). Their work is motivated by the fact that in GESS an **XOR** gate costs nothing (no garbled table needed, and share secrets don’t grow), while traditional Yao’s GC pays full price of generating and evaluating a garbled table for **XOR** gates.
* The GC FreeXOR construction enables the use of GESS XOR construction by adjusting GC secrets generation to repair the correctness broken by the naïve introduction of GESS XOR into GC, and observing that a strengthening of the assumptions on the encryption primitives used in the construction of GC garbled tables is sufficient for security of the new scheme.
* FreeXOR integrates GESS XOR into GC by requiring that *all* the circuit’s wires labels are generated with the same offset $∆$.
* That is, we require that for each wire $w_i$ of GC Cb and its labels $w^0_i , w^1_i$ , it holds that $w^0_i ⊕ w^1_i = ∆$, for a randomly chosen $∆ ∈_R \{0, 1\}^κ$.
* Introducing this label correlation enables GESS XOR to correctly reconstruct output labels.
* To address the security guarantee, FreeXOR uses Random Oracle (RO) for encryption of gates’ output labels, instead of the weaker (PRG-based) encryption schemes allowed by Yao GC.
* This is necessary since inputs to different instances of $H$ are correlated by $∆$, and furthermore different values masked by $H$’s output are also correlated by $∆$.
* The standard security definition of a PRG does not guarantee that the outputs of $H$ are pseudorandom in this case, but a random oracle does.
The full garbling protocol for FreeXOR is given in Figure 4.1:
![](https://i.imgur.com/8TSZKvD.png)
The FreeXOR GC protocol proceeds identically to the standard Yao GC protocols of Figure 3.2, except that in Step 4, P$_2$ processes XOR gates without needing any ciphertexts or encryption: for an XOR-gate G$_i$ with garbled input labels $w_a = (k_a, p_a), w_b = (k_b, p_b)$, the output label is directly computed as ($k_a ⊕ k_b, p_a ⊕ p_b$).
> Kolesnikov et al. (2014) proposed a generalization of FreeXOR called fleXOR. In fleXOR, an XOR gate can be garbled using 0, 1, or 2 ciphertexts, depending on structural and combinatorial properties of the circuit. FleXOR can be made compatible with GRR2 applied to **AND** gates, and thus supports two-ciphertext **AND** gates. The half gates technique described in the next section, however, avoids the complexity of fleXOR, and reduces the cost of **AND** gates to two ciphertexts with full compatibility with FreeXOR.
#### 4.1.3 Half Gates
Zahur et al. (2015) introduced an efficient garbling technique that requires only two ciphertexts per **AND** gate and fully supports FreeXOR.
* The key idea is to represent an **AND** gate as **XOR** of two *half gates*, which are** AND** gates where one of the inputs is known to one of the parties.
* Since a half gate requires a garbled table with two entries, it can be transmitted using the garbled row reduction (GRR3) technique with a single ciphertext.
* Implementing an **AND** gate using half gates requires constructing:
* A generator half gate (where the generator knows one of the inputs).
* And an evaluator half gate (where the evaluator knows one of the inputs).
**Generator Half Gate:** First, consider the case of an **AND** gate where the input wires are $a$ and $b$ and the output wire is $c$.
* The generator half-AND gate computes $v_c = v_a ∧ v_b$, where $v_a$ is somehow known to the circuit generator.
* When $v_a$ is false, the generator knows $v_c$ is false regardless of $vb$.
* When $v_a$ is true, $v_c = v_b$.
* We use $a^0 , b^0$, and $c^0$ to denote the wire labels encoding false for wires $a, b$, and $c$ respectively.
* Using the FreeXOR design, the wire label for $b$ is either $b^0 or b^1 = b^0 ⊕ ∆$.
* The generator produces the two ciphertexts:
* These are permuted according to the pointer bits of $b^0$, according to the point-and-permute optimization.
![](https://i.imgur.com/ptHT0t0.png)
* To evaluate the half gate and obtain $v_a ∧v_b$, the evaluator takes a hash of its wire label for $b$ (either $b_0$ or $b_1$) and decrypts the appropriate ciphertext.
* If the evaluator has $b^0$ , it can compute $H(b^0)$ and obtain $c^0$ (the correct semantic false output) by xor-ing it with the first ciphertext.
* If the evaluator has $b^1 = b^0 ⊕ ∆$, it computes $H(b^1)$ to obtain $c^0 ⊕ v_a · ∆$.
* If $v_a = 0$, this is $c^0$.
* If $v_a = 1$, this is $c^1 = c^0 ⊕ ∆$.
* Intuitively, the evaluator will never know both $b^0$ and $b^1$, hence the inactive ciphertext appears completely random.
**Evaluator Half Gate:** For the evaluator half gate, $v_c = v_a ∧ v_b$, the evaluator knows the value of $v_a$ when the gate is evaluated, and the generator knows neither input.
* Thus, the evaluator can behave differently depending on the known plaintext value of wire $a$.
* The generator provides the two ciphertexts:
![](https://i.imgur.com/9sVY26p.png)
* The ciphertexts are not permuted here—since the evaluator already knows $v_a$, it is fine (and necessary) to arrange them deterministically in this order.
* When $v_a$ is false, the evaluator knows it has $a^0$ and can compute $H(a^0)$ to obtain output wire c 0 .
* When $v^a$ is true, the evaluator knows it has $a^1$ so can compute $H(a^1)$ to obtain $c^0 ⊕ b^0$.
* It can then xor this with the wire label it has for $b$, to obtain either $c^0$ (false, when $b = b^0$) or $c^1 = c^0 ⊕ ∆$ (true, when $b^1 = b^0 ⊕ ∆$), without learning the semantic value of $b$ or $c$.
> As with the generator half gate, using garbled row-reduction (Section 4.1.1) reduces the two ciphertexts to a single ciphertext. In this case, the generator simply sets $c^0 = H(a^0)$ (making the first ciphertext all zeroes) and sends the second ciphertext.
**Combining Half Gates:** It remains to show how the two half gates can be used to evaluate a gate $v_c = v_a ∧ v_b$, in a garbled circuit, where neither party can know the semantic value of either input.
* The trick is for the generator to generate a uniformly random bit $r$, and to transform the original **AND** gate into two half gates involving $r$:
![](https://i.imgur.com/AQyb3py.png)
* This has the same value as $v_a ∧ v_b$ since it distributes to $v_a ∧ (r ⊕ r ⊕ v_b$).
* The first **AND** gate ($v_a ∧ r$) can be garbled with a generator half-gate.
* The second **AND** gate ($v_a ∧ (r ⊕ v_b$)) can be garbled with an evaluator half-gate, but only if $r ⊕ v_b$ is leaked to the evaluator.
* Since $r$ is uniformly random and not known to the evaluator, this leaks no sensitive information to the evaluator.
The generator does not know $v_b$, but can convey $r ⊕ v_b$ to the evaluator without any overhead, as follows:
* The generator will choose $r$ to be the point-and-permute pointer bit of the false wire label on wire $b$, which is already chosen uniformly randomly.
* Thus, the evaluator learns $r ⊕ v_b$ directly from the pointer bit on the wire it holds for $b$ without learning anything about $v_b$.
Since the **XOR** gates do not require generating and sending garbled tables by using FreeXOR, we can compute an **AND** gate with only two ciphertexts, two invocations of $H$, and two “free” **XOR** operations.
* Zahur et al. (2015) proved the security of the half-gates scheme for any $H$ that satisfies correlation robustness for naturally derived keys.
* In all settings, including low-latency local area networks, both the time and energy cost of bandwidth far exceed the cost of computing the encryptions (see the next section for how $H$ is computed in this and other garbling schemes), and hence the half-gates method is preferred over any other known garbling scheme.
* Zahur et al. (2015) proved that no garbling scheme in a certain natural class of “linear” schemes could use fewer than two ciphertexts per gate.
* Hence, under these assumptions the half-gates scheme is bandwidth-optimal for circuits composed of two-input binary gates (see Section 4.5 for progress on alternatives).
#### 4.1.4 Garbling Operation
Network bandwith is the main cost for garbled circuits protocols in most practical scenarios. However, computation costs of GC is also substantial, and is dominated by calls to the encryption function implementing the random oracle $H$ in garbling gates, introduced in Section 3.1.2. Several techniques have been developed to reduce that cost, in particular by taking advantage of built-in cryptographic operations in modern processors.
* Since 2010, Intel cores have included special-purpose AES-NI instructions for implementing AES encryption, and most processors from other vendors include similar instructions.
* Further, once an AES key is set up (which involves AES round keys generation), the AES encryption is particularly fast.
* This combination of incentives motivated Bellare et al. (2013) to develop fixed-key AES garbling schemes, where $H$ is implemented using fixed-key AES as a cryptographic permutation.
* Their design is based on a *dual-key* cipher (Bellare et al., 2012), where two keys are both needed to decrypt a ciphertext.
* Bellare et al. (2012) show how a secure dual-key cipher can be built using a single fixed-key AES operation under the assumption that fixed-key AES is effectively a random permutation.
* Since the permutation is invertible, it is necessary to combine the permutation with the key using the Davies-Meyer construction (Winternitz, 1984): $ρ(K) = π(K) ⊕ K$
* Bellare et al. (2013) explored the space of secure garbling functions constructed from a fixed-key permutation, and found the fastest garbling method using:
* $π(K||T)[1 : k] ⊕ K ⊕ X$.
* Where $K ← 2A ⊕ 4B$.
* $A$ and $B$ are the wire keys.
* $T$ is a tweak.
* And $X$ is the output wire.
Gueron et al. (2015) pointed out that the assumption that fixed-key AES behaves like a random permutation is non-standard and may be questionable in practice.
* They developed a fast garbling scheme based only on the more standard assumption that AES is a pseudorandom function.
* In particular, they showed that most of the performance benefits of fixed-key AES can be obtained just by carefully pipelining the AES key schedule in the processor.
Note also that the FreeXOR optimization also requires stronger than standard assumptions (Choi et al., 2012b), and the half-gates method depends on FreeXOR.
* Gueron et al. (2015) showed a garbling construction alternative to FreeXOR that requires only standard assumptions.
* But requires a single ciphertext for each **XOR** gate.
* Moreover, their construction is compatible with a scheme for reducing the number of ciphertexts needed for **AND** gates to two (without relying on FreeXOR, as is necessary for half gates).
* The resulting scheme has higher cost than the half-gates scheme because of the need to transmit one ciphertext for each **XOR**, but shows that it is possible to develop efficient (within about a factor of two of the cost of half gates) garbling schemes based only on standard assumptions.
### 4.2 Optimizing Circuits
Since the main cost of executing a circuit-based MPC protocol scales linearly with the size of the circuit, any reduction in circuit size will have a direct impact on the cost of the protocol.
#### 4.2.1 Manual Design
Several projects have manually designed circuits to minimize the costs of secure computation often focusing on reducing the number of non-free gates when FreeXOR is used.
* Manual circuit design can take advantage of opportunities that are not found by automated tools, but because of the effort required to manually design circuits, is only suitable for widely-used circuits.
**Oblivious permutation:** Shuffling an array of data in an oblivious permutation is an important building block for many privacy-preserving algorithms, including private set intersection (Huang et al., 2012a) and square-root ORAM (Section 5.4).
* A basic component of an oblivious permutation, as well as many other algorithms, is a conditional *swapper* (also called an $X$ switching block by Kolesnikov and Schneider (2008b) and Kolesnikov and Schneider (2008a)).
* Which takes in two inputs, $a_1$ and $a_2$, and produces two outputs, $b_1$ and $b_2$.
* Depending on the value of the swap bit $p$, either the outputs match the inputs ($b_1 = a_1$ and b_2 = a_2) or the outputs are the inputs in swapped order ($b_1 = a_2$ and $b_2 = b_1$).
* The swap bit $p$ is known to the circuit generator, but must not be revealed to the evaluator.
Kolesnikov and Schneider (2008b) provided a design for a swapper that takes advantage of FreeXOR and requires only a two-row garbled table (which can be reduced to a single ciphertext using garbled row reduction from Section 4.1.1). The swapper is implemented as:
![](https://i.imgur.com/TvfGIN6.png)
![](https://i.imgur.com/SLuu5rZ.png)
* The swapper is illustrated in Figure 4.2.
* There the block $f$ is set to 0 if no swapping is desired.
* And to 1 to implement swapping.
* The $f$ block is implemented as a conjunction of the input with the programming bit $p$, so Figure 4.2 corresponds to Equation 4.1.
* Since wire outputs can be reused, $p ∧ (a_1 ⊕ a_2)$ only needs to be evaluated once.
* Referring back to the half-gates garbling and the notation of Section 4.1.3, when $p$ is known to the generator, this conjunction is a generator half gate.
> With the above conditional swapper, a random oblivious permutation can be produced by the circuit generator by selecting a random permutation and configuring the swappers in a Waksman network (Waksman, 1968) as necessary to produce it (Huang et al., 2012a).
**Low-depth circuits: optimizing for GMW:** In the GMW protocol (Section 3.2) each **AND** gate evaluation requires an OT, and hence a round of communication.
* **AND** gates on the same level can be batched and executed in the same round.
* Thus, unlike Yao’s GC where the cost of execution is independent of its depth.
* For GMW protocol executions, the cost depends heavily on the depth of the circuit.
* Choi et al. (2012a) built an efficient implementation of GMW by using OT precomputation (Beaver, 1995) to reduce the on-line computation to a simple XOR, and OT extension protocols (Section 3.7.2) to reduce the overall cost of OT.
* A communication round (two messages) is still required during evaluation for each level of **AND** gates, however, so circuit execution time depends on the depth of the circuit.
* Schneider and Zohner (2013) provided further optimizations to the OT protocols for use in GMW, and designed lowdepth circuits for several specific problems.
* Since GMW supports FreeXOR, the effective depth of a circuit is the maximum number of **AND** gates on any path.
* Schneider and Zohner (2013) were able to produce results on low-latency networks with GMW that were competitive with Yao’s GC implementations by designing low-depth circuits for addition, squaring, comparison, and computing Hamming weight, and by using single-instruction multiple data (SIMD) instructions to pack operations on multiple bits, following on the approach used by Sharemind (Bogdanov et al., 2008a).
#### 4.2.2 Automated Tools
Boolean circuits go back to the earliest days of computing (Shannon, 1937). Because they have core applications in computing (e.g., in hardware components), there are a number of tools that have been developed to produce efficient Boolean circuits. The output of some of these tools can be adapted to circuit-based secure computation.
**CBMC-GC:** Holzer et al. (2012) used a model checking tool as the basis for a tool that compiles C programs into Boolean circuits for use in a garbled circuits protocol.
* CBMC operates at the level of bits in the machine, so the Boolean formula it generates is consistent with the program semantics at the bit level.
* When used as a model checker, CBMC attempts to find a satisfying assignment of the Boolean formula corresponding to the input program.
* If a satisfying assignment is found, it corresponds to a program trace that violates an assertion in the program.
* CBMC unrolls loops and inlines recursive function calls up to the given model-checking bound, removing cycles from the program.
* For many programs, CBMC can statically determine the maximum number of loop iterations.
* When it cannot, programmers can use annotations to state this explicitly.
* When used in bounded model checking, an assertion is inserted that will be violated if the unrolling was insufficient.
* Variables are replaced by bit vectors of the appropriate size, and the program is converted to single-static assignment form so that fresh variables are introduced instead of assigning to a given variable more than once.
* Normally, CBMC would convert the program to a Boolean formula, but internally it is represented as a circuit.
* Hence, CBMC can be used as a component in a garbled circuits compiler that translates an input program in C into a Boolean circuit.
* To build CBMC-GC, Holzer et al. (2012) modified CBMC to output a Boolean circuit which can be then executed in circuit-based secure computation framework (such as the one from Huang et al. (2011b), which was used by CBMC-GC).
* Since CBMC was designed to optimize circuits for producing Boolean formulas for SAT solvers, modifications were done to produce better circuits for garbled circuit execution.
* In particular, **XOR** gates are preferred in GC execution due to the FreeXOR technique (whereas the corresponding costs in model checking favor AND gates).
* To minimize the number of non-free gates, Holzer et al. (2012) replaced the built-in circuits CBMC would use for operations like addition and comparison, with designs that minimize costs with free **XOR** gates.
**TinyGarble:** Another approach to generating circuits for MPC is to leverage the decades of effort that have been invested in hardware circuit synthesis tools. Hardware description language (HDL) synthesis tools transform a high-level description of an algorithm, which could be written in a programming language or common HDL language such as Verilog, into a Boolean circuit.
* A synthesis tool optimizes a circuit to minimize its size and cost, and then outputs a *netlist*, which is a straightforward description of a circuit as a list of logic gates with connected inputs and outputs.
* Conventional hardware synthesis tools, however, do not generate circuits suitable for MPC protocols because they generate circuits that may have cycles and they are designed to optimize for different costs that are encountered the MPC execution.
* In particular, they assume the cost of gates based on hardware implementations.
* With TinyGarble, Songhori et al. (2015) overcame these problems in adapting circuit synthesis tools for generating circuits for MPC, and Yao’s GC in particular.
The approach of TinyGarble is to use sequential logic in a garbled circuit.
* In a sequential circuit, instead of just connecting gates in a combinational way where each gate’s outputs depend only on its inputs and no cycles are permitted, a circuit also can maintain state.
* In hardware, state would be stored in a physical memory element (such as a flip-flop), and updated with each clock cycle.
* To execute (generate and send) a garbled circuit, TinyGarble instead unrolls a sequential circuit, so the stored state is an additional input to the circuit, and new garbled gates are generated for each iteration.
* This means the representation is compact, even for large circuit executions, which allows performance improvement due to the ability to store the circuit in processor cache and avoid expensive RAM accesses.
* This method trades off a slight increase in the number of garbled gates to execute for a reduction in the size of the circuit representation.
> Songhori et al. (2015) report a 67% reduction in the number of non-**XOR** gates in 1024-bit multiplication compared to automatically-generated circuits for same function. For a more diverse function set (implementing a MIPS processor), the circuit generation has modest performance improvement as compared to prior work (the synthesized MIPS CPU circuit reduces the number of non-**XOR** gates by less than 15% compared to a straightforward assembly of MIPS CPU from constituent blocks).
### 4.3 Protocol Execution
The main limit on early garbled circuit execution frameworks, starting with Fairplay (Malkhi et al., 2004), is that they needed to generate and store the entire garbled circuit.
* In this section, we discuss various improvements to the way MPC protocols are executed that have overcome these scaling issues and eliminated much of the overhead of circuit execution.
**Pipelined Execution:** Huang et al. (2011b) introduced garbled circuit pipelining, which eliminated the need for either party to ever store the entire garbled circuit.
* Instead of generating the full garbled circuit and then sending it, the circuit generation and evaluation phases are interleaved.
* Before the circuit execution begins, both parties instantiate the circuit structure, which is small relative to the size of the full garbled circuit since it can reuse components and is made of normal gate representations instead of non-reusable garbled gates.
* To execute the protocol, the generator produces garbled gates in an order that is determined by the topology of the circuit, and transmits the garbled tables to the evaluator as they are produced.
* As the client receives them, it associates each received garbled table with the corresponding gate of the circuit.
* Since the order of generating and evaluating the circuit is fixed according to the circuit (and must not depend on the parties’ private inputs), keeping the two parties synchronized requires essentially no overhead
* As it evaluates the circuit, the evaluator maintains a set of live wire labels and evaluates the received gates as soon as all their inputs are ready.
> This approach allows the storage for each gate to be reused after it is evaluated, resulting in much smaller memory footprint and greatly increased performance.
**Compressing Circuits:** Pipelining eliminates the need to store the entire garbled circuit, but still requires the full structural circuit to be instantiated. Sequential circuits, mentioned earlier in Section 4.2.2, are one way to overcome this by enabling the same circuit structure to be reused but require a particular approach to circuit synthesis and some additional overhead to maintain the sequential circuit state.
Another approach, initiated by Kreuter et al. (2013), uses lazy generation from a circuit representation that supports bounded loops.
* Structural circuits are compactly encoded using a *Portable Circuit Format* (PCF), which is generated by a circuit compiler and interpreted as the protocol executes.
* The input to the the circuit compiler is intermediate level stack machine bytecode output by the LCC front-end compiler (Fraser and Hanson, 1995), enabling the system to generate MPC protocols from different high-level programs.
* The circuit compiler takes in an intermediate level description of a program to execute as an MPC, and outputs a compressed circuit representation.
* This representation is then used as the input to interpreters that execute the generator and evaluator for a Yao’s GC protocol, although the same representation could be used for other interpreters to executed different circuit-based protocols.
* The key insight enabling PCF’s scalability is to evaluate loops without unrolling them by reusing the same circuit structure while having each party locally maintain the loop index.
* Thus, new garbled tables can be computed as necessary for each loop execution, but the size of the circuit, and local memory needed, does not grow with the number of iterations.
> To support secure computation, garbled wire values are represented by unknown values, which cannot be used as the conditions for conditional branches. The PCF compiler implemented several optimizations to reduce the cost of the circuits, and was able to scale to circuits with billions of gates (e.g., over 42 billion gates, of which 15 billion were non-free, to compute 1024-bit RSA).
**Mixed Protocols:** Although generic MPC protocols such as Yao’s GC and GMW can execute any function, there are often much more efficient ways to implement specific functions. For example, additively homomorphic encryption schemes (including Paillier (1999) and Damgård and Jurik (2001)) can perform large additions much more efficiently than can be done with Boolean circuits.
* With homomorphic encryption, instead of jointly computing a function using a general-purpose protocol, P$_1$ encrypts its input and sends it to P$_2$.
* P$_2$ then uses the encryption homomorphism to compute (under encryption) a function on the encrypted input, and sends the encrypted result back to P$_1$.
* Unless the output of the homomorphic computation is the final MPC result, its plaintext value cannot be revealed.
* Kolesnikov et al. (2010) and Kolesnikov et al. (2013) describe a general mechanism for converting between homomorphically-encrypted and garbled GC values.
* The party that evaluates the homomorphic encryption, P$_2$, generates a random mask $r$, which is added to the output of the homomorphic encryption, $Enc(x)$, before being sent to P$_1$ for decryption.
* Thus the value received by P$_1$ is $Enc(x + r)$, which P$_1$ can decrypt to obtain $x + r$.
* To enter $x$ into the GC evaluation, P$_1$ provides $x + r$ and P$_2$ provides $r$ as their inputs into the GC.
* The garbled circuit performs the subtraction to cancel out the mask, producing a garbled representation of $x$.
**Outsourcing MPC:** Although it is possible to run MPC protocols directly on low-power devices, such as smartphones (Huang et al., 2011a), the high cost of bandwidth and the limited energy available for mobile devices makes it desirable to outsource the execution of an MPC protocol in a way that minimizes the resource needed for the end user device without compromising security.
We focus here on the scheme from Carter et al. (2016) which targets the scenario where a mobile phone user wants to outsource the execution of an MPC protocol to a cloud service.
* The other party in the MPC is a server that has high bandwidth and computing resources, so the primary goal of the design is to make the bulk of the MPC execution be between the server and cloud service, rather than between the server and mobile phone client.
* The cloud service may be malicious, but it is assumed not to collude with any other party.
* It is a requirement that no information about either the inputs or outputs of the secure function evaluation are leaked to the cloud service.
* To obtain the inputs with lower resources from the client, the protocol uses an outsourced oblivious transfer protocol.
* To provide privacy of the outputs, a blinding circuit is added to the original circuit that masks the output with a random pad known only to the client and server.
* By moving the bulk of the garbled circuit execution cost to the cloud service, the costs for the mobile device can be dramatically reduced.
### 4.4 Programming Tools
Many programming tools have been developed for building privacy-preserving applications using MPC.
* These tools vary by:
* The input languages they support.
* How they combine the input program into a circuit and how the output is represented.
* As well as the protocols they support.
Table 4.2 provides a highlevel summary of selected tools for building MPC applications.
![](https://i.imgur.com/qrPGS0O.png)
> We don’t attempt to provide a full survey of MPC programming tools here, but describe one example of a secure computation programming framework next.
**Obliv-C:** The Obliv-C language is a strict extension of C that supports all C features, along with new data types and control structures to support dataoblivious programs that will be implemented using MPC protocols.
* Obliv-C is designed to provide high-level programming abstractions while exposing the essential data-oblivious nature of such computations.
* This allows programmers to implement libraries for data-oblivious computation that include low-level optimizations without needing to specify circuits.
* In Obliv-C, a datatype declared with the obliv type modifier is oblivious to the program execution.
* It is represented in encrypted form during the protocol execution, so nothing in the program execution can depend on its semantic value.
* The only way any values derived from secret data can be converted back to a semantic value is by calling an explicit **reveal** function.
* When this function is invoked by both parties on the same variable, the value is decrypted by the executing protocol, and its actual value is now available to the program.
* Control flow of a program cannot depend on oblivious data since its semantic value is not available to the execution.
* Instead, Obliv-C provides oblivious control structures.
* For example, consider the following statement where $x$ and $y$ are **obliv** variables:
![](https://i.imgur.com/f0r0LIq.png)
* Since the truth value of the $x > y$ condition will not be known even at runtime, there is no way for the execution to know if the assignment occurs.
* Instead, every assignment statement inside an oblivious conditional context must use “multiplexer” circuits that select based on the semantic value of the comparison condition within the MPC whether to perform the update or have no effect.
* Within the encrypted protocol, the correct semantics are implemented to ensure semantic values are updated only on the branch that would actually be executed based on the oblivious condition.
* Figure 4.3 shows an example of how an unconditional block (denoted with ∼**obliv**(var)) can be used to implement oblivious data structures in Obliv-C.
* This is an excerpt of an implementation of a simple resizable array implemented using a **struct** that contains oblivious variables representing the content and actual size of the array, and an opaque variable representing its maximum possible size.
* While the current length of the array is unknown (since we might append() while inside an **obliv if**), we can still use an unconditional block to track a conservative upper bound of the length.
* This simple example illustrates how Obliv-C can be used to implement low-level optimizations for complex oblivious data structures, without needing to implement them at the level of circuits.
![](https://i.imgur.com/aDeiTXj.png)