On characterizing the existence of partial one-way permutations

✍ Scribed by Jörg Rothe; Lane A. Hemaspaandra

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 84 KB
• Volume: 82
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00269-1

✦ Synopsis

We study the easy certificate classes introduced by Hemaspaandra, Rothe, and Wechsung, with regard to the question of whether or not surjective one-way functions exist. This is a natural open question in worst-case cryptography. We show that the existence of partial one-way permutations can be characterized by separating P from the class of UP sets that, for all unambiguous polynomial-time Turing machines accepting them, always have easy (i.e., polynomial-time computable) certificates. This characterization expands results of Grollmann and Selman. We also establish characterizations of the existence of (partial and total) surjective poly-to-one one-way functions.