Lin, Hui Jia
Traditionally, cryptographic protocols are analyzed in a "stand-alone" setting, where a single protocol execution takes place in isolation. In the age of the Internet, however, a great number of executions of different protocols co-exist and are tightly inter-connected. This concurrency severely undermines the foundation of the traditional study of cryptography. Since the early 90's, it has been an important theme in cryptography to address security in such concurrent setting. However, till recently, no satisfactory solutions were proposed for performing general tasks in a concurrently secure way. In this thesis, we resolve "concurrent security"-we exhibit a construction of cryptographic protocols for general tasks that remain secure even in concurrent settings like the Internet. Different from previous works, our construction does not rely on any trusted infrastructure or strong hardness assumptions. As such, our construction broadens the applicability of cryptography by enabling it in more realistic settings and weakening the preconditions it is based on. Beyond the general feasibility result, we also significantly improve the efficiency of secure protocols for performing general tasks even in the standalone setting: We construct constant-round secure protocols for general tasks based on enhanced trapdoor permutations; this yields the first improvement on the round-efficiency-from linear to constant-over the original construction of [GMW87] based on the same assumptions as [GMW87]. Towards our constructions, we identify the key role of "input independence" in achieving concurrent security. Intuitively, if adversaries are forced to act independently in different protocol executions, then concurrency comes for free since it is as if each execution were taking place in isolation. We study two notions of "input independence": Non-malleability and adaptive hardness. Both notions are central tools in cryptography and have been extensively studied. A main question is to determine the number of rounds needed for protocols satisfying these notions. In this thesis, we completely resolve the round-complexity of these two notions in the context of commitments: We construct constantround non-malleable commitments-introduced by [DDN91]-and [omega](log n)-round adaptively hard commitments-or CCA-secure commitments introduced in this thesis-from the minimal assumption of one-way functions without using any trusted infrastructure; the latter construction as we show is round optimal.
Secure Multi-Party Computation; CCA security; Non-Malleability
Pass, Rafael N.
Kleinberg, Jon M; Joachims, Thorsten
Ph.D. of Computer Science
Doctor of Philosophy
dissertation or thesis