Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory

Lane A. Hemaspaandra, Jörg Rothe, Amitabh Saxena

Abstract

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) that are total, commutative, and associative but not strongly noninvertible. In this paper we improve the sufficient condition to P ≠ NP.
BibTeX
@inproceedings{hemaspaandra2005enforcing,
  author = {Lane A. Hemaspaandra and Jörg Rothe and Amitabh Saxena},
  title = {{Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory}},
  booktitle = {ICTCS},
  year = {2005},
  doi = {10.1007/11560586\_22},
}

Loading related content...

Figure