SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. (English) Zbl 07765204
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 708-721 (2021).
MSC:
| 68Qxx | Theory of computing |
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. · Zbl 1397.94045 · doi:10.1007/978-3-662-53644-5_1 |
| [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. · Zbl 1427.68112 · doi:10.1145/3188745.3188924 |
| [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. · Zbl 1455.94120 · doi: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 |
| [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. · Zbl 1397.94048 · doi:10.1007/978-3-662-53644-5_2 |
| [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. · Zbl 1293.68264 · doi:10.1145/2488608.2488623 |
| [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. · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18 |
| [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. · Zbl 07650354 · doi: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. · Zbl 1427.94076 · doi:10.1145/3188745.3188870 |
| [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. · doi:10.1109/FOCS.2015.94 |
| [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. · Zbl 1455.94132 · doi: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. · Zbl 1369.68209 · doi:10.1145/3055399.3055497 |
| [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. · Zbl 1481.94088 · doi:10.1007/978-3-030-45388-6_4 |
| [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. · Zbl 1504.94110 · doi:10.1007/978-3-030-56877-1_26 |
| [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. · Zbl 0656.68109 |
| [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. · Zbl 1434.94060 · doi:10.1145/3313276.3316380 |
| [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. · Zbl 1423.94058 · doi: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. · Zbl 1204.94063 |
| [24] | Ran Canetti and Justin Holmgren. 2016. Fully Succinct Garbled RAM. In ITCS. ACM. Pages 169-178. · Zbl 1334.68064 |
| [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. · Zbl 1321.94050 |
| [26] | David G. Cantor and Hans Zassenhaus. 1981. A new algorithm for factoring polynomials over finite fields. Mathematics of Compuation, 1981. Pages 587-592. · Zbl 0493.12024 |
| [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. · Zbl 1325.68095 · doi:10.1145/1516512.1516516 |
| [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. · Zbl 1334.94068 |
| [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. · Zbl 1434.94063 · doi:10.1145/3313276.3316400 |
| [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. · Zbl 0764.94015 |
| [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. · Zbl 1303.94076 · doi:10.1007/978-3-642-28914-9_4 |
| [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. · Zbl 1185.91019 · doi:10.1137/070699652 |
| [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. · Zbl 1436.94054 · doi:10.1007/978-3-030-26954-8_1 |
| [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. · Zbl 1479.94164 · doi:10.1007/978-3-030-45727-3_5 |
| [36] | Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO. Pages 186-194. · Zbl 0636.94012 |
| [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. · Zbl 1391.94752 · doi:10.1007/978-3-662-53008-5_20 |
| [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. · Zbl 1300.94056 · doi: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. · Zbl 1393.68071 |
| [42] | Jens Groth. 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In ASIACRYPT. Lecture Notes in Computer Science. 6477, Springer. Pages 321-340. · Zbl 1253.94049 |
| [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. · Zbl 1291.94096 · doi:10.1007/978-3-642-30057-8_37 |
| [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. · doi: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. · Zbl 1410.68145 · doi: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. · Zbl 1397.94074 · doi:10.1007/978-3-662-53644-5_4 |
| [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. · Zbl 1434.94070 · doi:10.1145/3313276.3316411 |
| [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. · Zbl 1293.68176 · doi:10.1145/2488608.2488679 |
| [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. · Zbl 1315.68135 |
| [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. · Zbl 1409.94881 · doi: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. |
| [55] | Venkata Koppula, Allison Bishop Lewko, and Brent Waters. 2015. Indistinguishability Obfuscation for Turing Machines with Unbounded Memory. In STOC. ACM. Pages 419-428. · Zbl 1321.94069 |
| [56] | Helger Lipmaa. 2012. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. In TCC. Pages 169-189. · Zbl 1303.94090 |
| [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. · Zbl 0799.68097 |
| [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. · doi:10.1109/SFCS.1994.365746 |
| [60] | Silvio Micali. 2000. Computationally Sound Proofs.. SIAM J. Comput., 30, 4, 2000. Pages 1253-1298. · Zbl 1009.68053 |
| [61] | Moni Naor. 2003. On Cryptographic Assumptions and Challenges. In Proceedings of the 23rd Annual International Cryptology Conference. Pages 96-109. · Zbl 1122.94391 |
| [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. · Zbl 1412.94198 · doi:10.1007/978-3-319-70503-3_9 |
| [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 · Zbl 0806.68048 · doi:10.1016/S0022-0000(05)80063-7 |
| [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. · Zbl 1304.68043 · doi:10.1007/978-3-642-28914-9_24 |
| [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. · Zbl 1456.94106 · doi:10.1007/978-3-030-26948-7_4 |
| [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. · Zbl 1228.94027 · doi:10.1145/1374376.1374406 |
| [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. · Zbl 07559103 · doi: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. · Zbl 1304.94106 · doi: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. · Zbl 1373.68274 · doi:10.1145/2897518.2897652 |
| [70] | Adi Shamir. 1992. IP = PSPACE. J. ACM, 39, 4, 1992. Pages 869-877. · Zbl 0799.68096 |
| [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. · doi: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 |
| [73] | Tim Abbot, Daniel Kane, and Paul Valiant. 2004. On algorithms for Nash equilibria. Unpublished manuscript, 2004. https://web.mit.edu/tabbott/Public/final.pdf |
| [74] | 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. · Zbl 1397.94045 · doi:10.1007/978-3-662-53644-5_1 |
| [75] | 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. · Zbl 1427.68112 · doi:10.1145/3188745.3188924 |
| [76] | Boaz Barak. 2001. How to Go Beyond the Black-Box Simulation Barrier. In FOCS. Pages 106-115. |
| [77] | 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. · Zbl 1455.94120 · doi:10.1007/978-3-030-36033-7_20 |
| [78] | 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 |
| [79] | 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. · Zbl 1397.94048 · doi:10.1007/978-3-662-53644-5_2 |
| [80] | 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 |
| [81] | 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. · Zbl 1293.68264 · doi:10.1145/2488608.2488623 |
| [82] | 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. · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18 |
| [83] | 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. |
| [84] | 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. · Zbl 07650354 · doi:10.4230/LIPIcs.ITCS.2020.6 |
| [85] | 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. · Zbl 1427.94076 · doi:10.1145/3188745.3188870 |
| [86] | 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. · doi:10.1109/FOCS.2015.94 |
| [87] | 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. · Zbl 1455.94132 · doi:10.1007/978-3-030-36033-7_16 |
| [88] | 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 |
| [89] | 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. · Zbl 1369.68209 · doi:10.1145/3055399.3055497 |
| [90] | 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. · Zbl 1481.94088 · doi:10.1007/978-3-030-45388-6_4 |
| [91] | 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. · Zbl 1504.94110 · doi:10.1007/978-3-030-56877-1_26 |
| [92] | Gilles Brassard, David Chaum, and Claude Crépeau. 1988. Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci., 37, 2, 1988. Pages 156-189. · Zbl 0656.68109 |
| [93] | 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. · Zbl 1434.94060 · doi:10.1145/3313276.3316380 |
| [94] | 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. · Zbl 1423.94058 · doi:10.1007/978-3-319-78381-9_4 |
| [95] | Ran Canetti, Oded Goldreich, and Shai Halevi. 2004. The random oracle methodology, revisited. J. ACM, 51, 4, 2004. Pages 557-594. · Zbl 1204.94063 |
| [96] | Ran Canetti and Justin Holmgren. 2016. Fully Succinct Garbled RAM. In ITCS. ACM. Pages 169-178. · Zbl 1334.68064 |
| [97] | Ran Canetti, Justin Holmgren, Abhishek Jain, and Vinod Vaikuntanathan. 2015. Succinct Garbling and Indistinguishability Obfuscation for RAM Programs. In STOC. ACM. Pages 429-437. · Zbl 1321.94050 |
| [98] | David G. Cantor and Hans Zassenhaus. 1981. A new algorithm for factoring polynomials over finite fields. Mathematics of Compuation, 1981. Pages 587-592. · Zbl 0493.12024 |
| [99] | 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. · Zbl 1325.68095 · doi:10.1145/1516512.1516516 |
| [100] | 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. · Zbl 1334.94068 |
| [101] | 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. · Zbl 1434.94063 · doi:10.1145/3313276.3316400 |
| [102] | 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 |
| [103] | Ivan Damg\r ard. 1992. Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks. In Proceedings of CRYPTOï¿œ91. Pages 445-456. · Zbl 0764.94015 |
| [104] | 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. · Zbl 1303.94076 · doi:10.1007/978-3-642-28914-9_4 |
| [105] | 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. · Zbl 1185.91019 · doi:10.1137/070699652 |
| [106] | 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. · Zbl 1436.94054 · doi:10.1007/978-3-030-26954-8_1 |
| [107] | 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. · Zbl 1479.94164 · doi:10.1007/978-3-030-45727-3_5 |
| [108] | Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO. Pages 186-194. · Zbl 0636.94012 |
| [109] | 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. · Zbl 1391.94752 · doi:10.1007/978-3-662-53008-5_20 |
| [110] | Romain Gay and Rafael Pass. 2020. Indistinguishability Obfuscation from Circular Security. IACR Cryptol. ePrint Arch., 2020. https://eprint.iacr.org/2020/1010 |
| [111] | 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. · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37 |
| [112] | Shafi Goldwasser and Yael Tauman Kalai. 2003. On the (In)security of the Fiat-Shamir Paradigm. In FOCS. Pages 102-. |
| [113] | Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2015. Delegating Computation: Interactive Proofs for Muggles. J. ACM, 62, 4, 2015. Pages 27. · Zbl 1393.68071 |
| [114] | Jens Groth. 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In ASIACRYPT. Lecture Notes in Computer Science. 6477, Springer. Pages 321-340. · Zbl 1253.94049 |
| [115] | 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. · Zbl 1291.94096 · doi:10.1007/978-3-642-30057-8_37 |
| [116] | 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. · doi:10.1109/FOCS.2018.00085 |
| [117] | 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. · Zbl 1410.68145 · doi:10.1137/1.9781611974782.88 |
| [118] | 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 |
| [119] | 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 |
| [120] | 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. · Zbl 1397.94074 · doi:10.1007/978-3-662-53644-5_4 |
| [121] | 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. · Zbl 1434.94070 · doi:10.1145/3313276.3316411 |
| [122] | Yael Tauman Kalai, Omer Paneth, and Lisa Yang. 2020. PPAD-Hardness and Delegation with Unambiguous Proofs. CRYPTO. |
| [123] | 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. · Zbl 1293.68176 · doi:10.1145/2488608.2488679 |
| [124] | 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. · Zbl 1315.68135 |
| [125] | 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. · Zbl 1409.94881 · doi:10.1007/978-3-319-63715-0_8 |
| [126] | 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. |
| [127] | Venkata Koppula, Allison Bishop Lewko, and Brent Waters. 2015. Indistinguishability Obfuscation for Turing Machines with Unbounded Memory. In STOC. ACM. Pages 419-428. · Zbl 1321.94069 |
| [128] | Helger Lipmaa. 2012. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. In TCC. Pages 169-189. · Zbl 1303.94090 |
| [129] | 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 |
| [130] | 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. · Zbl 0799.68097 |
| [131] | 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. · doi:10.1109/SFCS.1994.365746 |
| [132] | Silvio Micali. 2000. Computationally Sound Proofs.. SIAM J. Comput., 30, 4, 2000. Pages 1253-1298. · Zbl 1009.68053 |
| [133] | Moni Naor. 2003. On Cryptographic Assumptions and Challenges. In Proceedings of the 23rd Annual International Cryptology Conference. Pages 96-109. · Zbl 1122.94391 |
| [134] | 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. · Zbl 1412.94198 · doi:10.1007/978-3-319-70503-3_9 |
| [135] | 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 · Zbl 0806.68048 · doi:10.1016/S0022-0000(05)80063-7 |
| [136] | 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. · Zbl 1304.68043 · doi:10.1007/978-3-642-28914-9_24 |
| [137] | 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. · Zbl 1456.94106 · doi:10.1007/978-3-030-26948-7_4 |
| [138] | 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. · Zbl 1228.94027 · doi:10.1145/1374376.1374406 |
| [139] | 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. · Zbl 07559103 · doi:10.4230/LIPIcs.ITCS.2019.60 |
| [140] | 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. · Zbl 1304.94106 · doi:10.1007/3-540-68339-9_33 |
| [141] | 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. · Zbl 1373.68274 · doi:10.1145/2897518.2897652 |
| [142] | Adi Shamir. 1992. IP = PSPACE. J. ACM, 39, 4, 1992. Pages 869-877. · Zbl 0799.68096 |
| [143] | 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. · doi:10.1109/SP.2018.00060 |
| [144] | Hoeteck Wee and Daniel Wichs. 2020. Candidate Obfuscation via Oblivious LWE Sampling. IACR Cryptol. ePrint Arch., 2020. https://eprint.iacr.org/2020/1042 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
