Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory
Lists
Only you see this
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...