Re: Looking for EXPTIME-algorithm

daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) writes:

filia&sofia wrote:
1. There is bijective mapping f: M -> N
2. It is (computationally) easy to calculate y = f (x), where x belongs
to M and y belongs to N
3. It is hard to calculate x = g (y), where g is inverse function of f.

One buzzword you might want to be looking for is "one-way permutation".

Calculation of x should take EXPTIME (EXPTIME-completeness would be
nice property).

Why EXPTIME? Why isn't it enough that inversion be infeasible? This
seems like an unusual constraint.

If you just want inversion to be infeasible, any one-way permutation should
do the trick. For instance: f(x) = x^2 mod n, where n is a RSA modulus (even
better, a Blum integer) of unknown factorization. There are various candidate
owp's in the literature.

How about if |M| < |N| and the first condition is f: M -> N is
injenctive mapping?

f(x) = g^x where g is some group element of large prime order, and where
the discrete log problem is hard, would be another plausible candidate.
If you use elliptic curves or some other group where there is no known
subexponential-time discrete log algorithm, it is even plausible that
inverting f will take EXPTIME (though of course you will never get any
proof of this).

Since the problem is in NP, (by assumption f is easy to calculate-- ie is
in P) proving it would be a proof that P!=NP.


.