Efficient Round-Optimal Secure Two-Party Computation from Sigma-protocol

Yonglong Tang, Chunming Tang

Published Apr 1, 2010• 0 citations

Abstract

In this paper, based on Sigma-protocol on HC (a NP-complete language), we firstly construct a Sigma-protocol for any NP language thm1 ∧ thm2, then transfer it into a non-interactive protocol from a hash function and a pseudo-random generator. Finally, we construct an efficient round-optimal secure two-party computation protocol from our non-interactive protocols.

DOI: 10.1109/cmc.2010.280

Related papers

Fast Two-Party Secure Computation with Minimal Assumptions.

Abhi A. Shelat, Chih-Hao Shen

Abstract. All recent implementations of two-party secure computation protocols require specific complexity assumptions for their correctness and/or efficiency (e.g., DDH, homomorphic encryption, Sigma protocols for specific languages). We propose and implement a Yao-based protocol for secure two-party computation against malicious adversaries that enjoys the following benefits: 1. it assumes the minimal hardness assumption, that is, oblivious transfers; 2. it has constant round complexity; 3. its overhead is linear times (in terms of security parameter) of the Yao protocol’s, which is the best one could hope for by using the circuit-level cut-and-choose technique to achieve malicious security; and 4. it is embarrassingly parallelizable in that its depth complexity is roughly the same as the Yao protocol. To achieve these properties, we use the cut-and-choose paradigm, but solve the main three problems for achieving malicious security (input consistency, selective failure, and output authentication) in a novel and efficient manner. In particular, we propose an efficient witness-indistinguishable proof for output authentication; we suggest the use of an auxiliary 2-universal circuit to ensure the generator’s input consistency; and we advance the performance of the state-of-the-art approach defending the selective failure attack. Not only does our protocol require weaker complexity assumptions, but our implementation of this protocol also demonstrates a several factor improvement over the best prior two-party secure computation protocol which rely on specific number theoretic assumptions.

Jan 1, 20130 citations

Bounded-concurrent secure two-party computation in a constant number of rounds

Rafael Pass, Alon Rosen

We consider the problem of constructing a general protocol for secure two-party computation in a way that preserves security under concurrent composition. In our treatment, we focus on the case where an a-priori bound on the number of concurrent sessions is specified before the protocol is constructed. (a.k.a. bounded concurrency). We make no setup assumptions. Lindel (STOC 2003) has shown that any protocol for bounded-concurrent secure two-party computation, whose security is established via black-box simulation, must have round complexity that is strictly larger than the bound on the number of concurrent sessions. In this paper, we construct a (non black-box) protocol for realizing bounded-concurrent secure two-party computation in a constant number of rounds. Our constructions rely on the existence of enhanced trapdoor permutations, as well as on the existence of hash functions that are collision-resistant against subexponential sized circuits.

Annual Symposium on Foundations of Computer ScienceMar 1, 200487 citations

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries.

Yehuda Lindell, Benny Pinkas B

Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1

Jan 1, 20080 citations

Design and Implementation of Maliciously Secure Two-Party Computation Based on Garbled Circuits

Afshar, Arash

In this thesis we design and implement three approaches to provide efficient Secure Two- Party Computation (2PC) protocols that are secure in presence of malicious adversaries. The field of secure two-party computation enables two mutually distrusting parties, each with their own private input, to run a computation of an arbitrary program. At the end of the computation, nothing about their private input is leaked except for what can be learned from the output of the computation. The seminal work of Yao in 1986 provided the first proof that such a computation is feasible using the so called garbled circuits and given an Oblivious Transfer protocol. In this thesis, we follow Yao’s garbled circuit approach and focus on efficient protocols that are secure against malicious adversaries. We examine three different categories of optimization. In each category, we present a 2PC protocol, prove its security, and implement it as a proof of concept to demonstrate its running time in practice. Non-interactive Secure Computation: In this category, we offer the first implementation of a malicious 2PC protocol that reduces the required rounds of interaction between the two parties to only two rounds (i.e., each party sends only one message to the other party). Mixed Secure Two-Party Computation: In the second category we target big and complex programs and break them into subprograms. Then, we compute each subprogram using the most efficient 2PC protocol that is suitable for it. Finally, we securely connect these subprograms together. The goal is to reduce the overhead of the garbled circuits significantly, which results in a more efficient overall 2PC protocol for programs with specific properties. Secure Computation for Random Access Machine Programs: In the third category, we target programs that require random access to the memory (as opposed to a sequential access). We present the first efficient maliciously-secure protocol for computing such programs.

Jan 1, 20170 citations

Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Oct 27, 2017173 citations

Efficient Non-Interactive Secure Two-Party Computation for Equality and Comparison

Negin Karimian Ardestani

Multi-party computation is receiving more and more attention as its application in more areas prove promising. In this research, our focus is on secure two-party computation. In particular, we propose non-interactive constructions for securely computing private equality testing and greater-than testing protocols. Our first construction is a private equality testing (PET) protocol. What distinguishes our construction from the state of the art is that it is single-round and secure against malicious adversaries. Our second construction is a private greater-than testing (PGT) protocol (i.e. the Yao's Millionaires problem) which is also single-round but only secure in the semi-honest model. Our protocols are based on the Peikert-Vaikuntanathan-Waters maliciously secure oblivious transfer and a collision resistant hash function. We formally prove that the PET protocol and the PGT protocol provide computational security. In this research, we developed our protocol for PET and run experiments to test it. The results provide evidence of efficiency of our protocol.

Jan 1, 20152 citations