UMD Theses and Dissertations

Permanent URI for this collectionhttp://hdl.handle.net/1903/3

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

20071

Settings

Author: search.filters.author.Horvitz, David OmerSubject: search.filters.subject.commitment

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Expressiveness of Definitions and Efficiency of Constructions in Computational Cryptography
    (2007-08-05) Horvitz, David Omer; Gligor, Virgil D; Katz, Jonathan; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The computational treatment of cryptography, and indeed any scientific treatment of a problem, is marked by its definitional side and by it constructive side. Results in this thesis better our understanding of both: on one side, they characterize the extent to which computational definitions capture the security of the basic task of symmetric encryption; on the other, they provide explicit bounds on the efficiency of commitment and secure two-party computation constructions. Specifically: - We relate the formal and computational treatments of symmetric encryption, obtaining a precise characterization of computational schemes whose computational semantics imply their formal semantics. We prove that this characterization is strictly weaker than previously-identified notions, and show how it may be realized in a simpler, more efficient manner. - We provide lower-bounds on the number of times a one-way permutation needs to be invoked (as a "black-box") in order to construct statistically-binding commitments. Our bounds are tight for the case of perfectly-binding schemes. - We show that the secure computation of any two-party functionality can be performed in an optimal two rounds of communication even in a setting that accounts for concurrent execution with other protocols (i.e., the Universal Composability framework). Here, we rely on the assumption that parties have access to a common reference string; some sort of setup is known to be necessary.