Secure function evaluation (SFE) allows a set of mutually distrustful parties to evaluate a function of their joint inputs without revealing their inputs to each other. SFE has been the focus of active research and recent work suggests that it can be made practical. Unfortunately, current protocols and implementations have inherent limitations that are hard to overcome using standard and practical techniques. Among them are: (1) requiring participants to do work linear in the size of the circuit representation of the function; (2) requiring all parties to do the same amount of work; and (3) not being able to provide complete fairness.
Secure function evaluation (SFE) allows a set of mutually distrustful parties to evaluate a function of their joint inputs without revealing their inputs to each other. SFE has been the focus of active research and recent work suggests that it can be made practical. Unfortunately, current protocols and implementations have inherent limitations that are hard to overcome using standard and practical techniques. Among them are: (1) requiring participants to do work linear in the size of the circuit representation of the function; (2) requiring all parties to do the same amount of work; and (3) not being able to provide complete fairness.
Secure function evaluation (SFE) allows a set of mutually distrustful parties to evaluate a function of their joint inputs without revealing their inputs to each other. SFE has been the focus of active research and recent work suggests that it can be made practical. Unfortunately, current protocols and implementations have inherent limitations that are hard to overcome using standard and practical techniques. Among them are: (1) requiring participants to do work linear in the size of the circuit representation of the function; (2) requiring all parties to do the same amount of work; and (3) not being able to provide complete fairness. A promising approach for overcoming these limitations is to augment the SFE setting with a small set of untrusted servers that have no input to the computation and that receive no output, but that make their computational resources available to the parties. In this model, referred to as server-aided SFE, the goal is to tradeoff the parties ’ work at the expense of the servers. Motivated by the emergence of public cloud services such as Amazon EC2 and Microsoft Azure, recent work has explored the extent to which server-aided SFE can be achieved with a single server. In this work, we revisit the sever-aided setting from a practical perspective and design singleserver-aided SFE protocols that are considerably more efficient than all previously-known protocols. We achieve this in part by introducing several new techniques for garbled-circuit-based protocols, including a new and efficient input-checking mechanism for cut-and-choose and a new pipelining technique that works in the presence of malicious adversaries. Furthermore, we extend the serveraided model to guarantee fairness which is an important property to achieve in practice. Finally, we implement and evaluate our constructions experimentally and show that our protocols (regardless of the number of parties involved) yield implementations that are 4 and 6 times faster than the most optimized two-party SFE implementation when the server is assumed to be malicious and covert, respectively.
General two-party Secure Function Evaluation (SFE) allows mutually distrusting parties to (jointly) correctly compute any function on their private input data, without revealing the inputs. SFE, properly designed, guarantees to satisfy the most stringent security requirements, even for interactive computation. Two-party SFE can benefit almost any client-server interaction where privacy is required, such as privacy-preserving credit checking, medical classification, or face recognition. Today, SFE is subject of an immense amount of research in a variety of directions, and is not easy to navigate. In this paper, we systematize the most practically important work of the vast research knowledge on general SFE. It turns out that the most efficient SFE protocols today are obtained by combining several basic techniques, such as garbled circuits and homomorphic encryption. We limit our detailed discussion to efficient general techniques. In particular, we do not discuss the details of currently practically inefficient techniques, such as fully homomorphic encryption (although we elaborate on its practical relevance), nor do we cover specialized techniques applicable only to small classes of functions. As an important practical contribution, we present a framework in which today’s practically most
Secure function evaluation (SFE) is an area of cryptography concerned with the design of algorithms that allow mutually distrustful partners to evaluate desired functions on their inputs, while maximally preserving input privacy. With faster computers and networks, and continuous algorithm improvements, SFE has become within reach of practicality. The first large-scale industrial application of SFE—the result of over 20 years of relevant research—has been successfully completed in Denmark, where SFE was used to run a country-wide secure sugar beets auction. In this paper, we will provide a brief overview of SFE, the problem it solves, and its uses. We will describe several recent research advancements and argue that SFE is “the next big thing.”
General two-party Secure Function Evaluation (SFE) allows mutually distrusting parties to correctly compute any function on their private input data, without revealing the inputs. Two-party SFE can benefit almost any client-server interaction where privacy is required, such as privacy-preserving credit checking, medical classification, or face recognition. Today, SFE is a subject of immense amount of research in a variety of directions and is not easy to navigate. In this article, we systematize the most practically important works of the vast research knowledge on general SFE. We argue that in many cases the most efficient SFE protocols are obtained by combining several basic techniques, e.g., garbled circuits and (additively) homomorphic encryption. As a valuable methodological contribution, we present a framework in which today's most efficient techniques for general SFE can be viewed as building blocks with well-defined interfaces that can be easily combined into a complete efficient solution. Further, our approach naturally allows automated protocol generation (compilation) and has been implemented partially in the TASTY framework. In summary, we provide a comprehensive guide in state-of-the-art SFE, with the additional goal of extracting, systematizing and unifying the most relevant and promising general SFE techniques. Our target audience are graduate students wishing to enter the SFE field and advanced engineers seeking to develop SFE solutions. We hope our guide paints a high-level picture of the field, including most common approaches and their trade-offs and gives precise and numerous pointers to formal treatment of its specific aspects.
This thesis focuses on practical aspects of general two-party Secure Function Evaluation (SFE). We give a new SFE protocol that allows free evaluation of XOR gates and is provably secure against semi-honest adversaries in the random oracle model. Furthermore, the extension of SFE to private functions (PF-SFE) using universal circuits (UC) is considered. Based on our new practical UC construction, FairplayPF is implemented as extension of the well-known Fairplay SFE system to demonstrate practicability of UC-based PF-SFE. Also new protocols for SFE and PF-SFE of functions alternatively represented as Ordered Binary Decision Diagram (OBDD) are given.