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

Lecture notes in computer science

Complexity of Multi-party Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

Published Jan 1, 2009• 50 citations
Publisher
DOI
10.1007/978-3-642-00457-5_16

Related papers

Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation.

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

In symmetric secure function evaluation (SSFE), Alice has an input x, Bob has an input y, and both parties wish to securely compute f(x, y). We show several new results classifying the feasibility of securely implementing these functions in several security settings. Namely, we give new alternate characterizations of the functions that have (statistically) secure protocols against passive and active (standalone), computationally unbounded adversaries. We also show a strict, infinite hierarchy of complexity for SSFE functions with respect to universally composable security against unbounded adversaries. That is, there exists a sequence of functions f1, f2,... such that there exists a UC-secure protocol for fi in the fj-hybrid world if and only if i ≤ j. The main new technical tool that unifies our unrealizability results is a powerful protocol simulation theorem, which may be of independent interest. Essentially, in any adversarial setting (UC, standalone, or passive), f is securely realizable if and only if a very simple (deterministic) “canonical ” protocol for f achieves the desired security. Thus, to show that f is unrealizable, one need simply demonstrate a single attack on a single simple protocol. 1

•Jan 1, 2008•1 citation

Cryptographic Complexity of Multi-Party Computation Problems: Classifications and Separations

Manoj Prabhakaran, Mike Rosulek

Lecture notes in computer science•Aug 20, 2008•37 citations

TOWARD LOWER COMMUNICATION IN GARBLED CIRCUIT EVALUATION

M. Ehsanpour

Secure Multi-party Computation (SMC) is a classical problem in theoretical security. In a SMC problem, two or more parties must compute correctly a function f on their respective inputs x and y, while preserving the privacy of their inputs and additional security properties. One of the approaches proposed for addressing the SMC problem relies on the design of Garbled Circuit (GC). In Garbled Circuits (GCs), the function to be computed is represented as a Boolean circuit composed of binary gates. The input and output wire of each gate is masked such that the party evaluating the Garbled Boolean Circuits (GBC) cannot gain any information about the inputs or the intermediate results that appear during the function evaluation. The complexity of today's most efficient GC protocol depends linearly on the size of the Boolean circuit representation of the evaluated function. The total cost and run-time interaction between parties increase linearly with the number of gates and can be huge for complex GBCs. Actually, interest has grown in the efficiency of this technique and in its applications to computation outsourcing in untrusted environments. A recent work shows that XOR gates in a Boolean circuit have no cost for the secure computation protocol. Therefore, circuits with a reduced number of non-XOR gates are more convenient and one of the possible ways to reduce the complexity of the computation is to reduce the number of non-XOR gates in the Boolean circuit. Recalling that, the main aim of this work is to reduce the number of non-XOR gates, which directly results in a reduced number of interactions between the parties and transfer complexity at runtime, we present different approaches for reducing the communication cost of Secure Multi-party Computation (SMC) and improving the overall computation time and efficiency of the execution of SMC.

•Feb 28, 2018•0 citations

Secure multi-party computation problems and their applications

Wenliang Kevin Du, Mikhail J. Atallah

New Security Paradigms Workshop•Jan 1, 2001•18 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, 2019•2 citations

Engineering Secure Two-Party Computation Protocols: Design, Optimization, and Applications of Efficient Secure Function Evaluation

Thomas H. Schneider

•Aug 4, 2012•25 citations
In symmetric secure function evaluation (SSFE), Alice has an input x, Bob has an input y, and both parties wish to securely compute f(x, y). We show several new results classifying the feasibility of securely implementing these functions in several security settings. Namely, we give new alternate characterizations of the functions that have (statistically) secure protocols against passive and active (standalone), computationally unbounded adversaries. We also show a strict, infinite hierarchy of complexity for SSFE functions with respect to universally composable security against unbounded adversaries. That is, there exists a sequence of functions f1, f2,... such that there exists a UC-secure protocol for fi in the fj-hybrid world if and only if i ≤ j. The main new technical tool that unifies our unrealizability results is a powerful protocol simulation theorem, which may be of independent interest. Essentially, in any adversarial setting (UC, standalone, or passive), f is securely realizable if and only if a very simple (deterministic) “canonical ” protocol for f achieves the desired security. Thus, to show that f is unrealizable, one need simply demonstrate a single attack on a single simple protocol. 1
Secure Multi-party Computation (SMC) is a classical problem in theoretical security. In a SMC problem, two or more parties must compute correctly a function f on their respective inputs x and y, while preserving the privacy of their inputs and additional security properties. One of the approaches proposed for addressing the SMC problem relies on the design of Garbled Circuit (GC). In Garbled Circuits (GCs), the function to be computed is represented as a Boolean circuit composed of binary gates. The input and output wire of each gate is masked such that the party evaluating the Garbled Boolean Circuits (GBC) cannot gain any information about the inputs or the intermediate results that appear during the function evaluation. The complexity of today's most efficient GC protocol depends linearly on the size of the Boolean circuit representation of the evaluated function. The total cost and run-time interaction between parties increase linearly with the number of gates and can be huge for complex GBCs. Actually, interest has grown in the efficiency of this technique and in its applications to computation outsourcing in untrusted environments. A recent work shows that XOR gates in a Boolean circuit have no cost for the secure computation protocol. Therefore, circuits with a reduced number of non-XOR gates are more convenient and one of the possible ways to reduce the complexity of the computation is to reduce the number of non-XOR gates in the Boolean circuit. Recalling that, the main aim of this work is to reduce the number of non-XOR gates, which directly results in a reduced number of interactions between the parties and transfer complexity at runtime, we present different approaches for reducing the communication cost of Secure Multi-party Computation (SMC) and improving the overall computation time and efficiency of the execution of SMC.
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).