zbMATH — the first resource for mathematics

Time hierarchies for cryptographic function inversion with advice. (English. Russian original) Zbl 1178.94188
J. Math. Sci., New York 158, No. 5, 633-644 (2009); translation from Zap. Nauchn. Semin. POMI 358, 54-76 (2008).
Summary: We prove a time hierarchy theorem for inverting functions computable in a slightly nonuniform 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 \(\geq 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\neq NP\), then for every \(l > k \geq 1\),
\[ (\text{\textbf{DTime}}[n^k]\cap \text{\textbf{NTime}}[n])/1 \subsetneq (\text{\textbf{DTime}}[n^l]\cap \text{\textbf{NTime}}[n])/1. \]
94A60 Cryptography
Full Text: DOI
[1] S. Aaronson, ”Complexity Zoo,” http://www.complexityzoo.com .
[2] L. Babai, L. Fortnow, and C. Lund, ”Non-deterministic exponential time has two-prover interactive protocols,” Comput. Complexity, 1, 3–40 (1991). · Zbl 0774.68041
[3] B. Barak, ”A probabilistic time hierarchy theorem for slightly nonuniform algorithms,” Lect. Notes Comput. Sci., 2483, 194–208 (2002). · Zbl 1028.68058
[4] S. Cook, ”A hierarchy theorem for nondeterministic time complexity,” J. Comput. System Sci., 7, 343–353 (1973). · Zbl 0278.68042
[5] L. Fortnow, ”Diagonalization,” Bull. Eur. Assoc. Theor. Comput. Sci., 71, 102–112 (2000). · Zbl 0973.68086
[6] L. Fortnow and R. Santhanam, ”Hierarchy theorems for probabilistic polynomial time,” in: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE (2004), pp. 316–324.
[7] L. Fortnow, R. Santhanarn, and L. Trevisan, ”Hierarchies for semantic classes,” in: Proceedings of the 37th ACM Symposium on the Theory of Computing, ACM (2005), pp. 348–355. · Zbl 1192.68292
[8] O. Goldreich, Foundations of Cryptography, Vol. 1: Basic Tools, Cambridge Univ. Press (2001). · Zbl 1007.94016
[9] O. Goldreich, M. Sudan, and L. Trevisan, ”From logarithmic advice to single-bit advice,” Technical Report TR-04-093, Electron. Colloq. Comput. Complexity (2004). · Zbl 1343.68080
[10] L. A. Hemaspaandra and M. Ogihara, The Complexity Theory Companion, Springer (2002). · Zbl 0993.68042
[11] J. Hartmanis and R. Stearns, ”On the computational complexity of algorithms,” Trans. Amer. Math. Soc., 117, 285–306 (1965). · Zbl 0131.15404
[12] F. Hennie and R. Stearns, ”Two-tape simulation of multitape Turing machines,” J. ACM, 13, No. 4, 533–546 (1966). · Zbl 0148.24801
[13] L. Levin, ”Universal search problems,” Problemy Peredachi Informatsii, 9, No. 3, 265–266 (1973). · Zbl 0313.02026
[14] L. Levin, ”One-way functions and pseudorandom generators,” Combinatorica, 7, 357–363 (1987). · Zbl 0641.68061
[15] D. van Melkebeek and K. Pervyshev, ”A generic time hierarchy with one bit of advice,” Comput. Complexity, 16, No. 2, 139–179 (2007). · Zbl 1173.68023
[16] C. Papadimitriou, Computational Complexity, Addison-Wesley (1991). · Zbl 0731.68036
[17] K. Pervyshev, ”Time hierarchies for computations with a bit of advice,” Technical Report TR-05-054, Electron. Colloq. Comput. Complexity (2005).
[18] J. Seiferas, M. Fischer, and A. Meyer, ”Separating nondeterministic time complexity classes,” J. ACM, 25, 146–167 (1978). · Zbl 0366.68038
[19] L. Trevisan and S. Vadhan, ”Pseudorandomness and average-case complexity via uniform reductions,” in: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, IEEE (2002), pp. 129–138. · Zbl 1133.68023
[20] A. Yao, ”Theory and application of trapdoor functions,” in: Proceedings of the 23th Annual IEEE Symposium on Foundations of Computer Science, IEEE (1982), pp. 80–91.
[21] S. Žak, ”A Turing machine time hierarchy,” Theoret. Comput. Sci., 26, 327–333 (1983). · Zbl 0525.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.