Top

Published in:

2020 | OriginalPaper | Chapter

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

Authors : Shuichi Hirahara, Osamu Watanabe

Published in: Complexity and Approximation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We explain our recent results [21] on the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators. This work is motivated by the desire of showing the limits of black-box reductions to some distributional \(\mathsf {NP}\) problem. We show that a black-box nonadaptive randomized reduction to any distinguisher for (not only polynomial-time but also) exponential-time computable hitting set generators can be simulated in \(\mathsf {AM}\cap \mathsf {co} \mathsf {AM}\); we also show an upper bound of \(\mathsf {S}_2^\mathsf {NP}\) even if there is no computational bound on a hitting set generator. These results provide additional evidence that the recent worst-case to average-case reductions within \(\mathsf {NP}\) shown by Hirahara (2018, FOCS) are inherently non-black-box. (We omit all detailed arguments and proofs, which can be found in [21].)

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Promise Problems on Probability Distributions

next chapter Computability of the Solutions to Navier-Stokes Equations via Effective Approximation

As a black-box reduction to any distinguisher for G, it is required in [15] that there exists a single machine that computes a reduction to every oracle avoiding G. On the other hand, as stated in Theorem 1, we allow reductions to depend on oracles, which makes our results stronger.

We emphasize that we are concerned the nonadaptivity of reductions used in the security proof of pseudorandom generators. Several simplified constructions of pseudorandom generators \(G^f\) from one-way functions f (e.g., [16, 23]) are nonadaptive in the sense that \(G^f\) can be efficiently computed with nonadaptive oracle access to f; however, the security reductions of these constructions are adaptive because of the use of Holenstein’s uniform hardcore lemma [22]. Similarly, the reduction of [17, Lemma 6.5] is adaptive. (We note that, in the special case when the degeneracy of a one-way function is efficiently computable, the reduction of [17] is nonadaptive.).

Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 701–710 (2006)

Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: Erratum for: on basing one-way functions on NP-hardness. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 795–796 (2010)

Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35(6), 1467–1493 (2006)MathSciNetCrossRef

Allender, E., Das, B.: Zero knowledge and circuit minimization. Inf. Comput. 256, 2–8 (2017)MathSciNetCrossRef

Allender, E., Friedman, L., Gasarch, W.I.: Limits on the computational power of random strings. Inf. Comput. 222, 80–92 (2013)MathSciNetCrossRef

Allender, E., Hirahara, S.: New insights on the (non-) hardness of circuit minimization and related problems. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 54:1–54:14 (2017)MathSciNetCrossRef

Applebaum, B., Barak, B., Xiao, D.: On basing lower-bounds for learning on worst-case assumptions. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 211–220 (2008)

Bogdanov, A., Brzuska, C.: On basing size-verifiable one-way functions on NP-hardness. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 1–6. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_1CrossRef

Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. SIAM J. Comput. 36(4), 1119–1159 (2006)MathSciNetCrossRef

10.

Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: Proceedings of the Conference on Computational Complexity (CCC), pp. 10:1–10:24 (2016)

11.

Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM J. Comput. 22(5), 994–1005 (1993)MathSciNetCrossRef

12.

Fortnow, L.: The complexity of perfect zero-knowledge. Adv. Comput. Res. 5, 327–343 (1989)CrossRef

13.

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)MathSciNetCrossRef

14.

Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 59–68 (1986)

15.

Gutfreund, D., Vadhan, S.: Limitations of hardness vs. randomness under uniform reductions. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX/RANDOM -2008. LNCS, vol. 5171, pp. 469–482. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85363-3_37CrossRef

16.

Haitner, I., Reingold, O., Vadhan, S.P.: Efficiency improvements in constructing pseudorandom generators from one-way functions. SIAM J. Comput. 42(3), 1405–1430 (2013)MathSciNetCrossRef

17.

Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRef

18.

Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 247–258 (2018)

19.

Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: Proceedings of the Computational Complexity Conference (CCC), pp. 7:1–7:20 (2017)

20.

Hirahara, S., Watanabe, O.: Limits of minimum circuit size problem as oracle. In: Proceedings of the Conference on Computational Complexity (CCC), pp. 18:1–18:20 (2016)

21.

Hirahara, S., Watanabe, O.: On nonadaptive reductions to the set of random strings and its dense subsets. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 26, p. 25 (2019)

22.

Holenstein, T.: Key agreement from weak bit agreement. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 664–673 (2005)

23.

Holenstein, T.: Pseudorandom generators from one-way functions: a simple construction for any hardness. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 443–461. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_23CrossRef

24.

Kabanets, V., Cai, J.: Circuit minimization problem. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 73–79 (2000)

25.

Ko, K.: On helping by robust oracle machines. Theor. Comput. Sci. 52, 15–36 (1987)MathSciNetCrossRef

26.

Ko, K.: On the complexity of learning minimum time-bounded turing machines. SIAM J. Comput. 20(5), 962–986 (1991)MathSciNetCrossRef

27.

Levin, L.A.: Randomness conservation inequalities; information and independence in mathematical theories. Inf. Control 61(1), 15–37 (1984)MathSciNetCrossRef

28.

Nisan, N., Wigderson, A.: Hardness vs Randomness. J. Comput. Syst. Sci. 49(2), 149–167 (1994)MathSciNetCrossRef

29.

Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Proceedings of the Structure in Complexity Theory Conference, pp. 133–138 (1991)

30.

Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24–35 (1997)MathSciNetCrossRef

31.

Rudich, S.: Super-bits, demi-bits, and NP/qpoly-natural proofs. In: Rolim, J. (ed.) RANDOM 1997. LNCS, vol. 1269, pp. 85–93. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63248-4_8CrossRef

32.

Trevisan, L., Vadhan, S.P.: Pseudorandomness and average-case complexity via uniform reductions. Comput. Complex. 16(4), 331–364 (2007)MathSciNetCrossRef

33.

Vadhan, S.P.: An unconditional study of computational zero knowledge. SIAM J. Comput. 36(4), 1160–1214 (2006)MathSciNetCrossRef

34.

Yap, C.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287–300 (1983)CrossRef

Title: On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
Authors: Shuichi Hirahara
Osamu Watanabe
Publisher: Springer International Publishing
Book: Complexity and Approximation
Print ISBN: 978-3-030-41671-3

Electronic ISBN: 978-3-030-41672-0

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-41672-0_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner