Secure two-party computation, called Secure Function Evaluation (SFE), enables two mutually mistrusting parties (client & server) to evaluate an arbitrary function $f$ on their respective private inputs $x,y$ while revealing nothing but the result $z=f(x,y)$. Although such generic techniques were widely believed to be inefficient, the rapidly growing speed of computers and communication networks, algorithmic improvements, automatic generation and optimizations of SFE protocols have made them usable in practical application scenarios.
This thesis presents the following advances in the design, optimization and applications of efficient SFE protocols.
Circuit Optimizations and Constructions.
The complexity of today's most efficient SFE protocols depends linearly on the size of the boolean circuit representation of the evaluated function. Further, recent techniques for SFE based on improved Garbled Circuits (GCs) allow for very efficient secure evaluation of XOR gates.
We give transformations that substantially reduce the size of boolean circuits if the costs for evaluating XOR gates are lower than for other types of gates. Our optimizations provide more efficient circuits for standard functionalities such as integer comparison and fast multiplication.
Applications that benefit from our improvements are secure first-price auctions.
Hardware-Assisted GC Protocols.
We improve the deployability of SFE protocols by using tamper-proof Hardware (HW) tokens.
In particular, GCs can be generated by a tamper-proof HW token which is provided by the server to a client but not trusted by the client. The presented HW-assisted SFE protocol makes the communication between client and server independent of the size of the evaluated function. Further, we show how GCs can be evaluated in HW in a leakage resilient way, so-called One-Time Programs.
As application we show how the combination of GCs and tamper-proof HW allows to securely outsource data to an untrusted cloud service provider such that arbitrary functions can be computed securely on the data with low latency.
Modular Design of Efficient SFE Protocols.
Automatic generation of SFE protocols from high-level specifications makes SFE usable for application programmers and yields less error-prone implementations.
We present a framework which enables to modularly design efficient SFE protocols as sequence of operations on encrypted data. In our framework, efficient SFE protocols based on Homomorphic Encryption and GCs can be combined while abstracting from the underlying cryptographic details.
Our corresponding language and tool, called Tool for Automating Secure Two-partY computations (TASTY), allow to describe, automatically generate, execute, and benchmark such modular and efficient SFE protocols.
As application we show efficient protocols for privacy-preserving face recognition.