Recent compilers allow a general-purpose program (written in a conventional programming language) that handles private data to be translated into secure distributed implementation of the corresponding functionality. The resulting program is then guaranteed to provably protect private data using secure multi-party computation techniques. The goals of such compilers are generality, usability, and efficiency, but the complete set of features of a modern programming language has not been supported to date by the existing compilers. In particular, recent compilers PICCO and the two-party ANSI C compiler strive to translate any C program into its secure multi-party implementation, but currently lack support for pointers and dynamic memory allocation, which are important components of many C programs. In this work, we mitigate the limitation and add support for pointers to private data and consequently dynamic memory allocation to the PICCO compiler, enabling it to handle a more diverse set of programs over private data. Because doing so opens up a new design space, we investigate the use of pointers to private data (with known as well as private locations stored in them) in programs and report our findings. Besides dynamic memory allocation, we examine other important topics associated with common pointer use such as reference by pointer address, casting, and building various data structures in the context of secure multi-party computation. This results in enabling the compiler to automatically translate a user program that uses pointers to private data into its distributed implementation that provably protects private data throughout the computation. We empirically evaluate the constructions and report on performance of representative programs.
Universal circuits UCs can be programmed to evaluate any circuit of a given size k. They provide elegant solutions in various application scenarios, e.g. for private function evaluationi¾?PFE and for improving the flexibility of attribute-based encryptioni¾?ABE schemes. The optimal size of a universal circuit is proven to be @math Ωklogk. Valianti¾?STOC'76 proposed a size-optimized UC construction, which has not been put in practice ever since. The only implementation of universal circuits was provided by Kolesnikov and Schneider FC'08, with sizei¾? @math Oklog2k. In this paper, we refine the size of Valiant's UC and further improve the construction by at least 2k. We show that due to recent optimizations and our improvements, it is the best solution to apply in the case for circuits with a constant number of inputs and outputs. When the number of inputs or outputs is linear in the number of gates, we propose a more efficient hybrid solution based on the two existing constructions. We validate the practicality of Valiant's UC, by giving an example implementation for PFE using these size-optimized UCs. We present GarbledCPU, the first framework that realizes a hardware-based general purpose sequential processor for secure computation. Our MIPS-based implementation enables development of applications (functions) in a high-level language while performing secure function evaluation (SFE) using Yao's garbled circuit protocol in hardware. GarbledCPU provides three degrees of freedom for SFE which allow leveraging the trade-off between privacy and performance: public functions, private functions, and semi-private functions. We synthesize GarbledCPU on a Virtex-7 FPGA as a proof-of-concept implementation and evaluate it on various benchmarks including Hamming distance, private set intersection and AES. Our results indicate that our pipelined hardware framework outperforms the fastest available software implementation.