Cited By
View all- Amit NRothblum G(2024)Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way FunctionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68403-6_1(3-37)Online publication date: 18-Aug-2024
Constant-Round Arguments from One-Way Functions
Pages 1537 - 1544
Abstract
We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of P, such as depth-bounded computations. Kilian’s celebrated work [STOC 1992] provides such 4-message arguments for P (actually, for NP) using collision-resistant hash functions. We show that one-way functions suffice for obtaining constant-round arguments of almost-linear verification time for languages in P that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian’s) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time. Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear verification complexity are not known even for NC (indeed, even for AC1).
References
[1]
Benny Applebaum and Yoni Moses. Locally computable UOWHF with linear shrinkage. IACR Cryptol. ePrint Arch., page 423, 2013.
[2]
Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci., 37(2):156–189, 1988.
[3]
László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 21–31, 1991.
[4]
Boaz Barak and Oded Goldreich. Universal arguments and their applications. SIAM J. Comput., 38(5):1661–1694, 2008.
[5]
Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In Advances in Cryptology - CRYPTO ’88, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings, pages 37–56, 1988.
[6]
Nir Bitansky, Yael Tauman Kalai, and Omer Paneth. Multi-collision resistance: a paradigm for keyless hash functions. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 671–684. ACM, 2018.
[7]
Mihir Bellare and Phillip Rogaway. Collision-resistant hashing: Towards making uowhfs practical. In Burton S. Kaliski Jr., editor, Advances in Cryptology - CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, volume 1294 of Lecture Notes in Computer Science, pages 470–484. Springer, 1997.
[8]
Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. Snargs for P from LWE. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 68–79. IEEE, 2021.
[9]
Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114–133, 1981.
[10]
Ivan Damgård. A design principle for hash functions. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 416–427. Springer, 1989.
[11]
Lance Fortnow and Carsten Lund. Interactive proof systems and alternating time-space complexity. In Christian Choffrut and Matthias Jantzen, editors, STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings, volume 480 of Lecture Notes in Computer Science, pages 263–274. Springer, 1991.
[12]
Oded Goldreich and Johan Håstad. On the complexity of interactive proofs with bounded communication. Inf. Process. Lett., 67(4):205–214, 1998.
[13]
Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27, 2015.
[14]
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989.
[15]
Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):691–729, 1991.
[16]
Oded Goldreich. Computational complexity - a conceptual perspective. Cambridge University Press, 2008.
[17]
Oded Goldreich. On the doubly-efficient interactive proof systems of GKR. Electron. Colloquium Comput. Complex., TR17-101, 2017.
[18]
Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 39:1–39:43, 2017.
[19]
Oded Goldreich and Guy N. Rothblum. Constant-round interactive proof systems for AC0[2] and NC1. In Oded Goldreich, editor, Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation, volume 12050 of Lecture Notes in Computer Science, pages 326–351. Springer, 2020.
[20]
Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Adv. Comput. Res., 5:73–90, 1989.
[21]
Oded Goldreich, Salil P. Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Comput. Complex., 11(1-2):1–53, 2002.
[22]
Iftach Haitner, Jonathan J. Hoch, Omer Reingold, and Gil Segev. Finding collisions in interactive protocols - tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput., 44(1):193–242, 2015.
[23]
Justin Holmgren and Alex Lombardi. Cryptographic hashing from strong one-way functions (or: One-way product functions and their applications). In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 850–858. IEEE Computer Society, 2018.
[24]
Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil P. Vadhan. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput., 39(3):1153–1218, 2009.
[25]
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. IEEE Computer Society, 1989.
[26]
Yuval Ishai. Zero-knowledge proofs from information-theoretic proof systems - part i. Available at https://zkproof.org/2020/08/12/information-theoretic-proof-systems/, 2020.
[27]
Yuval Ishai. Zero-knowledge proofs from information-theoretic proof systems - part ii. Available at https://zkproof.org/2020/10/15/information-theoretic-proof-systems-part-ii/, 2020.
[28]
Russell Impagliazzo and Moti Yung. Direct minimum-knowledge computations. In Carl Pomerance, editor, Advances in Cryptology - CRYPTO ’87, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings, volume 293 of Lecture Notes in Computer Science, pages 40–51. Springer, 1987.
[29]
Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC, pages 723–732, 1992.
[30]
Jonathan Katz and Chiu-Yuen Koo. On constructing universal one-way hash functions from arbitrary one-way functions, 2005. [email protected] 13051 received 16 Sep 2005, last revised 24 Sep 2005.
[31]
Ilan Komargodski, Moni Naor, and Eylon Yogev. Collision resistant hashing for paranoids: Dealing with multiple collisions. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume 10821 of Lecture Notes in Computer Science, pages 162–194. Springer, 2018.
[32]
Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: The power of no-signaling proofs. J. ACM, 69(1):1:1–1:82, 2022.
[33]
Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1992.
[34]
Ralph C. Merkle. One way hash functions and DES. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 428–446. Springer, 1989.
[35]
Silvio Micali. CS proofs (extended abstracts). In FOCS, pages 436–453, 1994.
[36]
Moni Naor. Bit commitment using pseudorandomness. J. Cryptology, 4(2):151–158, 1991.
[37]
Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications. In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 33–43. ACM, 1989.
[38]
Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333–338, 1987.
[39]
John Rompel. One-way functions are necessary and sufficient for secure signatures. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 387–394. ACM, 1990.
[40]
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 49–62, 2016.
[41]
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Efficient batch verification for UP. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 22:1–22:23, 2018.
[42]
Ron D. Rothblum and Prashant Nalini Vasudevan. Collision-resistance from multi-collision-resistance. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part III, volume 13509 of Lecture Notes in Computer Science, pages 503–529. Springer, 2022.
[43]
Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In STOC, pages 793–802, 2013.
[44]
Adi Shamir. IP = PSPACE. J. ACM, 39(4):869–877, 1992.
[45]
Daniel R. Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT ’98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding, volume 1403 of Lecture Notes in Computer Science, pages 334–345. Springer, 1998.
[46]
Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77–82. ACM, 1987.
[47]
Madhu Sudan. Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, volume 1001 of Lecture Notes in Computer Science. Springer, 1995.
[48]
Justin Thaler. Proofs, arguments, and zero-knowledge. Available at https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html, 2022.
[49]
Hoeteck Wee. On round-efficient argument systems. In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 140–152. Springer, 2005.
Index Terms
- Constant-Round Arguments from One-Way Functions
Recommendations
Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions
Advances in Cryptology – CRYPTO 2024AbstractWhat are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments ...
On basing one-way functions on NP-hardness
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingWe consider the possibility of basing one-way functions on NP-Hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a polynomial-time computable function f. Our main findings are the ...
Coin Flipping with Constant Bias Implies One-Way Functions
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer ScienceIt is well known (cf., Impagliazzo and Luby [FOCS '89]) that the existence of almost all ``interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2023
1926 pages
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 June 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
STOC '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 249Total Downloads
- Downloads (Last 12 months)140
- Downloads (Last 6 weeks)18
Reflects downloads up to 21 Jan 2025
Other Metrics
Citations
Cited By
View all- Amit NRothblum G(2024)Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way FunctionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68403-6_1(3-37)Online publication date: 18-Aug-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in