We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition---assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the “angel-based” framework of Prabhakaran and Sahai [STOC'04, ACM, New York, 2004, pp. 242--251] and implies superpolynomial-time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment attacks (CCA security), means that security holds even if the attacker has access to an extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent nonmalleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted setup. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive having adaptive hardness from standard hardness assumptions, using no trusted setup or public keys.
We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition---assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the “angel-based” framework of Prabhakaran and Sahai [STOC'04, ACM, New York, 2004, pp. 242--251] and implies superpolynomial-time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment attacks (CCA security), means that security holds even if the attacker has access to an extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent nonmalleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted setup. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive having adaptive hardness from standard hardness assumptions, using no trusted setup or public keys.
We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition- assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the "angelbased" framework of Prabhakaran and Sahai (STOC'04) and implies super-polynomial time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment-attacks (CCA security), means that security holds even if the attacker has access to a extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent non-malleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted set-up. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive requiring adaptive hardness from standard hardness assumptions, using no trusted set-up or public keys.
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
We close the gap between black-box and non-black-box constructions of composable secure multiparty computation in the plain model under the minimal assumption of semi-honest oblivious transfer. The notion of protocol composition we target is angel-based security, or more precisely, security with super-polynomial helpers. In this notion, both the simulator and the adversary are given access to an oracle called an angel that can perform some predefined super-polynomial time task. Angel-based security maintains the attractive properties of the universal composition framework while providing meaningful security guarantees in complex environments without having to trust anyone. Angel-based security can be achieved using non-black-box constructions in max(R_OT,Õ(log n)) rounds where R_OT is the round-complexity of semi-honest oblivious transfer. However, current best known black-box constructions under the same assumption require max(R_OT,Õ(log² n)) rounds. If R_OT is a constant, the gap between non-black-box and black-box constructions can be a multiplicative factor log n. We close this gap by presenting a max(R_OT,Õ(log n)) round black-box construction. We achieve this result by constructing constant-round 1-1 CCA-secure commitments assuming only black-box access to one-way functions.
We present a unified framework for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Our framework captures essentially all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions. Moreover, using our framework we provide first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and in the non-uniform simulation model. Conceptually, our framework can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC ‘09], who considered only non-adaptive adversaries. Their main insight was that stand-alone non-malleability was sufficient for UC-security. A main conceptual contribution of this work is, quite surprisingly, that it is indeed the case even when considering adaptive security. A key element in our construction is a commitment scheme that satisfies a new notion of nonmalleability.
An important security concern for crypto-graphic protocols is the extent to which they adversely affect the security of the systems in which they run. In particular, can we rule out the possibility that introducing a new protocol to a system might, as a "side effect", break the security of unsuspecting protocols in that system? Universally Composable (UC) security rules out such adverse side effects. However, many functionalities of interest provably cannot be realized with UC security unless the protocol participants are willing to put some trust in external computational entities. We propose a notion of security that: (a) allows realizing practically any functionality by protocols in the plain model without putting trust in any external entity; (b) guarantees that secure protocols according to this notion have no adverse side-effects on existing protocols in the system -- as long as the security of these existing protocols is proven via the traditional methodology of black box reduction to a game-based cryptographic hardness assumption with bounded number of rounds. Our security notion builds on the angel-based security notion of Prabhakaran and Sahai. A key part in our analysis is to come up with a CCA-secure commitment scheme that (a) cannot be proven secure via a black box reduction to a game-based assumption, but (b) can be proven secure using a non-black-box reduction. To the best of our knowledge, this is the first time that the interplay between black-box provability and unprovability is used to demonstrate security properties of protocols.
Modeling security for protocols running in the complex network environment of the Internet can be a daunting task. Ideally, a security model for the Internet should provide the following guarantee: a protocol that implements a particular task specification will retain all the same security properties as the specification itself, even when an arbitrary set of protocols runs concurrently on the same network. This guarantee must hold even when other protocols are maliciously designed to interact badly with the analyzed protocol, and even when the analyzed protocol is composed with other protocols. The popular Universal Composability (UC) security framework aims to provide this guarantee.
Unfortunately, such strong security guarantees come with a price: they are impossible to achieve without the use of some trusted setup. Typically, this trusted setup is global in nature, and takes the form of a Public Key Infrastructure (PKI) and/or a Common Reference String (CRS). However, the current approach to modeling security in the presence of such setups falls short of providing expected security guarantees. A quintessential example of this phenomenon is the deniability concern: there exist natural protocols that meet the strongest known security notions (including UC) while failing to provide the same deniability guarantees that their task specifications imply they should provide.
We introduce the Generalized Universal Composability (GUC) framework to extend the UC security notion and enable the re-establishment of its original intuitive security guarantees even for protocols that use global trusted setups. In particular, GUC enables us to guarantee that secure protocols will provide the same level of deniability as the task specification they implement. To demonstrate the usefulness of the GUC framework, we first apply it to the analysis and construction of deniable authentication protocols. Building upon such deniable authentication protocols, we then prove a general feasibility result showing how to construct protocols satisfying our security notion for a large class of two-party and multi-party tasks (assuming the availability of some reasonable trusted setup). Finally, we highlight the practical applicability of GUC by constructing efficient protocols that securely instantiate two common cryptographic tasks: commitments and zero-knowledge proofs.