Private Function Evaluation (PFE) allows two parties to compute a function f (x) based on their private inputs, where one party provides the function f and the other party provides the input x without either party knowing about the other's input, therefore preserving privacy.Secure Function Evaluation allows two parties to compute a global function f (x, y) based on their private inputs x and y.A Universal Circuit (UC) is a globally known structure that can simulate functions.We can therefore achieve PFE using SFE by making the UC global and providing it with private inputs f and x from the two parties.The UC is a structure made up of nodes which have to be programmed (setting control bits for each node) according to the function it has to simulate.Valiant proposed the first Universal Circuit (UC) constructions, which are recursive and use either 2-way or 4-way recursion split methods (STOC'76).The most recent UC implementation based on Valiant's 4-way UC construction was realized by Günther et al (ASIACRYPT'17), which is also modular.Lipmaa et al. generalized a k-way UC construction which is depicted in a modular manner (Eprint 2016/017).Günther et al. prove that their modular 4-way split UC construction outperforms the 2-way split UC construction by Kiss and Schneider, that is, results in asymptotically smaller UCs.Though being modular, this UC construction stores every internal state of the algorithm in memory and therefore, memory becomes a bottleneck.For this reason, this construction cannot be used in practice for large-scale UC applications.We introduce a scalable approach of UC generation based on Günther et al.'s modular 4-way split UC generation.Our approach leverages the file system storage with very little use of memory and can yield UC sizes in the orders of billion.Also, multiple instances of our UC implementation can be run in parallel on big machines, which was not possible or reasonable to do in older UC implementations.We show our scalable file-based UC generation which makes it extremely intuitive to perform the next step: the programming of the UC.With this scalability, we can realize large-scale PFE applications, for instance remote diagnostics of smart cars for autonomous driving, remote diagnostics of cars for automobile insurance, home automation and remote patient monitoring.Users of the aforementioned applications will no longer be concerned with sharing sensitive data to owners of the applications. d . PFE Applications of Universal CircuitsWe mention some PFE applications of UCs in this section with referral to [KS16] for more details.Private Function Evaluation with UC allows for easy integration into existing SFE frameworks.For instance, using outsource SFE to outsource UC-based PFE [KR11].[BPSW07] shows privacy-preserving evaluation of diagnostic programs, where the owner of the program does not want to reveal the diagnostic method and the user does not want to reveal his data.Medical systems [BFK+09] and remote software fault diagnosis are both examples of such programs, where in both cases privacy-preserving is desired for the function and the user's input.Remote streaming data can be obliviously filtered using secret keywords [OI05], from 1 which data privacy can be preserved by using PFE to search the matching data with a private search function..
Private Function Evaluation (PFE) allows two parties to compute a function f (x) based on their private inputs, where one party provides the function f and the other party provides the input x without either party knowing about the other's input, therefore preserving privacy.Secure Function Evaluation allows two parties to compute a global function f (x, y) based on their private inputs x and y.A Universal Circuit (UC) is a globally known structure that can simulate functions.We can therefore achieve PFE using SFE by making the UC global and providing it with private inputs f and x from the two parties.The UC is a structure made up of nodes which have to be programmed (setting control bits for each node) according to the function it has to simulate.Valiant proposed the first Universal Circuit (UC) constructions, which are recursive and use either 2-way or 4-way recursion split methods (STOC'76).The most recent UC implementation based on Valiant's 4-way UC construction was realized by Günther et al (ASIACRYPT'17), which is also modular.Lipmaa et al. generalized a k-way UC construction which is depicted in a modular manner (Eprint 2016/017).Günther et al. prove that their modular 4-way split UC construction outperforms the 2-way split UC construction by Kiss and Schneider, that is, results in asymptotically smaller UCs.Though being modular, this UC construction stores every internal state of the algorithm in memory and therefore, memory becomes a bottleneck.For this reason, this construction cannot be used in practice for large-scale UC applications.We introduce a scalable approach of UC generation based on Günther et al.'s modular 4-way split UC generation.Our approach leverages the file system storage with very little use of memory and can yield UC sizes in the orders of billion.Also, multiple instances of our UC implementation can be run in parallel on big machines, which was not possible or reasonable to do in older UC implementations.We show our scalable file-based UC generation which makes it extremely intuitive to perform the next step: the programming of the UC.With this scalability, we can realize large-scale PFE applications, for instance remote diagnostics of smart cars for autonomous driving, remote diagnostics of cars for automobile insurance, home automation and remote patient monitoring.Users of the aforementioned applications will no longer be concerned with sharing sensitive data to owners of the applications. d . PFE Applications of Universal CircuitsWe mention some PFE applications of UCs in this section with referral to [KS16] for more details.Private Function Evaluation with UC allows for easy integration into existing SFE frameworks.For instance, using outsource SFE to outsource UC-based PFE [KR11].[BPSW07] shows privacy-preserving evaluation of diagnostic programs, where the owner of the program does not want to reveal the diagnostic method and the user does not want to reveal his data.Medical systems [BFK+09] and remote software fault diagnosis are both examples of such programs, where in both cases privacy-preserving is desired for the function and the user's input.Remote streaming data can be obliviously filtered using secret keywords [OI05], from 1 which data privacy can be preserved by using PFE to search the matching data with a private search function..
In this thesis, we study the problem of general-purpose private function evaluation (PFE) wherein a single party P1 holds a circuit C, while each Pi for 1<=i<=m holds a private input xi, and the goal is for a subset (or all) of the parties to learn C(x1,…,xm) but nothing else. We pursue the design of PFE with better concrete and/or asymptotic complexity for a variety of settings. We put forth a general framework for designing PFE as the first alternative general approach to universal circuits. In this framework, the task of hiding the circuit topology and securely evaluating its gates are addressed independently through two functionalities we call CTH (Circuit Topology Hiding) and PGE (Private Gate Evaluation). We instantiate our framework using the building blocks of several well-known general MPC constructions, obtaining more efficient PFE than prior work for two-party PFE, multi-party PFE and PFE for arithmetic circuits. Next, we propose the first general framework for designing actively secure PFE, not based on universal circuits. On the theoretical side, our framework yields the first actively secure PFE with linear complexity in the circuit size. On the practical side, we obtain the first actively secure PFE for arithmetic circuits with O(glogg) complexity where g is the circuit size, significantly improving over previous constructions with complexity O(g^5). Despite its inefficiency, we identify various advantages for PFE based on universal circuits. Valiant's construction (STOC 1976) yields universal circuits with the optimal asymptotic complexity, and has been employed in several recent works. But somewhat surprisingly, no implementations of the construction exist. We look back at this construction, and provide a more approachable description. This enables us to provide constant factor improvements and the first implementation. A more accurate comparison made possible through our implementation shows that the improved Valiant's UC performs better than the theoretical estimate, and in fact is almost always smaller than the UC construction of Kolesnikov and Schneider (FC 2008). We also observe, for the first time, that the same construction can be adapted to yield size-optimized universal arithmetic circuits (UAC).
The cryptographic primitive Secure Function Evaluation (SFE) enables the evaluation of a function public function f (x, y), under input parameters that are provided by different parties without them revealing their specific value.Restricting SFE further by requiring the function to be only known by one party is called Private Function Evaluation (PFE).Furthermore Semi-Private Function Evaluation (SPF-SFE) can help to increase the maximum function size which can be evaluated in a somewhat private manner.One way to achieve SPF-SFE is to split the function into blocks, as was shown in [PSS09].However their implementation was crafted specifically for Yao's garbled Circuit protocol.Therefore there are protocols, namely Goldreich-Micali-Wigderson (GMW), by which it could not be evaluated.We provide circuit designs for different Privately Programmable Blocks, which are constructed to work with the GMW protocol as well.Additionally we provide a toolchain to achieve SPF-SFE efficiently.Furthermore we implemented a tool used in the toolchain, which uses the aforementioned designs and can combine them with plain circuits and Universal Circuits (UCs) to build a single programmable circuit.A function designer can use the toolchain to balance out his needs for function privacy with performance.Contents 5.2.4 Combined Circuits . . .
We consider the problem of private function evaluation (PFE) in the two-party setting. Here, informally, one party holds an input x while the other holds a circuit describing a function f; the goal is for one (or both) of the parties to learn f(x) while revealing nothing more to either party. In contrast to the usual setting of secure computation — where the function being computed is known to both parties — PFE is useful in settings where the function (i.e., algorithm) itself must remain secret, e.g., because it is proprietary or classified. It is known that PFE can be reduced to standard secure computation by having the parties evaluate a universal circuit, and this is the approach taken in most prior work. Using a universal circuit, however, introduces additional overhead and results in a more complex implementation. We show here a completely new technique for PFE that avoids universal circuits, and results in constant-round protocols with communication/computational complexity linear in the size of the circuit computing f. This gives the first constant-round protocol for PFE with linear complexity (without using fully homomorphic encryption), even restricted to semi-honest adversaries. 1
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.
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