Document Open Access Logo

The Cost of Statistical Security in Proofs for Repeated Squaring

Authors Cody Freitag , Ilan Komargodski

PDF
Thumbnail PDF

File

LIPIcs.ITC.2023.4.pdf
  • Filesize: 0.81 MB
  • 23 pages

Document Identifiers

Author Details

Cody Freitag
  • Cornell Tech, New York, NY, USA
Ilan Komargodski
  • The Hebrew University, Jerusalem, Israel
  • NTT Research, Sunnyvale, CA, USA

Funding

  • Freitag, Cody: Cody Freitag’s work was partially done during an internship at NTT Research. He is also supported in part by the National Science Foundation Graduate Research Fellowship under Grant No. DGE–2139899, DARPA Award HR00110C0086, and AFOSR Award FA9550-18-1-0267.
  • Komargodski, Ilan: Ilan Komargodski is the incumbent of the Harry & Abe Sherman Senior Lectureship at the School of Computer Science and Engineering at the Hebrew University, supported in part by an Alon Young Faculty Fellowship, by a JPM Faculty Research Award, by a grant from the Israel Science Foundation (ISF Grant No. 1774/20), and by a grant from the US-Israel Binational Science Foundation and the US National Science Foundation (BSF-NSF Grant No. 2020643).

Cite As Get BibTex

Cody Freitag and Ilan Komargodski. The Cost of Statistical Security in Proofs for Repeated Squaring. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITC.2023.4

Abstract

In recent years, the number of applications of the repeated squaring assumption has been growing rapidly. The assumption states that, given a group element x, an integer T, and an RSA modulus N, it is hard to compute x^2^T mod N - or even decide whether y?=x^2^T mod N - in parallel time less than the trivial approach of simply computing T squares. This rise has been driven by efficient proof systems for repeated squaring, opening the door to more efficient constructions of verifiable delay functions, various secure computation primitives, and proof systems for more general languages.

In this work, we study the complexity of statistically sound proofs for the repeated squaring relation. Technically, we consider proofs where the prover sends at most k ≥ 0 elements and the (probabilistic) verifier performs generic group operations over the group ℤ_N^⋆. As our main contribution, we show that for any (one-round) proof with a randomized verifier (i.e., an MA proof) the verifier either runs in parallel time Ω(T/(k+1)) with high probability, or is able to factor N given the proof provided by the prover. This shows that either the prover essentially sends p,q such that N = p⋅ q (which is infeasible or undesirable in most applications), or a variant of Pietrzak’s proof of repeated squaring (ITCS 2019) has optimal verifier complexity O(T/(k+1)). In particular, it is impossible to obtain a statistically sound one-round proof of repeated squaring with efficiency on par with the computationally-sound protocol of Wesolowski (EUROCRYPT 2019), with a generic group verifier.
We further extend our one-round lower bound to a natural class of recursive interactive proofs for repeated squaring. For r-round recursive proofs where the prover is allowed to send k group elements per round, we show that the verifier either runs in parallel time Ω(T/(k+1)^r) with high probability, or is able to factor N given the proof transcript.

Subject Classification

ACM Subject Classification
  • Theory of computation → Proof complexity
Keywords
  • Cryptographic Proofs
  • Repeated Squaring
  • Lower Bounds

Metrics

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

Related Versions

References

  1. Chia network. https://chia.net/. Accessed: 2022-10-05.
  2. Divesh Aggarwal and Ueli Maurer. Breaking RSA generically is equivalent to factoring. IEEE Trans. Inf. Theory, 62(11):6251-6259, 2016. Google Scholar
  3. Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Chethan Kamath, Alex Lombardi, Omer Paneth, and Ron D. Rothblum. Ppad is as hard as lwe and iterated squaring. In TCC, 2022. Google Scholar
  4. Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and Pratik Soni. Time- and space-efficient arguments from groups of unknown order. In Advances in Cryptology - CRYPTO, pages 123-152, 2021. Google Scholar
  5. Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable delay functions. In Advances in Cryptology - CRYPTO, pages 757-788, 2018. Google Scholar
  6. Dan Boneh, Benedikt Bünz, and Ben Fisch. A survey of two verifiable delay functions. IACR Cryptol. ePrint Arch., page 712, 2018. Google Scholar
  7. Dan Boneh, Benedikt Bünz, and Ben Fisch. Batching techniques for accumulators with applications to iops and stateless blockchains. In CRYPTO (1), volume 11692 of Lecture Notes in Computer Science, pages 561-586. Springer, 2019. Google Scholar
  8. Jonathan Bootle, Alessandro Chiesa, and Katerina Sotiraki. Sumcheck arguments and their applications. In CRYPTO (1), volume 12825 of Lecture Notes in Computer Science, pages 742-773. Springer, 2021. Google Scholar
  9. Johannes Buchmann and Safuat Hamdy. A survey on iq cryptography. In Public-Key Cryptography and Computational Number Theory, pages 1-15, 2001. Google Scholar
  10. Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent snarks from DARK compilers. In Advances in Cryptology - EUROCRYPT, pages 677-706, 2020. Google Scholar
  11. Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass. Continuous verifiable delay functions. In Advances in Cryptology - EUROCRYPT, pages 125-154, 2020. Google Scholar
  12. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology - CRYPTO, pages 186-194, 1986. Google Scholar
  13. Cody Freitag, Ilan Komargodski, Rafael Pass, and Naomi Sirkin. Non-malleable time-lock puzzles and applications. In Theory of Cryptography - 19th International Conference, TCC, pages 447-479, 2021. Google Scholar
  14. Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The algebraic group model and its applications. In Advances in Cryptology - CRYPTO, pages 33-62, 2018. Google Scholar
  15. Oded Goldreich and Johan Håstad. On the complexity of interactive proofs with bounded communication. Inf. Process. Lett., 67(4):205-214, 1998. Google Scholar
  16. Oded Goldreich, Salil P. Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Comput. Complex., 11(1-2):1-53, 2002. Google Scholar
  17. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1-27:64, 2015. Google Scholar
  18. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. URL: http://www.jstor.org/stable/2282952.
  19. Charlotte Hoffmann, Pavel Hubácek, Chethan Kamath, Karen Klein, and Krzysztof Pietrzak. Practical statistically-sound proofs of exponentiation in any group. In CRYPTO (2), 2022. Google Scholar
  20. Justin Holmgren, Alex Lombardi, and Ron D. Rothblum. Fiat-shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). In STOC, pages 750-760. ACM, 2021. Google Scholar
  21. Tibor Jager and Jörg Schwenk. On the analysis of cryptographic assumptions in the generic ring model. J. Cryptol., 26(2):225-245, 2013. Google Scholar
  22. Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Yun Zhang. Snargs for bounded depth computations and PPAD hardness from sub-exponential LWE. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 708-721, 2021. Google Scholar
  23. Jonathan Katz, Julian Loss, and Jiayu Xu. On the security of time-lock puzzles and timed commitments. In Theory of Cryptography - TCC, pages 390-413, 2020. Google Scholar
  24. Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC, pages 723-732, 1992. Google Scholar
  25. Swastik Kopparty and Abhishek Bhrushundi. Lecture 3: Finding integer solutions to systems of linear equations, fall 2014. URL: https://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec3.pdf.
  26. Alex Lombardi and Vinod Vaikuntanathan. Fiat-shamir for repeated squaring with applications to ppad-hardness and vdfs. In Advances in Cryptology - CRYPTO, pages 632-651, 2020. Google Scholar
  27. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, 1992. Google Scholar
  28. Ueli M. Maurer. Abstract models of computation in cryptography. In IMACC, volume 3796 of Lecture Notes in Computer Science, pages 1-12. Springer, 2005. Google Scholar
  29. Gary L Miller. Riemann’s hypothesis and tests for primality. Journal of computer and system sciences, 13(3):300-317, 1976. Google Scholar
  30. Krzysztof Pietrzak. Simple verifiable delay functions. In 10th Innovations in Theoretical Computer Science Conference, ITCS, pages 60:1-60:15, 2019. Google Scholar
  31. Michael O Rabin. Probabilistic algorithm for testing primality. Journal of number theory, 12(1):128-138, 1980. Google Scholar
  32. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. SIAM J. Comput., 50(3), 2021. Google Scholar
  33. Ronald L Rivest, Adi Shamir, and David A Wagner. Time-lock puzzles and timed-release crypto. Technical report, Massachusetts Institute of Technology. Laboratory for Computer Science, 1996. Google Scholar
  34. Lior Rotem. Simple and efficient batch verification techniques for verifiable delay functions. In TCC (3), volume 13044 of Lecture Notes in Computer Science, pages 382-414. Springer, 2021. Google Scholar
  35. Lior Rotem. Revisiting the uber assumption in the algebraic group model: Fine-grained bounds in hidden-order groups and improved reductions in bilinear groups. In ITC, volume 230 of LIPIcs, pages 13:1-13:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  36. Lior Rotem and Gil Segev. Generically speeding-up repeated squaring is equivalent to factoring: Sharp thresholds for all generic-ring delay functions. In Advances in Cryptology - CRYPTO, pages 481-509, 2020. Google Scholar
  37. Lior Rotem, Gil Segev, and Ido Shahaf. Generic-group delay functions require hidden-order groups. In Advances in Cryptology - EUROCRYPT, pages 155-180, 2020. Google Scholar
  38. Adi Shamir. Ip=pspace. In 31st Annual Symposium on Foundations of Computer Science, FOCS, pages 11-15, 1990. Google Scholar
  39. Victor Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT, volume 1233 of Lecture Notes in Computer Science, pages 256-266. Springer, 1997. Google Scholar
  40. Victor Shoup. A computational introduction to number theory and algebra. Cambridge University Press, 2006. Google Scholar
  41. Benjamin Wesolowski. Efficient verifiable delay functions. J. Cryptol., 33(4):2113-2147, 2020. Google Scholar
  42. Mark Zhandry. To label, or not to label (in generic groups). IACR Cryptol. ePrint Arch., page 226, 2022. 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