2 Search Results for "Freitag, Cody"

Document
DOI: 10.4230/LIPIcs.ITC.2023.4
The Cost of Statistical Security in Proofs for Repeated Squaring

Authors: Cody Freitag and Ilan Komargodski

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{freitag_et_al:LIPIcs.ITC.2023.4,
  author =	{Freitag, Cody and Komargodski, Ilan},
  title =	{{The Cost of Statistical Security in Proofs for Repeated Squaring}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.4},
  URN =		{urn:nbn:de:0030-drops-183326},
  doi =		{10.4230/LIPIcs.ITC.2023.4},
  annote =	{Keywords: Cryptographic Proofs, Repeated Squaring, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.44
Testing Hereditary Properties of Sequences

Authors: Cody R. Freitag, Eric Price, and William J. Swartworth

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
A hereditary property of a sequence is one that is preserved when restricting to subsequences. We show that there exist hereditary properties of sequences that cannot be tested with sublinear queries, resolving an open question posed by Newman et al. This proof relies crucially on an infinite alphabet, however; for finite alphabets, we observe that any hereditary property can be tested with a constant number of queries.
Cite as

Cody R. Freitag, Eric Price, and William J. Swartworth. Testing Hereditary Properties of Sequences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 44:1-44:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{freitag_et_al:LIPIcs.APPROX-RANDOM.2017.44,
  author =	{Freitag, Cody R. and Price, Eric and Swartworth, William J.},
  title =	{{Testing Hereditary Properties of Sequences}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{44:1--44:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.44},
  URN =		{urn:nbn:de:0030-drops-75938},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.44},
  annote =	{Keywords: Property Testing}
}
  • Refine by Author
  • 1 Freitag, Cody
  • 1 Freitag, Cody R.
  • 1 Komargodski, Ilan
  • 1 Price, Eric
  • 1 Swartworth, William J.

  • Refine by Classification
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 1 Cryptographic Proofs
  • 1 Lower Bounds
  • 1 Property Testing
  • 1 Repeated Squaring

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact