Time hierarchies for cryptographic function inversion with advice

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 $\ge1/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 $\mathbf P\neq\mathbf{NP}$, then for every $l>k\ge1$
$$ (\mathbf{DTime}[n^k]\cap\mathbf{NTime}[n])/1\subsetneq(\mathbf{DTime}[n^l]\cap\mathbf{NTime}[n])/1. $$
Bibl. – 16 titles.