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

Securing Yao's garbled circuit construction against active adversaries

Mehmet Sabır Kiraz, Lam Berry Schoenmakers

Published Jan 1, 2006• 0 citations
OpenAlex

Abstract

Abstract. We propose a new two-party computation protocol using Yao’s garbled circuits, which is secure in the case of malicious behavior. To illustrate the need for the new protocol, we first discuss security issues of three existing protocols for secure two-party computation using garbled circuits, in the case of malicious behavior. The first is a protocol by Pinkas (Eurocrypt 2003), and the other two are the committed-input scheme and the k-leaked model, both presented by Mohassel and Franklin (PKC 2006). We address security flaws in all schemes, which allow leaking of information on the private inputs. In the k-leaked model leaking of some information is permitted if a participant is cheating, but then the honest participant should be aware of it. We show that this is not the case. After discussing these security issues of the known schemes, we describe our new protocol. It is based on the protocol by Pinkas, and the correction of the flaw of the scheme by Pinkas makes our protocol not only more secure, but also more efficient. We provide a detailed informal security analysis of our new protocol. Keywords: Secure two-party computation, Yao’s garbled circuit, active adversary 1

Related papers

A protocol issue for the malicious case of Yao's garbled circuit construction

Mehmet Sabır Kiraz, Berry Schoenmakers

We present a protocol issue that arises with the use of oblivious transfer in the malicious case of several two-party computation protocols based on Yao’s garbled circuit. We describe this issue for a protocol by Pinkas (Eurocrypt 2003) and for the Fairplay protocol, and we discuss why this issue still persists for a recently suggested modification of the Fairplay protocol. We propose a solution using committed oblivious transfer instead of (plain) oblivious transfer. We also introduce the notion of committing oblivious transfer, which leads to an alternative, potentially more efficient solution. 1

•Jan 1, 2006•69 citations

The Use of Circuit Evaluation Techniques for Secure Computation

Oleg Selajev

Secure two-party computation problem is about two parties that want to compute some function of their private inputs in a way that other party won’t learn it. We describe a general way to perform secure two-party computation of a function specified as a boolean circuit, which was proposed by A.A. Yao in 1982. This method is named Yao garbled circuit evaluation and is secure against semi-honest adversaries. We present a new efficient protocol for secure two-party computation Circus, that is secure against malicious adversary in consistency model. Consistency model implies that either both parties will receive correct output and persist privacy of their inputs or a honest party will know, that is was cheated and that adversary potentially have learnt 1 bit of other party’s input value. We specify all necessary sub-protocols and their security requirements and prove security of Circus in malicious environment.

•Jan 1, 2011•1 citation

Design and Implementation of Maliciously Secure Two-Party Computation Based on Garbled Circuits

Afshar, Arash

In this thesis we design and implement three approaches to provide efficient Secure Two- Party Computation (2PC) protocols that are secure in presence of malicious adversaries. The field of secure two-party computation enables two mutually distrusting parties, each with their own private input, to run a computation of an arbitrary program. At the end of the computation, nothing about their private input is leaked except for what can be learned from the output of the computation. The seminal work of Yao in 1986 provided the first proof that such a computation is feasible using the so called garbled circuits and given an Oblivious Transfer protocol. In this thesis, we follow Yao’s garbled circuit approach and focus on efficient protocols that are secure against malicious adversaries. We examine three different categories of optimization. In each category, we present a 2PC protocol, prove its security, and implement it as a proof of concept to demonstrate its running time in practice. Non-interactive Secure Computation: In this category, we offer the first implementation of a malicious 2PC protocol that reduces the required rounds of interaction between the two parties to only two rounds (i.e., each party sends only one message to the other party). Mixed Secure Two-Party Computation: In the second category we target big and complex programs and break them into subprograms. Then, we compute each subprogram using the most efficient 2PC protocol that is suitable for it. Finally, we securely connect these subprograms together. The goal is to reduce the overhead of the garbled circuits significantly, which results in a more efficient overall 2PC protocol for programs with specific properties. Secure Computation for Random Access Machine Programs: In the third category, we target programs that require random access to the memory (as opposed to a sequential access). We present the first efficient maliciously-secure protocol for computing such programs.

•Jan 1, 2017•0 citations

Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries.

Yehuda Lindell

In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of Yao’s garbled circuits (FOCS 1986). In the semi-honest model, where just one garbled circuit is constructed and evaluated, Yao’s protocol has proven itself to be very efficient. However, a malicious adversary who constructs the garbled circuit may construct a garbling of a different circuit computing a different function, and this cannot be detected (due to the garbling). In order to solve this problem, many circuits are sent and some of them are opened to check that they are correct while the others are evaluated. This methodology, called cut-and-choose, introduces significant overhead, both in computation and in communication, and is mainly due to the number of circuits that must be used in order to prevent cheating. In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most 2−40, the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of 2−s where s is the number of garbled circuits, in contrast to the previous best of 2−0.32s. We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, all of the evaluated circuits must be incorrect, and not just the majority as in previous works. The security of our protocol relies on the Decisional Diffie-Hellman assumption.

•Jan 1, 2013•0 citations

Secure and fair two-party computation

Mehmet Sabır Kiraz

Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.

•Jan 1, 2007•19 citations

Efficient Fair Secure Two-Party Computation

Ou Ruan, Zhou Jing, Minghui Zheng +1 more

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called "garbled circuit". Later, many protocols based on garbled circuit approach have been presented, most of which discussed malicious adversaries and efficiency about 2PC. However, there only have a few protocols dealing with the fundamental property of fairness for Yao's garbled circuit approach, in which one involved a trusted third party and the others are very expensive. In the paper, we propose' an efficient Yao's garbled circuit protocol for fair secure 2PC based on ElGamal encryption, Pedersen commitment, Cachin et al.'s verifiable oblivious transfer and Ou-Ruan et al.'s gradual release homomorphic timed commitment. The protocol achieves two advantages: it doesn't need the third party and it is more efficient than other fair secure Yao's protocols.

IEEE Asia-Pacific Services Computing Conference (APSCC)•Dec 1, 2012•5 citations
Abstract. We propose a new two-party computation protocol using Yao’s garbled circuits, which is secure in the case of malicious behavior. To illustrate the need for the new protocol, we first discuss security issues of three existing protocols for secure two-party computation using garbled circuits, in the case of malicious behavior. The first is a protocol by Pinkas (Eurocrypt 2003), and the other two are the committed-input scheme and the k-leaked model, both presented by Mohassel and Franklin (PKC 2006). We address security flaws in all schemes, which allow leaking of information on the private inputs. In the k-leaked model leaking of some information is permitted if a participant is cheating, but then the honest participant should be aware of it. We show that this is not the case. After discussing these security issues of the known schemes, we describe our new protocol. It is based on the protocol by Pinkas, and the correction of the flaw of the scheme by Pinkas makes our protocol not only more secure, but also more efficient. We provide a detailed informal security analysis of our new protocol. Keywords: Secure two-party computation, Yao’s garbled circuit, active adversary 1
We present a protocol issue that arises with the use of oblivious transfer in the malicious case of several two-party computation protocols based on Yao’s garbled circuit. We describe this issue for a protocol by Pinkas (Eurocrypt 2003) and for the Fairplay protocol, and we discuss why this issue still persists for a recently suggested modification of the Fairplay protocol. We propose a solution using committed oblivious transfer instead of (plain) oblivious transfer. We also introduce the notion of committing oblivious transfer, which leads to an alternative, potentially more efficient solution. 1
Secure two-party computation problem is about two parties that want to compute some function of their private inputs in a way that other party won’t learn it. We describe a general way to perform secure two-party computation of a function specified as a boolean circuit, which was proposed by A.A. Yao in 1982. This method is named Yao garbled circuit evaluation and is secure against semi-honest adversaries. We present a new efficient protocol for secure two-party computation Circus, that is secure against malicious adversary in consistency model. Consistency model implies that either both parties will receive correct output and persist privacy of their inputs or a honest party will know, that is was cheated and that adversary potentially have learnt 1 bit of other party’s input value. We specify all necessary sub-protocols and their security requirements and prove security of Circus in malicious environment.
In this thesis we design and implement three approaches to provide efficient Secure Two- Party Computation (2PC) protocols that are secure in presence of malicious adversaries. The field of secure two-party computation enables two mutually distrusting parties, each with their own private input, to run a computation of an arbitrary program. At the end of the computation, nothing about their private input is leaked except for what can be learned from the output of the computation. The seminal work of Yao in 1986 provided the first proof that such a computation is feasible using the so called garbled circuits and given an Oblivious Transfer protocol. In this thesis, we follow Yao’s garbled circuit approach and focus on efficient protocols that are secure against malicious adversaries. We examine three different categories of optimization. In each category, we present a 2PC protocol, prove its security, and implement it as a proof of concept to demonstrate its running time in practice. Non-interactive Secure Computation: In this category, we offer the first implementation of a malicious 2PC protocol that reduces the required rounds of interaction between the two parties to only two rounds (i.e., each party sends only one message to the other party). Mixed Secure Two-Party Computation: In the second category we target big and complex programs and break them into subprograms. Then, we compute each subprogram using the most efficient 2PC protocol that is suitable for it. Finally, we securely connect these subprograms together. The goal is to reduce the overhead of the garbled circuits significantly, which results in a more efficient overall 2PC protocol for programs with specific properties. Secure Computation for Random Access Machine Programs: In the third category, we target programs that require random access to the memory (as opposed to a sequential access). We present the first efficient maliciously-secure protocol for computing such programs.
In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of Yao’s garbled circuits (FOCS 1986). In the semi-honest model, where just one garbled circuit is constructed and evaluated, Yao’s protocol has proven itself to be very efficient. However, a malicious adversary who constructs the garbled circuit may construct a garbling of a different circuit computing a different function, and this cannot be detected (due to the garbling). In order to solve this problem, many circuits are sent and some of them are opened to check that they are correct while the others are evaluated. This methodology, called cut-and-choose, introduces significant overhead, both in computation and in communication, and is mainly due to the number of circuits that must be used in order to prevent cheating. In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most 2−40, the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of 2−s where s is the number of garbled circuits, in contrast to the previous best of 2−0.32s. We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, all of the evaluated circuits must be incorrect, and not just the majority as in previous works. The security of our protocol relies on the Decisional Diffie-Hellman assumption.
Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.
Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called "garbled circuit". Later, many protocols based on garbled circuit approach have been presented, most of which discussed malicious adversaries and efficiency about 2PC. However, there only have a few protocols dealing with the fundamental property of fairness for Yao's garbled circuit approach, in which one involved a trusted third party and the others are very expensive. In the paper, we propose' an efficient Yao's garbled circuit protocol for fair secure 2PC based on ElGamal encryption, Pedersen commitment, Cachin et al.'s verifiable oblivious transfer and Ou-Ruan et al.'s gradual release homomorphic timed commitment. The protocol achieves two advantages: it doesn't need the third party and it is more efficient than other fair secure Yao's protocols.