Document Open Access Logo

On Search Complexity of Discrete Logarithm

Authors Pavel Hubáček , Jan Václavek

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.60.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

Pavel Hubáček
  • Charles University, Prague, Czech Republic
Jan Václavek
  • Charles University, Prague, Czech Republic

Funding

  • Hubáček, Pavel: Supported by the Grant Agency of the Czech Republic under the grant agreement no. 19-27871X and by the Charles University projects PRIMUS/17/SCI/9 and UNCE/SCI/004.

Acknowledgements

We wish to thank the anonymous reviewers for their helpful suggestions on the presentation of our results. The first author is grateful to Chethan Kamath for multiple enlightening discussions about TFNP and for suggesting Dove as a name for a total search problem contained in the complexity class PPP.

Cite As Get BibTex

Pavel Hubáček and Jan Václavek. On Search Complexity of Discrete Logarithm. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.60

Abstract

In this work, we study the discrete logarithm problem in the context of TFNP - the complexity class of search problems with a syntactically guaranteed existence of solutions for all instances. Our main results establish that suitable variants of the discrete logarithm problem are complete for the complexity class PPP, respectively PWPP, i.e., the subclasses of TFNP capturing total search problems with a solution guaranteed by the pigeonhole principle, respectively the weak pigeonhole principle. Besides answering an open problem from the recent work of Sotiraki, Zampetakis, and Zirdelis (FOCS’18), our completeness results for PPP and PWPP have implications for the recent line of work proving conditional lower bounds for problems in TFNP under cryptographic assumptions. In particular, they highlight that any attempt at basing average-case hardness in subclasses of TFNP (other than PWPP and PPP) on the average-case hardness of the discrete logarithm problem must exploit its structural properties beyond what is necessary for constructions of collision-resistant hash functions.
Additionally, our reductions provide new structural insights into the class PWPP by establishing two new PWPP-complete problems. First, the problem Dove, a relaxation of the PPP-complete problem Pigeon. Dove is the first PWPP-complete problem not defined in terms of an explicitly shrinking function. Second, the problem Claw, a total search problem capturing the computational complexity of breaking claw-free permutations. In the context of TFNP, the PWPP-completeness of Claw matches the known intrinsic relationship between collision-resistant hash functions and claw-free permutations established in the cryptographic literature.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • discrete logarithm
  • total search problems
  • completeness
  • TFNP
  • PPP
  • PWPP

Metrics

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

Related Versions

References

  1. Nir Bitansky and Idan Gerichter. On the cryptographic hardness of local search. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, pages 6:1-6:29, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.6.
  2. Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of finding a Nash equilibrium. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1480-1498, 2015. URL: https://doi.org/10.1109/FOCS.2015.94.
  3. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3), 2009. URL: https://doi.org/10.1145/1516512.1516516.
  4. 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, Phoenix, AZ, USA, June 23-26, 2019, pages 1103-1114. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316400.
  5. Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. PPAD-hardness via iterated squaring modulo a composite. IACR Cryptology ePrint Archive, 2019:667, 2019. URL: https://eprint.iacr.org/2019/667.
  6. Ivan Damgård. Collision free hash functions and public key signature schemes. In David Chaum and Wyn L. Price, editors, Advances in Cryptology - EUROCRYPT '87, Workshop on the Theory and Application of of Cryptographic Techniques, Amsterdam, The Netherlands, April 13-15, 1987, Proceedings, volume 304 of Lecture Notes in Computer Science, pages 203-216. Springer, 1987. URL: https://doi.org/10.1007/3-540-39118-5_19.
  7. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195-259, 2009. URL: https://doi.org/10.1137/070699652.
  8. Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass. Continuous verifiable delay functions. In Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part III, volume 12107 of Lecture Notes in Computer Science, pages 125-154, 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_5.
  9. Aris Filos-Ratsikas and Paul W. Goldberg. The complexity of splitting necklaces and bisecting ham sandwiches. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 638-649, 2019. URL: https://doi.org/10.1145/3313276.3316334.
  10. 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. URL: https://doi.org/10.1007/978-3-662-53008-5_20.
  11. Pavel Hubáček, Moni Naor, and Eylon Yogev. The journey from NP to TFNP hardness. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 60:1-60:21, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.60.
  12. Pavel Hubáček and Jan Václavek. On search complexity of discrete logarithm. CoRR, abs/2107.02617, 2021. URL: http://arxiv.org/abs/2107.02617.
  13. Pavel Hubáček and Eylon Yogev. Hardness of continuous local search: Query complexity and cryptographic lower bounds. SIAM J. Comput., 49(6):1128-1172, 2020. URL: https://doi.org/10.1137/17M1118014.
  14. Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky. Sufficient conditions for collision-resistant hashing. In Joe Kilian, editor, Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings, volume 3378 of Lecture Notes in Computer Science, pages 445-456. Springer, 2005. URL: https://doi.org/10.1007/978-3-540-30576-7_24.
  15. Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang. Snargs for bounded depth computations and PPAD hardness from sub-exponential LWE. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 708-721. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451055.
  16. Emil Jeřábek. Integer factoring and modular square roots. J. Comput. Syst. Sci., 82(2):380-394, 2016. URL: https://doi.org/10.1016/j.jcss.2015.08.001.
  17. Antoine Joux, Andrew M. Odlyzko, and Cécile Pierrot. The past, evolving present, and future of the discrete logarithm. In Çetin Kaya Koç, editor, Open Problems in Mathematics and Computational Science, pages 5-36. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-10683-0_2.
  18. Ilan Komargodski and Gil Segev. From Minicrypt to Obfustopia via private-key functional encryption. J. Cryptol., 33(2):406-458, 2020. URL: https://doi.org/10.1007/s00145-019-09327-x.
  19. Alex Lombardi and Vinod Vaikuntanathan. Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs. In Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part III, volume 12172 of Lecture Notes in Computer Science, pages 632-651. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-56877-1_22.
  20. 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: https://doi.org/10.1016/S0022-0000(05)80063-7.
  21. Alexander Russell. Necessary and sufficient condtions for collision-free hashing. J. Cryptol., 8(2):87-100, 1995. URL: https://doi.org/10.1007/BF00190757.
  22. Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. PPP-completeness with connections to cryptography. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 148-158. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00023.
  23. Yuliang Zheng, Tsutomu Matsumoto, and Hideki Imai. Duality between two cryptographic primitives. In Shojiro Sakata, editor, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 8th International Symposium, AAECC-8, Tokyo, Japan, August 20-24, 1990, Proceedings, volume 508 of Lecture Notes in Computer Science, pages 379-390. Springer, 1990. URL: https://doi.org/10.1007/3-540-54195-0_66.
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