Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Generalizing Semi-Private Function Evaluation

Bieber, Julian

Published Oct 1, 2016• 0 citations
OpenAlex

Abstract

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

Related papers

A systematic approach to practically efficient general two-party secure function evaluation protocols and their modular design

Vladimir Kolesnikov, Ahmad‐Reza Sadeghi, Thomas H. Schneider

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.

Journal of Computer Security•Mar 1, 2013•37 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, 2018•0 citations

New Techniques for Private Function Evaluation

Seyed Saeed Sadeghian

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

•Jan 1, 2015•4 citations

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, 2013•0 citations

From Dust to Dawn: Practically Efficient Two-Party Secure Function Evaluation Protocols and their Modular Design.

Vladimir Kolesnikov, Ahmad‐Reza Sadeghi, Thomas H. Schneider

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

•Jan 1, 2010•28 citations

Outsourcing computation for private function evaluation

Henry Carter, Patrick Traynor

Outsourced secure multiparty computation (SMC) protocols allow resource-constrained devices to execute input-private computation with great efficiency. Unfortunately, existing outsourced SMC protocols require that all parties know the function being evaluated, precluding applications where the function itself must remain private. We develop the first linear-complexity protocols for outsourcing private function evaluation (PFE), SMC protocols that provide input and function privacy. Assuming a semi-honest function holder, we build on existing two-party PFE constructions to develop outsourced protocols that are secure against a semi-honest, covert, or malicious outsourcing server and malicious mobile participants. To do this, we develop a garbling technique for combining public and private sub-circuits in a single computation. This allows us to apply auxiliary checks for malicious behaviour using only free-XOR gates. These protocols demonstrate the feasibility of outsourced PFE and provide a first step towards privacy-preserving applications for use in cloud computing.

International Journal of Information and Computer Security•Jan 1, 2019•1 citation
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 . . .
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.
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).
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
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
Outsourced secure multiparty computation (SMC) protocols allow resource-constrained devices to execute input-private computation with great efficiency. Unfortunately, existing outsourced SMC protocols require that all parties know the function being evaluated, precluding applications where the function itself must remain private. We develop the first linear-complexity protocols for outsourcing private function evaluation (PFE), SMC protocols that provide input and function privacy. Assuming a semi-honest function holder, we build on existing two-party PFE constructions to develop outsourced protocols that are secure against a semi-honest, covert, or malicious outsourcing server and malicious mobile participants. To do this, we develop a garbling technique for combining public and private sub-circuits in a single computation. This allows us to apply auxiliary checks for malicious behaviour using only free-XOR gates. These protocols demonstrate the feasibility of outsourced PFE and provide a first step towards privacy-preserving applications for use in cloud computing.