Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-076 | 2nd July 2005 00:00

#### Time hierarchies for cryptographic function inversion with advice

TR05-076
Authors: Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev
Publication: 15th July 2005 18:29
Keywords:

Abstract:

We prove a time hierarchy theorem for inverting functions
computable in polynomial time with one bit of advice.
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
at least 1/p(n) on infinitely many lengths of input