Computer Science – Computational Complexity
Scientific paper
1999-07-26
Computer Science
Computational Complexity
12 pages; An extended abstract of this paper was presented at the Third Italian Conference on Algorithms and Complexity
Scientific paper
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\"adel'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.
Hemaspaandra Lane A.
Rothe Joerg
No associations
LandOfFree
Characterizations of the Existence of Partial and Total One-Way Permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Characterizations of the Existence of Partial and Total One-Way Permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizations of the Existence of Partial and Total One-Way Permutations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-619318