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
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
The cryptographic primitive Secure Function Evaluation (SFE) enables the evaluation of a function public function f (x, y), under input parameters that are provided by different parties without them revealing their specific value.Restricting SFE further by requiring the function to be only known by one party is called Private Function Evaluation (PFE).Furthermore Semi-Private Function Evaluation (SPF-SFE) can help to increase the maximum function size which can be evaluated in a somewhat private manner.One way to achieve SPF-SFE is to split the function into blocks, as was shown in [PSS09].However their implementation was crafted specifically for Yao's garbled Circuit protocol.Therefore there are protocols, namely Goldreich-Micali-Wigderson (GMW), by which it could not be evaluated.We provide circuit designs for different Privately Programmable Blocks, which are constructed to work with the GMW protocol as well.Additionally we provide a toolchain to achieve SPF-SFE efficiently.Furthermore we implemented a tool used in the toolchain, which uses the aforementioned designs and can combine them with plain circuits and Universal Circuits (UCs) to build a single programmable circuit.A function designer can use the toolchain to balance out his needs for function privacy with performance.Contents 5.2.4 Combined Circuits . . .
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.
Abstract. We show how two existing paradigms for two-party secure function evaluation (SFE) in the semi-honest model can be combined securely and efficiently – those based on additively homomorphic encryption (HE) with those based on garbled circuits (GC) and vice versa. Additionally, we propose new GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using the above building blocks (including the protocols for combining HE and GC). Based on these results, we present efficient constant-round protocols for secure integer comparison, and the related problems of minimum selection and minimum distance, which are crucial building blocks of many cryptographic schemes such as privacy preserving biometric authentication (e.g., face recognition, fingerprint matching, etc).
We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input xA, Bob has an input xB and we want Bob to learn some function y = f(xA, xB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice’s key. In a trivial insecure protocol, Alice can just send her short input xA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such “output-size dependence” inherent in SFE? Surprisingly, we show that output-size dependence can be avoided in the honest-butcurious setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a “somewhere statistically binding (SSB) hash”, and which may be of independent interest. On the negative side, we show that output-size dependence is inherent in the fully malicious setting, or even already in an honest-but-deterministic setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.
We consider the problem of private function evaluation (PFE) in the two-party setting. Here, informally, one party holds an input x while the other holds a circuit describing a function f; the goal is for one (or both) of the parties to learn f(x) while revealing nothing more to either party. In contrast to the usual setting of secure computation — where the function being computed is known to both parties — PFE is useful in settings where the function (i.e., algorithm) itself must remain secret, e.g., because it is proprietary or classified. It is known that PFE can be reduced to standard secure computation by having the parties evaluate a universal circuit, and this is the approach taken in most prior work. Using a universal circuit, however, introduces additional overhead and results in a more complex implementation. We show here a completely new technique for PFE that avoids universal circuits, and results in constant-round protocols with communication/computational complexity linear in the size of the circuit computing f. This gives the first constant-round protocol for PFE with linear complexity (without using fully homomorphic encryption), even restricted to semi-honest adversaries. 1