Characterizations of the Existence of Partial and Total One-Way Permutations
<|reference_start|>Characterizations of the Existence of Partial and Total One-Way Permutations: 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.<|reference_end|>
@article{rothe1999characterizations,
    title={Characterizations of the Existence of Partial and Total One-Way
  Permutations},
    author={Joerg Rothe and Lane A. Hemaspaandra},
    journal={arXiv preprint arXiv:cs/9907040},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9907040},
    primaryClass={cs.CC cs.CR}
}