research-article

Public Access

SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE

Authors:

Yael Tauman Kalai,

Dakshita Khurana,

Rachel ZhangAuthors Info & Claims

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

Pages 708 - 721

https://doi.org/10.1145/3406325.3451055

Published: 15 June 2021 Publication History

Abstract

We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential Learning With Errors (LWE) assumption. For a circuit C:{0,1}^N→{0,1} of size S and depth D, the prover runs in time poly(S), the communication complexity is D · polylog(S), and the verifier runs in time (D+N) ·polylog(S). To obtain this result, we introduce a new cryptographic primitive: a lossy correlation-intractable hash function family. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the GKR protocol, assuming the sub-exponential hardness of LWE.

Additionally, by relying on the result of Choudhuri et al. (STOC 2019), we establish (sub-exponential) average-case hardness of PPAD, assuming the sub-exponential hardness of LWE.

References

[1]

Tim Abbot, Daniel Kane, and Paul Valiant. 2004. On algorithms for Nash equilibria. Unpublished manuscript, 2004. https://web.mit.edu/tabbott/Public/final.pdf

[2]

Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin, and Wei-Kai Lin. 2016. Delegating RAM Computations with Adaptive Soundness and Privacy. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II. Pages 3–30. https://doi.org/10.1007/978-3-662-53644-5_1

Digital Library

[3]

Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs. 2018. 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. https://doi.org/10.1145/3188745.3188924

Digital Library

[4]

Boaz Barak. 2001. How to Go Beyond the Black-Box Simulation Barrier. In FOCS. Pages 106–115.

[5]

James Bartusek, Liron Bronfman, Justin Holmgren, Fermi Ma, Ron D. Rothblum, Dennis Hofheinz, and Alon Rosen. 2019. On the (In)security of Kilian-Based SNARGs. In Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II. Lecture Notes in Computer Science. 11892, Springer. Pages 522–551. https://doi.org/10.1007/978-3-030-36033-7_20

[6]

Mihir Bellare, Phillip Rogaway, Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby. 1993. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In ACM Conference on Computer and Communications Security. ACM. Pages 62–73. isbn:0-89791-629-8

Digital Library

[7]

Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner, Martin Hirt, and Adam D. Smith. 2016. Interactive Oracle Proofs. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II. Lecture Notes in Computer Science. 9986, Pages 31–60. https://doi.org/10.1007/978-3-662-53644-5_2

Digital Library

[8]

Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer. 2014. The Hunting of the SNARK. IACR Cryptology ePrint Archive, 2014, 2014. Pages 580. http://eprint.iacr.org/2014/580

[9]

Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. 2013. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013. Pages 111–120. https://doi.org/10.1145/2488608.2488623

Digital Library

[10]

Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. 2013. Succinct Non-interactive Arguments via Linear Interactive Proofs. In TCC. Pages 315–333. https://doi.org/10.1007/978-3-642-36594-2_18

Digital Library

[11]

Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang. 2015. Succinct Randomized Encodings and their Applications. IACR Cryptology ePrint Archive, 2015, 2015. Pages 356.

[12]

Nir Bitansky, Idan Gerichter, and Thomas Vidick. 2020. On the Cryptographic Hardness of Local Search. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA. LIPIcs. 151, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Pages 6:1–6:29. https://doi.org/10.4230/LIPIcs.ITCS.2020.6

[13]

Nir Bitansky, Yael Tauman Kalai, Omer Paneth, Ilias Diakonikolas, David Kempe, and Monika Henzinger. 2018. Multi-collision resistance: a paradigm for keyless hash functions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018. ACM. Pages 671–684. https://doi.org/10.1145/3188745.3188870

Digital Library

[14]

Nir Bitansky, Omer Paneth, Alon Rosen, and Venkatesan Guruswami. 2015. 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. IEEE Computer Society. Pages 1480–1498. https://doi.org/10.1109/FOCS.2015.94

Digital Library

[15]

Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. 2019. Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles. In Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II. Pages 407–437. https://doi.org/10.1007/978-3-030-36033-7_16

[16]

Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. 2020. Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices. IACR Cryptol. ePrint Arch., 2020. https://eprint.iacr.org/2020/1024

[17]

Zvika Brakerski, Justin Holmgren, and Yael Tauman Kalai. 2017. 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. https://doi.org/10.1145/3055399.3055497

Digital Library

[18]

Zvika Brakerski, Yael Kalai, Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas. 2020. Witness Indistinguishability for Any Single-Round Argument with Applications to Access Control. In Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part II. Lecture Notes in Computer Science. 12111, Springer. Pages 97–123. https://doi.org/10.1007/978-3-030-45388-6_4

Digital Library

[19]

Zvika Brakerski, Venkata Koppula, Tamer Mour, Daniele Micciancio, and Thomas Ristenpart. 2020. NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations. In Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part III. Lecture Notes in Computer Science. 12172, Springer. Pages 738–767. https://doi.org/10.1007/978-3-030-56877-1_26

Digital Library

[20]

Gilles Brassard, David Chaum, and Claude Crépeau. 1988. Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci., 37, 2, 1988. Pages 156–189.

[21]

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs, Moses Charikar, and Edith Cohen. 2019. Fiat-Shamir: from practice to theory. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. ACM. Pages 1082–1090. https://doi.org/10.1145/3313276.3316380

Digital Library

[22]

Ran Canetti, Yilei Chen, Leonid Reyzin, and Ron D. Rothblum. 2018. Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption. In 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 I. Pages 91–122. https://doi.org/10.1007/978-3-319-78381-9_4

[23]

Ran Canetti, Oded Goldreich, and Shai Halevi. 2004. The random oracle methodology, revisited. J. ACM, 51, 4, 2004. Pages 557–594.

[24]

Ran Canetti and Justin Holmgren. 2016. Fully Succinct Garbled RAM. In ITCS. ACM. Pages 169–178.

[25]

Ran Canetti, Justin Holmgren, Abhishek Jain, and Vinod Vaikuntanathan. 2015. Succinct Garbling and Indistinguishability Obfuscation for RAM Programs. In STOC. ACM. Pages 429–437.

[26]

David G. Cantor and Hans Zassenhaus. 1981. A new algorithm for factoring polynomials over finite fields. Mathematics of Compuation, 1981. Pages 587–592.

[27]

Xi Chen, Xiaotie Deng, and Shang-Hua Teng. 2009. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56, 3, 2009. Pages 14:1–14:57. https://doi.org/10.1145/1516512.1516516

Digital Library

[28]

Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, and Hong-Sheng Zhou. 2016. Cryptography for Parallel RAM from Indistinguishability Obfuscation. In ITCS. ACM. Pages 179–190.

[29]

Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy N. Rothblum, Moses Charikar, and Edith Cohen. 2019. 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. ACM. Pages 1103–1114. https://doi.org/10.1145/3313276.3316400

Digital Library

[30]

Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. 2019. PPAD-Hardness via Iterated Squaring Modulo a Composite. IACR Cryptol. ePrint Arch., 2019, 2019. Pages 667. https://eprint.iacr.org/2019/667

[31]

Ivan Damg\r ard. 1992. Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks. In Proceedings of CRYPTOï¿œ91. Pages 445–456.

[32]

Ivan Damg\r ard, Sebastian Faust, and Carmit Hazay. 2012. Secure Two-Party Computation with Low Communication. In Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings. Pages 54–74. https://doi.org/10.1007/978-3-642-28914-9_4

Digital Library

[33]

Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. 2009. The Complexity of Computing a Nash Equilibrium. SIAM J. Comput., 39, 1, 2009. Pages 195–259. https://doi.org/10.1137/070699652

Digital Library

[34]

Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, Rafail Ostrovsky, Alexandra Boldyreva, and Daniele Micciancio. 2019. Trapdoor Hash Functions and Their Applications. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III. Lecture Notes in Computer Science. 11694, Springer. Pages 3–32. https://doi.org/10.1007/978-3-030-26954-8_1

Digital Library

[35]

Naomi Ephraim, Cody Freitag, Ilan Komargodski, Rafael Pass, Anne Canteaut, and Yuval Ishai. 2020. 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. Lecture Notes in Computer Science. 12107, Springer. Pages 125–154. https://doi.org/10.1007/978-3-030-45727-3_5

Digital Library

[36]

Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO. Pages 186–194.

[37]

Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, Matthew Robshaw, and Jonathan Katz. 2016. Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium. In Advances in Cryptology - CRYPTO 2016, Proceedings, Part II. Lecture Notes in Computer Science. 9815, Springer. Pages 579–604. https://doi.org/10.1007/978-3-662-53008-5_20

Digital Library

[38]

Romain Gay and Rafael Pass. 2020. Indistinguishability Obfuscation from Circular Security. IACR Cryptol. ePrint Arch., 2020. https://eprint.iacr.org/2020/1010

[39]

Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. 2013. Quadratic Span Programs and Succinct NIZKs without PCPs. In Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings. Pages 626–645. https://doi.org/10.1007/978-3-642-38348-9_37

[40]

Shafi Goldwasser and Yael Tauman Kalai. 2003. On the (In)security of the Fiat-Shamir Paradigm. In FOCS. Pages 102–.

[41]

Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2015. Delegating Computation: Interactive Proofs for Muggles. J. ACM, 62, 4, 2015. Pages 27.

[42]

Jens Groth. 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In ASIACRYPT. Lecture Notes in Computer Science. 6477, Springer. Pages 321–340.

[43]

Brett Hemenway, Rafail Ostrovsky, Marc Fischlin, Johannes A. Buchmann, and Mark Manulis. 2012. Extended-DDH and Lossy Trapdoor Functions. In Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings. Lecture Notes in Computer Science. 7293, Springer. Pages 627–643. https://doi.org/10.1007/978-3-642-30057-8_37

Digital Library

[44]

Justin Holmgren, Alex Lombardi, and Mikkel Thorup. 2018. Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and Their Applications). In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018. IEEE Computer Society. Pages 850–858. https://doi.org/10.1109/FOCS.2018.00085

[45]

Pavel Hubácek, Eylon Yogev, and Philip N. Klein. 2017. Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. SIAM. Pages 1352–1371. https://doi.org/10.1137/1.9781611974782.88

[46]

Aayush Jain, Huijia Lin, and Amit Sahai. 2020. Indistinguishability Obfuscation from Well-Founded Assumptions. Cryptology ePrint Archive, Report 2020/1003. https://eprint.iacr.org/2020/1003

[47]

Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang. 2020. SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE. IACR Cryptol. ePrint Arch., 2020. https://eprint.iacr.org/2020/980.pdf

[48]

Yael Tauman Kalai and Omer Paneth. 2016. Delegating RAM Computations. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II. Pages 91–118. https://doi.org/10.1007/978-3-662-53644-5_4

Digital Library

[49]

Yael Tauman Kalai, Omer Paneth, Lisa Yang, Moses Charikar, and Edith Cohen. 2019. How to delegate computations publicly. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. ACM. Pages 1115–1124. https://doi.org/10.1145/3313276.3316411

Digital Library

[50]

Yael Tauman Kalai, Omer Paneth, and Lisa Yang. 2020. PPAD-Hardness and Delegation with Unambiguous Proofs. CRYPTO.

[51]

Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. 2013. Delegation for bounded space. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013. Pages 565–574. https://doi.org/10.1145/2488608.2488679

Digital Library

[52]

Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. 2014. How to delegate computations: the power of no-signaling proofs. In STOC. ACM. Pages 485–494.

[53]

Yael Tauman Kalai, Guy N. Rothblum, Ron D. Rothblum, Jonathan Katz, and Hovav Shacham. 2017. From Obfuscation to the Security of Fiat-Shamir for Proofs. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II. Lecture Notes in Computer Science. 10402, Springer. Pages 224–251. https://doi.org/10.1007/978-3-319-63715-0_8

[54]

Joe Kilian. 1992. A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing. ACM. Pages 723–732.

Digital Library

[55]

Venkata Koppula, Allison Bishop Lewko, and Brent Waters. 2015. Indistinguishability Obfuscation for Turing Machines with Unbounded Memory. In STOC. ACM. Pages 419–428.

[56]

Helger Lipmaa. 2012. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. In TCC. Pages 169–189.

[57]

Alex Lombardi and Vinod Vaikuntanathan. 2020. Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs. Cryptology ePrint Archive, Report 2020/772. https://eprint.iacr.org/2020/772

[58]

Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. 1992. Algebraic Methods for Interactive Proof Systems. J. ACM, 39, 4, 1992. Pages 859–868.

[59]

Silvio Micali. 1994. CS Proofs (Extended Abstracts). In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994. Pages 436–453. https://doi.org/10.1109/SFCS.1994.365746

Digital Library

[60]

Silvio Micali. 2000. Computationally Sound Proofs. SIAM J. Comput., 30, 4, 2000. Pages 1253–1298.

[61]

Moni Naor. 2003. On Cryptographic Assumptions and Challenges. In Proceedings of the 23rd Annual International Cryptology Conference. Pages 96–109.

[62]

Omer Paneth and Guy N. Rothblum. 2017. On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-interactive Arguments. In Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part II. Pages 283–315. https://doi.org/10.1007/978-3-319-70503-3_9

Digital Library

[63]

Christos H. Papadimitriou. 1994. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci., 48, 3, 1994. Pages 498–532. https://doi.org/10.1016/S0022-0000(05)80063-7

Digital Library

[64]

Bryan Parno, Mariana Raykova, and Vinod Vaikuntanathan. 2012. How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption. In Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings. Pages 422–439. https://doi.org/10.1007/978-3-642-28914-9_24

Digital Library

[65]

Chris Peikert, Sina Shiehian, Alexandra Boldyreva, and Daniele Micciancio. 2019. Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors. In Advances in Cryptology - CRYPTO 2019, Proceedings, Part I. Lecture Notes in Computer Science. 11692, Springer. Pages 89–114. https://doi.org/10.1007/978-3-030-26948-7_4

Digital Library

[66]

Chris Peikert, Brent Waters, and Cynthia Dwork. 2008. Lossy trapdoor functions and their applications. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008. ACM. Pages 187–196. https://doi.org/10.1145/1374376.1374406

Digital Library

[67]

Krzysztof Pietrzak and Avrim Blum. 2019. Simple Verifiable Delay Functions. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA. LIPIcs. 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Pages 60:1–60:15. https://doi.org/10.4230/LIPIcs.ITCS.2019.60

[68]

David Pointcheval, Jacques Stern, and Ueli M. Maurer. 1996. Security Proofs for Signature Schemes. In Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding. Lecture Notes in Computer Science. 1070, Springer. Pages 387–398. https://doi.org/10.1007/3-540-68339-9_33

[69]

Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2016. 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. https://doi.org/10.1145/2897518.2897652

Digital Library

[70]

Adi Shamir. 1992. IP = PSPACE. J. ACM, 39, 4, 1992. Pages 869–877.

[71]

Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walfish. 2018. Doubly-Efficient zkSNARKs Without Trusted Setup. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA. IEEE Computer Society. Pages 926–943. https://doi.org/10.1109/SP.2018.00060

[72]

Hoeteck Wee and Daniel Wichs. 2020. Candidate Obfuscation via Oblivious LWE Sampling. IACR Cryptol. ePrint Arch., 2020. https://eprint.iacr.org/2020/1042

Cited By

Bosshard ABootle JSprenger C(2024)Formal Verification of the Sumcheck Protocol2024 IEEE 37th Computer Security Foundations Symposium (CSF)10.1109/CSF61375.2024.00014(605-619)Online publication date: 8-Jul-2024
https://doi.org/10.1109/CSF61375.2024.00014
Dao QJain AJin Z(2024)Non-interactive Zero-Knowledge from LPN and MQAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68400-5_10(321-360)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68400-5_10
Freitag CPaneth OPass R(2024)Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-ResistanceAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_5(112-141)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58737-5_5
Show More Cited By

Index Terms

SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
1. Theory of computation
  1. Computational complexity and cryptography

Recommendations

Fiat-Shamir: from practice to theory
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

We give new instantiations of the Fiat-Shamir transform using explicit, efficiently computable hash functions. We improve over prior work by reducing the security of these protocols to qualitatively simpler and weaker computational hardness assumptions. ...
SNARGs under LWE via Propositional Proofs
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

We construct a succinct non-interactive argument (SNARG) system for every NP language L that has a propositional proof of non-membership, i.e. of x∉ L. The soundness of our SNARG system relies on the hardness of the learning with errors (LWE) problem. ...
SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption
Advances in Cryptology – EUROCRYPT 2023
Abstract
We construct succinct non-interactive arguments (SNARGs) for bounded-depth computations assuming that the decisional Diffie-Hellman (DDH) problem is sub-exponentially hard. This is the first construction of such SNARGs from a Diffie-Hellman ...
$^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 2021

1797 pages

ISBN:9781450380539

DOI:10.1145/3406325

General Chair:
Samir Khuller
Northwestern University, USA
,
Program Chair:
Virginia Vassilevska Williams
Massachusetts Institute of Technology, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DARPA
Paul E. Gray (1954) UROP Fund

Conference

STOC '21

Sponsor:

SIGACT

STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 21 - 25, 2021

Virtual, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
395
Total Downloads

Downloads (Last 12 months)139
Downloads (Last 6 weeks)20

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bosshard ABootle JSprenger C(2024)Formal Verification of the Sumcheck Protocol2024 IEEE 37th Computer Security Foundations Symposium (CSF)10.1109/CSF61375.2024.00014(605-619)Online publication date: 8-Jul-2024
https://doi.org/10.1109/CSF61375.2024.00014
Dao QJain AJin Z(2024)Non-interactive Zero-Knowledge from LPN and MQAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68400-5_10(321-360)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68400-5_10
Freitag CPaneth OPass R(2024)Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-ResistanceAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_5(112-141)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58737-5_5
Kalai YLombardi AVaikuntanathan VWichs DSaha BServedio R(2023)Boosting Batch Arguments and RAM DelegationProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585200(1545-1552)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585200
Kiyoshima S(2023)Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with ErrorsTheory of Cryptography10.1007/978-3-031-48621-0_12(333-362)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48621-0_12
Agarwal AAlamati NKhurana DRaghuraman SRindal P(2023)On Black-Box Verifiable OutsourcingTheory of Cryptography10.1007/978-3-031-48615-9_6(158-187)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48615-9_6
Aldema Tshuva EBoyle ECohen RMoran TOshman R(2023)Locally Verifiable Distributed SNARGsTheory of Cryptography10.1007/978-3-031-48615-9_3(65-90)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48615-9_3
Bartusek JKhurana DSrinivasan A(2023)Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)Advances in Cryptology – CRYPTO 202310.1007/978-3-031-38554-4_8(224-257)Online publication date: 9-Aug-2023
https://doi.org/10.1007/978-3-031-38554-4_8
Choudhuri AGarg SJain AJin ZZhang J(2023)Correlation Intractability and SNARGs from Sub-exponential DDHAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38551-3_20(635-668)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38551-3_20
Kalai YLombardi AVaikuntanathan V(2023)SNARGs and PPAD Hardness from the Decisional Diffie-Hellman AssumptionAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30617-4_16(470-498)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30617-4_16
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents