Document Open Access Logo

On the Cryptographic Hardness of Local Search

Authors Nir Bitansky , Idan Gerichter

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.6.pdf
  • Filesize: 0.66 MB
  • 29 pages

Document Identifiers

Author Details

Nir Bitansky
  • Tel Aviv University, Israel
Idan Gerichter
  • Tel Aviv University, Israel

Funding

This work was supported in part by ISF grant 18/484, and by Len Blavatnik and the Blavatnik Family Foundation.
  • Bitansky, Nir: Supported by the Alon Young Faculty Fellowship.

Cite As Get BibTex

Nir Bitansky and Idan Gerichter. On the Cryptographic Hardness of Local Search. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 6:1-6:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.6

Abstract

We show new hardness results for the class of Polynomial Local Search problems (PLS): 
- Hardness of PLS based on a falsifiable assumption on bilinear groups introduced by Kalai, Paneth, and Yang (STOC 2019), and the Exponential Time Hypothesis for randomized algorithms. Previous standard model constructions relied on non-falsifiable and non-standard assumptions. 
- Hardness of PLS relative to random oracles. The construction is essentially different than previous constructions, and in particular is unconditionally secure. The construction also demonstrates the hardness of parallelizing local search. 
 The core observation behind the results is that the unique proofs property of incrementally-verifiable computations previously used to demonstrate hardness in PLS can be traded with a simple incremental completeness property.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Cryptography
  • PLS
  • Lower Bounds
  • Incremental Computation

Metrics

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

References

  1. Tim Abbot, Daniel Kane, and Paul Valiant. On algorithms for nash equilibria. Unpublished, 2004. Google Scholar
  2. Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei. Local max-cut in smoothed polynomial time. CoRR, abs/1610.04807, 2016. URL: http://arxiv.org/abs/1610.04807.
  3. Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs. Succinct delegation for low-space non-deterministic computation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 709-721, 2018. URL: https://doi.org/10.1145/3188745.3188924.
  4. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (Im)Possibility of Obfuscating Programs. J. ACM, 59(2):6:1-6:48, May 2012. URL: https://doi.org/10.1145/2160158.2160159.
  5. Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive Composition and Bootstrapping for SNARKS and Proof-carrying Data. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, pages 111-120, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2488608.2488623.
  6. Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. On the Existence of Extractable One-Way Functions. SIAM J. Comput., 45(5):1910-1952, 2016. URL: https://doi.org/10.1137/140975048.
  7. Nir Bitansky, Omer Paneth, and Alon Rosen. On the Cryptographic Hardness of Finding a Nash Equilibrium. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1480-1498, October 2015. URL: https://doi.org/10.1109/FOCS.2015.94.
  8. Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical Identity Based Encryption with Constant Size Ciphertext. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, pages 440-456, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  9. Dan Boneh, Craig Gentry, and Brent Waters. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005, pages 258-275, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  10. Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. Nash Equilibrium in Smoothed Polynomial Time for Network Coordination Games, September 2018. URL: http://arxiv.org/abs/1809.02280.
  11. Zvika Brakerski, Justin Holmgren, and Yael Tauman Kalai. Non-interactive delegation and batch NP verification from standard computational assumptions. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 474-482, 2017. URL: https://doi.org/10.1145/3055399.3055497.
  12. Buresh-Oppenheim. On the TFNP complexity of factoring. Unpublished, 2006. Google Scholar
  13. Ran Canetti, Yilei Chen, and Leonid Reyzin. On the Correlation Intractability of Obfuscated Pseudorandom Functions. In Proceedings, Part I, of the 13th International Conference on Theory of Cryptography - Volume 9562, TCC 2016-A, pages 389-415, Berlin, Heidelberg, 2016. Springer-Verlag. URL: https://doi.org/10.1007/978-3-662-49096-9_17.
  14. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the Complexity of Computing Two-player Nash Equilibria. J. ACM, 56(3):14:1-14:57, May 2009. URL: https://doi.org/10.1145/1516512.1516516.
  15. Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. PPAD-Hardness via Iterated Squaring Modulo a Composite. Cryptology ePrint Archive, Report 2019/667, 2019. URL: https://eprint.iacr.org/2019/667.
  16. Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. Finding a Nash Equilibrium is No Easier Than Breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1103-1114, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3313276.3316400.
  17. Bram Cohen and Krzysztof Pietrzak. Simple Proofs of Sequential Work. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018, pages 451-467, Cham, 2018. Springer International Publishing. Google Scholar
  18. Constantinos Daskalakis, Paul Goldberg, and Christos H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM J. Comput., 39:195-259, February 2009. URL: https://doi.org/10.1137/070699652.
  19. Constantinos Daskalakis and Christos Papadimitriou. Continuous Local Search. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, pages 790-804, Philadelphia, PA, USA, 2011. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2133036.2133098.
  20. Nico Döttling, Russell W. F. Lai, and Giulio Malavolta. Incremental Proofs of Sequential Work. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, pages 292-323, Cham, 2019. Springer International Publishing. Google Scholar
  21. Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass. Continuous Verifiable Delay Functions. Cryptology ePrint Archive, Report 2019/619, 2019. URL: https://eprint.iacr.org/2019/619.
  22. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The Complexity of Pure Nash Equilibria. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC '04, pages 604-612, New York, NY, USA, 2004. ACM. URL: https://doi.org/10.1145/1007352.1007445.
  23. Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium. In Advances in Cryptology - CRYPTO 2016, pages 579-604, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. Google Scholar
  24. Craig Gentry and Daniel Wichs. Separating Succinct Non-interactive Arguments from All Falsifiable Assumptions. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 99-108, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993651.
  25. Paul W. Goldberg and Christos H. Papadimitriou. Towards a unified complexity theory of total functions. J. Comput. Syst. Sci., 94:167-192, 2018. URL: https://doi.org/10.1016/j.jcss.2017.12.003.
  26. Oded Goldreich and Johan Håstad. On the Complexity of Interactive Proofs with Bounded Communication. Inf. Process. Lett., 67(4):205-214, 1998. URL: https://doi.org/10.1016/S0020-0190(98)00116-1.
  27. Oded Goldreich, Salil P. Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Computational Complexity, 11(1-2):1-53, 2002. URL: https://doi.org/10.1007/s00037-002-0169-0.
  28. Pavel Hubácek, Moni Naor, and Eylon Yogev. The Journey from NP to TFNP Hardness. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1-60:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.60.
  29. Pavel Hubáček and Eylon Yogev. Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, pages 1352-1371. ACM, 2016. URL: https://doi.org/10.1137/1.9781611974782.88.
  30. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  31. Hisao Ishibuchi and Tadahiko Murata. A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 28(3):392-403, August 1998. URL: https://doi.org/10.1109/5326.704576.
  32. Emil Jerábek. Integer factoring and modular square roots. CoRR, abs/1207.5220, 2012. URL: http://arxiv.org/abs/1207.5220.
  33. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988. URL: https://doi.org/10.1016/0022-0000(88)90046-3.
  34. Yael Tauman Kalai, Omer Paneth, and Lisa Yang. How to Delegate Computations Publicly. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1115-1124, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3313276.3316411.
  35. Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to Delegate Computations: The Power of No-Signaling Proofs. In In Proceedings of the 46th annual ACM symposium on Theory of computing (STOC), pages 485-494. ACM, January 2014. URL: https://www.microsoft.com/en-us/research/publication/delegate-computations-power-no-signaling-proofs/.
  36. Ilan Komargodski, Moni Naor, and Eylon Yogev. White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 622-632, October 2017. Google Scholar
  37. Ilan Komargodski, Moni Naor, and Eylon Yogev. White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 622-632, 2017. URL: https://doi.org/10.1109/FOCS.2017.63.
  38. S. Lin and Brain W. Kernighan. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Oper. Res., 21(2):498-516, April 1973. URL: https://doi.org/10.1287/opre.21.2.498.
  39. Carsten Lund, Lance Fortnow, H Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems, November 1990. URL: https://doi.org/10.1109/FSCS.1990.89518.
  40. Mohammad Mahmoody, Tal Moran, and Salil Vadhan. Publicly Verifiable Proofs of Sequential Work. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS '13, pages 373-388, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2422436.2422479.
  41. Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. URL: https://doi.org/10.1016/0304-3975(91)90200-L.
  42. Ralph Merkle. Secrecy, Authentication and Public Key Systems. PhD thesis, Stanford University, Department of Electrical Engineering, June 1979. Google Scholar
  43. John C. Nash. The (Dantzig) simplex method for linear programming. Computing in Science Engineering, 2(1):29-31, January 2000. URL: https://doi.org/10.1109/5992.814654.
  44. Omer Paneth and Guy N. Rothblum. On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-interactive Arguments. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography, pages 283-315, Cham, 2017. Springer International Publishing. Google Scholar
  45. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80063-7.
  46. Krzysztof Pietrzak. Simple Verifiable Delay Functions. Cryptology ePrint Archive, Report 2018/627, 2018. URL: https://eprint.iacr.org/2018/627.
  47. Ronald L. Rivest, Adi Shamir, and David A. Wagner. Time-lock puzzles and timed-release crypto. Technical Report MIT/LCS/TR-684, MIT, February 2000. Google Scholar
  48. Alon Rosen, Gil Segev, and Ido Shahaf. Can PPAD Hardness be Based on Standard Cryptographic Assumptions? In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography, pages 747-776, Cham, 2017. Springer International Publishing. Google Scholar
  49. Alejandro Schaffer and Mihalis Yannakakis. Simple Local Search Problems That are Hard to Solve. SIAM J. Comput., 20:56-87, February 1991. URL: https://doi.org/10.1137/0220004.
  50. Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. PPP-Completeness with Connections to Cryptography. CoRR, abs/1808.06407, 2018. URL: http://arxiv.org/abs/1808.06407.
  51. Paul Valiant. Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency. In Ran Canetti, editor, Theory of Cryptography, pages 1-18, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. 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 About DROPS Imprint Privacy Contact