Expressiveness of Definitions and Efficiency of Constructions in Computational Cryptography

dc.contributor.advisorGligor, Virgil Den_US
dc.contributor.advisorKatz, Jonathanen_US
dc.contributor.authorHorvitz, David Omeren_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.description.abstractThe 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 <em>formal</em> and <em>computational</em> treatments of symmetric encryption, obtaining a <em>precise</em> 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 <em>perfectly</em>-binding schemes. - We show that the secure computation of <em>any</em> two-party functionality can be performed in an optimal <em>two</em> 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.en_US
dc.format.extent847307 bytes
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledsymmetric encryptionen_US
dc.subject.pquncontrolledformal modelingen_US
dc.subject.pquncontrolleduniversal composabilityen_US
dc.subject.pquncontrolledsecure computationen_US
dc.titleExpressiveness of Definitions and Efficiency of Constructions in Computational Cryptographyen_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
827.45 KB
Adobe Portable Document Format