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).
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..
The area of "computing with encrypted data" has been studied by numerous authors in the past twenty years since it is fundamental to understanding properties of encryption and it has many practical applications. The related fundamental area of "secure function evaluation" has been studied since the mid 80's. In its basic two-party case, two parties (Alice and Bob) evaluate a known circuit over private inputs (or a private input and a private circuit). Much attention has been paid to the important issue of minimizing rounds of computation in this model. Namely, the number of communication rounds in which Alice and Bob need to engage in to evaluate a circuit on encrypted data securely. Advancements in these areas have been recognized as open problems and have remained open for a number of years. In this paper we give a one round, and thus round optimal, protocol for secure evaluation of circuits which is in polynomial time for NC/sup 1/ circuits. The protocol involves an input party sending encrypted input to a second party, a cryptocomputer, which evaluates the circuit (or a known circuit over its additional private input) non-interactively, securely and obliviously, and provides the output to the input party without learning it. This improves on previous (general) results that are specialized to the case of NC/sup 1/ circuits and require a constant number of communication rounds. We further suggest applications to network and mobile computing.