Document Open Access Logo

On One-Way Functions from NP-Complete Problems

Authors Yanyi Liu, Rafael Pass

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.36.pdf
  • Filesize: 1.01 MB
  • 24 pages

Document Identifiers

Author Details

Yanyi Liu
  • Cornell Tech, New York, NY, USA
Rafael Pass
  • Cornell Tech, New York, NY, USA
  • Tel-Aviv University, Israel

Funding

  • Pass, Rafael: Work partially done while being on a sabbatical at Tel-Aviv University. Supported in part by NSF Award SATC-1704788, NSF Award RI-1703846, AFOSR Award FA9550-18-1-0267, and a JP Morgan Faculty Award. This material is based upon work supported by DARPA under Agreement No. HR00110C0086. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.

Acknowledgements

We are very grateful to Vinod Vaikuntanathan and Rahul Ilango for helpful comments on an earlier version of this paper. We thank the anonymous reviewers for their helpful comments.

Cite As Get BibTex

Yanyi Liu and Rafael Pass. On One-Way Functions from NP-Complete Problems. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 36:1-36:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.36

Abstract

We present the first natural NP-complete problem whose average-case hardness w.r.t. the uniform distribution over instances is equivalent to the existence of one-way functions (OWFs). The problem, which originated in the 1960s, is the Conditional Time-Bounded Kolmogorov Complexity Problem: let K^t(x∣z) be the length of the shortest "program" that, given the "auxiliary input" z, outputs the string x within time t(|x|), and let McK^tP[ζ] be the set of strings (x,z,k) where |z| = ζ(|x|), |k| = log |x| and K^t(x∣z) < k, where, for our purposes, a "program" is defined as a RAM machine.
Our main result shows that for every polynomial t(n) ≥ n², there exists some polynomial ζ such that McK^tP[ζ] is NP-complete. We additionally extend the result of Liu-Pass (FOCS'20) to show that for every polynomial t(n) ≥ 1.1n, and every polynomial ζ(⋅), mild average-case hardness of McK^tP[ζ] is equivalent to the existence of OWFs. Taken together, these results provide the following crisp characterization of what is required to base OWFs on NP ⊈ BPP: 
There exists concrete polynomials t,ζ such that "Basing OWFs on NP ⊈ BPP" is equivalent to providing a "worst-case to (mild) average-case reduction for McK^tP[ζ]". 
In other words, the "holy-grail" of Cryptography (i.e., basing OWFs on NP ⊈ BPP) is equivalent to a basic question in algorithmic information theory.
As an independent contribution, we show that our NP-completeness result can be used to shed new light on the feasibility of the polynomial-time bounded symmetry of information assertion (Kolmogorov'68).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • One-way Functions
  • NP-Completeness
  • Kolmogorov Complexity

Metrics

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

Related Versions

References

  1. Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 99-108. ACM, 1996. URL: https://doi.org/10.1145/237814.237838.
  2. Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 284-293. ACM, 1997. URL: https://doi.org/10.1145/258533.258604.
  3. Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on NP-hardness. In STOC '06, pages 701-710, 2006. URL: https://doi.org/10.1145/1132516.1132614.
  4. Eric Allender, Harry Buhrman, Michal Kouckỳ, Dieter Van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM Journal on Computing, 35(6):1467-1493, 2006. Google Scholar
  5. Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-way functions and a conditional variant of MKTP. Electron. Colloquium Comput. Complex., 28:9, 2021. Revision 2; October 19, 2021. Google Scholar
  6. Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-way functions and a conditional variant of MKTP. Electron. Colloquium Comput. Complex., 28:9, 2021. Revision 1; April 18, 2021. Google Scholar
  7. Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-way functions and a conditional variant of MKTP. Electron. Colloquium Comput. Complex., 28:9, 2021. Google Scholar
  8. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks. Minimizing disjunctive normal form formulas and ac^0 circuits given a truth table. SIAM J. Comput., 38(1):63-84, 2008. URL: https://doi.org/10.1137/060664537.
  9. Manuel Blum. Coin flipping by telephone - A protocol for solving impossible problems. In COMPCON'82, Digest of Papers, Twenty-Fourth IEEE Computer Society International Conference, San Francisco, California, USA, February 22-25, 1982, pages 133-137. IEEE Computer Society, 1982. Google Scholar
  10. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850-864, 1984. Google Scholar
  11. Andrej Bogdanov and Christina Brzuska. On basing size-verifiable one-way functions on NP-hardness. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I, volume 9014 of Lecture Notes in Computer Science, pages 1-6. Springer, 2015. Google Scholar
  12. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for np problems. In FOCS '03, pages 308-317, 2003. Google Scholar
  13. Gilles Brassard. Relativized cryptography. IEEE Transactions on Information Theory, 29(6):877-893, 1983. Google Scholar
  14. Gregory J. Chaitin. On the simplicity and speed of programs for computing infinite sets of natural numbers. J. ACM, 16(3):407-422, 1969. Google Scholar
  15. Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, 1976. Google Scholar
  16. Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In STOC '90, pages 416-426, 1990. URL: https://doi.org/10.1145/100216.100272.
  17. Rosario Gennaro and Luca Trevisan. Lower bounds on the efficiency of generic cryptographic constructions. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 305-313. IEEE Computer Society, 2000. Google Scholar
  18. Halley Goldberg and Valentine Kabanets. A simpler proof of the worst-case to average-case reduction for polynomial hierarchy via symmetry of information. Electronic Colloquium on Computational Complexity (ECCC), 2022. URL: https://eccc.weizmann.ac.il/report/2022/007.
  19. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. On the cryptographic applications of random functions. In CRYPTO, pages 276-288, 1984. Google Scholar
  20. Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270-299, 1984. Google Scholar
  21. S. Dov Gordon, Hoeteck Wee, David Xiao, and Arkady Yerukhimovich. On the round complexity of zero-knowledge proofs based on one-way permutations. In LATINCRYPT, pages 189-204, 2010. Google Scholar
  22. Iftach Haitner, Mohammad Mahmoody, and David Xiao. A new sampling protocol and applications to basing cryptographic primitives on the hardness of NP. In IEEE Conference on Computational Complexity, pages 76-87, 2010. Google Scholar
  23. J. Hartmanis. Generalized kolmogorov complexity and the structure of feasible computations. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 439-445, November 1983. URL: https://doi.org/10.1109/SFCS.1983.21.
  24. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364-1396, 1999. Google Scholar
  25. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 247-258, 2018. Google Scholar
  26. Shuichi Hirahara. Unexpected hardness results for kolmogorov complexity under uniform reductions. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1038-1051. ACM, 2020. Google Scholar
  27. Shuichi Hirahara. Symmetry of information in heuristica. Manuscript, 2021. Google Scholar
  28. Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam. Np-hardness of minimum circuit size problem for OR-AND-MOD circuits. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 5:1-5:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.5.
  29. Rahul Ilango. AC⁰[p] lower bounds and NP-hardness for variants of MCSP. Electron. Colloquium Comput. Complex., 26:21, 2019. URL: https://eccc.weizmann.ac.il/report/2019/021.
  30. Rahul Ilango. Approaching MCSP from above and below: Hardness for a conditional variant and AC^0[p]. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, pages 34:1-34:26, 2020. Google Scholar
  31. Rahul Ilango. Personal communication, 2021. Google Scholar
  32. Rahul Ilango, Bruno Loff, and Igor Carboni Oliveira. NP-hardness of circuit minimization for multi-output functions. In 35th Computational Complexity Conference, CCC 2020, pages 22:1-22:36, 2020. Google Scholar
  33. Russell Impagliazzo. A personal view of average-case complexity. In Structure in Complexity Theory '95, pages 134-147, 1995. Google Scholar
  34. Russell Impagliazzo and Michael Luby. 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, 30 October - 1 November 1989, pages 230-235, 1989. Google Scholar
  35. Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 236-241. IEEE Computer Society, 1989. Google Scholar
  36. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 73-79, 2000. Google Scholar
  37. Ker-I Ko. On the notion of infinite pseudorandom sequences. Theor. Comput. Sci., 48(3):9-33, 1986. URL: https://doi.org/10.1016/0304-3975(86)90081-2.
  38. Ker-I Ko. On the complexity of learning minimum time-bounded turing machines. SIAM J. Comput., 20(5):962-986, 1991. Google Scholar
  39. A. N. Kolmogorov. Several theorems about algorithmic entropy and algorithmic amount of information (a talk at a moscow math. soc. meeting 10/31/67). An abstract in Usp. Mat. Nauk, 23(2):201, 1968. Google Scholar
  40. A. N. Kolmogorov. Three approaches to the quantitative definition of information. International Journal of Computer Mathematics, 2(1-4):157-168, 1968. Google Scholar
  41. L. A. Levin. The tale of one-way functions. Problems of Information Transmission, 39(1):92-103, 2003. URL: https://doi.org/10.1023/A:1023634616182.
  42. Leonid A. Levin. Universal search problems (russian), translated into English by BA Trakhtenbrot in [Trakhtenbrot, 1984]. Problems of Information Transmission, 9(3):265-266, 1973. Google Scholar
  43. Yanyi Liu and Rafael Pass. On one-way functions and Kolmogorov complexity. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1243-1254. IEEE, 2020. Google Scholar
  44. Yanyi Liu and Rafael Pass. On one-way functions from np-complete problems. Cryptology ePrint Archive, Report 2021/513, 2021. ; received on April 19, 2021. URL: https://ia.cr/2021/513.
  45. Yanyi Liu and Rafael Pass. On one-way functions from np-complete problems. Electron. Colloquium Comput. Complex., 28:59, 2021. URL: https://eccc.weizmann.ac.il/report/2021/059.
  46. Yanyi Liu and Rafael Pass. On the possibility of basing cryptography on EXP ≠ BPP. In CRYPTO, 2021. Google Scholar
  47. Noam Livne. On the construction of one-way functions from average case hardness. In ICS, pages 301-309. Citeseer, 2010. Google Scholar
  48. Luc Longpré and Sarah Mocas. Symmetry of information and one-way functions. In Wen-Lian Hsu and Richard C. T. Lee, editors, ISA '91 Algorithms, 2nd International Symposium on Algorithms, Taipei, Republic of China, December 16-18, 1991, Proceedings, volume 557 of Lecture Notes in Computer Science, pages 308-315. Springer, 1991. URL: https://doi.org/10.1007/3-540-54945-5_75.
  49. Luc Longpré and Osamu Watanabe. On symmetry of information and polynomial time invertibility. In Algorithms and Computation, pages 410-419, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg. Google Scholar
  50. R. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24(5):525-530, 1978. Google Scholar
  51. Moni Naor. Bit commitment using pseudorandomness. J. Cryptology, 4(2):151-158, 1991. Google Scholar
  52. A. M. Odlyzko. The rise and fall of knapsack cryptosystems. In In Cryptology and Computational Number Theory, pages 75-88. A.M.S, 1990. Google Scholar
  53. Rafael Pass. Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 96-110. IEEE Computer Society, 2006. Google Scholar
  54. Hanlin Ren and Rahul Santhanam. Hardness of KT characterizes parallel cryptography. Electron. Colloquium Comput. Complex., 28:57, 2021. URL: https://eccc.weizmann.ac.il/report/2021/057.
  55. Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems (reprint). Commun. ACM, 26(1):96-99, 1983. URL: https://doi.org/10.1145/357980.358017.
  56. John Rompel. One-way functions are necessary and sufficient for secure signatures. In STOC, pages 387-394, 1990. Google Scholar
  57. Michael Sipser. A complexity theoretic approach to randomness. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 330-335. ACM, 1983. Google Scholar
  58. R.J. Solomonoff. A formal theory of inductive inference. part i. Information and Control, 7(1):1-22, 1964. URL: https://doi.org/10.1016/S0019-9958(64)90223-2.
  59. Boris A Trakhtenbrot. A survey of Russian approaches to perebor (brute-force searches) algorithms. Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  60. Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 453-461. ACM, 2001. URL: https://doi.org/10.1145/380752.380839.
  61. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80-91, 1982. Google Scholar
  62. A. K. Zvonkin and L. A. Levin. the Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms. Russian Mathematical Surveys, 25(6):83-124, December 1970. URL: https://doi.org/10.1070/RM1970v025n06ABEH001269.
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 About DROPS Imprint Privacy Contact