Show simple item record

dc.contributor.advisorKatz, Jonathanen_US
dc.contributor.authorYerukhimovich, Arkady Borisen_US
dc.date.accessioned2012-02-17T06:32:51Z
dc.date.available2012-02-17T06:32:51Z
dc.date.issued2011en_US
dc.identifier.urihttp://hdl.handle.net/1903/12199
dc.description.abstractFor more than 20 years, black-box impossibility results have been used to argue the infeasibility of constructing certain cryptographic primitives (e.g., key agreement) from others (e.g., one-way functions). In this dissertation we further extend the frontier of this field by demonstrating several new impossibility results as well as a new framework for studying a more general class of constructions. Our first two results demonstrate impossibility of black-box constructions of two commonly used cryptographic primitives. In our first result we study the feasibility of black-box constructions of predicate encryption schemes from standard assumptions and demonstrate strong limitations on the types of schemes that can be constructed. In our second result we study black-box constructions of constant-round zero-knowledge proofs from one-way permutations and show that, under commonly believed complexity assumptions, no such constructions exist. A widely recognized limitation of black-box impossibility results, however, is that they say nothing about the usefulness of (known) non-black-box techniques. This state of affairs is unsatisfying as we would at least like to rule out constructions using the set of techniques we have at our disposal. With this motivation in mind, in the final result of this dissertation we propose a new framework for black-box constructions with a non-black-box flavor, specifically, those that rely on zero-knowledge proofs relative to some oracle. Our framework is powerful enough to capture a large class of known constructions, however we show that the original black-box separation of key agreement from one-way functions still holds even in this non-black-box setting that allows for zero-knowledge proofs.en_US
dc.titleA Study of Separations in Cryptography: New Results and New Modelsen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentComputer Scienceen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledblack-box separationsen_US
dc.subject.pquncontrolledkey agreementen_US
dc.subject.pquncontrolledpredicate encryptionen_US
dc.subject.pquncontrolledzero-knowledge proofsen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record