A simple protocol for secure circuit evaluation

Jan L. Camenisch, Robert R. Enderlein, Victor Shoup

Martı́n Abadi, Joan Feigenbaum A

Moni Naor, Kobbi Nissim B

A secure function evaluation protocol allows two parties to jointly compute a function f(x; y) of their inputs in a manner not leaking more information than necessary. A major result in this field is: "any function f that can be computed using polynomial resources can be computed securely using polynomial resources" (where `resources' refers to communication and computation). This result follows by a general transformation from any circuit for f to a secure protocol that evaluates f . Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of f . We propose a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of f . We start with an efficient (insecure) protocol for f and transform it into a secure protocol. In other words, "any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter". We show several simple applications of this new methodology resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem ", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation. 1.

Stephen R. Tate, Ke Xu

In this paper, we examine a form of garbled (or encrypted) circuit introduced by Beaver, Micali, and Rogaway as part of their design of a constant-round secure function evaluation (SFE) protocol [5]. We show that a subtle flaw in their construction allows even a simple passive adversary (also known as an "honest-but-curious adversary") to discover private data when evaluating such a garbled circuit. In particular, information leaks from the garbled circuit at places where multiple gates share a common input wire, and is extracted by exploiting dependencies between the gate labels of the multiple gates that share that input wire. In addition to showing how this flaw manifests itself and how it can be exploited, we pinpoint the errors in the corresponding security proof [19]. Finally, we introduce a new type of gate called a "splitter" which corrects the security flaw by removing all instances of shared input wires, and using this we can correct the problems in the proof as well, giving a secure garbled circuit. This corrected

Huanhuan CHEN

Xiao Shaun Wang, Samuel Ranellucci, Jonathan I. Katz

We propose a simple and efficient framework for obtaining efficient constant-round protocols for maliciously secure two-party computation. Our framework uses a function-independent preprocessing phase to generate authenticated information for the two parties; this information is then used to construct a single "authenticated" garbled circuit which is transmitted and evaluated. We also show how to efficiently instantiate the preprocessing phase with a new, highly optimized version of the TinyOT protocol by Nielsen et al.