New Techniques for Private Function Evaluation

Seyed Saeed Sadeghian

Published Jan 1, 2015• 4 citations

Abstract

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).

DOI: 10.11575/prism/27099

Related papers

How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation.

Payman Mohassel, Seyed Saeed Sadeghian

We revisit the problem of general-purpose private function evaluation (PFE) wherein a single party P1 holds a circuit C, while each Pi for 1 ≤ i ≤ n holds a private input xi, and the goal is for a subset (or all) of the parties to learn C(x1,..., xn) but nothing else. We put forth a general framework for designing PFE where the task of hiding the circuit and securely evaluating its gates are addressed independently: First, we reduce the task of hiding the circuit topology to oblivious evaluation of a mapping that encodes the topology of the circuit, which we refer to as oblivious extended permutation (OEP) since the mapping is a generalization of the permutation mapping. Second, we design a subprotocol for private evaluation of a single gate (PFE for one gate), which we refer to as private gate evaluation (PGE). Finally, we show how to naturally combine the two components to obtain efficient and secure PFE. We apply our framework to several well-known general-purpose MPC constructions, in each case, obtaining the most efficient PFE construction to date, for the considered setting. Similar to the previous work we only consider semi-honest adversaries in this paper. • In the multiparty case with dishonest majority, we apply our techniques to the seminal GMW protocol [GMW87] and obtain the first general-purpose PFE with linear complexity in the circuit

Jan 1, 20130 citations

Actively Secure Private Function Evaluation.

Payman Mohassel, Seyed Saeed Sadeghian, Nigel Paul Smart

Abstract. We propose the first general framework for designing actively secure private function eval-uation (PFE), not based on universal circuits. Our framework is naturally divided into pre-processing and online stages and can be instantiated using any generic actively secure multiparty computation (MPC) protocol. Our framework helps address the main open questions about efficiency of actively secure PFE. 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(g · log g) complexity where g is the circuit size. The best previous construction (of practical interest) is based on an arithmetic universal circuit and has complexity O(g5). We also introduce the first linear Zero-Knowledge proof of correctness of “extended permutation ” of ciphertexts (a generalization of ZK proof of correct shuffles) which maybe of independent interest.

Jan 1, 20140 citations

Improving scalability of universal circuits for large-scale private function evaluation

Masaud Y. Alhassan

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..

Mar 1, 20180 citations

Constant-Round Private Function Evaluation with Linear Complexity.

Jonathan I. Katz, Lior Malka

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

Jan 1, 20100 citations

Efficient and secure schemes for private function evaluation

Muhammed Ali Bingöl

Development of computing devices with the proliferation of the Internet has prompted enormous opportunities for cooperative computation. These computations could occur between trusted or partially trusted partners, or even between competitors. Secure multi-party computation (MPC) protocols allow two or more parties to collaborate and compute a public functionality using their private inputs without the need for a trusted third-party. However, the generic solutions for MPC are not adequate for some particular cases where the function itself is also sensitive and required to be kept private. Private function evaluation (PFE) is a special case of MPC, where the function to be computed is known by only one party. PFE is useful in several real-life applications where an algorithm or a function itself needs to remain secret for reasons such as protecting intellectual property or security classification level. Recently, designing efficient PFE protocols have been a challenging and attractive task for cryptography researchers. iv In this dissertation, we mainly focus on improving two-party private function evaluation (2PFE) schemes. Our primary goal is enhancing the state-of-the-art by designing secure and cost-efficient 2PFE protocols for both symmetric and asymmetric cryptography based solutions. In this respect, we first aim to improve 2PFE protocols based on (mostly) symmetric cryptographic primitives. We look back at the seminal PFE framework presented by Mohassel and Sadeghian at Eurocrypt'13. We show how to adapt and utilize the well-known half gates garbling technique (Zahur et al., Eurocrypt'15) to their constant round 2PFE scheme. Compared to their scheme, our resulting optimization significantly improves both underlying oblivious extended permutation (OEP) and secure 2-party computation (2PC) protocols, and yields a more than 40% reduction in overall communication cost. We next propose a novel and highly efficient 2PFE scheme based on the decisional Di e-Hellman (DDH) assumption. Our scheme consists of two protocols, one is utilized in the initial execution, and the other is in the subsequent runs. One of the novelties of our scheme over the state-of-the-art is that it results in a significant cost reduction when the same private function is evaluated more than once between the same or varying parties. To the best of our knowledge, this is the most efficient and the first 2PFE scheme that enjoys reusability feature. Our protocols achieve linear communication and computation complexities, and a constant number of rounds which is at most three (depending on the size of the inputs of the party that holds the function).

Jan 4, 20192 citations

Generalizing Semi-Private Function Evaluation

Bieber, Julian

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 . . .

Oct 1, 20160 citations