Document Open Access Logo

The Journey from NP to TFNP Hardness

Authors Pavel Hubácek, Moni Naor, Eylon Yogev

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.60.pdf
  • Filesize: 0.6 MB
  • 21 pages

Document Identifiers

Author Details

Pavel Hubácek
Moni Naor
Eylon Yogev

Cite AsGet BibTex

Pavel Hubácek, Moni Naor, and Eylon Yogev. The Journey from NP to TFNP Hardness. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ITCS.2017.60

Abstract

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist. Currently, no problem in TFNP is known to be hard under assumptions such as NP hardness, the existence of one-way functions, or even public-key cryptography. The only known hardness results are based on less general assumptions such as the existence of collision-resistant hash functions, one-way permutations less established cryptographic primitives (e.g. program obfuscation or functional encryption). Several works explained this status by showing various barriers to proving hardness of TFNP. In particular, it has been shown that hardness of TFNP hardness cannot be based on worst-case NP hardness, unless NP=coNP. Therefore, we ask the following question: What is the weakest assumption sufficient for showing hardness in TFNP? In this work, we answer this question and show that hard-on-average TFNP problems can be based on the weak assumption that there exists a hard-on-average language in NP. In particular, this includes the assumption of the existence of one-way functions. In terms of techniques, we show an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs.
Keywords
  • TFNP
  • derandomization
  • one-way functions
  • average-case hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai, and Eylon Yogev. Universal obfuscation and witness encryption: Boosting correctness and combining security. IACR Cryptology ePrint Archive, 2016:281, 2016. Google Scholar
  2. Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, and Guang Yang. Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Computational Complexity, 25(2):349-418, 2016. Google Scholar
  3. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  4. Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, and Ronen Shaltiel. Pseudorandomness when the odds are against you. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 9:1-9:35, 2016. Google Scholar
  5. Gilad Asharov and Gil Segev. Limits on the power of indistinguishability obfuscation and functional encryption. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 191-209, 2015. Google Scholar
  6. Gilad Asharov and Gil Segev. On constructing one-way permutations from indistinguishability obfuscation. In Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II, pages 512-541, 2016. Google Scholar
  7. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In CRYPTO, volume 2139 of Lecture Notes in Computer Science, pages 1-18. Springer, 2001. URL: http://dx.doi.org/10.1007/3-540-44647-8_1.
  8. Boaz Barak, Yehuda Lindell, and Salil P. Vadhan. Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci., 72(2):321-391, 2006. Google Scholar
  9. Boaz Barak, Shien Jin Ong, and Salil P. Vadhan. Derandomization in cryptography. SIAM J. Comput., 37(2):380-400, 2007. Google Scholar
  10. Mihir Bellare and Shafi Goldwasser. The complexity of decision versus search. SIAM J. Comput., 23(1):97-119, 1994. URL: http://dx.doi.org/10.1137/S0097539792228289.
  11. Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby. On the theory of average case complexity. J. Comput. Syst. Sci., 44(2):193-219, 1992. Google Scholar
  12. Nir Bitansky, Akshay Degwekar, and Vinod Vaikuntanathan. Structure vs hardness through the obfuscation lens. Electronic Colloquium on Computational Complexity (ECCC), 23:91, 2016. Google Scholar
  13. Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of finding a Nash equilibrium. In 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, October 18-20, 2015, pages 1480-1498, 2015. Google Scholar
  14. Nir Bitansky and Vinod Vaikuntanathan. A note on perfect correctness by derandomization. Electronic Colloquium on Computational Complexity (ECCC), 22:187, 2015. Google Scholar
  15. Manuel Blum and Sampath Kannan. Designing programs that check their work. J. ACM, 42(1):269-291, 1995. Google Scholar
  16. Gilles Brassard. Relativized cryptography. IEEE Trans. Information Theory, 29(6):877-893, 1983. Google Scholar
  17. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, and Nikolai K. Vereshchagin. Does the polynomial hierarchy collapse if onto functions are invertible? Theory Comput. Syst., 46(1):143-156, 2010. Google Scholar
  18. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3), 2009. Google Scholar
  19. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195-259, 2009. Google Scholar
  20. Constantinos Daskalakis and Christos H. Papadimitriou. Continuous local search. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 790-804, 2011. Google Scholar
  21. Cynthia Dwork and Moni Naor. Zaps and their applications. SIAM J. Comput., 36(6):1513-1543, 2007. Google Scholar
  22. Cynthia Dwork, Moni Naor, and Omer Reingold. Immunizing encryption schemes from decryption errors. In Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, pages 342-360, 2004. Google Scholar
  23. Shimon Even, Alan L. Selman, and Yacov Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159-173, 1984. Google Scholar
  24. Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 416-426, 1990. Google Scholar
  25. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In FOCS, pages 40-49, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.13.
  26. Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. Revisiting the cryptographic hardness of finding a Nash equilibrium. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, pages 579-604, 2016. Google Scholar
  27. Paul W. Goldberg and Christos H. Papadimitriou. Towards a unified complexity theory of total functions, 2016. Unpublished manuscript. URL: http://www.cs.ox.ac.uk/people/paul.goldberg/papers/paper-2.pdf.
  28. Oded Goldreich. Computational complexity - a conceptual perspective. Cambridge University Press, 2008. Google Scholar
  29. Pavel Hubáček and Eylon Yogev. Hardness of continuous local search: Query complexity and cryptographic lower bounds. Electronic Colloquium on Computational Complexity (ECCC), 23:63, 2016. Google Scholar
  30. Russell Impagliazzo. A personal view of average-case complexity. In Structure in Complexity Theory Conference, pages 134-147. IEEE Computer Society, 1995. URL: http://dx.doi.org/10.1109/SCT.1995.514853.
  31. Russell Impagliazzo and Leonid A. Levin. No better ways to generate hard NP instances than picking uniformly at random. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 812-821, 1990. Google Scholar
  32. Russell Impagliazzo and Michael Luby. One-way functions are essential for complexity based cryptography (extended abstract). In FOCS, pages 230-235. IEEE Computer Society, 1989. URL: http://dx.doi.org/10.1109/SFCS.1989.63483.
  33. Russell Impagliazzo and Moni Naor. Decision trees and downward closures. In Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D. C., USA, June 14-17, 1988, pages 29-38, 1988. Google Scholar
  34. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 220-229, 1997. Google Scholar
  35. Emil Jeřábek. Integer factoring and modular square roots. J. Comput. Syst. Sci., 82(2):380-394, 2016. Google Scholar
  36. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79-100, 1988. URL: http://dx.doi.org/10.1016/0022-0000(88)90046-3.
  37. Jeff Kahn, Michael E. Saks, and Clifford D. Smyth. The dual BKR inequality and Rudich’s conjecture. Combinatorics, Probability & Computing, 20(2):257-266, 2011. Google Scholar
  38. Jonathan Katz and Chiu-Yuen Koo. On constructing universal one-way hash functions from arbitrary one-way functions. IACR Cryptology ePrint Archive, 2005:328, 2005. URL: http://eprint.iacr.org/2005/328.
  39. Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, and Eylon Yogev. One-way functions and (im)perfect obfuscation. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 374-383, 2014. Google Scholar
  40. Clemens Lautemann. BPP and the polynomial hierarchy. Inf. Process. Lett., 17(4):215-217, 1983. Google Scholar
  41. László Lovász, Moni Naor, Ilan Newman, and Avi Wigderson. Search problems in the decision tree model. SIAM J. Discrete Math., 8(1):119-132, 1995. Google Scholar
  42. Mohammad Mahmoody and David Xiao. On the power of randomized reductions and the checkability of SAT. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 64-75, 2010. Google Scholar
  43. Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theor. Comput. Sci., 81(2):317-324, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90200-L.
  44. Moni Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151-158, 1991. URL: http://dx.doi.org/10.1007/BF00196774.
  45. Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pages 33-43, 1989. Google Scholar
  46. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  47. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498-532, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80063-7.
  48. John Rompel. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 387-394, 1990. Google Scholar
  49. Alon Rosen, Gil Segev, and Ido Shahaf. Can PPAD hardness be based on standard cryptographic assumptions? Electronic Colloquium on Computational Complexity (ECCC), 23:59, 2016. Google Scholar
  50. Steven Rudich. Limits on the Provable Consequences of One-way Functions. PhD thesis, University of California at Berkeley, 1989. Google Scholar
  51. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In STOC, pages 475-484. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591825.
  52. Daniel R. Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding, pages 334-345, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact