Characterizations of the Existence of Partial and Total One-Way Permutations
| dc.creator | Rothe, Joerg | |
| dc.creator | Hemaspaandra, Lane A. | |
| dc.date | 1999-07-26 | |
| dc.date.accessioned | 2026-07-07T03:24:16Z | |
| dc.date.available | 2026-07-07T03:24:16Z | |
| dc.description | In this note, 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 an important open question in cryptology. 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 extends results of Grollmann and Selman. By Grädel's recent results about one-way functions, this also links statements about easy certificates of NP sets with statements in finite model theory. Similarly, there exist surjective poly-one one-way functions if and only if there is a set L in P such that not all FewP machines accepting L always have easy certificates. We also establish a condition necessary and sufficient for the existence of (total) one-way permutations. | |
| dc.description | 12 pages; An extended abstract of this paper was presented at the Third Italian Conference on Algorithms and Complexity | |
| dc.identifier | https://arxiv.org/abs/cs/9907040 | |
| dc.identifier | http://arxiv.org/abs/cs/9907040 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33262 | |
| dc.subject | Computational Complexity | |
| dc.subject | Cryptography and Security | |
| dc.subject | F.1.3; E.3 | |
| dc.title | Characterizations of the Existence of Partial and Total One-Way Permutations | |
| dc.type | text |