###
Steklov Institute of Mathematics at St.Petersburg

#
PREPRINT 20/2006

D. Grigoriev, E. A. Hirsch, K. Pervyshev##
TIME HIERARCHIES
FOR CRYPTOGRAPHIC FUNCTION INVERSION
WITH ADVICE

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)]

Back to all preprints

Back to the Steklov
Institute of Mathematics at St.Petersburg