Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory
<|reference_start|>Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory: Rabi and Sherman [RS97,RS93] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i.e., p-time computable, honest, p-time noninvertible functions; this paper is in the worst-case model, not the average-case model) that are total, commutative, and associative but not strongly noninvertible. In this paper we improve the sufficient condition to ``P does not equal NP.''   More generally, in this paper we completely characterize which types of one-way functions stand or fall together with (plain) one-way functions--equivalently, stand or fall together with P not equaling NP. We look at the four attributes used in Rabi and Sherman's seminal work on algebraic properties of one-way functions (see [RS97,RS93]) and subsequent papers--strongness (of noninvertibility), totality, commutativity, and associativity--and for each attribute, we allow it to be required to hold, required to fail, or ``don't care.'' In this categorization there are 3^4 = 81 potential types of one-way functions. We prove that each of these 81 feature-laden types stand or fall together with the existence of (plain) one-way functions.<|reference_end|>
@article{hemaspaandra2005enforcing,
    title={Enforcing and Defying Associativity, Commutativity, Totality, and Strong
  Noninvertibility for One-Way Functions in Complexity Theory},
    author={Lane A. Hemaspaandra, Joerg Rothe, Amitabh Saxena},
    journal={arXiv preprint arXiv:cs/0503049},
    year={2005},
    number={URCS-TR-2005-854},
    archivePrefix={arXiv},
    eprint={cs/0503049},
    primaryClass={cs.CC}
}