IEEE International Conference on Computer and Information Technology (CIT)

On Reusable Projective Garbling Schemes

Tommi Meskanen, Valtteri Niemi, Noora Nieminen

Published Sep 1, 2014• 2 citations

Abstract

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.

DOI: 10.1109/cit.2014.63

Related papers

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, 20144 citations

Equivocating Yao

Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam

ACM Symposium on Theory of Computing (STOC)Jun 15, 201715 citations

Adaptively Secure Two-Party Computation with Erasures.

Yehuda Lindell

In the setting of multiparty computation a set of parties with private inputs wish to compute some joint function of their inputs, whilst preserving certain security properties (like privacy and correctness). An adaptively secure protocol is one in which the security properties are preserved even if an adversary can adaptively and dynamically corrupt parties during a computation. This provides a high level of security, that is arguably necessary in today’s world of active computer break-ins. Until now, the work on adaptively secure multiparty computation has focused almost exclusively on the setting of an honest majority, and very few works have considered the honest minority and two-party cases. In addition, significant computational and communication costs are incurred by most protocols that achieve adaptive security. In this work, we consider the two-party setting and assume that honest parties may erase data. We show that in this model it is possible to securely compute any two-party functionality in the presence of adaptive semi-honest adversaries. Furthermore, our protocol remains secure under concurrent general composition (meaning that it remains secure irrespective of the other protocols running together with it). Our protocol is based on Yao’s garbled-circuit construction and, importantly, is as efficient as the analogous protocol for static corruptions. We argue that the model of adaptive corruptions with erasures has been unjustifiably neglected and that it deserves much more attention. 1

Jan 1, 20090 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, 20160 citations

A State-Separating Proof for Yao's Garbling Scheme

Chris Brzuska, Sabine Oechsner

Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao's garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof in the style of state-separating proofs (ASIACRYPT 2018).

IEEE Computer Security Foundations Workshop (CSFW)Jul 1, 20236 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 ComputingJan 13, 20222 citations