Secure and Private Function Evaluation with Intel SGX

Secure function evaluation (SFE) allows two parties to jointly evaluate a publicly known function without revealing their respective inputs. SFE can be realized via well-known cryptographic protocols, such as Yao's garbled circuits (GC) and the protocol of Goldreich, Micali, and Wigderson (GMW), which obliviously evaluate a Boolean circuit representation of the function. Unfortunately, even with the most recent optimizations that touch known lower bounds, these protocols incur an impractical high communication overhead. In this work, we efficiently realize SFE by evaluating the function in a trusted execution environment (TEE), concretely the widely available Intel Software Guard Extensions (SGX). We address the unresolved issue of countless software side-channel vulnerabilities in a unique way, namely by evaluating Boolean circuits - as used by cryptographic SFE protocols - inside an Intel SGX enclave. This way, all possible paths of the function are executed and all memory accesses are guaranteed to be independent of the actual input data. The communication of our protocol depends only on the number of inputs and outputs (it is optimal up to an additive constant), but not on the circuit size (in contrast to Yao's GC and the GMW protocol). Furthermore, we are the first to also address efficient private function evaluation (PFE) via TEEs, where one of the parties provides a function that represents intellectual property and is computed obliviously on the other party's input. For realizing PFE, we securely evaluate universal circuits (UCs) that can be programmed via input bits to emulate any function up to a given size. We provide a prototype implementation of our SFE and PFE protocols based on Intel SGX. We empirically compare its performance to the ABY framework (Demmler et al., NDSS'15) that provides state-of-the-art implementations of Yao's GC and the GMW protocol as well as an adapter for evaluating UCs. For PFE with a UC emulating a circuit with 10000 gates (representing, e.g., a secret function to calculate individual car insurance rates), we improve the run-time by factor 2.3x over Yao's GC and by at least two orders of magnitude over the GMW protocol in a high-latency Internet setting. The communication is reduced by factors 106x and 131x compared to Yao's GC and the GMW protocol, respectively.