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

Adaptively Secure Garbled Circuits from One-Way Functions.

Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, Daniel Wichs

Published Jan 1, 2015• 0 citations
OpenAlex

Abstract

A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao’s scheme has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input x prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose x after seeing the garbled circuit, while preserving on-line efficiency. In this work, we modify Yao’s scheme in a way that allows us to prove adaptive security under one-way functions. As our main instantiation, we get a scheme where the on-line complexity is only proportional to the width w of the circuit, which corresponds to the space complexity of the computation, but is independent of the circuit’s depth d. Alternately, we can also get an instantiation where the on-line complexity is only proportional to the input/output size and the depth d of the circuit but independent of its width w, albeit in this case we incur a 2 security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit. As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits. ∗This work was done in part while some of the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS1523467. †University of Pennsylvania. Department of Computer Science. fbrett@cis.upenn.edu ‡Northeastern University. Department of Computer Science. zahra@ccs.neu.edu §University of California, Los Angeles. Department of Computer Science and Mathematics. rafail@cs.ucla.edu Research supported in part by NSF grants 09165174, 1065276, 1118126 and 1136174, US-Israel BSF grant 2008411, OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award, Teradata Research Award, and Lockheed-Martin Corporation Research Award. This material is based upon work supported in part by DARPA Safeware program. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government. ¶Boston University and Northeastern University. Department of Computer Science. scafuro@bu.edu Research supported by NSF grants 1012798. ‖Northeastern University. Department of Computer Science. wichs@ccs.neu.edu. Research supported by NSF grants CNS-1347350, CNS-1314722, CNS-1413964.

Related papers

Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model

Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam

Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2017•14 citations

Hierarchy for classes of projective garbling schemes

Tommi Meskanen, Noora Nieminen, Valtteri Niemi

Recently, privacy has become one of the hottest topics in the world of the Internet-based communications and computation. Many applications, such as cloud computing and various cloud services, require information security and privacy. However, in many cases the level of security in current solutions is insufficient. Methods to ensure secure multiparty computation have been studied for decades, but because of the needs of the modern computation this topic has recently become increasingly popular. Yao's garbled circuit is one method to compute a function f on an argument x privately without revealing any information about f and x except f(x). Unfortunately, current constructions for garbled circuits have limitations - either efficient construction at the cost of reusability or reusability at the cost of efficiency. In this paper we aim at somewhere between these two extremes by defining new security measures for garbling schemes. These definitions support design of reusable garbled circuits that achieve adaptive security even when the function argument is handled bitwise. Moreover, we show how the new classes are related to the existing security classes of garbling schemes. As a result, we obtain an extended hierarchy for the classes of garbling schemes.

•Jan 1, 2014•4 citations

Foundations of Reactive Garbling Schemes.

Jesper Buus Nielsen, Samuel Ranellucci

Abstract. Garbled circuits is a cryptographic technique, which has been used among other things for the con-struction of two and three-party secure computation, private function evaluation and secure outsourcing. Garbling schemes is a primitive which formalizes the syntax and security properties of garbled circuits. We dene a gener-alization of garbling schemes called reactive garbling schemes. We consider functions and garbled functions taking multiple inputs and giving multiple outputs. Two garbled functions can be linked together: an encoded output of one garbled function can be transformed into an encoded input of the other garbled function without commu-nication between the parties. Reactive garbling schemes also allow partial evaluation of garbled functions even when only some of the encoded inputs are provided. It is possible to further evaluate the linked garbled functions when more garbled inputs become available. It is also possible to later garble more functions and link them to the ongoing garbled evaluation. We provide rigorous denitions for reactive garbling schemes. We dene a new notion of security for reactive garbling schemes called condentiality. We provide both simulation based and in-distinguishability based notions of security. We also show that the simulation based notion of security implies the indistinguishability based notion of security. We present an instantiation of reactive garbling schemes. We present an application of reactive garbling schemes to reactive two-party computation secure against a malicious adversary. We demonstrate how garbling schemes can be used to give abstract black-box descriptions and proof of several advanced applications of garbled circuits in the literature, including Minilego and Lindell’s forge-and-loose technique. 1

•Jan 1, 2015•3 citations

Reactive Garbling: Foundation, Instantiation, Application

Jesper Buus Nielsen, Samuel Ranellucci

Garbled circuits is a cryptographic technique, which has been used among other things for the construction of two and threeparty secure computation, private function evaluation and secure outsourcing. Garbling schemes is a primitive which formalizes the syntax and security properties of garbled circuits. We define a generalization of garbling schemes called reactive garbling schemes. We consider functions and garbled functions taking multiple inputs and giving multiple outputs. Two garbled functions can be linked together: an encoded output of one garbled function can be transformed into an encoded input of the other garbled function without communication between the parties. Reactive garbling schemes also allow partial evaluation of garbled functions even when only some of the encoded inputs are provided. It is possible to further evaluate the linked garbled functions when more garbled inputs become available. It is also possible to later garble more functions and link them to the ongoing garbled evaluation. We provide rigorous definitions for reactive garbling schemes. We define a new notion of security for reactive garbling schemes called confidentiality. We provide both simulation based and indistinguishability based notions of security. We also show that the simulation based notion of security implies the indistinguishability based notion of security. We present an instantiation of reactive garbling schemes. We present an application of reactive garbling schemes to reactive two-party computation secure against a malicious, static adversary. We demonstrate how garbling schemes can be used to give abstract black-box descriptions and proof of several advanced applications of garbled circuits in the literature, including Minilego and Lindell’s forge-and-lose technique.

•Jan 1, 2016•0 citations

Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation.

Payman Mohassel, Ben Riva

Applying cut-and-choose techniques to Yao’s garbled circuit protocol has been a promising approach for designing efficient Two-Party Computation (2PC) with malicious and covert security, as is evident from various optimizations and software implementations in the recent years. We revisit the security and efficiency properties of this popular approach and propose alternative constructions and a new definition that are more suitable for use in practice. • We design an efficient fully-secure 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors, and ignoring factors that are independent of the circuit in use) in the Random Oracle Model, where |C | is the circuit size and t is a statistical security parameter. This is essentially the optimal complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject. Our protocol utilizes novel techniques for enforcing garbler’s input consistency and handling twooutput functions that are more efficient than all prior solutions. • Motivated by the goal of eliminating the all-or-nothing nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard covert model, and offers a smoother security vs. efficiency tradeoff to protocol designers in choosing the right deterrence factor. In our new notion, correctness is always guaranteed, privacy is fully guaranteed with probability (1 − ɛ), and with probability ɛ (i.e. the event of undetected cheating), privacy is only “partially compromised ” with at most a single bit of information leaked, in case of an abort. We present two efficient 2PC constructions achieving our new notion. Both protocols are competitive with the previous covert 2PC protocols based on cut-and-choose. A distinct feature of the techniques we use in all our constructions is to check consistency of inputs and outputs using new gadgets that are themselves garbled circuits, and to verify validity of these gadgets using multi-stage cut-and-choose openings.

•Jan 1, 2013•0 citations

Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model

Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam

Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We answer this question in the affirmative. We define a new type of symmetric encryption, called functionally equivocal encryption (FEE), and show that when Yao's scheme is implemented with FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one-way function. Combining our scheme with noncommitting encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. Using standard techniques, this protocol can be made standalone secure against malicious corruptions in the plain model and universal composability secure in the common random string model. Additional applications include the first fully leakage-tolerant general multiparty computation protocol (with preprocessing), as well as a public-key version of FEE which can serve as a replacement for noncommitting encryption with better efficiency than what is possible for the latter.

SIAM Journal on Computing•Jan 13, 2022•2 citations
A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao’s scheme has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input x prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose x after seeing the garbled circuit, while preserving on-line efficiency. In this work, we modify Yao’s scheme in a way that allows us to prove adaptive security under one-way functions. As our main instantiation, we get a scheme where the on-line complexity is only proportional to the width w of the circuit, which corresponds to the space complexity of the computation, but is independent of the circuit’s depth d. Alternately, we can also get an instantiation where the on-line complexity is only proportional to the input/output size and the depth d of the circuit but independent of its width w, albeit in this case we incur a 2 security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit. As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits. ∗This work was done in part while some of the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS1523467. †University of Pennsylvania. Department of Computer Science. fbrett@cis.upenn.edu ‡Northeastern University. Department of Computer Science. zahra@ccs.neu.edu §University of California, Los Angeles. Department of Computer Science and Mathematics. rafail@cs.ucla.edu Research supported in part by NSF grants 09165174, 1065276, 1118126 and 1136174, US-Israel BSF grant 2008411, OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award, Teradata Research Award, and Lockheed-Martin Corporation Research Award. This material is based upon work supported in part by DARPA Safeware program. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government. ¶Boston University and Northeastern University. Department of Computer Science. scafuro@bu.edu Research supported by NSF grants 1012798. ‖Northeastern University. Department of Computer Science. wichs@ccs.neu.edu. Research supported by NSF grants CNS-1347350, CNS-1314722, CNS-1413964.
Recently, privacy has become one of the hottest topics in the world of the Internet-based communications and computation. Many applications, such as cloud computing and various cloud services, require information security and privacy. However, in many cases the level of security in current solutions is insufficient. Methods to ensure secure multiparty computation have been studied for decades, but because of the needs of the modern computation this topic has recently become increasingly popular. Yao's garbled circuit is one method to compute a function f on an argument x privately without revealing any information about f and x except f(x). Unfortunately, current constructions for garbled circuits have limitations - either efficient construction at the cost of reusability or reusability at the cost of efficiency. In this paper we aim at somewhere between these two extremes by defining new security measures for garbling schemes. These definitions support design of reusable garbled circuits that achieve adaptive security even when the function argument is handled bitwise. Moreover, we show how the new classes are related to the existing security classes of garbling schemes. As a result, we obtain an extended hierarchy for the classes of garbling schemes.
Abstract. Garbled circuits is a cryptographic technique, which has been used among other things for the con-struction of two and three-party secure computation, private function evaluation and secure outsourcing. Garbling schemes is a primitive which formalizes the syntax and security properties of garbled circuits. We dene a gener-alization of garbling schemes called reactive garbling schemes. We consider functions and garbled functions taking multiple inputs and giving multiple outputs. Two garbled functions can be linked together: an encoded output of one garbled function can be transformed into an encoded input of the other garbled function without commu-nication between the parties. Reactive garbling schemes also allow partial evaluation of garbled functions even when only some of the encoded inputs are provided. It is possible to further evaluate the linked garbled functions when more garbled inputs become available. It is also possible to later garble more functions and link them to the ongoing garbled evaluation. We provide rigorous denitions for reactive garbling schemes. We dene a new notion of security for reactive garbling schemes called condentiality. We provide both simulation based and in-distinguishability based notions of security. We also show that the simulation based notion of security implies the indistinguishability based notion of security. We present an instantiation of reactive garbling schemes. We present an application of reactive garbling schemes to reactive two-party computation secure against a malicious adversary. We demonstrate how garbling schemes can be used to give abstract black-box descriptions and proof of several advanced applications of garbled circuits in the literature, including Minilego and Lindell’s forge-and-loose technique. 1
Garbled circuits is a cryptographic technique, which has been used among other things for the construction of two and threeparty secure computation, private function evaluation and secure outsourcing. Garbling schemes is a primitive which formalizes the syntax and security properties of garbled circuits. We define a generalization of garbling schemes called reactive garbling schemes. We consider functions and garbled functions taking multiple inputs and giving multiple outputs. Two garbled functions can be linked together: an encoded output of one garbled function can be transformed into an encoded input of the other garbled function without communication between the parties. Reactive garbling schemes also allow partial evaluation of garbled functions even when only some of the encoded inputs are provided. It is possible to further evaluate the linked garbled functions when more garbled inputs become available. It is also possible to later garble more functions and link them to the ongoing garbled evaluation. We provide rigorous definitions for reactive garbling schemes. We define a new notion of security for reactive garbling schemes called confidentiality. We provide both simulation based and indistinguishability based notions of security. We also show that the simulation based notion of security implies the indistinguishability based notion of security. We present an instantiation of reactive garbling schemes. We present an application of reactive garbling schemes to reactive two-party computation secure against a malicious, static adversary. We demonstrate how garbling schemes can be used to give abstract black-box descriptions and proof of several advanced applications of garbled circuits in the literature, including Minilego and Lindell’s forge-and-lose technique.
Applying cut-and-choose techniques to Yao’s garbled circuit protocol has been a promising approach for designing efficient Two-Party Computation (2PC) with malicious and covert security, as is evident from various optimizations and software implementations in the recent years. We revisit the security and efficiency properties of this popular approach and propose alternative constructions and a new definition that are more suitable for use in practice. • We design an efficient fully-secure 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors, and ignoring factors that are independent of the circuit in use) in the Random Oracle Model, where |C | is the circuit size and t is a statistical security parameter. This is essentially the optimal complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject. Our protocol utilizes novel techniques for enforcing garbler’s input consistency and handling twooutput functions that are more efficient than all prior solutions. • Motivated by the goal of eliminating the all-or-nothing nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard covert model, and offers a smoother security vs. efficiency tradeoff to protocol designers in choosing the right deterrence factor. In our new notion, correctness is always guaranteed, privacy is fully guaranteed with probability (1 − ɛ), and with probability ɛ (i.e. the event of undetected cheating), privacy is only “partially compromised ” with at most a single bit of information leaked, in case of an abort. We present two efficient 2PC constructions achieving our new notion. Both protocols are competitive with the previous covert 2PC protocols based on cut-and-choose. A distinct feature of the techniques we use in all our constructions is to check consistency of inputs and outputs using new gadgets that are themselves garbled circuits, and to verify validity of these gadgets using multi-stage cut-and-choose openings.
Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We answer this question in the affirmative. We define a new type of symmetric encryption, called functionally equivocal encryption (FEE), and show that when Yao's scheme is implemented with FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one-way function. Combining our scheme with noncommitting encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. Using standard techniques, this protocol can be made standalone secure against malicious corruptions in the plain model and universal composability secure in the common random string model. Additional applications include the first fully leakage-tolerant general multiparty computation protocol (with preprocessing), as well as a public-key version of FEE which can serve as a replacement for noncommitting encryption with better efficiency than what is possible for the latter.