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

Annual Symposium on Foundations of Computer Science

How to Garble Arithmetic Circuits

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Published Oct 1, 2011• 87 citations
Publisher

Abstract

Yao's garbled circuit construction transforms a boolean circuit C : {0, 1}n→ {0, 1}minto a "garbled circuit" Ĉ along with n pairs of k-bit keys, one for each input bit, such that Ĉ together with the n keys corresponding to an input x reveal C(x) and no additional information about x. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit C : ℤn→ ℤmover integers from a bounded (but possibly exponential) range into a garbled circuit Ĉ along with n affine functions Li: ℤ → ℤksuch that Ĉ together with the n integer vectors Li(xi) reveal C(x) and no additional information about x. The security of our construction relies on the intractability of the learning with errors (LWE) problem.

DOI
10.1109/focs.2011.40

Related papers

How to Garble Arithmetic Circuits

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$ into a “garbled circuit” $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C : \mathbb{Z}^n\to\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\hat{C}$ along with $n$ affine functions $L_i : \mathbb{Z}\to \mathbb{Z}^k$ such that $\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors problem.

SIAM Journal on Computing•Jan 1, 2014•34 citations

How to Garble Arithmetic Circuits.

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$ into a “garbled circuit” $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C : \mathbb{Z}^n\to\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\hat{C}$ along with $n$ affine functions $L_i : \mathbb{Z}\to \mathbb{Z}^k$ such that $\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors problem.

Electronic colloquium on computational complexity•Jan 1, 2012•0 citations

Reusable garbled circuits and succinct functional encryption

Shafi Goldwasser, Yael Tauman Kalai, Raluca Ada Popa +2 more

Garbled circuits, introduced by Yao in the mid 80s, allow computing a function f on an input x without leaking anything about f or x besides f(x). Garbled circuits found numerous applications, but every known construction suffers from one limitation: it offers no security if used on multiple inputs x. In this paper, we construct for the first time reusable garbled circuits. The key building block is a new succinct single-key functional encryption scheme. Functional encryption is an ambitious primitive: given an encryp-tion Enc(x) of a value x, and a secret key skf for a function f, anyone can compute f(x) without learning any other information about x. We construct, for the first time, a succinct functional encryption scheme for any polynomial-time function f where succinctness means that the ciphertext size does not grow with the size of the circuit for f, but only with its depth. The security of our construction is based on the intractability of the Learning with Errors (LWE) problem and holds as long as an adversary has access to a single key skf (or even an a priori bounded number of keys for different functions). Building on our succinct single-key functional encryption scheme, we show several new applications in addition to reusable garbled circuits, such as a paradigm for general function obfuscation which we call token-based obfuscation, homomorphic encryption for a class of Turing machines where the evaluation runs in input-specific time rather than worst-case time, and a scheme for delegating computation which is publicly verifiable and maintains the privacy of the computation.

•Jun 1, 2013•1 citation

Reusable garbled circuits and succinct functional encryption

Shafi Goldwasser, Yael Tauman Kalai, Raluca Ada Popa +2 more

Garbled circuits, introduced by Yao in the mid 80s, allow computing a function f on an input x without leaking anything about f or x besides f(x). Garbled circuits found numerous applications, but every known construction suffers from one limitation: it offers no security if used on multiple inputs x. In this paper, we construct for the first time reusable garbled circuits. The key building block is a new succinct single-key functional encryption scheme.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•465 citations

On Multiparty Garbling of Arithmetic Circuits.

Aner Ben-Efraim

We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC ’90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Using mixed Boolean-arithmetic circuits allows more efficient secure computation of functions that naturally combine Boolean and arithmetic computations. Our garbled circuits are secure in the semi-honest model, under the same hardness assumptions as Ball et al., and can be efficiently and securely computed in constant rounds assuming an honest majority.

•Jan 1, 2017•1 citation

Adaptively Secure Garbled Circuits from One-Way Functions.

Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky +2 more

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.

•Jan 1, 2015•0 citations
Yao's garbled circuit construction transforms a boolean circuit C : {0, 1}n→ {0, 1}minto a "garbled circuit" Ĉ along with n pairs of k-bit keys, one for each input bit, such that Ĉ together with the n keys corresponding to an input x reveal C(x) and no additional information about x. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit C : ℤn→ ℤmover integers from a bounded (but possibly exponential) range into a garbled circuit Ĉ along with n affine functions Li: ℤ → ℤksuch that Ĉ together with the n integer vectors Li(xi) reveal C(x) and no additional information about x. The security of our construction relies on the intractability of the learning with errors (LWE) problem.
Yao's garbled circuit construction transforms a boolean circuit C:{0,1}n→{0,1}mC:\{0,1\}^n\to\{0,1\}^mC:{0,1}n→{0,1}m into a “garbled circuit” C^\hat{C}C^ along with nnn pairs of kkk-bit keys, one for each input bit, such that C^\hat{C}C^ together with the nnn keys corresponding to an input xxx reveal C(x)C(x)C(x) and no additional information about xxx. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit C:Zn→ZmC : \mathbb{Z}^n\to\mathbb{Z}^mC:Zn→Zm over integers from a bounded (but possibly exponential) range into a garbled circuit C^\hat{C}C^ along with nnn affine functions Li:Z→ZkL_i : \mathbb{Z}\to \mathbb{Z}^kLi​:Z→Zk such that C^\hat{C}C^ together with the nnn integer vectors Li(xi)L_i(x_i)Li​(xi​) reveal C(x)C(x)C(x) and no additional information about xxx. The security of our construction relies on the intractability of the learning with errors problem.
Yao's garbled circuit construction transforms a boolean circuit C:{0,1}n→{0,1}mC:\{0,1\}^n\to\{0,1\}^mC:{0,1}n→{0,1}m into a “garbled circuit” C^\hat{C}C^ along with nnn pairs of kkk-bit keys, one for each input bit, such that C^\hat{C}C^ together with the nnn keys corresponding to an input xxx reveal C(x)C(x)C(x) and no additional information about xxx. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit C:Zn→ZmC : \mathbb{Z}^n\to\mathbb{Z}^mC:Zn→Zm over integers from a bounded (but possibly exponential) range into a garbled circuit C^\hat{C}C^ along with nnn affine functions Li:Z→ZkL_i : \mathbb{Z}\to \mathbb{Z}^kLi​:Z→Zk such that C^\hat{C}C^ together with the nnn integer vectors Li(xi)L_i(x_i)Li​(xi​) reveal C(x)C(x)C(x) and no additional information about xxx. The security of our construction relies on the intractability of the learning with errors problem.
Garbled circuits, introduced by Yao in the mid 80s, allow computing a function f on an input x without leaking anything about f or x besides f(x). Garbled circuits found numerous applications, but every known construction suffers from one limitation: it offers no security if used on multiple inputs x. In this paper, we construct for the first time reusable garbled circuits. The key building block is a new succinct single-key functional encryption scheme. Functional encryption is an ambitious primitive: given an encryp-tion Enc(x) of a value x, and a secret key skf for a function f, anyone can compute f(x) without learning any other information about x. We construct, for the first time, a succinct functional encryption scheme for any polynomial-time function f where succinctness means that the ciphertext size does not grow with the size of the circuit for f, but only with its depth. The security of our construction is based on the intractability of the Learning with Errors (LWE) problem and holds as long as an adversary has access to a single key skf (or even an a priori bounded number of keys for different functions). Building on our succinct single-key functional encryption scheme, we show several new applications in addition to reusable garbled circuits, such as a paradigm for general function obfuscation which we call token-based obfuscation, homomorphic encryption for a class of Turing machines where the evaluation runs in input-specific time rather than worst-case time, and a scheme for delegating computation which is publicly verifiable and maintains the privacy of the computation.
We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC ’90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Using mixed Boolean-arithmetic circuits allows more efficient secure computation of functions that naturally combine Boolean and arithmetic computations. Our garbled circuits are secure in the semi-honest model, under the same hardness assumptions as Ball et al., and can be efficiently and securely computed in constant rounds assuming an honest majority.
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.