TinyGarble: Efficient, Scalable, and Versatile Privacy-Preserving Computation Through Sequential Garbled Circuit
Mohammadgholi Songhori, Ebrahim
Koushanfar, Farinaz; Cavallaro, Joseph
Doctor of Philosophy
Privacy-preserving computation is a standing challenge central to several modern-world applications which require computing on sensitive data. Secure Function Evaluation (SFE) refers to provably secure techniques aiming to address this problem by enabling multiple parties to compute an arbitrary function jointly on their private inputs. The most promising two-party SFE method is called the Garbled Circuit (GC) protocol introduced by Andrew Yao. The protocol relays on representing the function as a Boolean circuit and encrypting/communicating at the logic gate level. Despite several significant improvements in GC, efficiency, scalability and ease-of-use of the available methods are limited by the naive circuit representation as a directed acyclic graph, ad-hoc logic optimizations, and custom compilers. In this thesis, we proposed a holistic solution to enhance the efficiency, scalability, and simplicity of the GC protocol. Our approach has three main pillars to address these key challenges: GC synthesis, sequential GC, and garbled processor. The GC synthesis is a novel automated methodology based on logic synthesis techniques for generating optimized Boolean circuits for the GC protocol. Using sequential GC, we achieve an unprecedented level of compactness and scalability using sequential circuit descriptions. We combine GC synthesis and sequential GC in an open-source framework called TinyGarble. The preliminary implementation of benchmark functions using TinyGarble demonstrates a high degree of memory-footprint compactness as well as improvement in overall efficiency compared to results of existing tools. Our sequential description also enables us, for the first time, to design and realize a garbled processor to reduce the problem of private function evaluation to a conventional SFE problem. In addition, the garbled processor allows users to develop SFE applications in high-level languages (e.g., C) and eliminates the need for Boolean circuit generation. We present ARM2GC, a garbled processor framework based on TinyGarble and the ARM processor. It allows users to develop GC applications using high-level programming languages with comparable efficiency to the best previous results. The primary enabler to make this construction practical and efficient is the introduction of SkipGate, a new algorithm that omits the communication cost of a Boolean gate when its output is independent of the private data. Benchmark evaluations demonstrate efficiency and usability of ARM2GC compared with the prior art in high-level GC compilation.
Privacy-Preserving Computation; Logic Synthesis; Garbled Circuit; Secure Function Evaluation; Logic Design