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

Simple item page
dc.creatorHemaspaandra, Lane A.
dc.creatorRothe, Joerg
dc.creatorSaxena, Amitabh
dc.date2005-03-21
dc.date2007-11-01
dc.date.accessioned2026-07-07T08:39:47Z
dc.date.available2026-07-07T08:39:47Z
dc.descriptionRabi 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.
dc.descriptionUpdated version
dc.identifierhttps://arxiv.org/abs/cs/0503049
dc.identifierhttp://arxiv.org/abs/cs/0503049
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/141193
dc.subjectComputational Complexity
dc.subjectF.1.3
dc.titleEnforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory
dc.typetext

Files

Collections

arXiv