Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

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 give thesis/dissertation in DRUM

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

Browse

Filters

2007 - 20102

Settings

Subject: search.filters.subject.secure computation

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    On Fairness in Secure Computation
    (2010) Gordon, Samuel Dov; Katz, Jonathan; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Secure computation is a fundamental problem in modern cryptography in which multiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980's demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the fairness property, which states that no player should receive their output from the computation unless all players receive their output. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guarantee different notions of partial fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impossibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the presence of rational adversaries, and, finally, we further study the difficulty of achieving fairness by exploring how much external help is necessary for enabling fair secure computation.
  • 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.