Concurrently Secure Computation in Constant Rounds

Sanjam Garg, Vipul Goyal, Abhishek Jain, Amit Sahai

Published Jan 1, 2011• 0 citations

Abstract

We study the problem of constructing concurrently secure computation protocols in the plain model, where no trust is required in any party or setup. While the well established UC framework for concurrent security is impossible to achieve in this setting, a meaningful notion of concurrent security based on super-polynomial simulation (SPS) is achievable and has been extensively studied [Pas03, PS04, BS05, LPV09, CLP10]. The recent work of [CLP10] obtains a concurrently secure computation protocol in the plain model with SPS security under standard assumptions, but requires a number of rounds of interaction that is polynomial in the security parameter. In this work, we obtain the first concurrently secure computation protocol in the plain model with SPS security that uses only a constant number of rounds and requires only standard assumptions. To accomplish our result, we introduce a new proof technique that significantly reduces the demands placed on “rewinding techniques ” employed in previous work. We believe that our techniques are of independent interest and likely to be applicable in other settings related to secure

Related papers

Protocols for Bounded-Concurrent Secure Two-Party Computation in the Plain Model.

Yehuda Lindell

Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of bounded-concurrent self composition, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that any two-party functionality can be securely computed under boundedconcurrent self composition, in the plain model (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, for any model of concurrency. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient protocols for this task.

Jan 1, 20036 citations

How to Play ANY Mental Game Over the Net Concurrently composable secure computation without setup assumptions

Boaz Barak, Amit Sahai

We construct a protocol for general multi-party computation that remains secure even if executed concurrently with multiple copies of itself and of arbitrary other protocols. This is the first such construction that is based on standard cryptographic assumptions and does not require setup conditions such as the existence of a common reference string. Furthermore, our protocol utilizes only a constant number of communication rounds and remains secure also with respect to adaptive adversaries (without using memory erasures). The security of our protocol is demonstrated by a simulator with a quasi-polynomial simulation overhead, as opposed to the standard notion of polynomial simulation. However, quasipolynomial simulation still provides sufficient security for almost all applications. Furthermore, it was previously shown that there does not exist such a protocol with polynomial simulation

Jan 1, 20050 citations

Round-Efficient Concurrently Composable Secure Computation via a Robust Extraction Lemma.

Vipul Goyal, Omkant Pandey, Amit Sahai

We consider the problem of constructing protocols for secure computation that achieve strong concurrent and composable notions of security in the plain model. Unfortunately UC-secure secure computation protocols are impossible in this setting, but the Angel-Based Composable Security notion offers a promising alternative. Until now, however, under standard (polynomialtime) assumptions, only protocols with polynomially many rounds were known to exist. In this work, we give the first Õ(log n)-round secure computation protocol in the plain model that achieves angel-based composable security in the concurrent setting, under standard assumptions. We do so by constructing the first Õ(log n)-round CCA-secure commitment protocol. Our CCA-secure commitment protocol is secure based on the minimal assumption that one-way functions exist. A central tool in obtaining our result is a new robust concurrent extraction lemma that we introduce and prove, based on the minimal assumptions that one-way functions exist. This robust concurrent extraction lemma shows how to build concurrent extraction procedures that work even in the context of an “external ” protocol that cannot be rewound by the extractor. We believe this lemma can be used to simplify many existing works on concurrent security, and is of independent interest. In fact, our lemma when used in conjunction with the concurrent-simulation schedule of Pass and Venkitasubramaniam (TCC’08), also yields a constant round construction based additionally on the existence of quasi-polynomial time (PQT) secure one-way functions. 1

Jan 1, 20121 citation

Bounded-concurrent secure multi-party computation with a dishonest majority

Rafael Pass

We show how to securely realize any multi-party functionality in a way that preserves security under an a-priori bounded number of concurrent executions, regardless of the number of corrupted parties. Previous protocols for the above task either rely on set-up assumptions such as a Common Reference String, or require an honest majority. Our constructions are in the plain model and rely on standard intractability assumptions (enhanced trapdoor permutations and collision resistant hash functions). Even though our main focus is on feasibility of concurrent multi-party computation we actually obtain a protocol using only a constant number of communication rounds. As a consequence our protocol yields the first construction of constant-round phstand-alone secure multi-party computation with a dishonest majority, proven secure under standard (polynomial-time) hardness assumptions; previous solutions to this task either require logarithmic round-complexity, or subexponential hardness assumptions. The core of our protocol is a novel construction of (concurrently) simulation-sound zero-knowledge protocols, which might be of independent interest. Finally, we extend the framework constructed to give a protocol for secure multi-party (and thus two-party) computation for any number of corrupted parties, which remains secure even when arbitrary subsets of parties concurrently execute the protocol, possibly with interchangeable roles. As far as we know, for the case of two-party or multi-party protocols with a dishonest majority, this is the first positive result for any non-trivial functionality which achieves this property in the plain model.

ACM Symposium on Theory of Computing (STOC)Jun 13, 2004183 citations

Bounded-concurrent secure two-party computation without setup assumptions

Yehuda Lindell

In this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (A general protocol can be used for obtaining secure computation of any functionality.) We consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". We present both negative and positive results for this model. Specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. An important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). On the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). Our protocol has O(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. We note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.

ACM Symposium on Theory of Computing (STOC)Jan 1, 200310 citations

Positive Results for Concurrently Secure Computation in the Plain Model.

Vipul Goyal

We consider the question of designing concurrently self-composable protocols in the plain model. We first focus on the minimal setting where there is a party P1 which might interact with several other parties in any unbounded (polynomial) number of concurrent sessions. P1 holds a single input x which it uses in all the concurrent sessions. An analogy is a server interacting with various clients at the same time. In this “single input ” setting, we show that many (or even most) functionalities can be securely realized in the plain model. More precisely, we are able to realize all functionalities except ones which are a (weak form of) cryptographic unpredictable function. We complement our positive result by showing an impossibility result in this setting for a functionality which evaluates a pseudorandom function. Our security definition follows the standard ideal/real world simulation paradigm (with no super polynomial simulation etc). There is no apriori bound on the number of concurrent executions. We also show interesting extensions of our positive results to the more general setting where the honest parties may choose different inputs in different session (even adaptively), the roles that the parties assume in the protocol may be interchangeable, etc. Prior to our work, the only positive results known in the plain model in the fully concurrent setting were for zero-knowledge. 0 1

Jan 1, 20111 citation