Re: Q: One-way functions

From: John A. Malley (102667.2235@compuserve.com)
Date: 03/31/03 

From: "John A. Malley" <102667.2235@compuserve.com>
Date: Sun, 30 Mar 2003 21:15:07 -0800

Rick Wash wrote:
[...]

There's been some refinement in the constrainsts on computational
classes that must exist if one-way functions exist.

Christos H. Papadimitriou in his book "Computational Complexity", c.
1995, ISBN0-201-53082-1 shows the more appropriate computational context
for discussing the existence of one-way functions is "is P!= UP?" and
not "is P!= NP?". On page 283 he shows P = UP iff there are no one-way
functions.

UP (a subset of NP) is the class of languages accepted by unambiguous
polynoimal-time bounded nondeterministic Turing Machines. A
nondeterministic Turing Machine is unambiguous if for any input x, there
is at most one accepting computation.

In 2001, Homan and Thakur showed that one-way permutations exist iff

        P != UP intersect coUP

See Homan, C.M., Thakur, M., "One-Way Permutations and Self-Witnessing
Languages", TR760, Computer Science Dept., U. Rochester, November 2001.

ftp://ftp.cs.rochester.edu/pub/papers/theory/01.tr760.One-way_permutations_and_self-witnessing_languages.ps.gz

So this means the existence of signiture schemes, identification
schemes, telephone coin flipping, private-key cryptosystems and
pseudorandom generators require P != UP intersect coUP.

So (somebody correct me if I get this wrong), given

        P!= UP iff there are one-way functions,
          P != UP intersect coUP iff there are one-way permutations,

if UP != coUP then there are one-way functions that are not permutations
  else all one-way functions are one-way permutations.

John A. Malley
102667.2235@compuserve.com