This preprint was accepted December 22, 2006
ABSTRACT:
We prove a time hierarchy theorem for inverting
functions
computable in a slightly non-uniform polynomial time.
In particular, we prove that if there is a strongly
one-way
function
then for any $k$
and for any polynomial $p$,
there is a function $f$ computable in linear time
with one bit of advice such that there is a
polynomial-time
probabilistic adversary that inverts $f$ with
probability
$\ge 1/p(n)$ on infinitely many lengths of input
while all probabilistic $O(n^k)$-time adversaries
with logarithmic advice invert $f$ with probability
less than $1/p(n)$
on almost all lengths of input.
We also prove a similar theorem in the worst-case
setting, i.e.,
if $\P\neq\NP$, then for every $l>k\ge1$
$$
(\DTime{n^k} \cap \NTime{n})/1 \subsetneq
(\DTime{n^l} \cap \NTime{n})/1.
$$
[Full text:
(.ps.gz)]