A protocol for two-party secure function evaluation (2P-SFE) aims to allow the parties to learn the output of function f of their private inputs, while leaking nothing more. In a sense, such a protocol realizes a trusted oracle that computes f and returns the result to both parties. There have been tremendous strides in efficiency over the past ten years, yet 2P-SFE protocols remain impractical for most real-time, online computations, particularly on modestly provisioned devices. Intel's Software Guard Extensions (SGX) provides hardware-protected execution environments, called enclaves, that may be viewed as trusted computation oracles. While SGX provides native CPU speed for secure computation, previous side-channel and micro-architecture attacks have demonstrated how security guarantees of enclaves can be compromised. In this paper, we explore a balanced approach to 2P-SFE on SGX-enabled processors by constructing a protocol for evaluating f relative to a partitioning of f. This approach alleviates the burden of trust on the enclave by allowing the protocol designer to choose which components should be evaluated within the enclave, and which via standard cryptographic techniques. We describe SGX-enabled SFE protocols (modeling the enclave as an oracle), and formalize the strongest-possible notion of 2P-SFE for our setting. We prove our protocol meets this notion when properly realized. We implement the protocol and apply it to two practical problems: privacy-preserving queries to a database, and a version of Dijkstra's algorithm for privacy-preserving navigation. Our evaluation shows that our SGX-enabled SFE scheme enjoys a 38x increase in performance over garbled-circuit-based SFE. Finally, we justify modeling of the enclave as an oracle by implementing protections against known side-channels.

Recent developments in secure computation have led to significant improvementsin efficiency and functionality. These efforts created compilers that form thebackbone of practical secure computation research. Unfortunately, many of theartifacts that are being used to demonstrate new research for secure computationare incomplete, incorrect, or unstable, leading to demonstrably erroneousresults and inefficiencies - extending even to the most recently developedcompiler systems. This is a problem because it hampers research and underminesfeasibility tests when other researchers attempt to use these tools. We addressthese problems and present Frigate, a principled compiler and fast circuitinterpreter for secure computation. To ensure correctness we apply bestpractices for compiler design and development, including the use of standarddata structures, helpful negative results, and structured validation testing. Our systematic validation tests include checks on the internal compiler state, combinations of operators, and edge cases based on widely used techniques anderrors we have observed in other work. This produces a compiler that buildscorrect circuits, is efficient and extensible. Frigate creates circuits withgate counts comparable to previous work, but does so with compile time speedupsas high as 447x compared with the best results from previous work in circuit compilers. By creating avalidated tool, our compiler will allow future secure computationimplementations to be developed quickly and correctly.

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.

Abstract Secure multiparty computation (SMC) offers a technique to preserve functionality and data privacy in mobile applications. Current protocols that make this costly cryptographic construction feasible on mobile devices securely outsource the bulk of the computation to a cloud provider. However, these outsourcing techniques are built on specific secure computation assumptions and tools, and applying new SMC ideas to the outsourced setting requires the protocols to be completely rebuilt and proven secure. In this work, we develop a generic technique for lifting any secure two‐party computation protocol into an outsourced two‐party SMC protocol. By augmenting the function being evaluated with auxiliary consistency checks and input values, we can create an outsourced protocol with low overhead cost. Our implementation and evaluation show that in the best case our outsourcing additions execute within the confidence intervals of two servers running the same computation and consume approximately the same bandwidth. In addition, the mobile device itself uses minimal bandwidth over a single round of communication. This work demonstrates that efficient outsourcing is possible with any underlying SMC scheme and provides an outsourcing protocol that is efficient and directly applicable to current and future SMC techniques. Copyright © 2016 John Wiley & Sons, Ltd.

Two-party secure-function evaluation (SFE) has become significantly more feasible, even on resource-constrained devices, because of advances in server-aided computation systems. However, there are still bottlenecks, particularly in the input-validation stage of a computation. Moreover, SFE research has not yet devoted sufficient attention to the important problem of retaining state after a computation has been performed so that expensive processing does not have to be repeated if a similar computation is done again. This paper presents PartialGC, an SFE system that allows the reuse of encrypted values generated during a garbled-circuit computation. We show that using PartialGC can reduce computation time by as much as 96% and bandwidth by as much as 98% in comparison with previous outsourcing schemes for secure computation. We demonstrate the feasibility of our approach with two sets of experiments, one in which the garbled circuit is evaluated on a mobile device and one in which it is evaluated on a server. We also use PartialGC to build a privacy-preserving ``friend-finder'' application for Android. The reuse of previous inputs to allow stateful evaluation represents a new way of looking at SFE and further reduces computational barriers.

As organizations become increasingly reliant on cloud computing for servicing their data storage requirements, the need to govern access control at finer granularities becomes particularly important. This challenge is increased by the lack of policy supporting data migration across geographic boundaries and through organizations with divergent regulatory policies. In this paper, we present an architecture for secure and distributed management of provenance, enabling its use in security-critical applications. Provenance, a metadata history detailing the derivation of an object, contains information that allows for expressive, policy-independent access control decisions. We consider how to manage and validate the metadata of a provenance-aware cloud system, and introduce protocols that allow for secure transfer of provenance metadata between end hosts and cloud authorities. Using these protocols, we develop a provenance-based access control mechanism for Cumulus cloud storage, capable of processing thousands of operations per second on a single deployment. Through the introduction of replicated components, we achieve overhead costs of just 14%, demonstrating that provenance-based access control is a practical and scalable solution for the cloud.