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

SIAM Journal on Computing

How to Garble Arithmetic Circuits

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz Z

Published Jan 1, 2014• 34 citations
Publisher

Abstract

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.

DOI
10.1137/120875193

Related papers

How to Garble Arithmetic Circuits.

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz Z

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

How to Garble Arithmetic Circuits

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz Z

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2011•84 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

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.

•Jan 1, 2013•1 citation

Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently.

Marek Jawurek, Florian Kerschbaum, Claudio Orlandi

Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice. In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao’s garbled circuit technique. The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., “I know x s.t. y = SHA-256(x)” for a common input y (or other “unstructured” languages), but no efficient protocols for this task are currently known. It is clear that zero-knowledge is a subset of secure two-party computation (i.e., any protocol for generic secure computation can be used to do zero-knowledge). The main contribution of this paper is to construct an efficient protocol for the special case of secure two-party computation where only one party has input (like in the zero-knowledge case). The protocol achieves active security and is essentially only twice as slow as the passive secure version of Yao’s garbled circuit protocol. This is a great improvement with respect to the cut-n-choose technique to make Yao’s protocol actively secure, where the complexity grows linearly with the security parameter.

•Jan 1, 2013•11 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.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•460 citations
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.
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.
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.
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.
Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice. In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao’s garbled circuit technique. The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., “I know x s.t. y = SHA-256(x)” for a common input y (or other “unstructured” languages), but no efficient protocols for this task are currently known. It is clear that zero-knowledge is a subset of secure two-party computation (i.e., any protocol for generic secure computation can be used to do zero-knowledge). The main contribution of this paper is to construct an efficient protocol for the special case of secure two-party computation where only one party has input (like in the zero-knowledge case). The protocol achieves active security and is essentially only twice as slow as the passive secure version of Yao’s garbled circuit protocol. This is a great improvement with respect to the cut-n-choose technique to make Yao’s protocol actively secure, where the complexity grows linearly with the security parameter.