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.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, 20131 citation

Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond.

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

Functional encryption is a powerful primitive: given an encryption Enc(x) of a value x and a secret key skf corresponding to a circuit f, it enables efficient computation of f(x) without revealing any additional information about x. Constructing functional encryption schemes with succinct ciphertexts that guarantee security for even a single secret key (for a general function f) is an important open problem with far reaching applications, which this paper addresses. Our main result is a functional encryption scheme for any general function f of depth d, with succinct ciphertexts whose size grows with the depth d rather than the size of the circuit for f. We prove the security of our construction based on the intractability of the learning with error (LWE) problem. More generally, we show how to construct a functional encryption scheme from any public-index predicate encryption scheme and fully homomorphic encryption scheme. Previously, the only known constructions of functional encryption were either for specific inner product predicates, or for a weak form of functional encryption where the ciphertext size grows with the size of the circuit for f. We demonstrate the power of this result, by using it to construct a reusable circuit garbling scheme withFunctional encryption is a powerful primitive: given an encryption Enc(x) of a value x and a secret key skf corresponding to a circuit f, it enables efficient computation of f(x) without revealing any additional information about x. Constructing functional encryption schemes with succinct ciphertexts that guarantee security for even a single secret key (for a general function f) is an important open problem with far reaching applications, which this paper addresses. Our main result is a functional encryption scheme for any general function f of depth d, with succinct ciphertexts whose size grows with the depth d rather than the size of the circuit for f. We prove the security of our construction based on the intractability of the learning with error (LWE) problem. More generally, we show how to construct a functional encryption scheme from any public-index predicate encryption scheme and fully homomorphic encryption scheme. Previously, the only known constructions of functional encryption were either for specific inner product predicates, or for a weak form of functional encryption where the ciphertext size grows with the size of the circuit for f. We demonstrate the power of this result, by using it to construct a reusable circuit garbling scheme with

Jan 1, 201238 citations

Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks

Shweta Agrawal

We construct a functional encryption scheme for circuits which simultaneously achieves and improves upon the security of the current best known, and incomparable, constructions from standard assumptions: reusable garbled circuits by Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (STOC 2013) [GKP+13] and predicate encryption for circuits by Gorbunov, Vaikuntanathan and Wee (CRYPTO 2015) [GVW15]. Our scheme is secure based on the learning with errors (LWE) assumption. Our construction implies: 1. A new construction for reusable garbled circuits that achieves stronger security than the only known prior construction [GKP+13]. 2. A new construction for bounded collusion functional encryption with substantial efficiency benefits: our public parameters and ciphertext size incur an additive growth of $O(Q^2)$ , where Q is the number of permissible queries (We note that due to a lower bound [AGVW13], the ciphertext size must necessarily grow with Q). Additionally, the ciphertext of our scheme is succinct, in that it does not depend on the size of the circuit. By contrast, the prior best construction [GKP+13, GVW12] incurred a multiplicative blowup of $O(Q^4)$ in both the public parameters and ciphertext size. However, our scheme is secure in a weaker game than [GVW12].We construct a functional encryption scheme for circuits which simultaneously achieves and improves upon the security of the current best known, and incomparable, constructions from standard assumptions: reusable garbled circuits by Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (STOC 2013) [GKP+13] and predicate encryption for circuits by Gorbunov, Vaikuntanathan and Wee (CRYPTO 2015) [GVW15]. Our scheme is secure based on the learning with errors (LWE) assumption. Our construction implies: 1. A new construction for reusable garbled circuits that achieves stronger security than the only known prior construction [GKP+13]. 2. A new construction for bounded collusion functional encryption with substantial efficiency benefits: our public parameters and ciphertext size incur an additive growth of $O(Q^2)$, where Q is the number of permissible queries (We note that due to a lower bound [AGVW13], the ciphertext size must necessarily grow with Q). Additionally, the ciphertext of our scheme is succinct, in that it does not depend on the size of the circuit. By contrast, the prior best construction [GKP+13, GVW12] incurred a multiplicative blowup of $O(Q^4)$ in both the public parameters and ciphertext size. However, our scheme is secure in a weaker game than [GVW12].

Jan 1, 20162 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.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, 20144 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\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.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 complexityJan 1, 20120 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.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, 20160 citations

O(Q^2)

, where Q is the number of permissible queries (We note that due to a lower bound [AGVW13], the ciphertext size must necessarily grow with Q). Additionally, the ciphertext of our scheme is succinct, in that it does not depend on the size of the circuit. By contrast, the prior best construction [GKP+13, GVW12] incurred a multiplicative blowup of

O(Q^4)

in both the public parameters and ciphertext size. However, our scheme is secure in a weaker game than [GVW12].

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.