Cryptography today has evolved far beyond its traditional goal of secure message transmission. Through the notion of secure computation, a set of mutually dis- trustful agents can collaborate to accomplish a common goal while preserving each agent's privacy to a maximal extent. In the seminal works of Yao and Goldreich, Micali and Wigderson, it was shown that any computational task can be securely implemented through a protocol. Traditionally, the rules governing privacy for these protocols have been designed to work only when a single execution running in isolation. However, with the advent of the Internet, many transactions occur simultaneously, and the protocols designed for the single execution setting fail to remain secure in a concurrent setting. While both the need and definitions for concurrent security were realized in the early 90's, practical protocols that are concurrently secure are lacking. The protocols designed for concurrent security, thus far, have mostly relied on having a trusted setup or a relaxed definition of security. In this thesis, we put forward a unified framework for the construction of concurrently secure protocols both with and without trusted set-up. This framework not only provides a conceptually simple solution for essentially all previous results, but also significantly improves efficiency and reduces the requirements on the trusted setup used in these works. Moreover, in several setup models, our constructions are tight with respect to computational assumptions and efficiency.
Cryptography today has evolved far beyond its traditional goal of secure message transmission. Through the notion of secure computation, a set of mutually dis- trustful agents can collaborate to accomplish a common goal while preserving each agent's privacy to a maximal extent. In the seminal works of Yao and Goldreich, Micali and Wigderson, it was shown that any computational task can be securely implemented through a protocol. Traditionally, the rules governing privacy for these protocols have been designed to work only when a single execution running in isolation. However, with the advent of the Internet, many transactions occur simultaneously, and the protocols designed for the single execution setting fail to remain secure in a concurrent setting. While both the need and definitions for concurrent security were realized in the early 90's, practical protocols that are concurrently secure are lacking. The protocols designed for concurrent security, thus far, have mostly relied on having a trusted setup or a relaxed definition of security. In this thesis, we put forward a unified framework for the construction of concurrently secure protocols both with and without trusted set-up. This framework not only provides a conceptually simple solution for essentially all previous results, but also significantly improves efficiency and reduces the requirements on the trusted setup used in these works. Moreover, in several setup models, our constructions are tight with respect to computational assumptions and efficiency.
The notion of secure computation is central to cryptography. Introduced in the seminal works of Yao [FOCS'82, FOCS'86] and Goldreich, Micali and Wigderson [STOC'87], secure multiparty computation allows a group of (mutually) distrustful parties to jointly compute any functionality over their individual private inputs in such a manner that the honest parties obtain the correct outputs and no group of malicious parties learn anything beyond their inputs and the prescribed outputs. General feasibility results for secure computation were given by Yao [FOCS'86] and Goldreich et al. [STOC'87] more than two decades ago. Subsequent to these works, designing secure computation protocols that can tolerate more powerful adversaries and satisfy stronger notions of security has been a very active area of research. In this dissertation, we study two such new frontiers in the area of secure computation.
In the first part of this dissertation, we initiate a study of designing leakage-resilient interactive protocols. Specifically, we consider the scenario where an adversary, in addition to corrupting a subset of parties, can leak (potentially via physical attacks) arbitrary information from the secret state of any honest party. This is in contrast to the standard notion of secure computation where it is assumed that the adversary only has black-box'' access to the honest parties. In particular, we formalize a meaningful definition of leakage-resilient zero knowledge proof systems and provide constructions that satisfy our notion. We also discuss various applications of our results.
The second part of this dissertation concerns with the general question of whether it is possible to securely run cryptographic protocols over an insecure network environment such as the Internet. It is well-known that the standard notion of secure computation is only relevant to the stand-alone setting where a single protocol is being executed in isolation; as such it does not guarantee security when multiple protocol sessions may be executed concurrently under the control of an adversary who is present across all sessions. We consider the open problem of constructing secure password-based authenticated key exchange protocols in such a setting in the plain model (i.e., without assuming any trusted infrastructure or random oracles). We give the first construction of such a protocol based on standard cryptographic assumptions. Our results are in fact much more general, and extend to other functionalities w.r.t. a (necessarily) weakened notion of concurrently secure computation.
The results presented in this dissertation stem from two papers which are joint works with Sanjam Garg and Amit Sahai, and with Vipul Goyal and Rafail Ostrovsky, respectively.
We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments. Essentially all results on concurrent secure computation--both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)--are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions.
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.
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.
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.
This thesis proposes several protocols for achieving secure com- putation under concurrent and physical attacks. Secure computation allows many parties to compute a joint function of their inputs, while keeping the privacy of their input preserved. It is required that the pri- vacy one party's input is preserved even if other parties participating in the protocol collude or deviate from the protocol. In this thesis we focus on concurrent and physical attacks, where adversarial parties try to break the privacy of honest parties by ex- ploiting the network connection or physical weaknesses of the honest parties' machine. In the rst part of the thesis we discuss how to construct proto- cols that are Universally Composable (UC for short) based on physical setup assumptions. We explore the use of Physically Uncloneable Func- tions (PUFs) as setup assumption for achieving UC-secure computa- tions. PUF are physical noisy source of randomness. The use of PUFs in the UC-framework has been proposed already in [14]. However, this work assumes that all PUFs in the system are trusted. This means that, each party has to trust the PUFs generated by the other parties. In this thesis we focus on reducing the trust involved in the use of such PUFs and we introduce the Malicious PUFs model in which only PUFs generated by honest parties are assumed to be trusted. Thus the secu- rity of each party relies on its own PUF only and holds regardless of the goodness of the PUFs generated/used by the adversary. We are able to show that, under this more realistic assumption, one can achieve UC- secure computation, under computational assumptions. Moreover, we show how to achieve unconditional UC-secure commitments with (ma- licious) PUFs and with stateless tamper-proof hardware tokens. We discuss our contribution on this matter in Part I. These results are contained in papers [80] and [28]. In the second part of the thesis we focus on the concurrent setting, and we investigate on protocols achieving round optimality and black- box access to a cryptographic primitive. We study two fundamental functionalities: commitment scheme and zero knowledge, and we focus on some of the round-optimal constructions and lower bounds con- cerning both functionalities. We nd that such constructions present subtle issues. Hence, we provide new protocols that actually achieve the security guarantee promised by previous results. Concerning physical attacks, we consider adversaries able to re- set the machine of the honest party. In a reset attack a machine is forced to run a protocol several times using the same randomness. In this thesis we provide the rst construction of a witness indistinguish- able argument system that is simultaneous resettable and argument of knowledge. We discuss about this contribution in Part III, which is the content of the paper. [edited by Author]