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 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!=NP, then for every l>k>=1 (DTime{n^k} \cap NTime{n})/1 \subsetneq (DTime{n^l} \cap NTime{n})/1.