In the analysis of many cryptographie protocole, it is useful to distinguish two classes of attacks: passive attacks in which an adversary eavesdrops on messages sent between honest users and active attacks (i.e, “man-in-the-middle” attacks) in which—in addition to eavesdropping—the adversary inserts, deletes, or arbitrarily modifies messages sent from one user to another. Passive attacks are well characterized (the adversary's choices are inherently limited) and techniques for achieving security against passive attacks are relatively well understood. Indeed, cryptographers have long focused on methods for countering passive eavesdropping attacks, and much work in the 1970's and 1980's has dealt with formalizing notions of security and providing provably-secure solutions for this setting. On the other hand, active attacks are not well characterized and precise modeling has been difficult. Few techniques exist for dealing with active attacks, and designing practical protocols secure against such attacks remains a challenge.
This dissertation considers active attacks in a variety of settings and provides new, provably-secure protocols preventing such attacks. Proofs of security are in the standard cryptographie model and rely on well-known cryptographie assumptions. The protocols presented here are efficient and practical, and may find application in real-world systems.
In the analysis of many cryptographie protocole, it is useful to distinguish two classes of attacks: passive attacks in which an adversary eavesdrops on messages sent between honest users and active attacks (i.e, “man-in-the-middle” attacks) in which—in addition to eavesdropping—the adversary inserts, deletes, or arbitrarily modifies messages sent from one user to another. Passive attacks are well characterized (the adversary's choices are inherently limited) and techniques for achieving security against passive attacks are relatively well understood. Indeed, cryptographers have long focused on methods for countering passive eavesdropping attacks, and much work in the 1970's and 1980's has dealt with formalizing notions of security and providing provably-secure solutions for this setting. On the other hand, active attacks are not well characterized and precise modeling has been difficult. Few techniques exist for dealing with active attacks, and designing practical protocols secure against such attacks remains a challenge.
This dissertation considers active attacks in a variety of settings and provides new, provably-secure protocols preventing such attacks. Proofs of security are in the standard cryptographie model and rely on well-known cryptographie assumptions. The protocols presented here are efficient and practical, and may find application in real-world systems.
One of the central questions in Cryptography today is proving security of the protocols "on the Internet", i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called "man-in-the-middle" attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, the main challenge in this setting is to provide security with respect to adaptive concurrent composition of protocols and also the non-malleability property, where the "man-in-the-middle" attacks are prevented. Despite much research effort, we do not know how to implement many basic tasks in this setting (which features concurrent composition and man-in-the-middle attacks). Indeed, even
We present a methodology to facilitate the design and analysis of secure cryptographic protocols. We advocate the general approach, and a new avenue for research, of restricting protocol designs to well-defined practices, instead of ever increasing the complexity of protocol security analysis mechanisms to deal with every newly discovered attack and the endless variations in protocol construction. In particular, we propose a novel notion of a fail-stop protocol, which automatically halts in response to any active attack that interferes with protocol execution, thus reducing protocol security analysis to that of passive attacks only. We suggest types of protocols that are fail-stop, outline some proof techniques for them, and use examples to illustrate how the notion of a fail-stop protocol can make protocol design easier and can provide a more solid basis for some available protocol analysis methods.
Abstract. Key establishment protocols based on hardness assumptions, such as the discrete logarithm problem and the integer factorization problem, are vulnerable to quantum computer attacks, whereas the protocols based on other hardness assumptions, such as the conjugacy search problem and the decomposition search problem, can resist such attacks. The existing protocols based on the hardness assumptions which can resist quantum computer attacks are only passively secure. Compilers are used to convert a passively secure protocol to an actively secure protocol. Compilers involve some tools such as a signature scheme and a collision-resistant hash function. If there are only passively secure protocols but not a signature scheme based on the same assumption, then the application of existing compilers requires the use of such tools based on different assumptions. But the introduction of new tools, based on different assumptions, makes the new actively secure protocol rely on more than one hardness assumption. We offer an approach to derive an actively secure two-party protocol from a passively secure two-party protocol without introducing further hardness assumptions. This serves as a useful formal tool to transform any basic algebraic method of public key cryptography to the real world applicable cryptographic scheme.
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.
This thesis is a study of erasures in cryptographic protocols. Erasing old data and keys is an important capability of honest parties in cryptographic protocols. It is useful in many settings, including proactive security in the presence of a mobile adversary, adaptive security in the presence of an adaptive adversary, forward security, and intrusion resilience. Some of these settings, such as achieving proactive security, is provably impossible without some form of erasures. Other settings, such as designing protocols that are secure against adaptive adversaries, are much simpler to achieve when erasures are allowed. Protocols for all these contexts typically assume the ability to perfectly erase information. Unfortunately, as amply demonstrated in the systems literature, perfect erasures are hard to implement in practice.
We propose a model of imperfect or partial erasures where erasure instructions are only partially effective and leave almost all the data intact, thus giving the honest parties only a limited capability to dispose old data. Nonetheless, we show how to design protocols for all of the above settings (including proactive security, adaptive security, forward security, and intrusion resilience) for which this weak form of erasures suffices.
We do not have to invent entirely new protocols, but rather show how to automatically modify protocols relying on perfect erasures into ones for which partial erasures suffices. Stated most generally, we provide a compiler that transforms any protocol relying on perfect erasures for security into one with the same functionality that remains secure even if the erasures are only partial. The key idea is a new redundant representation of secret data which can still be computed on, and yet is rendered useless when partially erased. We prove that any such compiler must incur a cost in additional storage, and that our compiler is near optimal in terms of its storage overhead.
We also give computationally more efficient compilers for a number of special cases: (1) when all the computations on secrets can be done in constant parallel time (NC0); (2) for a class of proactive secret sharing protocols where we leave the protocol intact except for changing the representation of the shares of the secret and the instructions that modify the shares (to correspondingly modify the new representation instead). (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)