Back to search

Cornell University

Concurrent Security

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lin, Hui Jia
Chair dc:contributor.chair
  • Pass, Rafael N.
Committee members dc:contributor.committeemember
  • Kleinberg, Jon M
  • Joachims, Thorsten

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7745174

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lin, Hui Jia. Concurrent Security. Doctor of Philosophy thesis, Cornell University, 2012. https://hdl.handle.net/1813/29141