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: Mon, 31 Mar 2003 00:27:13 -0800

David Wagner wrote:

> John A. Malley wrote:
>
>>So this means the existence of signiture schemes, identification
>>schemes, telephone coin flipping, private-key cryptosystems and
>>pseudorandom generators require P != UP intersect coUP.
>>
>
> Naah. I think one-way functions suffice for all of those.
> (though I'm not sure about telephone coin-flipping).
>

I remembered from Rudisch S. and Impagliazzo "Limits on the Provable
Consequences of One-Way Permutations",

http://www-2.cs.cmu.edu/~rudich/papers/oneway.ps

that the existence of one-way permutations implies the existence or the
possibility of the items in that list. They give references backing the
claim for each item in the list, but I admit I haven't read their
references, and I assumed that if one-way permutations don't exist then
those items don't exist or aren't possible. Did I goof?

>>if UP != coUP then there are one-way functions that are not
permutations else all one-way functions are one-way permutations.
>>
>
> How does that last bit follow?
>

Ah, now you got me thinking. :-)

If UP = coUP then the assumption P != UP simultaneously implies one-way
functions and one-way permutations exist. I jumped the gun and assumed
  simultaneous existence implies equality, but it doesn't.

I need to look at the example in Papadimitriou's book again with respect
to this question (what are the implications of UP = coUP verses not?)

Just in case anyone reading is interested, it goes like this:

Suppose there is a one-way function f. Define now the following language

        L_f = { (x,y): there is a z such that f(z) = y, and z <= x }

In writing z <= x we assume that all the strings in {0,1}^* are first
ordered by length, and for the same length are lexicographically
ordered, viewed as n-bit integers, so

        null < 0 < 1 < 00 < 01 < 10 < 11 < ....

It can be shown that L_f is an element of UP - P. There's an
unambiguous nondeterministic machine U that accepts L_f and that if L_f
is in P then f can be inverted by binary search, contradicting f's
one-wayness.

John A. Malley
102667.2235@compuserve.com

Relevant Pages

  • Re: Exception to the rule? (Tarski´s T-scheme)
    ... >>can substitute any proposition you want in for p, ... have to get the existence of a sentence from elsewhere. ... implies that, if there is one sentence, there are two things. ... It's not the T-schema which gives you that. ...
    (sci.logic)
  • Re: Double limits at the infinity.
    ... but I think this also implies the existence of the ... David C. Ullrich escreveu: ... >>+inf. ...
    (sci.math)
  • Re: infinity
    ... Only in the sense that a false statement implies anything. ... The issue is existence of sums, ... > but can you deny that, if in concept it existed, that it would be, ... that the "size" of the set of naturals, is in any reasonable sense, ...
    (sci.math)
  • Re: Complex numbers (for geometry proof)
    ... Fons a écrit: ... implies the existence of a complex number z_0 and a real number R so that ... I would either write some equations, or use the geometrical interpretation, getting what is known as "Leibniz problem" ...
    (sci.math)