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.

Bibliographie

[1] S. Aaronson, Complexity Zoo, http:// www.complexityzoo.com

[2] B. Barak, “A probabilistic time hierarchy theorem for slightly nonuniform algorithms”, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science, 2483, Springer-Verlag, Berlin, 2002, 194–208 | MR | Zbl

[3] S. Cook, “A hierarchy theorem for nondeterministic time complexity”, J. Computer System Sci., 7 (1973), 343–353 | DOI | MR | Zbl

[4] L. Fortnow, R. Santhanam, “Hierarchy theorems for probabilistic polynomial time”, Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004, 316–324

[5] L. Fortnow, R. Santhanam, L. Trevisan, “Hierarchies for semantic classes”, Proceedings of the 37th ACM Symposium on the Theory of Computing, ACM, New York, 2005, 348–355 | MR | Zbl

[6] O. Goldreich, Foundations of Cryptography. Vol. 1: Basic Tools, Cambridge University Press, Cambridge, 2001 | MR | Zbl

[7] O. Goldreich, M. Sudan, L. Trevisan, From logarithmic advice to single-bit advice, Technical Report TR-04-093, Electronic Colloquium on Computational Complexity, 2004

[8] L. A. Hemaspaandra, M. Ogihara, The Complexity Theory Companion, Springer, Berlin, 2002 | MR

[9] J. Hartmanis, R. Stearns, “On the computational complexity of algorithms”, Trans. Amer. Math. Soc., 117 (1965), 285–306 | DOI | MR | Zbl

[10] F. Hennie, R. Stearns, “Two-tape simulation of multitape Turing machines”, J. of ACM, 13:4 (1966), 533–546 | DOI | MR | Zbl

[11] L. Levin, “Universal search problems”, Problems of Information Transmission, 9:3 (1973), 265–266 (Russian) | MR

[12] D. van Melkebeek, K. Pervyshev, “A generic time hierarchy with one bit of advice”, Computational Complexity, 16:2 (2007), 139–179 | DOI | MR | Zbl

[13] C. Papadimitriou, Computational Complexity, Addison-Wesley, 1991 | MR

[14] K. Pervyshev, Time hierarchies for computations with a bit of advice, Technical Report TR-05-054, Electronic Colloquium on Computational Complexity, 2005

[15] J. Seiferas, M. Fischer, A. Meyer, “Separating nondeterministic time complexity classes”, J. of the ACM, 25:1 (1978), 146–167 | DOI | MR | Zbl

[16] S. Žák, “A Turing machine time hierarchy”, Theoretical Computer Science, 26:3 (1983), 327–333 | DOI | MR | Zbl