Abstract
We prove that if the hardness of inverting a size-verifiable one-way function can be based on NP-hardness via a general (adaptive) reduction, then NP ⊆ coAM. This claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but was later retracted (STOC 2010).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 701–710. ACM, New York (2006)
Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: Erratum for: On basing one-way functions on NP-hardness. In: Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC 2010, pp. 795–796. ACM, New York (2010)
Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC 1986, pp. 59–68. ACM, New York (1986)
Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, October- 30 November 1, pp. 230–235. IEEE Computer Society (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Bogdanov, A., Brzuska, C. (2015). On Basing Size-Verifiable One-Way Functions on NP-Hardness. In: Dodis, Y., Nielsen, J.B. (eds) Theory of Cryptography. TCC 2015. Lecture Notes in Computer Science, vol 9014. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46494-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-662-46494-6_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46493-9
Online ISBN: 978-3-662-46494-6
eBook Packages: Computer ScienceComputer Science (R0)