Hierarchy for classes of projective garbling schemes

Tommi Meskanen, Noora Nieminen, Valtteri Niemi

Published Jan 1, 2014• 4 citations

Abstract

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.

DOI: 10.1049/cp.2014.0586

Related papers

On Reusable Projective Garbling Schemes

Tommi Meskanen, Valtteri Niemi, Noora Nieminen

The popularity of network-based computation has increased during the past years. Storing data and performing computations using for example cloud services is commonplace nowadays. However, the information security in network-based computation rarely is satisfactory. One technique to improve information security for networked computations is based on secure multiparty computations. The idea of multiparty computation originates from Yao, who considered the secure computation with two parties by introducing the technique called garbled circuits. The technique was then generalized, but still the exact definitions for different security measures were not established until Bellare, Hoang and Rogaway proposed a definition of a garbling scheme and several security notions for garbling schemes. This gave inspiration to study the security properties of garbling schemes from different perspectives, including adaptivity and reusability. In this paper, we study the adaptive security for a certain type of reusable garbling schemes. First, we consider general constraints to achieve security for this specific type of garbling schemes. Then we analyze the adaptive security classes of reusable garbling schemes. More specifically, we prove a relation between security classes that has been left open in earlier research.

IEEE International Conference on Computer and Information Technology (CIT)Sep 1, 20142 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 definitions that are more suitable for use in practice. • We design an efficient fully-secure malicious 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors) 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

Jan 1, 20130 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.

Jan 1, 20131 citation

Fast Garbling of Circuits Under Standard Assumptions

Shay Gueron, Yehuda Lindell, Ariel Nof +1 more

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao's garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Oct 6, 201571 citations

Reusable garbled circuits and succinct functional encryption

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

ACM Symposium on Theory of Computing (STOC)May 28, 2013460 citations

Fast Garbling of Circuits Under Standard Assumptions.

Shay Gueron, Yehuda Lindell, Ariel Nof +1 more

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure com-putation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao’s garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

Jan 1, 20150 citations