Secure outsourced garbled circuit evaluation for mobile devices

Abstract

Garbled circuits provide a powerful tool for jointly evaluating functions while preserving the privacy of each user’s inputs. While recent research has made the use of this primitive more practical, such solutions generally assume that participants are symmetrically provisioned with massive computing resources. In reality, most people on the planet only have access to the comparatively sparse computational resources associated with their mobile phones, and those willing and able to pay for access to public cloud computing infrastructure cannot be assured that their data will remain unexposed. We address this problem by creating a new SFE protocol that allows mobile devices to securely outsource the majority of computation required to evaluate a garbled circuit. Our protocol, which builds on the most efficient garbled circuit evaluation techniques, includes a new outsourced oblivious transfer primitive that requires significantly less bandwidth and computation than standard OT primitives and outsourced input validation techniques that force the cloud to prove that it is executing all protocols correctly. After showing that our extensions are secure in the malicious model, we conduct an extensive performance evaluation for a number of standard SFE test applications as well as a privacy-preserving navigation application designed specifically for the mobile use-case. Our system reduces execution time by 98.92% and bandwidth by 99.95% for the edit distance problem of size 128 compared to non-outsourced evaluation. These results show that even the least capable devices are capable of using large garbled circuits for secure computation.

Keywords

Garbled circuits mobile privacy secure function evaluation

1. Introduction

Secure Function Evaluation (SFE) allows two or more parties to compute the result of a function without any party having to expose their potentially sensitive inputs to the others. While considered a generally theoretical curiosity even after the discovery of Yao’s garbled circuit [63], recent advances in this space have made such computation increasingly practical. Today, functions as complex as AES-128 and approaching one billion gates in size are possible at reasonable throughputs, even in the presence of a malicious adversary.

While recent research has made the constructions in this space appreciably more performant, the majority of related work makes a crucial assumption – that both parties are symmetrically provisioned with massive computing resources. For instance, Kreuter et al. [37] rely on the Ranger cluster at the Texas Advanced Computing Center to compute their results using 512 cores. In reality, the extent of a user’s computing power may be their mobile phone, which has many orders of magnitude less computational ability. In the increasingly common setting where a mobile device performs some computation with an application server, there is an asymmetry of computational ability that makes current SFE techniques highly impractical. Moreover, even if the mobile device is given access to a public compute cloud such as Amazon EC2 or Windows Azure, the sensitive nature of the user’s data and the history of data leakage from cloud services [58,61] prevent the direct porting of known SFE techniques.

In this paper, we develop mechanisms for the secure outsourcing of SFE computation from constrained devices to more capable infrastructure. Our protocol maintains the privacy of both the mobile user’s and the application server’s inputs and outputs while significantly reducing the computation and network overhead required by the mobile device for garbled circuit evaluation. We develop a number of extensions to allow the mobile device to check for malicious behavior from the circuit generator or the cloud and a novel Outsourced Oblivious Transfer (OOT) for sending garbled input data to the cloud. We then implement the new protocol on a commodity mobile device and reasonably provisioned servers and demonstrate significant performance improvements over evaluating garbled circuits directly on the mobile device.

We make the following contributions:

Outsourced oblivious transfer and outsourced consistency checks: Instead of blindly trusting the cloud with sensitive inputs, we develop a highly efficient Outsourced Oblivious Transfer primitive that allows mobile devices to securely delegate the majority of computation associated with oblivious transfers. We also provide mechanisms to outsource consistency checks to prevent a malicious circuit generator from providing corrupt garbled values. These checks are designed in such a way that the computational load is almost exclusively on the cloud, but cannot be forged by a malicious or “lazy” cloud. We demonstrate that both of our additions are secure in the malicious model as defined by Kamara et al. [31].

Performance analysis: Extending upon the implementation by Kreuter et al. [37], we conduct an extensive performance analysis against a number of simple applications (e.g., edit distance) and cryptographic benchmarks (e.g., AES-128). Our results show that outsourcing SFE provides improvements to both execution time and bandwidth overhead. For the edit distance problem of size 128, we reduce execution time by 98.92% and bandwidth by 99.95% compared to direct execution without outsourcing on the mobile device.

Privacy preserving navigation app: To demonstrate the practical need for our techniques, we design and implement an outsourced version of Dijkstra’s shortest path algorithm as part of a Navigation mobile app. Our app provides directions for a Presidential motorcade without exposing its location, destination, or known hazards that should be avoided (but remain secret should the mobile device be compromised). The optimized circuits generated for this app are among the largest circuits evaluated to date. Without our outsourcing techniques, such an application is far too processor, memory and bandwidth intensive for any mobile phone.

While this work is similar in function and provides equivalent security guarantees to the Salus protocols recently developed by Kamara et al. [31], our approach is dramatically different. The authors of the Salus protocol state that their protocol is optimized for outsourcing work from low-computation devices with high communication bandwidth. With provider-imposed bandwidth caps and relatively slow and unreliable cellular data connections, this is not a realistic assumption when developing solutions in the mobile environment. Thus, the optimization goals for our work are to reduce the computation and communication overhead required at the mobile device. Moreover, rather than providing a proof-of-concept work demonstrating that offloading computation is possible, this work seeks to develop and thoroughly demonstrate the practical potential for applying large garbled circuits to secure mobile applications.

The remainder of this work is organized as follows: Section 2 presents important related work and discusses how this paper differs from Salus; Section 3 provides cryptographic assumptions and definitions; Section 4 formally describes our protocols; Section 5 provides informal security discussion; Section 6 provides full proofs of security; Section 7 shows the results of our extensive performance analysis; Section 8 presents our privacy preserving navigation application for mobile phones; and Section 9 provides concluding remarks.

2. Related work

Three general categories of techniques have been developed to perform two-party SFE. The first, using homomorphic encryption, has yielded several special-purpose protocols using partially homomorphic encryption [4,5,7,15,56]. Other more generalizable protocols combine partially homomorphic encryption with garbled circuit constructions [20]. However, these schemes are manually optimized for specific functions. While protocols using fully homomorphic encryption (FHE) promise more generalizable results [16], these cryptosystems are currently too inefficient to be used practically, even on server-class machines. A second technique for secure function evaluation uses only the Oblivious Transfer (OT) primitive to compute certain functions [11,51,54,59]. While recent advances have made OT-based schemes more practical, their performance is only optimal for evaluating specific functions. Because of this, we focus this work on the most studied and widely applied technique, the Yao garbled circuit [63]. With the Fairplay implementation [46], garbled circuits were shown to have significant promise in terms of efficiency.

Beginning with Fairplay [46], several secure two-party computation implementations and applications have been developed using various circuit representations in the semi-honest adversarial model [24,27,29,38,41,45,55]. However, a malicious party using corrupted inputs or circuits can learn more information about the other party’s inputs in these constructions [33]. To resolve these issues, new protocols have been developed to achieve security in the malicious model, using cut-and-choose constructions [40,43,46,48,60,62], input commitments [60], and other various techniques [25,32,48]. To improve the performance of these schemes in both the malicious and semi-honest adversarial models, a number of optimization techniques have also been developed to reduce the cost of generating and evaluating circuits [12,18,26,35,40,50]. Kreuter et al. [36,37] combined several of these techniques into a general garbled circuit protocol that is secure in the malicious model and can efficiently evaluate circuits on the order of billions of gates using parallelized server-class machines. This SFE protocol is among the most efficient implementations to date that are fully secure in the malicious model.

Garbled circuit protocols rely on oblivious transfer schemes to exchange certain private values. While several OT schemes of various efficiencies have been developed [2,43,52,57], Ishai et al. demonstrated that any of these schemes can be extended to reduce $k^{c}$ oblivious transfers to k oblivious transfers for any given constant c [28]. Using this extension, exchanging potentially large inputs to garbled circuits became much less costly in terms of cryptographic operations and network overhead. Several more recent improvements to the Ishai et al. extension have further reduced the cost by as much as 2–3 times [1,34]. Even with this drastic improvement in efficiency, oblivious transfers still tend to be a costly step in evaluating garbled circuits.

Currently, the performance of garbled circuit protocols executed directly on mobile devices has been shown to be feasible only for small circuits in the semi-honest adversarial model [7,22]. While outsourcing general computation to the cloud has been widely considered for improving the efficiency of applications running on mobile devices, the concept has yet to be applied in practice to cryptographic constructions. Beginning in the 1980s with the outsourced RSA signature scheme by Matsumoto et al. [47], several theoretical schemes have been developed in the area of server-aided cryptography. However, most of these protocols were either broken or never implemented for practical purposes. Green et al. explored this idea further by outsourcing the costly decryption of ABE ciphertexts to server-class machines while still maintaining data privacy [19]. Naor et al. [53] develop an oblivious transfer technique that sends the chooser’s private selections to a third party, termed a Proxy Oblivious Transfer. While this idea is applied to a limited application in their work, it could be leveraged more generally into existing garbled circuit protocols. In the field of SFE, López-Alt et al. developed a theoretical construction for outsourcing multiparty computation using FHE [44]. When considering more practical SFE techniques, the costs of exchanging inputs and evaluating garbled circuits securely would make an outsourcing technique extremely useful in allowing limited capability devices to execute SFE protocols. Our work extends the Proxy Oblivious Transfer by combining it with the OT extension of Ishai et al. [28] allowing us to construct a garbled circuit evaluation protocol that securely outsources computation to the cloud.

In work performed concurrently and independently from our technique, Kamara et al. recently developed two protocols for outsourcing secure multiparty computation to the cloud in their Salus system [30,31]. While their work achieves similar functionality to ours, we distinguish our work in the following ways: first, their protocol is constructed with the assumption that they are outsourcing work from devices with low-computation but high-bandwidth capabilities. With cellular providers imposing bandwidth caps on customers and cellular data networks providing highly limited data transmission speed, we construct our protocol without this assumption using completely different cryptographic constructions. Second, their work focuses on demonstrating outsourced SFE as a proof-of-concept. Our work offers a rigorous performance analysis on mobile devices, and outlines a practical application that allows a mobile device to participate in the evaluation of garbled circuits that are orders of magnitude larger than those evaluated in the Salus system. Finally, their protocol that is secure in the malicious model requires that all parties share a secret key, which must be generated in a secure fashion before the protocol can be executed. Our protocol does not require any shared information prior to running the protocol, reducing the overhead of performing a multiparty fair coin tossing protocol a priori. While our work currently considers only the two-party model, by not requiring a preliminary multiparty fair coin toss, expanding our protocol to more parties will not incur the same expense as scaling such a protocol to a large number of participants. To properly compare security guarantees, we apply their security definitions in our analysis.

3. Assumptions and definitions

To construct a secure scheme for outsourcing garbled circuit evaluation, some new assumptions must be considered in addition to the standard security measures taken in a two-party secure computation. In this section, we discuss the intuition and practicality of assuming a non-colluding cloud, and we outline our extensions on standard techniques for preventing malicious behavior when evaluating garbled circuits. Finally, we conclude the section with formal definitions of security.

3.1. Non-collusion with the cloud

Throughout our protocol, we assume that none of the parties involved will ever collude with the cloud. This requirement is based in theoretical bounds on the efficiency of garbled circuit evaluation and represents a realistic adversarial model. The fact that theoretical limitations exist when considering collusion in secure multiparty computation has been known and studied for many years [3,10,39], and other schemes considering secure computation with multiple parties require similar restrictions on who and how many parties may collude while preserving security [6,13,14,30,31]. Kamara et al. [31] observe that if an outsourcing protocol is secure when both the party generating the circuit and the cloud evaluating the circuit are malicious and colluding, this implies a secure two-party scheme where one party has sub-linear work with respect to the size of the circuit, which is currently only possible with fully homomorphic encryption. However, making the assumption that the cloud will not collude with the participating parties makes outsourcing securely a possibility in practice. In reality, many cloud providers such as Amazon or Microsoft would not allow outside parties to control or affect computation within their cloud system for reasons of trust and to preserve a professional reputation. In spite of this assumption, we cannot assume the cloud will always be semi-honest. For example, our protocol requires a number of consistency checks to be performed by the cloud that ensure the participants are not behaving maliciously. Without mechanisms to force the cloud to make these checks, a “lazy” cloud provider could save resources by simply returning that all checks verified without actually performing them. Thus, our adversarial model encompasses a non-colluding but potentially malicious cloud provider that is hosting the outsourced computation.

Kamara et al. [30] define this property formally as a non-cooperative adversary.

Definition 1.
An adversary $A_{i}$ is non-cooperative with respect to adversary $A_{j}$ if the messages $A_{i}$ sends to $A_{j}$ reveal no information about $A_{i}$ ’s private values to $A_{j}$ beyond what can be inferred from $A_{j}$ ’s output $f_{j} (x)$ .
This property ensures that the view of two adversaries is not shared in any way, even if both parties are corrupted. As demonstrated by Kamara et al. [30], this allows us to prove security using a set of partial outputs for each non-cooperative adversary (we define partial outputs later in this section). In practice, this allows us to guarantee security when all of the parties in the protocol are at least semi-honest (that is, they are not honest and may collude with one another unless defined as non-cooperative).
3.2. Attacks in the malicious setting

When running garbled circuit based secure multiparty computation in the malicious model, a number of well-documented attacks exist. We address here how our system counters each.

Malicious circuit generation: In the original Yao garbled circuit construction, a malicious generator can garble a circuit to evaluate a function $f^{'}$ that is not the function f agreed upon by both parties and could compromise the security of the evaluator’s input. To counter this, we employ an extension of the cut-and-choose technique using random seeds developed by Goyal et al. [18] and implemented by Kreuter et al. [37]. Essentially, the technique uses a cut-and-choose, where the generator commits to a set of circuits that all presumably compute the same function. The parties then use a fair coin toss to select some of the circuits to be evaluated and some that will be re-generated and hashed by the cloud given the random seeds used to generate them initially. The evaluating party then inspects the circuit commitments and compares them to the hash of the regenerated circuits to verify that all the check circuits were generated properly. Recent developments have produced significantly improved techniques for cut-and-choose in garbled circuit protocols [26,40]. Because the technique developed by Lindell [40] maintains separate roles of circuit generator and evaluator, we believe that it is possible to incorporate this optimization into our outsourcing protocol, and leave this improvement to future work.

Selective failure attack: If, when the generator is sending the evaluator’s garbled inputs during the oblivious transfer, he lets the evaluator choose between a valid garbled input bit and a corrupted garbled input, the evaluator’s ability to complete the circuit evaluation will reveal to the generator which input bit was used. To prevent this attack, we use the input encoding technique from Lindell and Pinkas [42], which lets the evaluator encode her input in such a way that a selective failure of the circuit reveals nothing about the actual input value. To prevent the generator from swapping garbled wire values, we use a commitment technique employed by Kreuter et al. [37].

Input consistency: Since multiple circuits are evaluated to ensure that a majority of circuits are correct, it is possible for either party to input different inputs to different evaluation circuits, which could reveal information about the other party’s inputs. To keep the evaluator’s inputs consistent, we again use the technique from Lindell and Pinkas [42], which sends all garbled inputs for every evaluation circuit in one oblivious transfer execution. To keep the generator’s inputs consistent, we use the malleable claw-free collection construction of shelat and Shen [60]. This technique is described in further detail in Section 3.3.

Output consistency: When evaluating a two-output function, we ensure that outputs of both parties are kept private from the cloud using an extension of the technique developed by Kiraz and Schoenmakers [33]. The outputs of both parties are XORed with random strings within the garbled circuit, and the cloud uses a witness-indistinguishable zero-knowledge proof as in the implementation by Kreuter et al. [37]. This allows the cloud to choose a majority output value without learning either party’s output or undetectably tampering with the output. At the same time, the witness-indistinguishable proofs prevent Alice and Bob from learning the index of the majority circuit. This prevents Bob from learning anything by knowing which circuit evaluated to the majority output value.

3.3. Malleable claw-free collections

To prevent the generating party from providing different inputs for each evaluation circuit, we implement the malleable claw-free collections technique developed by shelat and Shen [60]. Their construction essentially allows the generating party to prove that all of the garbled input values were generated by exactly one function in a function pair, while the ability to find an element that is generated by both functions implies that the generator can find a claw.

Goldreich and Kahan define a claw-free collection as a three-tuple of algorithms [17]. The index sampling algorithm, G, takes a security parameter $1^{n}$ as input, and specifies an index I. This index specifies a pair of domains $D_{I}^{0}$ , $D_{I}^{1}$ and a pair of functions $f_{I}^{0}$ , $f_{I}^{1}$ . The domain sampling algorithm D is given an index I and a bit σ as input and outputs a random element from the domain $D_{I}^{σ}$ . Finally, given input $I, σ, x \in D_{I}^{σ}$ , the evaluation function F outputs the value of the function $f_{I}^{σ}$ for input x. Given these definitions, they define the conditions of a claw free collection as follows.

Definition 2 (Claw-free collections [17,60]).

A three-tuple of algorithms $(G, D, F)$ is a claw-free collection if the following conditions hold.

Easy to evaluate: Both the index selecting algorithm G and the domain sampling algorithm D are probabilistic polynomial-time, while the evaluating algorithm F is deterministic polynomial-time.

Identical range distribution: Let $f_{I}^{b} (x)$ be the output of F given input $(b, I, x)$ . For any $I \in range (G)$ , the random variables are identically distributed.

Hard to form claws: For every non-uniform probabilistic polynomial-time algorithm A, every polynomial $p (\cdot)$ , and every sufficiently large n, it is true that $Pr [I \leftarrow G (1^{n}); (x, y) \leftarrow A (I) : f_{I}^{0} (x) = f_{I}^{1} (y)] < \frac{1}{p (n)}$ .

Given this definition, shelat and Shen build their scheme on a modified construction which adds in a malleability property, and focuses on a special case where $D_{I}^{0} = D_{I}^{1}$ and this domain forms a group. This allows the consistency of the inputs to be checked with a witness-indistinguishable proof.

Definition 3 (Malleable claw-free collection [60]).

A four-tuple of algorithms $(G, D, F, R)$ is a malleable claw-free collection if the following conditions hold:

A subset of claw-fee collections: $(G, D, F)$ is a claw-free collection, and the range of D and F form groups, denoted by $(G_{1}, ⋆)$ and $(G_{2}, ◇)$ respectively.

Uniform domain sampling: For any I in the range of G, random variable $D (0, I)$ and $D (1, I)$ are uniform over $G_{1}$ , and denoted by $D (I)$ for simplicity.

Malleability: $R : G_{1} \to G_{2}$ runs in polynomial time, and for $b \in {0, 1}$ , any I in the range of G, and any $m_{1}, m_{2} \in G_{1}$ , $f_{I}^{b} (m_{1} ⋆ m_{2}) = f_{I}^{b} (m_{1}) ◇ R_{I} (m_{2})$ .

Our implementation of a malleable claw-free collection uses the same construction as Kreuter et al. [37], built on the discrete logarithm assumption.

3.4. Model and definitions

The work of Kamara et al. [31] presents a definition of security based on the ideal-model/real-model security definitions common in secure multiparty computation. Because their definition formalizes the idea of a non-colluding cloud, we apply their definitions to our protocol for the two-party case in particular. We summarize their definitions below.

Real-model execution. The protocol takes place between two parties $(P_{1}, P_{2})$ executing the protocol and a server $P_{3}$ , where each of the executing parties $(P_{1}, P_{2})$ are provided input $x_{i}$ , auxiliary input $z_{i}$ , and random coins $r_{i}$ for $i = 1, 2$ . The server $P_{3}$ is provided only auxiliary input $z_{3}$ and random coins $r_{3}$ . In the execution, there exists some subset of independent parties $(A_{1}, \dots, A_{m})$ , $m ⩽ 3$ that are malicious adversaries (we preserve this definition from Kamara et al. [31] but prove security when $m = 1$ . This provides equivalent security to the Salus framework with two participants and the Cloud). Each adversary corrupts one executing party and does not share information with other adversaries. For all honest parties, let ${OUT}_{i}$ be its output, and for corrupted parties let ${OUT}_{i}$ be its view of the protocol execution. The ith partial output of a real execution is defined as: $\begin{array}{l} {REAL}^{(i)} (k, x; r) = {{OUT}_{j} : j \in H} \cup {OUT}_{i}, \end{array}$ where H is the set of honest parties, k is a computational security parameter, x is the set of all player inputs $x_{i}$ and $z_{i}$ for $i = 1, 2, 3$ , and r is all random coins of all players.

Ideal-model execution. In the ideal model, the setup of participants is the same except that all parties are interacting with a trusted party that evaluates the function. All parties are provided inputs $x_{i}$ , auxiliary input $z_{i}$ , and random coins $r_{i}$ . If a party is semi-honest, it provides its actual inputs to the trusted party, while if the party is malicious and non-colluding, it provides arbitrary input values. In the case of the server $P_{3}$ , this means simply providing its auxiliary input and random coins, as no input is provided to the function being evaluated. Once the function is evaluated by the trusted third party, it returns the result to the parties $P_{1}$ and $P_{2}$ , while the server $P_{3}$ does not receive the output. If a party aborts early or sends no input, the trusted party immediately aborts. For all honest parties, let ${OUT}_{i}$ be the output given to $P_{i}$ by the trusted party, and for corrupted parties let ${OUT}_{i}$ be some value output by $P_{i}$ . The ith partial output of an ideal execution in the presence of some set of independent simulators is defined as: $\begin{array}{l} {IDEAL}^{(i)} (k, x; r) = {{OUT}_{j} : j \in H} \cup {OUT}_{i}, \end{array}$ where H is the set of honest parties, k is a computational security parameter, x is the set of all player inputs $x_{i}$ and $z_{i}$ for $i = 1, 2, 3$ , and r is all random coins of all players. In this model, the formal definition of security is as follows:

Definition 4.
A protocol securely computes a function f if there exists a set of probabilistic polynomial-time (PPT) simulators ${{Sim}_{i}}_{i = 1, 2, 3}$ such that for all PPT adversaries $(A_{1}, \dots, A_{3})$ , x, and for all $i = 1, 2, 3$ : $\begin{array}{l} {{REAL}^{(i)} (k, x; r)}_{k \in N} \overset{c}{\approx} {{IDEAL}^{(i)} (k, x; r)}_{k \in N}, \end{array}$ where r is random and uniform.

4. Protocol

4.1. Participants

Our protocols reference three different entities:

Evaluator:

The evaluating party, called Alice, is assumed to be a mobile device that is participating in a secure two-party computation.

Generator:

The party generating the garbled circuit, called Bob, is an application- or web-server that is the second party participating with Alice in the secure computation.

Proxy:

The proxy, called Cloud, is a third party that is performing heavy computation on behalf of Alice, but is not trusted to know her input or the function output.

Fig. 1.

The complete outsourced SFE protocol.

4.2. Protocol phase summary

Our protocol can be divided into five phases, illustrated in Fig. 1. Given a circuit generator Bob, and an evaluating mobile device Alice, the protocol can be summarized as follows:

Phase 1: Bob generates a number of garbled circuits, some of which will be checked, others will be evaluated. After Bob commits to the circuits, Alice and Bob use a fair coin toss protocol to select which circuits will be checked or evaluated. For the check circuits, Bob sends the random seeds used to generate the circuits to the Cloud and the hashes of each circuit to Alice. These are checked to ensure that Bob has not constructed a circuit that is corrupted or deviates from the agreed-upon function.

Phase 2: Alice sends her inputs to Bob via an outsourced oblivious transfer. Bob then sends the corresponding garbled inputs to the Cloud. This allows the Cloud to receive Alice’s garbled inputs without Bob or the Cloud ever learning her true inputs.

Phase 3: Bob sends his garbled inputs to the Cloud, which verifies that they are consistent for each evaluation circuit. This prevents Bob from providing different inputs to different evaluation circuits.

Phase 4: The Cloud evaluates the circuit given Alice and Bob’s garbled inputs. Since the Cloud only sees garbled values during the evaluation of the circuit, it never learns anything about either party’s input or output. Since both output values are blinded with one-time pads, they remain private even when the Cloud takes a majority vote.

Phase 5: The Cloud sends the encrypted output values to Alice and Bob, who are guaranteed its authenticity through the use of commitments and zero-knowledge proofs.

4.3. Outsourced protocol

Common inputs: a function $f (x, y)$ that is to be securely computed; a malleable claw-free collection $(G_{CLW}, D_{CLW}, F_{CLW}, R_{CLW})$ ; a one-way, collision-resistant hash function $H : {0, 1}^{*} \to {0, 1}^{k}$ ; a primitive 1-out-of-2 oblivious transfer protocol; two commitment schemes: a perfectly binding commitment scheme ${com}_{B} (key, message)$ and the output commitment scheme ${com}_{O} (key, message)$ by Kiraz and Schoenmakers [33]; and the following security parameters: a statistical security parameter for the number of circuits built λ, a computational security parameter k, and the number of encoding bits ℓ for each of Alice’s input wires.

Private inputs: The generating party Bob provides his input to the function b and a random string of bits $b_{r}$ that is the length of the output string. The evaluating party Alice provides her input to the function a and a random string of bits $a_{r}$ that is the length of the output string. Assume without loss of generality that all input and output strings are of length n.

Output: The protocol outputs separate private values $fa$ for Alice and $fb$ for Bob.

Phase 1 (Circuit generation and checking).

Circuit preparation: Before beginning the protocol, both parties agree upon a circuit representation of the function $f (a, b)$ , where the outputs of the function may be defined separately for Alice and Bob as $f_{A} (a, b)$ and $f_{B} (a, b)$ . The circuit must also meet the following requirements:

Additional XOR gates must be added such that Bob’s output is set to $fb = f_{B} (a, b) \oplus b_{r}$ and Alice’s output is set to $fa = f_{A} (a, b) \oplus a_{r}$ .

For each of Alice’s input bits, the input wire $w_{i}$ is split into ℓ different input wires $w_{j, i}$ such that $w_{i} = w_{1, i} \oplus w_{2, i} \oplus \dots \oplus w_{ℓ, i}$ following the input encoding scheme by Lindell and Pinkas [42]. This prevents Bob from correlating a selective failure attack with any of Alice’s input bit values.

Circuit garbling: Bob first selects and malleable claw-free collection as index $I = G (1^{k})$ and sends I to Alice. Bob then takes the circuit C and creates λ independent garbled versions of C, called ${GC}_{1}, \dots, {GC}_{λ}$ , using random coins ${rc}_{1}, \dots, {rc}_{λ}$ and the garbling technique implemented by Kreuter et al. [37]. For Bob’s jth input wire on the ith circuit, Bob associates the value $H (β_{b, j, i})$ with the input value b, where $β_{b, j, i} = F_{CLW} (b, I, α_{b, j, i})$ . For Alice’s jth input wire, Bob associates the value $H (δ_{b, j, i})$ with the input value b, where $δ_{b, j, i} = F_{CLW} (b, I, γ_{b, j, i})$ . All the values $α_{b, j, i}$ and $γ_{b, j, i}$ for $b = {0, 1}$ , $j = 1, \dots, n$ , $i = 1, \dots, λ$ are selected randomly from the domain of the claw-free pair using D.

Circuit commitment: Bob generates commitments for all circuits by hashing $H ({GC}_{i}) = {HC}_{i}$ for $i = 1, \dots, λ$ . Bob sends these hashes to Alice. In addition, for every output wire $w_{b, j, i}$ for $b = {0, 1}$ , $j = 1, \dots, n$ and $i = 1, \dots, λ$ , Bob generates commitments ${CO}_{j, i} = {com}_{B} (c k_{j, i}, (H (w_{0, j, i}), H (w_{1, j, i})))$ using commitment keys $c k_{j, i}$ for $j = 1, \dots, n$ and $i = 1, \dots, λ$ and sends them to both Alice and the Cloud.

Input label commitment: Bob commits to Alice’s garbled input wires as follows: for each generated circuit $i = 1, \dots, λ$ and each of Alice’s input wires $j = 1, \dots, ℓ \cdot n$ , Bob creates a pair of commitment keys ${ak}_{0, j, i}$ , ${ak}_{1, j, i}$ and commits to the input wire label seeds $δ_{0, j, i}$ and $δ_{1, j, i}$ as ${CA}_{b, j, i} = {com}_{B} ({ak}_{b, j, i}, δ_{b, j, i})$ . For each of Alice’s input wires $j = 1, \dots, ℓ \cdot n$ , Bob randomly permutes the commitments within the pair ${CA}_{0, j, i}$ , ${CA}_{1, j, i}$ across every $i = 1, \dots, λ$ . This prevents the Cloud from correlating the location of the commitment with Alice’s input value during the OOT phase.

In the same fashion, Bob commits to his own input wires: for each circuit $i = 1, \dots, λ$ and each of his input wires $j = 1, \dots, n$ , Bob creates commitment keys ${bk}_{0, j, i}$ , ${bk}_{1, j, i}$ and commits to the input wire label seeds $β_{0, j, i}$ and $β_{1, j, i}$ as ${CB}_{b, j, i} = {com}_{B} ({bk}_{b, j, i}, β_{b, j, i})$ , permuting each pair ${CB}_{0, j, i}$ , ${CB}_{1, j, i}$ as above.

Cut and choose: Alice and Bob then run a fair coin toss protocol to agree on a set of circuits that will be evaluated, while the remaining circuits will be checked. The coin toss generates a set of indices $Chk \subset {1, \dots, λ}$ such that $| Chk | = \frac{3}{5} λ$ , as in shelat and Shen’s cut-and-choose protocol [60]. The remaining indices are placed in the set $Evl$ for evaluation, where $| Evl | = e = \frac{2}{5} λ$ . For every $i \in Chk$ , Bob sends ${rc}_{i}$ and the values $[α_{b, 1, i}, \dots, α_{b, n, i}]$ and $[γ_{b, 1, i}, \dots, γ_{b, ℓ \cdot n, i}]$ for $b = {0, 1}$ to the Cloud. Bob also sends all commitment keys $c k_{j, i}$ for $j = 1, \dots, n$ and $i \in Chk$ to the Cloud. Finally, Bob sends the commitment keys ${ak}_{b, j, i}$ and ${bk}_{b, j, i}$ for $b = {0, 1}$ , $i \in Chk$ , and $j = 1, \dots, ℓ \cdot n$ to the Cloud. The Cloud then garbles C using ${rc}_{i}$ for $i \in Chk$ , producing the set of garbled circuits ${GC}_{i}^{'}$ for $i \in Chk$ . For each $i \in Chk$ , the Cloud then hashes each check circuit $H ({GC}_{i}^{'}) = {HC}_{i}^{'}$ and checks that:

each commitment ${CO}_{j, i}$ for $j = 1, \dots, n$ is well formed,

the value $H (β_{b, j, i})$ is associated with the input value b for Bob’s jth input wire,

the value $H (δ_{b, j, i})$ is associated with the input value b for Alice’s jth input wire,

for every bit value b and input wire j, the values committed in ${CA}_{b, j, i}$ and ${CB}_{b, j, i}$ are correct.

If any of these checks fail, the Cloud immediately aborts. Otherwise, it sends the hash values

{HC}_{i}^{'}

for

i \in Chk

to Alice. For every

i \in Chk

, Alice checks if

{HC}_{i} = {HC}_{i}^{'}

to ensure that the circuits were generated correctly. If any of the hash comparisons fail, Alice aborts.

Fig. 2.

The outsourced oblivious transfer protocol.

Phase 2 (Outsourced Oblivious Transfer (OOT)).

Input encoding: For every bit $j = 1, \dots, n$ in her input a, Alice sets encoded input ${ea}_{j}$ as a random string of length ℓ such that ${ea}_{1, j} \oplus {ea}_{2, j} \oplus \dots \oplus {ea}_{ℓ, j} = a_{j}$ for each bit in a. This new encoded input string $ea$ is of length $ℓ \cdot n$ .

OT setup: Alice initializes an $ℓ \cdot n \times k$ matrix T with uniformly random bit values, while Bob initializes a random bit vector s of length k. See Fig. 2 for a more concise view.

Primitive OT operations: With Alice as the sender and Bob as the chooser, the parties initiate k 1-out-of-2 oblivious transfers. Alice’s input to the ith instance of the OT is the pair $(T^{i}, T^{i} \oplus ea)$ where $T^{i}$ is the ith column of T, while Bob’s input is the ith selection bit from the vector s. Bob organizes the k selected columns as a new matrix Q.

Permuting the selections: Alice generates a random bit string p of length $ℓ \cdot n$ , which she sends to Bob.

Encrypting the commitment keys: Bob generates a matrix of keys that will open the committed garbled input values and proofs of consistency as follows: for Alice’s jth input bit, Bob creates a pair $(x_{0, j}, x_{1, j})$ , where $x_{b, j} = [{ak}_{b, j, {Evl}_{1}}, {ak}_{b, j, {Evl}_{2}}, \dots, {ak}_{b, j, {Evl}_{e}}] ‖ [γ_{b_{j}, j, {Evl}_{2}} ⋆ {(γ_{b_{j}, j, {Evl}_{1}})}^{- 1}, γ_{b_{j}, j, {Evl}_{3}} ⋆ {(γ_{b_{j}, j, {Evl}_{1}})}^{- 1}, \dots, γ_{b_{j}, j, {Evl}_{e}} ⋆ {(γ_{b_{j}, j, {Evl}_{1}})}^{- 1}]$ and ${Evl}_{i}$ denotes the ith index in the set of evaluation circuits. For $j = 1, \dots, ℓ \cdot n$ , Bob prepares $(y_{0, j}, y_{1, j})$ where $y_{b, j} = x_{b, j} \oplus H (j, Q_{j} \oplus (b \cdot s))$ . Here, $Q_{j}$ denotes the jth row in the Q matrix and $(b \cdot s)$ denotes component-wise multiplication by the bit b. Bob permutes the entries using Alice’s permutation vector as $(y_{0 \oplus p_{j}, j}, y_{1 \oplus p_{j}, j})$ . Bob sends this permuted set of ciphertexts Y to the Cloud.

Receiving Alice’s garbled inputs: Alice blinds her input as $h = ea \oplus p$ and sends h and T to the Cloud. The Cloud recovers the commitment keys and consistency proofs $x_{b, j} = y_{h_{j}, j} \oplus H (j, T_{j})$ for $j = 1, \dots, ℓ \cdot n$ . Here, $h_{j}$ denotes the jth bit of the string h and $T_{j}$ denotes the jth row in the T matrix. Since for every $j \in Evl$ , the Cloud only has the commitment key for the b garbled value (not the $b \oplus 1$ garbled value), the Cloud can correctly decommit only the garbled labels corresponding to Alice’s input bits.

Verifying consistency across Alice’s inputs: Given the decommitted values $[δ_{b, 1, i}, \dots, δ_{b, ℓ \cdot n, i}]$ and the modified pre images $[γ_{b_{j}, j, {Evl}_{2}} ⋆ {(γ_{b_{j}, j, {Evl}_{1}})}^{- 1}, γ_{b_{j}, j, {Evl}_{3}} ⋆ {(γ_{b_{j}, j, {Evl}_{1}})}^{- 1}, \dots, γ_{b_{j}, j, {Evl}_{e}} ⋆ {(γ_{b_{j}, j, {Evl}_{1}})}^{- 1}]$ , the Cloud checks that: $\begin{array}{l} δ_{b_{j}, j, i} = δ_{b_{j}, j, {Evl}_{1}} ◇ R_{CLW} (I, γ_{b_{j}, j, i} ⋆ {(γ_{b_{j}, j, {Evl}_{1}})}^{- 1}) \end{array}$ for $i = 2, \dots, e$ . If any of these checks fails, the Cloud aborts the protocol. Otherwise, the Cloud now has garbled versions of Alice’s inputs ${ga}_{i}$ for $i \in Evl$ .

Phase 3 (Generator input consistency check).

Delivering inputs: Bob decommits the hash seeds for each of his garbled input values by sending ${bk}_{b_{i}, j, i}$ to the Cloud for $j = 1, \dots, n$ and $i \in Evl$ . The Cloud recovers the hash seeds $[β_{b_{1}, 1, i}, β_{b_{2}, 2, i}, \dots, β_{b_{n}, n, i}]$ for every evaluation circuit $i \in Evl$ and forwards a copy of these values to Alice. Bob then proves the consistency of his inputs by sending the modified preimages $[α_{b_{j}, j, {Evl}_{2}} ⋆ {(α_{b_{j}, j, {Evl}_{1}})}^{- 1}, α_{b_{j}, j, {Evl}_{3}} ⋆ {(α_{b_{j}, j, {Evl}_{1}})}^{- 1}, \dots, α_{b_{j}, j, {Evl}_{e}} ⋆ {(α_{b_{j}, j, {Evl}_{1}})}^{- 1}]$ such that $F_{CLW} (b_{i}, I, α_{b_{i}, j, i}) = β_{b_{i}, j, i}$ for $j = 1, \dots, n$ and $i \in Evl$ such that ${GC}_{i}$ was generated with the claw-free function pair indexed at I.

Check consistency: Alice then checks that all the hash seeds were generated by the same function by checking if: $\begin{array}{l} β_{b_{j}, j, i} = β_{b_{j}, j, {Evl}_{1}} ◇ R_{CLW} (I, α_{b_{j}, j, i} ⋆ {(α_{b_{j}, j, {Evl}_{1}})}^{- 1}) \end{array}$ for $i = 2, \dots, e$ . If any of these checks fails, Alice aborts the protocol. Otherwise, the Cloud now has garbled versions of Bob’s inputs ${gb}_{i}$ for $i \in Evl$ .

Phase 4 (Circuit evaluation).

Evaluating the circuit: For each evaluation circuit, the Cloud evaluates ${GC}_{i} ({ga}_{i}, {gb}_{i})$ for $i \in Evl$ in the pipelined manner described by Kreuter et al. [37]. Each circuit produces two garbled output strings, $({gfa}_{i}, {gfb}_{i})$ .

Checking the evaluation circuits: Once these output have been computed, the Cloud hashes each evaluation circuit as $H ({GC}_{i}) = {HC}_{i}^{'}$ for $i \in Evl$ and sends these hash values to Alice (this hash is performed in parallel with the previous step). Alice checks that for every i, ${HC}_{i} = {HC}_{i}^{'}$ . If any of these checks do not pass, Alice aborts the protocol.

Phase 5 (Output check and delivery).

Committing the outputs: The Cloud then generates random commitment keys ${ka}_{i}$ , ${kb}_{i}$ and commits the output values to their respective parties according to the commitment scheme defined by Kiraz and Schoenmakers [33], generating ${CA}_{j, i} = {com}_{O} ({ka}_{j, i}, {gfa}_{j, i})$ and ${CB}_{j, i} = {com}_{O} ({kb}_{j, i}, {gfb}_{j, i})$ for $j = 1, \dots, n$ and $i = 1, \dots, e$ . The Cloud then sends all $CA$ to Alice and $CB$ to Bob.

Selection of majority output: Bob opens the commitments ${CO}_{j, i}$ for $j = 1, \dots, n$ and $i = 1, \dots, e$ for both Alice and the Cloud. These commitments contain the mappings from the hash of each garbled output wire $H (w_{b, j, i})$ to real output values $b_{j, i}$ for $j = 1, \dots, n$ and $i = 1, \dots, e$ (note that the result of computation is still blinded from the Cloud by $a_{r}$ and $b_{r}$ ). The Cloud selects a circuit index $maj$ such that the output of that circuit matches the majority of outputs for both Alice and Bob. That is, ${fa}_{maj} = {fa}_{i}$ and ${fb}_{maj} = {fb}_{i}$ for i in a set of indices $IND$ that is of size $| IND | > \frac{e}{2}$ .

Proof of output consistency: Using the OR-proofs as described by Kiraz and Schoenmakers [33], the Cloud proves to Bob that $CB$ contains valid garbled output bit values based on the de-committed output values from the previous step. The Cloud then performs the same proof to Alice for her committed values $CA$ . Note that these proofs guarantee the output was generated by one of the circuits, but the value $maj$ remains hidden from both Alice and Bob, which prevents Bob from learning anything based on knowledge of how circuit $maj$ was constructed.

Output release: The Cloud then decommits ${gfa}_{maj}$ to Alice and ${gfb}_{maj}$ to Bob. Given these garbled outputs and the bit values corresponding to the hash of each output wire, Alice recovers her output string $fa$ , and Bob recovers his output string $fb$ .

Output decryption: Alice recovers her output $f_{A} (a, b) = fa \oplus a_{r}$ , while Bob recovers $f_{B} (a, b) = fb \oplus b_{r}$ .

4.4. Asymptotic evaluation

When considering the performance of our outsourcing scheme, our goal is to optimize the workload on the mobile device. Because this device will always be more limited in computing capability than the Cloud, we need to minimize the overhead at this bottleneck. The dominating operations on the mobile device can be summarized in three categories: the OOT protocol, which requires k oblivious transfers and $O (| a |)$ symmetric operations to generate the matrix T; the input consistency check, which requires $O (λ | b |)$ group operations; and the output verification proof, which requires $O (λ | f_{A} (a, b) |)$ additive homomorphic operations (i.e., Diffie–Hellman group operations) in the OR-proof and $| f_{A} (a, b) |$ XOR operations to decrypt the output (this single operation is dominated by the $O (λ | f_{A} (a, b) |)$ operations in the OR-proof and is omitted from our total). These operations produce an overall complexity of $O (λ (| b | + | f_{A} (a, b) |) + | a | + k)$ . When compared to the outsourcing technique developed by Kamara et al. [30,31], which incurs an overhead of $O (λ (| a | + | b | + | f (a, b) |))$ on the mobile device, our protocol has comparable asymptotic performance overall, and better asymptotic performance when the mobile input a is large. However, because Salus is implemented exclusively with symmetric cryptographic operations and our protocol requires several group operations, our improved asymptotic performance would not produce real time performance improvements unless the size of a is very large. These values are summarized in Table 1.

Table 1
Asymptotic analysis of the operations required on the mobile device for each outsourcing protocol

Protocol SYM GROUP OT

CMTB $O (| a |)$ $O (λ (| b | + | f_{A} (a, b) |))$ k

Salus $O (λ (| a | + | b | + | f_{A} (a, b) |))$ – –

Protocol	SYM	GROUP	OT
CMTB	$O (\| a \|)$	$O (λ (\| b \| + \| f_{A} (a, b) \|))$	k
Salus	$O (λ (\| a \| + \| b \| + \| f_{A} (a, b) \|))$	–	–

Notes: Here, SYM is symmetric cryptographic operations, GROUP is group algebraic operations, and OT is oblivious transfers. Recall that k is the security parameter, λ is the number of circuits generated, a is the mobile device’s input, and b is the application server’s input.

5. Security guarantees

In this section, we provide a summary of the security mechanisms used in our protocol and an informal discussion of the security guarantees of our outsourced oblivious transfer construction. While all of the basic consistency checks already exist in previous work, our protocol demonstrates how these checks can be modified to allow for secure computation in the outsourced model. In combination with our novel outsourced oblivious transfer protocol, this construction provides a significant step towards practical SFE on mobile devices that is secure against malicious adversaries.

Recall from Section 3 that there are generally four security concerns when evaluating garbled circuits in the malicious setting. To solve the problem of malicious circuit generation, we apply the random seed check variety of cut-and-choose developed by Goyal et al. [18]. To solve the problem of selective failure attacks, we employ the input encoding technique developed by Lindell and Pinkas [42]. To prevent an adversary from using inconsistent inputs across evaluation circuits, we employ the witness-indistinguishable proofs from shelat and Shen [60]. Finally, to ensure the majority output value is selected and not tampered with, we use the XOR-and-prove technique from Kiraz and Schoenmakers [33] as implemented by Kreuter et al. [37]. In combination with the standard semi-honest security guarantees of Yao garbled circuits, these security extensions secure our scheme in the malicious security model.

5.1. Garbled circuit generation

To ensure the evaluated circuits are generated honestly, we require two properties. First, we limit the generator Bob’s ability to trick Alice into evaluating a corrupted circuit using a cut-and-choose technique similar to a typical, two-party garbled circuit evaluation. Second, we ensure that a lazy Cloud attempting to conserve system resources cannot bypass the circuit checking step without being discovered. We call this the Cloud’s “proof-of-work”.

Claim 1 (Security).

Assuming that the hash function $H (\cdot)$ is a one-way, collision-resistant hash and that the commitment scheme used is fully binding, then the generator Bob has at best a $2^{- 0.32 λ}$ probability of tricking Alice into evaluating a majority of corrupted circuits, where λ is the number of circuits generated.

shelat and Shen [60] perform a rigorous analysis of the optimal cut-and-choose strategy for evaluating garbled circuits in the malicious setting. Given that the generator prepares λ circuits before the cut-and-choose, their protocol sets the number of check circuits to $\frac{3 λ}{5}$ rather than $\frac{λ}{2}$ , which is found in previous schemes. By their analysis, this provides a security level of $2^{- 0.32 λ}$ . Since our scheme is built on the implementation by Kreuter et al. [37], which uses the same cut-and-choose parameter as shelat and Shen, our garbled circuit check also provides a security parameter of $2^{- 0.32 λ}$ which is non-polynomial and negligible for large λ.

Claim 2 (Proof-of-work).

Assuming the hash function H is one-way and collision resistant, the Cloud has a negligible probability in the security parameter k of producing a check hash that passes the seed check without actually generating the check circuit.

As previously stated, before the circuit check begins the generator Bob sends the evaluator Alice λ hashed circuit values $H ({GC}_{i})$ . Once the evaluation circuits are selected, the Cloud must generate λ circuits and hash them into check hashes $H ({GC}_{i}^{'})$ . We assume that the Cloud does not collude with the generator (i.e. share any of the hash values sent to Alice). If the Cloud attempts to skip the generation of the check circuits, it must generate hash values $H_{i}^{'} = H_{i}$ for $i \in Chk$ . Based on security guarantees of the hash with output length k, the Cloud has a negligible probability of correctly generating these hash values.

5.2. Validity of evaluator inputs

To assure that the generator cannot learn anything about the evaluator’s inputs by corrupting the garbled values sent during the OT, we employ the random input encoding technique by Lindell and Pinkas [42], which is built into the implementation by Kreuter et al. [37]. This technique allows the evaluator to encode each input bit as the XOR of a set of input bits. Thus, if the generator corrupts one of those input bits as in a selective failure attack, it reveals essentially nothing about the evaluator’s true input. Additionally, we use the commitment technique employed by Kreuter et al. [37] to ensure that Bob cannot swap garbled input wire labels between the zero and one value. To accomplish this, the generator commits to the wire labels before the cut-and-choose. During the cut and choose, the input labels for the check circuits are opened to ensure that they correspond to only one value across all circuits. Then, during the OOT, the commitment keys for the labels that will be evaluated are sent instead of the wire labels themselves. Because our protocol implements this technique directly from the literature, we do not make any additional claims of security.

5.3. Input consistency

The security of our input consistency check is based on two schemes, one for the evaluator’s input and one for the generator’s input. To assure the evaluator’s inputs are consistent across circuits, we use the approach from Lindell and Pinkas [42], which is built into the implementation of Kreuter et al. [37]. Since the evaluator only performs one oblivious transfer for all the evaluation circuits, her received garbled inputs will all represent her input to the OT.

To assure that the generator’s inputs are consistent, we employ the malleable claw-free collection approach from shelat and Shen [60]. However, we modify the zero-knowledge proof to provide some guarantee that the Cloud server actually possesses well-formed inputs:

Claim 3.
Assuming the witness-indistinguishable proof used in the malleable claw-free collection input check catches inconsistent inputs except for a negligible probability, the generator in our protocol cannot trick the evaluator into using different inputs for different evaluation circuits with greater than negligible probability.

During the witness-indistinguishable proof, the generator sends the modified pre-image values to the mobile device, while the Cloud server sends the garbled input values of each evaluation circuit to the mobile device. The device then checks that all input values for each individual input wire were generated by the same function in the malleable claw-free pair. Based on the assumption that the generator and the Cloud will not collude, the probability of a malicious generator providing inconsistent modified pre-image values that match the garbled inputs possessed by the Cloud server is negligible in the security parameter of the malleable claw-free pair.
5.4. Output consistency

To ensure that the Cloud cannot learn either party’s output or tamper with either party’s output from the garbled circuit, we implement the technique of blinding and proving the garbled output values from the protocol by Kiraz and Schoenmakers [33]. The privacy and correctness of the generator’s output is guaranteed based on the security of this construction in Kiraz’s two-party secure function evaluation protocol. By the same proof for the generator’s output remaining secure, we argue that the evaluator’s output is also secure and correct. By using the same construction for both parties’ outputs, we guarantee output privacy and consistency, even in the presence of a malicious Cloud. Note that to maintain security, this construction only provides Bob and Alice with the output of computation, not the index of the majority evaluation circuit.

5.5. Outsourced oblivious transfer

Our outsourced oblivious transfer is an extension of a technique developed by Naor et al. [53] that allows the chooser to select entries that are forwarded to a third party rather than returned to the chooser. By combining their concept of a proxy oblivious transfer with the semi-honest OT extension by Ishai et al. [28], our outsourced oblivious transfer provides a secure OT in the malicious model. We achieve this result for four reasons:

First, since Alice never sees the outputs of the OT protocol, she cannot learn anything about the garbled values held by the generator. This saves us from having to implement Ishai’s extension to prevent the chooser from behaving maliciously.

Since the Cloud sees only random garbled values and Alice’s input blinded by a one-time pad, the Cloud learns nothing about Alice’s true inputs.

Since Bob’s view of the protocol is almost identical to his view in Ishai’s standard extension, the same security guarantees hold (i.e., security against a malicious sender).

Finally, if Alice does behave maliciously and uses inconsistent inputs to the primitive OT phase, there is a negligible probability that those values will hash to the correct one-time pad keys for recovering either commitment key, which will prevent the Cloud from de-committing the garbled input values.

It is important to note that this particular application of the OOT allows for this efficiency gain since the evaluation of the garbled circuit will fail if Alice behaves maliciously. By applying the maliciously secure extension by Ishai et al. [28], this primitive could be applied generally as an oblivious transfer primitive that is secure in the malicious model. Further discussion and analysis of this general application is outside the scope of this work.

6. Proof of security

We formally prove the security of our protocol with the following theorem, which gives security guarantees identical to the Salus protocol by Kamara et al. [31].

Theorem 1.
The outsourced two-party SFE protocol securely computes a function $f (a, b)$ in the following two corruption scenarios:(1) The Cloud is malicious and non-cooperative with respect to the rest of the parties, while all other parties are semi-honest;(2) The Cloud is semi-honest and exactly one other party is malicious.
Proof.
To demonstrate that: $\begin{array}{l} {{REAL}^{(i)} (k, x; r)}_{k \in N} \overset{c}{\approx} {{IDEAL}^{(i)} (k, x; r)}_{k \in N} \end{array}$ for all $i \in [A, B, C]$ , we consider separately the cases when Alice, Bob, and Cloud deviate from the protocol.

6.1. Malicious evaluator Alice $A^{*}$

In this scenario, both Bob and Cloud participate honestly in the protocol. Note that during the protocol execution, Alice only exchanges messages with the other participants at five points: the coin-flip during the cut-and-choose, the primitive oblivious transfer, sending decryption information at the end of the OOT, checking Bob’s input consistency, and receiving the proof of validity and output from the garbled circuit. Thus, our simulator needs only ensure that these sections of the protocol are indistinguishable to the adversary $A^{*}$ with respect to the security parameter k. Consider the following hybrid experiments and lemmas.

Simulating the coin-flip (Phase 1):

$Hybrid 1^{(A)} (k, x; r)$ : This experiment is the same as ${REAL}^{(A)} (k, x; r)$ except that instead of running a fair coin toss protocol with $A^{*}$ , the experiment chooses a random string ρ, and a coin-flipping simulator $S_{CF} (ρ, 1^{k})$ produces the protocol messages that output ρ.

Lemma 1.
${REAL}^{(A)} (k, x; r) \overset{c}{\approx} Hybrid 1^{(A)} (k, x; r)$ .
Proof.
Based on the security of the fair coin toss protocol, we know that there exists a simulator $S_{CF} (\cdot, \cdot)$ such that an interaction with $S_{CF} (\cdot, \cdot)$ is indistinguishable from a real protocol interaction. Since everything else in $Hybrid 1^{(A)} (k, x; r)$ is exactly the same as in ${REAL}^{(A)} (k, x; r)$ , this proves the lemma. □

Simulating the primitive OT (Phase 2):

$Hybrid 2^{(A)} (k, x; r)$ : This experiment is the same as $Hybrid 1^{(A)} (k, x; r)$ except that during the Outsourced Oblivious Transfer, the experiment invokes a simulator $S_{OT}$ to simulate the primitive oblivious transfer operation with $A^{}$ . The simulator sends $A^{}$ a random string s and receives the columns of the matrix $Q^{}$ .
Lemma 2.
$Hybrid 1^{(A)} (k, x; r) \overset{c}{\approx} Hybrid 2^{(A)} (k, x; r)$ .
Proof.
Based on the malicious security of the OT primitive, we know that there exists a simulator $S_{OT}$ such that an interaction with this simulator is indistinguishable from a real execution of the oblivious transfer protocol. Since everything else in $Hybrid 2^{(A)} (k, x; r)$ is identical to $Hybrid 1^{(A)} (k, x; r)$ , this proves the lemma. □

Checking the output of OOT (Phase 2):

$Hybrid 3^{(A)} (k, x; r)$ : This experiment is the same as $Hybrid 2^{(A)} (k, x; r)$ except that the experiment aborts if the matrix $Q^{}$ is not formed correctly (that is, if $A^{}$ used inconsistent input values ${ea}^{}$ for any column in generating $Q^{}$ ).
Lemma 3.
$Hybrid 2^{(A)} (k, x; r) \overset{c}{\approx} Hybrid 3^{(A)} (k, x; r)$ .
Proof.
Consider that in $Hybrid 2^{(A)} (k, x; r)$ , if for some value of i, $A^{}$ sends the column value $T^{i} \oplus {ea}^{'}$ for some ${ea}^{'} \neq {ea}^{}$ such that the ith bit is b in ${ea}^{}$ and $b \oplus 1$ in ${ea}^{'}$ . Then for every row in $Q^{}$ , the ith bit will be encrypted in the $b \oplus 1$ entry. However, when $A^{}$ sends the value ${ea}^{} \oplus p^{}$ to the Cloud for decryption, when the Cloud decrypts the ith choice, it will decrypt the $b \oplus 1$ entry instead of the b entry, which will yield an invalid decryption with probability $1 - ϵ$ for a negligible value of ϵ. Since, with high probability, this decryption is not a valid commitment key, the garbled input values will not decommit properly and the Cloud will abort. In $Hybrid 3^{(A)} (k, x; r)$ , since the experiment observes the messages $Q^{}$ , $p^{}$ , and ${ea}^{} \oplus p^{}$ , it can recover ${ea}^{}$ and check $Q^{}$ for consistency, aborting if an inconsistency is found. □

Simulating consistency check and substituting inputs (Phase 3):

$Hybrid 4^{(A)} (k, x; r)$ : This experiment is the same as $Hybrid 3^{(A)} (k, x; r)$ except that the experiment provides a string of $2 \cdot n$ zeros, denoted ${0}^{2 \cdot n}$ , during the consistency check to replace Bob’s input b.
Lemma 4.
$Hybrid 3^{(A)} (k, x; r) \overset{c}{\approx} Hybrid 4^{(A)} (k, x; r)$ .
Proof.
Here we cite Lemma 5 from the proof of shelat and Shen’s scheme [60]. Since the messages sent in our scheme are identical to theirs in content, we simply change the entity sending the message in the experiment and the lemma still holds. □

Simulating the output proof (Phase 5):

$Hybrid 5^{(A)} (k, x; r)$ : This experiment is the same as $Hybrid 4^{(A)} (k, x; r)$ except that instead of returning the output of the circuit, the experiment provides $A^{}$ with the result sent from the trusted external oracle.
Lemma 5.
$Hybrid 4^{(A)} (k, x; r) \overset{c}{\approx} Hybrid 5^{(A)} (k, x; r)$ .
Proof.
Based on the security of the garbled circuit construction being used, the trusted third party output and the circuit output will be indistinguishable when provided with $A^{}$ ’s input ${ea}^{}$ , which the experiment can recover because of the change made in $Hybrid 3^{(A)} (k, x; r)$ . In addition, since the experiment can observe the random seeds used to construct the proofs of output consistency used when generating the evaluation circuits, the experiment can reproduce valid proofs of consistency for the output value $f_{A} (a^{}, b)$ provided by the oracle. Based on the security proofs of these consistency checks by Kiraz and Schoenmakers [33], indistinguishability holds. □
Lemma 6.
$Hybrid 5^{(A)} (k, x; r)$ runs in polynomial time.
Proof.
Since $A^{}$ is strictly a polynomial-time adversary and all of the operations in the $REAL$ protocol are polynomial time, most of the operations performed can be summarized into a runtime $p (k)$ . The two simulators $S_{OT}$ and $S_{CF} (\cdot, \cdot)$ are assumed to be polynomial in runtime since they are, computationally secure simulators for their respective roles. Since they are both only executed once, the total running time can be expressed as $p (k) + r_{OT} + r_{CF}$ , where $r_{OT}$ is the runtime of the polynomial simulator $S_{OT}$ and $r_{CF}$ is the runtime of the polynomial simulator $S_{CF} (\cdot, \cdot)$ . Since all of these individual components are polynomial, the total runtime is also polynomial. □

$Hybrid 5^{(A)} (k, x; r)$ is exactly the experiment run by the simulator $S^{A}$ in the ideal world. Should $A^{}$ ever abort the protocol, the simulator $S^{A}$ will forward the abort to the trusted third party. Otherwise, it will follow $Hybrid 5^{(A)} (k, x; r)$ , controlling Bob and Cloud, and outputs whatever $A^{}$ outputs. By Lemmas 1–6, this simulator proves Theorem 1 when Alice is malicious.
6.2. Malicious generator Bob $B^{}$

In this scenario, both Alice and Cloud participate honestly in the protocol. Note that in the protocol, the generator exchanges messages with both parties at five critical points: circuit cut-and-choose, the primitive OT, the OOT result delivery, the input consistency check, and the output proof of integrity and delivery. Consider the following hybrid experiments and lemmas.

Simulating the cut-and-choose (Phase 1):

$Hybrid 1^{(B)} (k, x; r)$ : This experiment is the same as ${REAL}^{(B)} (k, x; r)$ except that if $B^{*}$ successfully passes the first cut-and-choose test, the experiment repeatedly rewinds $B^{*}$ , repeating the coin flip protocol and the verification of the circuit hashes and commitments until $B^{*}$ passes for a second time. Let ${Chk}_{i}$ be the set of check circuit indices for the ith successful cut-and-choose. If ${Chk}_{1} = {Chk}_{2}$ , then the experiment aborts.

Lemma 7.
${REAL}^{(B)} (k, x; r) \overset{c}{\approx} Hybrid 1^{(B)} (k, x; r)$ .
Proof.
Here we cite Lemma 8 from shelat and Shen’s protocol proof [60]. The idea in their proof is that if $B^{}$ never passes the cut-and-choose, then both the real and hybrid experiments will abort. However, if $B^{}$ passes once, they demonstrate that the probability of $B^{}$ passing again with the exact same set of check circuits is negligible within a polynomial number of rewinds. Since their cut-and-choose is identical to ours, indistinguishability holds in this setting. □

Checking input consistency and recovering inputs (Phase 3):

$Hybrid 2^{(B)} (k, x; r)$ : This experiment is the same as $Hybrid 1^{(B)} (k, x; r)$ except that the experiment recovers $B^{}$ ’s input $b^{}$ during the input consistency check using the random seed recovered in $Hybrid 1^{(B)} (k, x; r)$ . Since the experiment is running with a set of evaluation circuits ${Evl}_{2}$ produced during the second successful cut-and-choose, it possesses the random coins used to generate at least one of these circuits since ${Evl}_{1} \neq {Evl}_{2}$ . If the consistency check does not pass or if $B^{}$ ’s input cannot be recovered, the experiment immediately aborts.
Lemma 8.
$Hybrid 1^{(B)} (k, x; r) \overset{c}{\approx} Hybrid 2^{(B)} (k, x; r)$ .
Proof.
Based on the security of shelat and Shen’s claw-free collections technique for checking the consistency of $B^{}$ ’s inputs across evaluation circuits, then $B^{}$ can find a claw and change its input for one evaluation circuit with negligible probability. In $Hybrid 2^{(B)} (k, x; r)$ , since the experiment possesses at least one set of random coins ${rc}_{i}$ that was used to generate a circuit in the set ${Evl}_{2}$ , it can recover the input wire labels for that circuit and recover $B^{}$ ’s input. If the input is invalid (i.e., does not correspond to an input label), the circuit would fail to evaluate and would generate an abort in both hybrids. Thus, indistinguishability holds. □

Simulating the output proof (Phase 5):

$Hybrid 3^{(B)} (k, x; r)$ : This experiment is the same as $Hybrid 2^{(B)} (k, x; r)$ except that during the output phase the experiment prepares the result $f (a, b^{})$ received from the trusted third party as the output instead of the output from the circuit $f (a, b^{})$ . If no majority values ${fb}^{'}$ are found from the circuit, the experiment aborts. Otherwise, it uses the random coins ${rc}_{i}$ recovered from $Hybrid 1^{(B)} (k, x; r)$ to prove the validity of the output for some circuit.
Lemma 9.
$Hybrid 2^{(B)} (k, x; r) \overset{c}{\approx} Hybrid 3^{(B)} (k, x; r)$ .
Proof.
Based on the security of the garbled circuit construction being used, the trusted third party output and the circuit output will be indistinguishable when provided with $B^{}$ ’s input $b^{}$ , which the experiment can recover using the random coins ${rc}_{i}$ obtained in $Hybrid 1^{(B)} (k, x; r)$ . In addition, these random coins allow the experiment to construct the proofs of output consistency used when generating one of the evaluation circuits, thus the experiment can reproduce valid proofs of consistency for the output value $f_{B} (a, b^{})$ provided by the trusted third party. If no majority output value exists, in both hybrids the abort message would be sent. Finally, based on the security proofs of the witness indistinguishable consistency proofs developed by Kiraz and Schoenmakers [33], indistinguishability holds. □

Simulating the primitive OT (Phase 2):

$Hybrid 4^{(B)} (k, x; r)$ : This experiment is the same as $Hybrid 3^{(B)} (k, x; r)$ except that rather than run the primitive oblivious transfer with Alice, the experiment generates a random input string $a^{'}$ and a random matrix T, then runs a simulator $S_{OT}$ with $B^{}$ , which delivers to $B^{}$ exactly one element from the pair $(T^{i}, T^{i} \oplus {ea}^{'})$ depending on $B^{}$ ’s ith selection bit.
Lemma 10.
$Hybrid 3^{(B)} (k, x; r) \overset{c}{\approx} Hybrid 4^{(B)} (k, x; r)$ .
Proof.
Based on the security of the primitive OT scheme, we know that the simulator $S_{OT}$ exists, that it can recover $B^{}$ ’s selection bits $s^{}$ from the interaction, and that an interaction with it is indistinguishable from a real execution of the OT. Since $B^{}$ cannot learn any distinguishing information from Alice’s input, again based on the security of the OT primitive, then indistinguishability holds between the hybrid experiments. Note that the ordering of hybrids 4 and 5 is critical. If the Phase 2 hybrids were included in protocol order, the adversary $B^{}$ would receive the output $f_{B} (a^{'}, b^{})$ instead of $f_{B} (a, b^{})$ , which would allow him to distinguish between the real and ideal worlds. □

Checking the output of OOT (Phase 2):

$Hybrid 5^{(B)} (k, x; r)$ : This experiment is the same as $Hybrid 4^{(B)} (k, x; r)$ except that the experiment checks the validity of $B^{}$ ’s output from the OOT. Since the experiment possesses T, ${ea}^{'}$ , and $s^{}$ (which was recovered by the oblivious transfer simulator $S_{OT}$ in the previous hybrid), the experiment can check whether or not the encrypted set of outputs $Y^{}$ is well-formed. If it is not, the experiment immediately aborts.
Lemma 11.
$Hybrid 4^{(B)} (k, x; r) \overset{c}{\approx} Hybrid 5^{(B)} (k, x; r)$ .
Proof.
Recall that in $Hybrid 4^{(B)} (k, x; r)$ , if $B^{}$ does not format the output of the OOT correctly, Cloud will, with probability $1 - ϵ$ fail to recover a valid commitment key, where ϵ is negligible in the security parameter. Should this be the case, the committed garbled circuit labels will fail to decrypt properly, and the Cloud will abort the protocol. In $Hybrid 4^{(B)} (k, x; r)$ , since the experiment has observed the values Q, $s^{}$ , ${ea}^{'}$ , and $Y^{}$ , it can trivially observe if $Y^{}$ is correctly formed, and aborts if it is not. Additionally, for $B^{}$ to swap any of A’s input labels in the commitments, $B^{}$ must find a claw in the claw-free collection used to generate those input labels. Based on the security of shelat and Shen’s claw-free collections technique, used to check the consistency of A’s input across evaluation circuits in this phase, this will only happen with a negligible probability. □
Lemma 12.
$Hybrid 5^{(B)} (k, x; r)$ runs in polynomial time.
Proof.
Since all of the steps in the protocol run in expected polynomial time, the only step that must be verified is the rewinding phase. Based on Lemma 14 from shelat and Shen’s proof [60], the total time for the rewinds is also polynomial in k. Thus, the composition of all steps runs in polynomial time. □

$Hybrid 5^{(B)} (k, x; r)$ is exactly the experiment run by the simulator $S^{B}$ in the ideal world. Should $B^{}$ ever abort the protocol, the simulator $S^{B}$ will forward the abort to the trusted third party. Otherwise, it will follow $Hybrid 5^{(B)} (k, x; r)$ , controlling Alice and Cloud, and outputs whatever $B^{}$ outputs. By Lemmas 7–12, this simulator proves Theorem 1 when Bob is malicious.
6.3. Malicious cloud $C^{*}$

In this scenario, both Alice and Bob participate honestly in the protocol. Note that in the protocol, the Cloud participates in checking the circuits during the cut-and-choose, decrypting Alice’s inputs in the OOT, forwarding Bob’s inputs for consistency checking, evaluating the circuit, and proving and delivering the final output of computation. Consider the following hybrid experiments and lemmas.

Replacing inputs for the OOT (Phase 2):

$Hybrid 1^{(C)} (k, x; r)$ : This experiment is the same as ${REAL}^{(C)} (k, x; r)$ except that during the OOT, the experiment replaces Alice’s input $ea$ with a string of zeros ${ea}^{'} = {0}^{2 \cdot ℓ \cdot n}$ . This value is then used to select garbled input values from Bob in the OOT, which are then forwarded to $C^{*}$ according to the protocol.

Lemma 13.
${REAL}^{(C)} (k, x; r) \overset{c}{\approx} Hybrid 1^{(C)} (k, x; r)$ .
Proof.
In a real execution, $C^{}$ will observe the random matrix T, the encrypted commitment keys Y, and Alice’s input XOR’d with the permutation string $ea \oplus p$ . Based on the statistical indistinguishability of a value XOR’d with a random value, $ea \oplus p \overset{s}{\approx} p$ for any input value $ea$ . Since T is randomly generated in both ${REAL}^{(C)} (k, x; r)$ and $Hybrid 1^{(C)} (k, x; r)$ , they are trivially indistinguishable. Considering the output pairs Y, half of the commitment keys (those not selected by Alice) will consist of the keys in $x_{b, j} \oplus H (j, s)$ , which is computationally indistinguishable from random, and the keys in $x_{b, j}$ can only be recovered if $C^{}$ can find a collision with the hash value $H (j, s)$ without having Bob’s random value s. The remaining keys, which can be recovered by $C^{}$ , are permuted randomly, such that their ordering is statistically indistinguishable from a random ordering. Since the commitments are also permuted randomly, the same indistinguishability holds for the ordering of the garbled input wire values. Thus, $C^{}$ cannot distinguish an execution of OOT with Alice’s input $ea$ and the simulator’s input replacement ${ea}^{'}$ . Since the rest of the protocol follows ${REAL}^{(C)} (k, x; r)$ exactly, this proves the lemma. □

Replacing inputs for the consistency check (Phase 3):

$Hybrid 2^{(C)} (k, x; r)$ : This experiment is the same as $Hybrid 1^{(C)} (k, x; r)$ except that the experiment replaces Bob’s input b with all zeros ${0}^{2 \cdot n}$ . This value is then prepared and checked according to the protocol for consistency across evaluation circuits.
Lemma 14.
$Hybrid 1^{(C)} (k, x; r) \overset{c}{\approx} Hybrid 2^{(C)} (k, x; r)$ .
Proof.
In this hybrid, $C^{}$ observes a set of garbled input wire values from Bob. Based on the security of Yao garbled circuits, observing one set of garbled input wire values is indistinguishable from observing any other set of input wire values, such that $C^{}$ cannot distinguish between the garbled input for b and the garbled input for ${0}^{2 \cdot n}$ . Since the rest of the hybrid is the same as $Hybrid 1^{(C)} (k, x; r)$ , this proves the lemma. □

Checking the output of the circuit (Phase 5):

$Hybrid 3^{(C)} (k, x; r)$ : This experiment is the same as $Hybrid 2^{(C)} (k, x; r)$ except that after the circuit is evaluated, the experiment checks that the results output by $C^{}$ matches the expected results $f_{A} (a^{'}, b^{'})$ and $f_{B} (a^{'}, b^{'})$ . If $C^{}$ fails to produce a valid proof that the output came from the circuit or if the result does not match, the experiment immediately aborts.
Lemma 15.
$Hybrid 2^{(C)} (k, x; r) \overset{c}{\approx} Hybrid 3^{(C)} (k, x; r)$ .
Proof.
In $Hybrid 2^{(C)} (k, x; r)$ , $C^{}$ can only modify the output without detection with probability $1 - ϵ$ for some negligible probability ϵ, based on the security guarantees of Kiraz’s proof scheme [33]. In $Hybrid 3^{(C)} (k, x; r)$ the experiment catches $C^{}$ when it tries to change the output of the circuit with probability 1, so the distributions are computationally indistinguishable. □
Lemma 16.
$Hybrid 3^{(C)} (k, x; r)$ runs in polynomial time.
Proof.
Since the protocol itself requires only polynomially many steps, the time to run ${REAL}^{(C)} (k, x; r)$ can be expressed as $p (k)$ . The experiment also evaluates the polynomial-time function $f (\cdot, \cdot)$ over random inputs to check the output of $C^{}$ . We call this execution time $q (c)$ , where c is the size of the circuit being evaluated. So, the total execution time is $p (k) + q (c)$ , which is polynomial as a sum. □

$Hybrid 3^{(C)} (k, x; r)$ is exactly the experiment run by the simulator $S^{C}$ in the ideal world. Should $C^{}$ ever abort the protocol, the simulator $S^{C}$ will forward the abort to the trusted third party. Otherwise, it will follow $Hybrid 3^{(C)} (k, x; r)$ , controlling Alice and Bob. If the cut-and-choose, input consistency check, or output proof of correctness fail, then $S^{C}$ aborts to both $C^{}$ and the trusted third party. Otherwise, $S^{C}$ outputs whatever $C^{}$ outputs. By Lemmas 13–16, this simulator proves Theorem 1 when Cloud is malicious.

Given the simulators $S_{A}$ , $S_{B}$ , and $S_{C}$ , this proves the security of our protocol as stated in Theorem 1. □
7. Performance analysis

We now characterize how garbled circuits perform in the constrained-mobile environment with and without outsourcing. Two of the most important constraints for mobile devices are computation and bandwidth, and we show that order of magnitude improvements for both factors are possible with outsourced evaluation. We begin by describing our implementation framework and testbed before discussing results in detail. These results extend the experimental work performed by Carter et al. [9].

7.1. Framework and testbed

Our framework is based on the system designed by Kreuter et al. [37], hereafter referred to as KSS for brevity. We selected this system as our foundation and as our benchmarking comparison because it was the most efficient implementation of a two-party garbled circuit protocol at the time of our original publication. We contacted the authors of the Salus protocol [31] and requested the source code for their framework to compare the actual performance of their scheme with ours, but they were unable to release their code. Thus, an asymptotic comparison was the only fair comparison we could make to the only other existing outsourced scheme. Recent work has shown that using different underlying garbled circuit protocol can yield similar or better performance gains to our work [8,49]. However, these works also require a completely new outsourcing protocol and proofs of security, which is outside the scope of this work. For comparison between our protocol and these newer protocols, we refer the reader to [8,49].

Using KSS as a foundation, we implemented our outsourced protocol and performed modifications to allow for the use of the mobile device in the computation. Notably, KSS uses the Message Passing Interface (MPI), for communication between the multiple nodes of the multi-core machines relied on for circuit evaluation. Our solution replaces MPI calls on the mobile device with sockets that communicate directly with the Generator and Proxy. To provide a consistent comparison, we revised the KSS codebase to allow for direct evaluation between the mobile device (the Evaluator) and the cloud-based Generator. The modifications required included removing the MPI library from the phone client and functions, which did not exist on the phone. The largest difficulty was changing the Intel specific instructions to generic instruction, which would work on the ARM processor of the mobile device.

We also informed the original authors of KSS of several problems we noticed. They in turn fixed the problems necessary for our trials. We found the following problems: generator’s input consistency check was missing from one of the possible run environments, arrays did not work correctly in some cases, nested if statements did not work correctly, and for loops inside of if statements did not work correctly. We thank those authors for their assistance.

Our deployment platform consists of two Dell R610 servers, each containing dual 6-core Xeon processors with 32 GB of RAM and 300 GB 10K RPM hard drives, running the Linux 3.4 kernel and connected as a VLAN on an internal 1 Gbps switch. These machines perform the roles of the Generator and Proxy, respectively, as described in Section 4.1. The mobile device acts as the Evaluator. We use a Samsung Galaxy Nexus phone with a 1.2 GHz dual-core ARM Cortex-A9 processor and 1 GB of RAM, running the Android 4.0 “Ice Cream Sandwich” operating system. We connect an Apple Airport Express wireless access point to the switch. The Galaxy Nexus communicates to the Airport Express over an 802.11n 54 Mbps WiFi connection in an isolated environment to minimize co-channel interference. All tests are run 10 times with error bars on figures representing 95% confidence intervals.

We also ran tests using a 64-core server with 1 TB of memory where the phone was connected over a standard local network, which included additional traffic other than just our tests. This platform performed the roles of both the Generator and the Proxy. We experienced small but noticeable time differences depending upon what other tasks were being performed on the LAN.

When we use our 12-core servers both Bob and the Cloud each have their own 12-core server. In contrast, both parties are run on the same 64-core server. Each circuit can use two processes on our 64-core server or 1 process on each of our smaller 12-core servers. We ran our tests with the same security parameters as KSS for 80-bit security, although we vary the amount of circuits in our tests.

7.2. Execution time

Our tests evaluated the following problems:

Millionaires: This problem models the comparison of two parties comparing their net worth to determine who has more money without disclosing the actual values. We perform the test on input values ranging in size from 4 to 8192 bits. In our circuit two comparisons are performed, one for Bob and one for Alice. There is one bit of output for each party.

Edit (Levenshtein) distance: This is a string comparison algorithm that compares the number of modifications required to covert one string into another. We performed the comparison based on the circuit generated by Jha et al. [29] for strings sized between 4 and 128 bits. There are eight bits of output per party.

Set intersection: This problem matches elements between the private sets of two parties without learning anything beyond the intersecting elements. We base our implementation on the SCS-WN protocol proposed by Huang et al. [23], and evaluate for sets of size 2 to 128. Each element in the set is 8 bits for 16 to 1024 bits of input per party. Each party receives $N * 8$ bits of output, the size of the largest possible result, where N is the size of the set.

AES: We compute an AES encrypt operation with a 128-bit key length, based on a circuit evaluated by Kreuter et al. [37]. One party enters in the key, 128 bits, and other party enters in text to encrypt, which is also 128 bits.

Since our protocol specifies all outputs must be under blinds, we also need to input output blinds, each of our circuits also inputs a blind for each party. The size of the blind corresponds to the size of the party’s output.

Fig. 3.

Execution time for the Edit Distance program of varying input sizes, with 2 circuits evaluated. On 12 core servers.

Fig. 4.

Execution time for significant stages of garbled circuit computation for outsourced and non-outsourced evaluation. The Edit Distance program is evaluated with variable input sizes for the two-circuit case. On 12 core servers.

Figure 3 shows the result of the edit distance computation for input sizes of 2 to 128 with two circuits evaluated. This comparison represents worst-case operation due to the cost of setup for a small number of small circuits – with input size 2, the circuit is only 122 total gates in size. For larger input sizes, however, outsourced computation becomes significantly faster. Note that the graph is logarithmic such that by the time strings of size 32 are evaluated, the outsourced execution is over 6 times faster than non-outsourced execution, while for strings of size 128 (comprising over 3.4 million total gates), outsourced computation is over 16 times faster.

The reason for this becomes apparent when we examine Fig. 4. There are three primary operations that occur during the SFE transaction: the oblivious transfer (OT) of participant inputs, the circuit commit (including the circuit consistency check), and the circuit evaluation. As shown in the figure, the OT phase takes 292 ms for input size 2, but takes 467 ms for input size 128. By contrast, in the non-outsourced execution, the OT phase takes 307 ms for input size 2, but increases to 1860 ms for input size 128. The overwhelming factor, however, is the circuit evaluation phase. It increases from 34 ms (input size 2) when the evaluation is complete by the time the checks finish on the phone to 7320 ms (input size 128) for the outsourced evaluation, a 215 factor increase. For non-outsourced execution however, this phase increases from 108 ms (input size 2) to 98,800 ms (input size 128), a factor of 914 increase.

Fig. 5.

Execution time for the Edit Distance problem of size 32, with between 2 and 256 circuits evaluated. In the non-outsourced evaluation scheme, the mobile phone runs out of memory evaluating 256 circuits. On 12 core servers.

7.3. Evaluating multiple circuits

The security parameter for the garbled circuit check is $2^{- 0.32 λ}$ [37], where λ is the number of generated circuits. To ensure a sufficiently low probability ( $2^{- 80}$ ) of evaluating a corrupt circuit, 256 circuits must be evaluated. However, there are increasing execution costs as increasing numbers of circuits are generated. Figure 5 shows the execution time of the Edit Distance problem of size 32 with between 2 and 256 circuits being evaluated. In the outsourced scheme, costs rise as the number of circuits evaluated increases. Linear regression analysis shows we can model execution time T as a function of the number of evaluated circuits λ with the equation $T = 243.2 λ + 334.6 ms$ , with a coefficient of determination $R^{2}$ of 0.9971. However, note that in the non-outsourced scheme, execution time increases over 10 times as quickly compared to outsourced evaluation. Regression analysis shows execution time $T = 5435.7 λ + 961 ms$ , with $R^{2} = 0.9998$ . Because in this latter case, the mobile device needs to perform all computation locally as well as transmit all circuit data to the remote parties, these costs increase rapidly. Figure 6 confirms this trend in all of our test programs, which clearly show that execution times for our protocol tend to be faster and increase at a slower rate than the execution times of KSS. Figure 7 provides more detail about each phase of execution. Note that the OT costs are similar between outsourced and non-outsourced execution for this circuit size, but that the costs of consistency checks and evaluation vastly increase execution time for non-outsourced execution.

Fig. 6.

Execution time for all problems tested, with between 2 and 64 circuits evaluated. In the non-outsourced evaluation scheme, the mobile phone runs out of memory evaluating 128 and 256 circuits. Observed that with the exception of a few programs with small input sizes, the execution times of the non-outsourced test programs cluster higher than the outsourced programs. This shows an overall execution time reduction achieved through outsourcing. On 12 core servers.

Fig. 7.

Microbenchmarks of execution time for Edit Distance with input size 32, evaluating from 2 to 256 circuits. Note that the y-axis is log-scale; consequently, the vast majority of execution time is in the check and evaluation phases for non-outsourced evaluation. On 12 core servers.

Note as well that in the non-outsourced scheme, there are no reported values for 256 circuits, as the Galaxy Nexus phone ran out of memory before the execution completed. We observe that a single process on the phone is capable of allocating 512 MB of RAM before the phone would report an out of memory error, providing insight into how much intermediate state is required for non-outsourced evaluation. Thus, to handle circuits of any meaningful size with enough check circuits for a strong security parameter, the only way to be able to perform these operations is through outsourcing.

We present our complete performance results in the Appendix. Our experiments span circuits from small to large input size, and from 8 circuits evaluated to the 256 circuits required for a $2^{- 80}$ security parameter. Note that in many cases it is impossible to evaluate the non-outsourced computation because of the mobile device’s inability to store sufficient amounts of state. Note as well that particularly with complex circuits such as set intersection, even when the non-outsourced evaluation is capable of returning an answer, it can require orders of magnitude more time than with outsourced evaluation. For example, evaluating the set intersection problem with 128 inputs over 32 circuits requires just over 55 s for outsourced evaluation but over an hour and a half with the non-outsourced KSS execution scheme. Outsourced evaluation represents a time savings of 98.92%. Tables 5 and 6 in the Appendix reflect the 64-core results for the same set of tests. We also ran the non-outsourced KSS execution scheme on this server as a comparison point.

Multicore circuit evaluation. We briefly note the effects of multicore servers for circuit evaluation. The servers in our evaluation each contain dual 6-core CPUs, providing 12 total cores of computation. The computation process is largely CPU-bound: while circuits on the servers are being evaluated, each core was reporting approximately 100% utilization. This is evidenced by regression analysis when evaluating between 2 and 12 circuit copies; we find that execution time $T = 162.6 λ + 1614.6 ms$ , where λ is the number of circuits evaluated, with a coefficient of determination $R^{2}$ of 0.9903. As the number of circuits to be evaluated increases beyond the number of available cores, the incremental costs of adding new circuits becomes higher; in our observation of execution time for 12 to 256 circuits, our regression analysis provided the equation $T = 247.4 λ - 410.6 ms$ , with $R^{2} = 0.998$ . This demonstrates that evaluation of large numbers of circuits is optimal when every evaluated circuit can be provided with a dedicated core.

The results above show that as many-way servers are deployed in the cloud, it becomes easier to provide optimal efficiency computing outsourced circuits. A 256-core machine would be able to evaluate 256 circuits in parallel to provide the accepted standard $2^{- 80}$ security parameter. Depending on the computation performed, there can be a trade-off between a slightly weaker security parameter and maintaining optimal evaluation on servers with lower degrees of parallelism. In our testbed, optimal evaluation with 12 cores provides a security parameter of $2^{- 3.84}$ . Clearly more cores would provide stronger security while keeping execution times proportional to our results. A reasonable trade-off might be 32 circuits, as 32-core servers are readily available. Evaluating 32 circuits provides a security parameter of $2^{- 10.2}$ , equivalent to the adversary having less than a $\frac{1}{512}$ chance of causing the evaluator to compute over a majority of corrupt circuits. Stronger security guarantees on less parallel machines can be achieved at the cost of increasing execution time, as individual cores will not be dedicated to circuit evaluation. However, if a 256-core system is available, it will provide optimal results for achieving a $2^{- 80}$ security parameter.

Different programs have different bottlenecks that affect the performance. When the bottleneck of the execution is on the mobile device, the speed of the computation cannot benefit by having more cores. Our analysis of the results revealed this occurs when a circuit has a high amount of inputs, relatively few gates in the circuit, and uses many cores working in parallel. In the aforementioned cases the gate execution completes before the mobile device completes the generator’s input consistency. At 32 circuits the bottleneck is the input when we use our 12-core servers for AES, all millionaires programs, all set intersection programs other than size 128, edit distance 2, 4, and 8. On our 64-core test server input is the bottleneck at 32 circuits for AES, all millionaires programs, all set intersection programs other than size 128, and edit distance 2, 4, 8, and 16.

In our tests we used the standard KSS implementation in our phone client for our non-outsourced tests. If we had used a more memory efficient implementation like PCF [36] and combined it with other memory optimizations we would have been able to evaluate all of our programs directly on a mobile phone. However, if this were the case our results would show further improvements in time and bandwidth our system saves over the mobile KSS client.

7.4. Bandwidth

For a mobile device, the costs of transmitting data are intrinsically linked to power consumption, as excess data transmission and reception reduces battery life. Bandwidth is thus a critical resource constraint. In addition, because of potentially uncertain communication channels, transmitting an excess of information can be a rate-limiting factor for circuit evaluation. Figure 8 shows the bandwidth measurement between the phone and remote parties for the edit distance problem with 2 circuits. When we compared execution time for this problem in Fig. 3, we found that trivially small circuits could execute in less time without outsourcing. Note, however, that there are no cases where the non-outsourced scheme consumes less bandwidth than with outsourcing. Our other test programs showed similar results (see Fig. 9), with the non-outsourced execution trending exclusively higher in bandwidth use than the outsourced protocol.

Fig. 8.

Bandwidth measurements from the phone to remote parties for the Edit Distance problem with varying input sizes, executing two circuits. On 12 core servers.

Fig. 9.

Bandwidth measurements from the phone to remote parties for all problems with varying input sizes, executing between 2 and 64 circuits. Note that the non-outsourced measurements cluster higher than the outsourced measurements, indicating that outsourcing the computation consistently saves bandwidth across the tested applications. On 12 core servers.

This is a result of the significant improvements garnered by using our outsourced oblivious transfer (OOT) construction described in Section 4. Recall that with the OOT protocol, the mobile device sends inputs for evaluation to the generator; however, after this occurs, all further evaluation until the final output verification from the cloud proxy occurs between the generator and the proxy, ensuring that further communication is not required by the mobile device. Figure 8 shows that the amount of data transferred increases only nominally compared to the non-outsourced protocol. Apart from the initial set of inputs transmitted to the generator, data demands are largely constant. This is further reflected in Tables 7 and 8 in the Appendix, which shows the vast bandwidth savings over the 32-circuit evaluation of our representative programs. In particular, for large, complex circuits, the savings are vast: outsourced AES-128 requires 96.3% less bandwidth, while set intersection of size 128 requires 99.7% less bandwidth than in the non-outsourced evaluation. Remarkably, the edit distance 128 problem requires 99.95%, over 1900 times less bandwidth, for outsourced execution.

We performed an analytical analysis of what affects the amount of bandwidth. We determined input size is the only aspect of a program, which affects the amount of bandwidth used by the mobile device. The amount of gates in a circuit does not affect the amount of bandwidth used by the mobile device. The Alice’s input (OTs) and Bob’s input (consistency checks) both use bandwidth.

Fig. 10.

Execution time over varying network latency for the Edit Distance problem with varying input sizes, executing between 256 circuits. On 12 core servers.

7.5. Network latency

As network latency is a limiting factor on mobile phones, we wanted to see how our outsourced system performed in an environment with latency. We performed trials of our execution system with two different amounts of latency added, 100 ms and 500 ms. We used Linux’s tc command to emulate different latency amounts. It was found by Huang [21] that the median ping latency to a landserver on a 3G connection was between 180 ms to 250 ms.

In Fig. 10 we present the results of our latency tests. The slowdown of added latency is not uniform across all of our tests. With the Millionaires 8192, we observed a slowdown of about 1.9× to 1.2× from 0 latency to 100 ms latency, depending on the amount of circuits executed. Whereas Set Intersection 16 had a slowdown of 2.8× to 2× when we added 100 ms of latency. Making the transition from 0 latency to 500 ms makes the differences more apparent. We observed a slowdown of 3.7× to 2.8× for Millionaires 8192. Correspondingly, the Set Intersection 16 had an observed slowdown between 9.7× to 6.4×.

The reason for the difference in the slowdown is due to the different bottlenecks different programs have in our system. For some programs the bottleneck will be at the phases necessary for input for the different parties, the oblivious transfer (large mobile input) and consistency check (large generator input). For other programs the bottleneck will be the garbled circuit generation and evaluation. A future goal is to improve the performance of our system in high latency environments.

8. Evaluating large circuits

Beyond the standard benchmarks for comparing garbled circuit execution schemes, we aimed to provide compelling applications that exploit the mobile platform with large circuits that would be used in real-world scenarios. Based on our initial testing, these circuits are too large to evaluate directly on the mobile device using KSS due to the significant memory requirements. These experiments highlight the main practical contribution of our protocol, that we can now evaluate circuits that are orders of magnitude larger than was possible using previously existing techniques.

We discuss public-key cryptography and the Dijkstra shortest path algorithm, then describe how the latter can be used to implement a privacy-preserving navigation application for mobile phones.

Fig. 11.

Execution time for the large circuit test applications with varying input sizes, executing 128 circuits. On 64 core servers.

8.1. Large circuit benchmarks

Figure 11 shows the execution time required for a blinded RSA circuit of input size of 128. For these tests we used our more powerful 64-core server. As described in Section 7, larger testbeds capable of executing 128 or 256 cores in parallel would be able to provide similar results for executing the 256 circuits necessary for a $2^{- 80}$ security parameter as they could evaluate the added circuits in parallel. The main difference in execution time would come from the multiple OTs from the mobile device to the outsourced proxy. The RSA circuit has been previously evaluated with KSS, but never from the standpoint of a mobile device.

The RSA circuit inputs 128 bits each both parties as well the necessary output blinds. Both parties receive output 130 bits. The RSA circuit is the same circuit used in KSS12, which principally calculates a single modular exponentiation.

We only report the outsourced execution results, as the circuits are far too large to evaluate directly on the phone. As with the larger circuits described in Section 7, the phone runs out of memory from merely trying to store a representation of the circuit. Prior to optimization, the blinded RSA circuit is 192,537,834 gates and afterward, comprises 116,083,727 gates, or 774 MB in size.

Our Dijkstra’s circuit assumes each node has a maximum degree of 4. Each edge weight is represented internally with 16 bits. Each node is internally represented with 8 bits. The program performs $N - 1$ iterations of the algorithm in the circuit as it starts with the shortest path to the start node and adds the shortest path to a single node for every each iteration, where N is the number of nodes. The circuit inputs $N * 96$ bits of input form Bob, the map information, and 16 bits of input form Alice, the starting and ending nodes. The circuit outputs $8 * N$ bits to Alice, the shortest path. The program and also inputs the necessary bits for the output blinds as well.

The implementation of Dijkstra’s shortest-path algorithm results in very large circuits. The pre-optimized size of the shortest path circuit for 20 vertices is 20,288,444 gates and after optimization is 1,653,542 gates. The 100-node graph is even larger, with 168,422,382 gates post optimization, 1124 MB in size. This final example is among the largest publicly evaluated circuit to date (see the Appendix for complete results). While it may be possible for existing protocols to evaluate circuits of similar size, it is significant that we are evaluating comparably massive circuits from a resource-constrained mobile device. Table 2 gives the amount of bandwidth these larger programs use.

Table 2
Bandwidth of 128-bit RSA and Dijkstra 20, 50, and 100

32 circuits 64 circuits 128 circuits

RSA128 334,629 672,067 1,346,943

Dijkstra20 3,862,280 7,770,598 15,587,234

Dijkstra50 9,575,622 19,266,732 38,648,952

Dijkstra100 19,087,192 38,405,622 77,042,482

	32 circuits	64 circuits	128 circuits
RSA128	334,629	672,067	1,346,943
Dijkstra20	3,862,280	7,770,598	15,587,234
Dijkstra50	9,575,622	19,266,732	38,648,952
Dijkstra100	19,087,192	38,405,622	77,042,482

Note: All entries are in Bytes.

8.2. Privacy-preserving navigation

Mapping and navigation are some of the most popular uses of a smartphone. Consider how directions may be given using a mobile device and an application such as Google Maps, without revealing the user’s current location, their ultimate destination, or the route that they are following. That is, the navigation server should remain oblivious of these details to ensure their mutual privacy and to prevent giving away potentially sensitive details if the phone is compromised. Specifically, consider planning of the motorcade route for the recent Presidential inauguration. In this case, the route is generally known in advance but is potentially subject to change if sudden threats emerge. A field agent along the route wants to receive directions without providing the navigation service any additional details, and without sensitive information about the route loaded to the phone. Moreover, because the threats may be classified, the navigation service does not want the holder of the phone to be given this information directly.

To model this scenario, we overlay a graph topology on a map of downtown Washington DC, encoding intersections as vertices. Edge weights are a function of their distance and heuristics such as potential risks along a graph edge. Figure 12 shows graphs generated based on vertices of 20, 50, and 100 nodes, respectively. Note that the 100-node graph (Fig. 12(c)) encompasses a larger area and provides finer-grained resolution of individual intersections than the 20-node graph (Fig. 12(a)).

Fig. 12.

Map of potential presidential motorcade routes through Washington, DC. As the circuit size increases, a larger area can be represented at a finer granularity. (a) 20 identified intersections; (b) 50 identified intersections; (c) 100 identified intersections.

There is a trade-off between detail and execution time, however; as shown in Fig. 11, a 20-vertex graph can be evaluated in 1 min 46 s, while a 100-vertex graph requires almost 43 min with 128 circuits in our 64-core server testbed. We anticipate that based on the role a particular agent might have on a route, they will be able to generate a route that covers their particular geographical jurisdiction and thus have an appropriately-sized route, with only certain users requiring the highest-resolution output. Additionally, as described in Section 7.3, servers with more parallel cores can simultaneously evaluate more circuits, giving faster results.

Figure 13 reflects two routes. The first, overlaid with a dashed line, is the shortest path under optimal conditions that is output by our directions service, based on origin and destination points close to the historical start and end points of the past six presidential inaugural motorcades. Now consider that incidents have happened along the route, shown in the figure as a car icon in a hazard zone inside a red circle. The agent recalculates the optimal route, which has been updated by the navigation service to assign severe penalties to those corresponding graph edges. The updated route returned by the navigation service is shown in the figure as a path with a dotted line. In the 50-vertex graph in Fig. 12, the updated directions would be available in just over 135 s for 32-circuit evaluation, and 196 and a half seconds for 64-circuit evaluation.

Fig. 13.

Motorcade route with hazards along the route. The dashed line represents the optimal route, while the dotted line represents the modified route that takes hazards into account.

9. Conclusion

While garbled circuits offer a powerful tool for secure function evaluation, they typically assume participants with massive computing resources. Our work solves this problem by presenting a protocol for outsourcing garbled circuit evaluation from a resource-constrained mobile device to a cloud provider in the malicious setting. By extending existing garbled circuit evaluation techniques, our protocol significantly reduces both computational and network overhead on the mobile device while still maintaining the necessary checks for malicious or lazy behavior from all parties. Our outsourced oblivious transfer construction significantly reduces the communication load on the mobile device and can easily accommodate more efficient OT primitives as they are developed. The performance evaluation of our protocol shows dramatic decreases in required computation and bandwidth. For the edit distance problem of size 128 with 32 circuits, computation is reduced by 98.92% and bandwidth overhead reduced by 99.95% compared to non-outsourced execution. These savings are illustrated in our privacy-preserving navigation application, which allows a mobile device to efficiently evaluate a massive garbled circuit securely through outsourcing. These results demonstrate that the recent improvements in garbled circuit efficiency can be applied in practical privacy-preserving mobile applications on even the most resource-constrained devices.

Footnotes

Acknowledgments

This material is based on research sponsored by the U.S. National Science Foundation under grant numbers CNS-1464088, CNS-1526718, CNS-1540217, and CNS-1540218 and DARPA under agreement number FA8750-11-2-0211. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government. We would like to thank Adam Bates for his help with figures for this paper; Daniel Ellsworth for his help with setting up our testbed; Benjamin Kreuter, abhi shelat, and Chih-hao Shen for working with us on their garbled circuit compiler and evaluation framework; Chris Peikert for providing helpful feedback on our proofs of security; Thomas DuBuisson and Galois for their assistance in the performance evaluation; and Ian Goldberg for his guidance in shepherding the conference version of this work.

Experimental results

Table 10

Execution time for evaluating a 128-bit blinded RSA circuit and Dijkstra shortest path solvers over graphs with 20, 50, and 100 vertices

	32 circuits time (ms)	64 circuits (ms)	128 circuits (ms)	Optimized gates	Unoptimized gates	Size (MB)
RSA128	505,000.0 ± 2%	734,000.0 ± 4%	1,420,000.0 ± 1%	116,083,727	192,537,834	774
Dijkstra20	25,800.0 ± 2%	49,400.0 ± 1%	106,000.0 ± 1%	1,653,542	20,288,444	11
Dijkstra50	135,000.0 ± 1%	197,000.0 ± 3%	389,000.0 ± 2%	22,109,732	301,846,263	147
Dijkstra100	892,000.0 ± 2%	1,300,000.0 ± 2%	2,560,000.0 ± 1%	168,422,382	2,376,377,302	1124

Notes: All numbers are for outsourced evaluation, as the circuits are too large to be computed without outsourcing to a proxy.

References

Asharov ,

Lindell ,

Schneider and

Zohner , More efficient oblivious transfer and extensions for faster secure computation, in: Proceedings of the ACM Conference on Computer and Communications Security, 2013.

Bellare and

Micali , Non-interactive oblivious transfer and applications, in: Advances in Cryptology – CRYPTO, 1990.

Ben-Or ,

Goldwasser and

Wigderson , Completeness theorems for non-cryptographic fault-tolerant distributed computation, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1988.

Bendlin ,

Damgård ,

Orlandi and

Zakarias , Semi-homomorphic encryption and multiparty computation, in: Proceedings of the Annual International Conference on Theory and Applications of Cryptographic Techniques, 2011.

Brickell and

Shmatikov , Privacy-preserving graph algorithms in the semi-honest model, in: Proceedings of the International Conference on Theory and Application of Cryptology and Information Security, 2005.

Canetti ,

Lindell ,

Ostrovsky and

Sahai , Universally composable two-party and multi-party secure computation, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 2002.

Carter ,

Amrutkar ,

Dacosta and

Traynor , For your phone only: Custom protocols for efficient secure function evaluation on mobile devices, Journal of Security and Communication Networks (SCN) 7(7) (2014), 1165–1176.

Carter ,

Lever and

Traynor , Whitewash: Outsourcing garbled circuit generation for mobile devices, in: Proceedings of the Annual Computer Security Applications Conference (ACSAC), 2014.

Carter ,

Mood ,

Traynor and

Butler , Secure outsourced garbled circuit evaluation for mobile devices, in: Proceedings of the USENIX Security Symposium, 2013.

10.

Chaum ,

Crépeau and

Damgard , Multiparty unconditionally secure protocols, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1988.

11.

S.G.

Choi ,

K.-W.

Hwang ,

Katz ,

Malkin and

Rubenstein , Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces, in: RSA Cryptographers’ Track, 2012.

12.

S.G.

Choi ,

Katz ,

Kumaresan and

H.-S.

Zhou , On the security of the “free-xor” technique, in: Proceedings of the International Conference on Theory of Cryptography, 2012.

13.

Damgård and

Ishai , Scalable secure multiparty computation, in: Advances in Cryptology – CRYPTO, 2006.

14.

Damgård and

J.B.

Nielsen , Scalable and unconditionally secure multiparty computation, in: Advances in Cryptology – CRYPTO, 2007.

15.

Damgard ,

Pastro ,

Smart and

Zakarias , Multiparty computation from somewhat homomorphic encryption, in: Advances in Cryptology – CRYPTO, 2012.

16.

Gentry ,

Halevi and

N.P.

Smart , Homomorphic evaluation of the aes circuit, in: Advances in Cryptology – CRYPTO, 2012.

17.

Goldreich and

Kahan , How to construct constant-round zero-knowledge proof systems for NP, Journal of Cryptology 9 (1995), 167–189.

18.

Goyal ,

Mohassel and

Smith , Efficient two party and multi party computation against covert adversaries, in: Advances in Cryptology – EUROCRYPT, 2008.

19.

Green ,

Hohenberger and

Waters , Outsourcing the decryption of abe ciphertexts, in: Proceedings of the USENIX Security Symposium, 2011.

20.

Henecka ,

Kögl ,

A.-R.

Sadeghi ,

Schneider and

Wehrenberg , Tasty: Tool for automating secure two-party computations, in: Proceedings of the ACM Conference on Computer and Communications Security, 2010.

21.

Huang , Performance and power characterization of cellular networks and mobile application optimizations, PhD thesis, University of Michigan, 2013.

22.

Huang ,

Chapman and

Evans , Privacy-preserving applications on smartphones, in: Proceedings of the USENIX Workshop on Hot Topics in Security, 2011.

23.

Huang ,

Evans and

Katz , Private set intersection: Are garbled circuits better than custom protocols? in: Proceedings of the ISOC Symposium on Network and Distributed Systems Security, San Diego, CA, USA, 2012.

24.

Huang ,

Evans ,

Katz and

Malka , Faster secure two-party computation using garbled circuits, in: Proceedings of the USENIX Security Symposium, 2011.

25.

Huang ,

Katz and

Evans , Quid-pro-quo-tocols: Strengthening semi-honest protocols with dual execution, in: Proceedings of the IEEE Symposium on Security and Privacy, 2012.

26.

Huang ,

Katz and

Evans , Efficient secure two-party computation using symmetric cut-and-choose, in: Advances in Cryptology – CRYPTO, 2013.

27.

Iliev and

S.W.

Smith , Small, stupid, and scalable: Secure computing with faerieplay, in: The ACM Workshop on Scalable Trusted Computing, 2010.

28.

Ishai ,

Kilian ,

Nissim and

Petrank , Extending oblivious transfers efficiently, in: Proceedings of the Annual International Cryptology Conference, 2003.

29.

Jha ,

Kruger and

Shmatikov , Towards practical privacy for genomic computation, in: Proceedings of the IEEE Symposium on Security and Privacy, 2008.

30.

Kamara ,

Mohassel and

Raykova , Outsourcing multi-party computation, Report 2011/272, Cryptology ePrint Archive, 2011, http://eprint.iacr.org/.

31.

Kamara ,

Mohassel and

Riva , Salus: A system for server-aided secure function evaluation, in: Proceedings of the ACM Conference on Computer and Communications Security, 2012.

32.

M.S.

Kiraz , Secure and fair two-party computation, PhD thesis, Technische Universiteit Eindhoven, 2008.

33.

M.S.

Kiraz and

Schoenmakers , A protocol issue for the malicious case of Yao’s garbled circuit construction, in: Proceedings of Symposium on Information Theory in the Benelux, 2006.

34.

Kolesnikov and

Kumaresan , Improved OT extension for transferring short secrets, in: Advances in Cryptology – CRYPTO, 2013.

35.

Kolesnikov and

Schneider , Improved garbled circuit: Free xor gates and applications, in: Proceedings of the International Colloquium on Automata, Languages and Programming, Part II, 2008.

36.

Kreuter ,

Mood ,

shelat and

Butler , PCF: A portable circuit format for scalable two-party secure computation, in: Proceedings of the USENIX Security Symposium, 2013.

37.

Kreuter ,

shelat and

C.-H.

Shen , Billion-gate secure computation with malicious adversaries, in: Proceedings of the USENIX Security Symposium, 2012.

38.

Kruger ,

Jha ,

E.-J.

Goh and

Boneh , Secure function evaluation with ordered binary decision diagrams, in: Proceedings of the ACM Conference on Computer and Communications Security, 2006.

39.

Lindell , Lower bounds and impossibility results for concurrent self composition, Journal of Cryptology 21(2) (2008), 200–249.

40.

Lindell , Fast cut-and-choose based protocols for malicious and covert adversaries, in: Advances in Cryptology – CRYPTO, 2013.

41.

Lindell and

Pinkas , Privacy preserving data mining, in: Advances in Cryptology – CRYPTO, 2000.

42.

Lindell and

Pinkas , An efficient protocol for secure two-party computation in the presence of malicious adversaries, in: Advances in Cryptology – EUROCRYPT, 2007.

43.

Lindell and

Pinkas , Secure two-party computation via cut-and-choose oblivious transfer, in: Proceedings of the Conference on Theory of Cryptography, 2011.

44.

López-Alt ,

Tromer and

Vaikuntanathan , On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption, in: Proceedings of the Symposium on Theory of Computing, 2012.

45.

Malka , Vmcrypt: Modular software architecture for scalable secure computation, in: Proceedings of the 18th ACM Conference on Computer and Communications Security, 2011.

46.

Malkhi ,

Nisan ,

Pinkas and

Sella , Fairplay – A secure two-party computation system, in: Proceedings of the USENIX Security Symposium, 2004.

47.

Matsumoto ,

Kato and

Imai , Speeding up secret computations with insecure auxiliary devices, in: Advances in Cryptology – CRYPTO, 1988.

48.

Mohassel and

Franklin , Efficiency tradeoffs for malicious two-party computation, in: Proceedings of the Public Key Cryptography Conference, 2006.

49.

Mood ,

Gupta ,

Butler and

Feigenbaum , Reuse it or lose it: More efficient secure computation through reuse of encrypted values, in: Proceedings of the ACM Conference on Computer and Communications Security (CCS), 2014.

50.

Mood ,

Letaw and

Butler , Memory-efficient garbled circuit generation for mobile devices, in: Proceedings of the IFCA International Conference on Financial Cryptography and Data Security, 2012.

51.

Naor and

Pinkas , Oblivious transfer and polynomial evaluation, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1999.

52.

Naor and

Pinkas , Efficient oblivious transfer protocols, in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.

53.

Naor ,

Pinkas and

Sumner , Privacy preserving auctions and mechanism design, in: Proceedings of the ACM Conference on Electronic Commerce, 1999.

54.

J.B.

Nielsen ,

P.S.

Nordholt ,

Orlandi and

S.S.

Burra , A new approach to practical active-secure two-party computation, in: Advances in Cryptology – CRYPTO, 2012.

55.

Nipane ,

Dacosta and

Traynor , “Mix-in-place” anonymous networking using secure function evaluation, in: Proceedings of the Annual Computer Security Applications Conference, 2011.

56.

Osadchy ,

Pinkas ,

Jarrous and

Moskovich , Scifi – A system for secure face identification, in: Proceedings of the IEEE Symposium on Security and Privacy, 2010.

57.

Peikert ,

Vaikuntanathan and

Waters , A framework for efficient and composable oblivious transfer, in: Advances in Cryptology – CRYPTO, 2008.

58.

Rash , Dropbox password breach highlights cloud security weaknesses, 2012, available at: http://www.eweek.com/c/a/Security/Dropbox-Password-Breach-Highlights-Cloud-Security-Weaknesses-266215/.

59.

Schneider and

Zohner , GMW vs. Yao? Efficient secure two-party computation with low depth circuits, in: Proceedings of the IFCA International Conference on Financial Cryptography and Data Security, 2013.

60.

shelat and

C.-H.

Shen , Two-output secure computation with malicious adversaries, in: Advances in Cryptology – EUROCRYPT, 2011.

61.

Thomas , Microsoft cloud data breach heralds things to come, 2010, available at: http://www.pcworld.com/article/214775/microsoft_cloud_data_breach_sign_of_future.html.

62.

D.P.

Woodruff , Revisiting the efficiency of malicious two-party computation, in: Advances in Cryptology – EUROCRYPT, 2007.

63.

A.C.

Yao , Protocols for secure computations, in: Proceedings of the Annual Symposium on Foundations of Computer Science, 1982.

Secure outsourced garbled circuit evaluation for mobile devices

Abstract

Keywords

1. Introduction

2. Related work

3. Assumptions and definitions

3.1. Non-collusion with the cloud

3.3. Malleable claw-free collections

Definition 2 (Claw-free collections [17,60]).

Definition 3 (Malleable claw-free collection [60]).

3.4. Model and definitions

4.1. Participants

4.3. Outsourced protocol

Phase 1 (Circuit generation and checking).

Phase 3 (Generator input consistency check).

Phase 4 (Circuit evaluation).

Phase 5 (Output check and delivery).

4.4. Asymptotic evaluation

Table 1 Asymptotic analysis of the operations required on the mobile device for each outsourcing protocol Protocol SYM GROUP OT CMTB O ( | a | ) O ( λ ( | b | + | f A ( a , b ) | ) ) k Salus O ( λ ( | a | + | b | + | f A ( a , b ) | ) ) – –

5.1. Garbled circuit generation

Claim 1 (Security).

Claim 2 (Proof-of-work).

5.2. Validity of evaluator inputs

5.3. Input consistency

5.5. Outsourced oblivious transfer

6. Proof of security

7.1. Framework and testbed

7.2. Execution time

8. Evaluating large circuits

Table 2 Bandwidth of 128-bit RSA and Dijkstra 20, 50, and 100 32 circuits 64 circuits 128 circuits RSA128 334,629 672,067 1,346,943 Dijkstra20 3,862,280 7,770,598 15,587,234 Dijkstra50 9,575,622 19,266,732 38,648,952 Dijkstra100 19,087,192 38,405,622 77,042,482

Footnotes

Acknowledgments

Experimental results

References

Table 1
Asymptotic analysis of the operations required on the mobile device for each outsourcing protocol

Protocol SYM GROUP OT

CMTB $O (| a |)$ $O (λ (| b | + | f_{A} (a, b) |))$ k

Salus $O (λ (| a | + | b | + | f_{A} (a, b) |))$ – –

Table 2
Bandwidth of 128-bit RSA and Dijkstra 20, 50, and 100

32 circuits 64 circuits 128 circuits

RSA128 334,629 672,067 1,346,943

Dijkstra20 3,862,280 7,770,598 15,587,234

Dijkstra50 9,575,622 19,266,732 38,648,952

Dijkstra100 19,087,192 38,405,622 77,042,482