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

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

2005-03-21

arxiv.org/abs/cs/0503049v3

Computer Science

Computational Complexity

Updated version

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-160037