Time hierarchies for cryptographic function inversion with advice

E. A. Hirsch ; D. Yu. Grigor'ev ; K. V. Pervyshev

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 54-76

Résumé

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.