eCommons

 

Concurrent Security

Other Titles

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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

2012-01-31

Publisher

Keywords

Secure Multi-Party Computation; CCA security; Non-Malleability

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Pass, Rafael N.

Committee Co-Chair

Committee Member

Kleinberg, Jon M
Joachims, Thorsten

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record