Beyond the Circuit
How to minimize foreign arithmetic in ZKP circuits
Authors
Michele Orrù, George Kadianakis, Mary Maller, Greg Zaverucha
Michele Orrù
CNRS, FR
m at orru dot net
m at orru dot net
Greg Zaverucha
Microsoft Research, US
gregz at microsoft dot com
gregz at microsoft dot com
Abstract
A fundamental challenge in zero-knowledge proof systems is implementing operations that are “foreign” to the underlying constraint system, in that they are arithmetic operations with a different modulus than the one used by the proof system. The modulus of the constraint system is a large prime, and common examples of foreign operations are Boolean operations, field arithmetic, or public-key cryptography operations. We present novel techniques for efficiently embedding such foreign arithmetic in zero-knowledge, including (i) equality of discrete logarithms across different groups; (ii) scalar multiplication without requiring elliptic curve operations; (iii) proving knowledge of an AES encryption. Our approach combines rejection sampling, sigma protocols, and lookup protocols. We implement and provide concrete benchmarks for our protocols.
References
[AC20]
Thomas Attema and Ronald Cramer. Compressed $\varSigma$-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part III, volume 12172 of Lecture Notes in Computer Science, pages 513–543. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56877-1_18
[AES01]
Advanced Encryption Standard (AES). National Institute of Standards and Technology, NIST FIPS PUB 197, U.S. Department of Commerce. November 2001.
[AFLT12]
Michel Abdalla, Pierre-Alain Fouque, Vadim Lyubashevsky, and Mehdi Tibouchi. Tightly-Secure Signatures from Lossy Identification Schemes. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 572–590. April 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-29011-4_34
[AGM18]
Shashank Agrawal, Chaya Ganesh, and Payman Mohassel. Non-Interactive Zero-Knowledge Proofs for Composite Statements. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part III, volume 10993 of Lecture Notes in Computer Science, pages 643–673. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96878-0_22
[arn]
arnaucube. Proof of concept implementation of Sigmabus.
[ASM06]
Man Ho Au, Willy Susilo, and Yi Mu. Constant-Size Dynamic k-TAA. In Roberto De Prisco and Moti Yung, editors, SCN 06: 5th International Conference on Security in Communication Networks, volume 4116 of Lecture Notes in Computer Science, pages 111–125. September 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11832072_8
[BBdS+23]
Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß, Emmanuela Orsini, Lawrence Roy, and Peter Scholl. Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures from VOLE-in-the-Head. In CRYPTO 2023. 2023. Springer. DOI: 10.1007/978-3-031-38554-4_19
[BBDT16]
Amira Barki, Solenn Brunet, Nicolas Desmoulins, and Jacques Traoré. Improved Algebraic MACs and Practical Keyed-Verification Anonymous Credentials. In Roberto Avanzi and Howard M. Heys, editors, SAC 2016: 23rd Annual International Workshop on Selected Areas in Cryptography, volume 10532 of Lecture Notes in Computer Science, pages 360–380. August 2016. Springer, Cham. DOI: 10.1007/978-3-319-69453-5_20
[BBHR18]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018: 45th International Colloquium on Automata, Languages and Programming, volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:17. July 2018. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ICALP.2018.14
[BBS04]
Dan Boneh, Xavier Boyen, and Hovav Shacham. Short Group Signatures. In Matthew Franklin, editor, Advances in Cryptology – CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 41–55. August 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-28628-8_3
[BCC+16]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 327–357. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49896-5_12
[BCF+21a]
Daniel Benarroch, Matteo Campanelli, Dario Fiore, Kobi Gurkan, and Dimitris Kolonelos. Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular. In Nikita Borisov and Claudia Diaz, editors, Financial Cryptography and Data Security, pages 393–414, Berlin, Heidelberg. 2021. Springer Berlin Heidelberg. DOI: 10.1007/S10623-023-01245-1
[BCF+21b]
Daniel Benarroch, Matteo Campanelli, Dario Fiore, Jihye Kim, Jiwon Lee, Hyunok Oh, and Anaïs Querol. Proposal: commit-and-prove zero-knowledge proof systems and extensions. In 4th ZKProof Workshop. 2021.
[BCG+14]
Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin. In 2014 IEEE Symposium on Security and Privacy, pages 459–474. May 2014. IEEE Computer Society Press. DOI: 10.1109/SP.2014.36
[BCG+22]
Ran Bamberger Kenneth A and Canetti, Shafi Goldwasser, Rebecca Wexler, and Evan J Zimmerman. Verification dilemmas in law and the promise of zero-knowledge proofs. Berkeley Tech. LJ, 37:1, 2022.
[BCL+21]
Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra, and Nicholas Spooner. Proof-Carrying Data Without Succinct Arguments. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 681–710, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84242-0_24
[BCTV14]
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Scalable Zero Knowledge via Cycles of Elliptic Curves. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, Part II, volume 8617 of Lecture Notes in Computer Science, pages 276–294. August 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-44381-1_16
[Ber06]
Daniel J. Bernstein. Curve25519: New Diffie-Hellman Speed Records. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, PKC 2006: 9th International Conference on Theory and Practice of Public Key Cryptography, volume 3958 of Lecture Notes in Computer Science, pages 207–228. April 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11745853_14
[BGH19]
Sean Bowe, Jack Grigg, and Daira Hopwood. Halo: Recursive Proof Composition without a Trusted Setup. Cryptology ePrint Archive, Report 2019/1021. 2019.
[BLS03]
Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott. Constructing Elliptic Curves with Prescribed Embedding Degrees. In Stelvio Cimato, Clemente Galdi, and Giuseppe Persiano, editors, SCN 02: 3rd International Conference on Security in Communication Networks, volume 2576 of Lecture Notes in Computer Science, pages 257–267. September 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-36413-7_19
[Bow17]
Sean Bowe. BLS12-381: New zk-SNARK Elliptic Curve Construction. https://electriccoin.co/blog/new-snark-curve/. 2017.
[BS20]
Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography. Available online https://toc.cryptobook.us/book.pdf. 2020.
[CCC+23]
Ming-Shing Chen, Yu-Shian Chen, Chen-Mou Cheng, Shiuan Fu, Wei-Chih Hong, Jen-Hsuan Hsiang, Sheng-Te Hu, Po-Chun Kuo, Wei-Bin Lee, Feng-Hao Liu, and Justin Thaler. Preon: zk-SNARK based Signature Scheme. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/Preon-spec-web.pdf. 2023.
[CDDH19]
Jan Camenisch, Manu Drijvers, Petr Dzurenda, and Jan Hajny. Fast Keyed-Verification Anonymous Credentials on Standard Smart Cards. In ICT Systems Security and Privacy Protection, pages 286–298. 2019. DOI: 10.1007/978-3-030-22312-0_20
[CDG+17]
Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017: 24th Conference on Computer and Communications Security, pages 1825–1842. 2017. ACM Press. DOI: 10.1145/3133956.3133997
[CFQ19]
Matteo Campanelli, Dario Fiore, and Anaïs Querol. LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019: 26th Conference on Computer and Communications Security, pages 2075–2092. November 2019. ACM Press. DOI: 10.1145/3319535.3339820
[CGKR22]
Geoffroy Couteau, Dahmun Goudarzi, Michael Klooß, and Michael Reichle. Sharp: Short Relaxed Range Proofs. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022: 29th Conference on Computer and Communications Security, pages 609–622. November 2022. ACM Press. DOI: 10.1145/3548606.3560628
[CGM16]
Melissa Chase, Chaya Ganesh, and Payman Mohassel. Efficient Zero-Knowledge Proof of Algebraic and Non-Algebraic Statements with Applications to Privacy Preserving Credentials. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, Part III, volume 9816 of Lecture Notes in Computer Science, pages 499–530. August 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-53015-3_18
[CHM+20]
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 738–768. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45721-1_26
[CL02]
Jan Camenisch and Anna Lysyanskaya. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In Moti Yung, editor, Advances in Cryptology – CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 61–76. August 2002. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45708-9_5
[CL04]
Jan Camenisch and Anna Lysyanskaya. Signature Schemes and Anonymous Credentials from Bilinear Maps. In Matthew Franklin, editor, Advances in Cryptology – CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 56–72. August 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-28628-8_4
[CLOS02]
Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. Universally composable two-party and multi-party secure computation. In 34th Annual ACM Symposium on Theory of Computing, pages 494–503. May 2002. ACM Press. DOI: 10.1145/509907.509980
[CMZ14]
Melissa Chase, Sarah Meiklejohn, and Greg Zaverucha. Algebraic MACs and Keyed-Verification Anonymous Credentials. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, ACM CCS 2014: 21st Conference on Computer and Communications Security, pages 1205–1216. November 2014. ACM Press. DOI: 10.1145/2660267.2660328
[CP93]
David Chaum and Torben P. Pedersen. Wallet Databases with Observers. In Ernest F. Brickell, editor, Advances in Cryptology – CRYPTO'92, volume 740 of Lecture Notes in Computer Science, pages 89–105. August 1993. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48071-4_7
[CPZ20]
Melissa Chase, Trevor Perrin, and Greg Zaverucha. The Signal Private Group System and Anonymous Credentials Supporting Efficient Verifiable Encryption. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020: 27th Conference on Computer and Communications Security, pages 1445–1459. November 2020. ACM Press. DOI: 10.1145/3372297.3417887
[Cra97]
Ronald Cramer. Modular Design of Secure yet Practical Cryptographic Protocols. PhD thesis, CWI Amsterdam, The Netherlands, 1997.
[CT10]
Alessandro Chiesa and Eran Tromer. Proof-Carrying Data and Hearsay Arguments from Signature Cards.. In ICS, volume 10, pages 310–331. 2010.
[DBB+15]
Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark, and Dan Boneh. Provisions: Privacy-preserving Proofs of Solvency for Bitcoin Exchanges. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS 2015: 22nd Conference on Computer and Communications Security, pages 720–731. October 2015. ACM Press. DOI: 10.1145/2810103.2813674
[DD23]
Sai Deng and Bo Du. zkTree: a zk recursion tree with ZKP membership proofs. Cryptology ePrint Archive, Report 2023/208. 2023.
[DR91]
Joan Daemen and Vincent Rijmen. The design of Rijndael: AES. Journal of Cryptology, 4(1):3–72, 1991.
[FS87]
Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, Advances in Cryptology – CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 186–194. August 1987. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-47721-7_12
[FW24]
Georg Fuchsbauer and Mathias Wolf. Concurrently Secure Blind Schnorr Signatures. In EUROCRYPT '24 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part II, pages 124–160. 2024. DOI: 10.1007/978-3-031-58723-8_5
[GAZ+22]
Paul Grubbs, Arasu Arun, Ye Zhang, Joseph Bonneau, and Michael Walfish. Zero-Knowledge Middleboxes. In Kevin R. B. Butler and Kurt Thomas, editors, 31st USENIX Security Symposium, USENIX Security 2022. 2022.
[GKR+21]
Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021: 30th USENIX Security Symposium, pages 519–535. August 2021. USENIX Association.
[GMR89]
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing, 18(1):186–208, 1989.
[GOS06]
Jens Groth, Rafail Ostrovsky, and Amit Sahai. Perfect Non-interactive Zero Knowledge for NP. In Serge Vaudenay, editor, Advances in Cryptology – EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 339–358. 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11761679_21
[Gro16]
Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 305–326. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49896-5_11
[GS08]
Jens Groth and Amit Sahai. Efficient Non-interactive Proof Systems for Bilinear Groups. In Nigel P. Smart, editor, Advances in Cryptology – EUROCRYPT 2008, volume 4965 of Lecture Notes in Computer Science, pages 415–432. April 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-78967-3_24
[GWC19]
Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Report 2019/953. 2019.
[IKOS07]
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge from secure multiparty computation. In David S. Johnson and Uriel Feige, editors, 39th Annual ACM Symposium on Theory of Computing, pages 21–30. June 2007. ACM Press. DOI: 10.1145/1250790.1250794
[JBK+24]
Sergio Juárez, Mark Blunden, Joris Koopman, Anish Mohammed, Kapil Shenvi Pause, and Steve Thakur. Cross-chain bridges via backwards-compatible SNARKs. Cryptology ePrint Archive, Paper 2024/995. 2024.
[KHSS22]
Daniel Kang, Tatsunori Hashimoto, Ion Stoica, and Yi Sun. ZK-IMG: Attested Images via Zero-Knowledge Proofs to Fight Disinformation. 2022.
[Kil90]
Joe Kilian. Uses of Randomness in Algorithms and Protocols. MIT Press, Cambridge, MA, USA 1990.
[KLS18]
Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part III, volume 10822 of Lecture Notes in Computer Science, pages 552–586. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78372-7_18
[KP23]
Abhiram Kothapalli and Bryan Parno. Algebraic Reductions of Knowledge. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part IV, volume 14084 of Lecture Notes in Computer Science, pages 669–701. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38551-3_21
[KPS18]
Ahmed E. Kosba, Charalampos Papamanthou, and Elaine Shi. xJsnark: A Framework for Efficient Verifiable Computation. In 2018 IEEE Symposium on Security and Privacy, pages 944–961. May 2018. IEEE Computer Society Press. DOI: 10.1109/SP.2018.00018
[lam]
[Lin03]
Yehuda Lindell. Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. Journal of Cryptology, 16(3):143–184, June 2003. DOI: 10.1007/s00145-002-0143-7
[Lyu08]
Vadim Lyubashevsky. Lattice-Based Identification Schemes Secure Under Active Attacks. In Ronald Cramer, editor, PKC 2008: 11th International Workshop on Theory and Practice in Public Key Cryptography, volume 4939 of Lecture Notes in Computer Science, pages 162–179. March 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-78440-1_10
[Lyu09]
Vadim Lyubashevsky. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. In Mitsuru Matsui, editor, Advances in Cryptology – ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 598–616. December 2009. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-10366-7_35
[MGGR13]
Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin. Zerocoin: Anonymous Distributed E-Cash from Bitcoin. In 2013 IEEE Symposium on Security and Privacy, pages 397–411. May 2013. IEEE Computer Society Press. DOI: 10.1109/SP.2013.34
[MRV16]
Paz Morillo, Carla Ràfols, and Jorge Luis Villar. The Kernel Matrix Diffie-Hellman Assumption. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology – ASIACRYPT 2016, Part I, volume 10031 of Lecture Notes in Computer Science, pages 729–758. December 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-53887-6_27
[NBS23]
Wilson Nguyen, Dan Boneh, and Srinath Setty. Revisiting the Nova Proof System on a Cycle of Curves. https://eprint.iacr.org/2023/969. Cryptology ePrint Archive, Paper 2023/969. 2023.
[Oka93]
Tatsuaki Okamoto. Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. In Ernest F. Brickell, editor, Advances in Cryptology – CRYPTO'92, volume 740 of Lecture Notes in Computer Science, pages 31–53. August 1993. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48071-4_3
[OKMZ24]
Michele Orrù, George Kadianakis, Mary Maller, and Greg Zaverucha. Beyond the circuit: How to Minimize Foreign Arithmetic in ZKP Circuits. Cryptology ePrint Archive, Paper 2024/265. 2024.
[Ped92]
Torben P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Joan Feigenbaum, editor, Advances in Cryptology – CRYPTO'91, volume 576 of Lecture Notes in Computer Science, pages 129–140. August 1992. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-46766-1_9
[PS00]
David Pointcheval and Jacques Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 13(3):361–396, June 2000. DOI: 10.1007/s001450010003
[SAB+19]
Alberto Sonnino, Mustafa Al-Bassam, Shehar Bano, Sarah Meiklejohn, and George Danezis. Coconut: Threshold Issuance Selective Disclosure Credentials with Applications to Distributed Ledgers. In ISOC Network and Distributed System Security Symposium – NDSS 2019. February 2019. The Internet Society. DOI: 10.14722/ndss.2019.23272
[Sch91]
Claus-Peter Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, January 1991. DOI: 10.1007/BF00196725
[Sma99]
Nigel P. Smart. Elliptic Curve Cryptosystems over Small Fields of Odd Characteristic. Journal of Cryptology, 12(2):141–151, March 1999. DOI: 10.1007/PL00003820
[SSS+22]
Huachuang Sun, Haifeng Sun, Kevin Singh, Akhil Sai Peddireddy, Harshad Patil, Jianwei Liu, and Weikeng Chen. The inspection model for zero-knowledge proofs and efficient Zerocash with secp256k1 keys. Cryptology ePrint Archive, Report 2022/1079. 2022.
[Val08]
Paul Valiant. Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency. In Ran Canetti, editor, TCC 2008: 5th Theory of Cryptography Conference, volume 4948 of Lecture Notes in Computer Science, pages 1–18. March 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-78524-8_1
[XZC+22]
Tiancheng Xie, Jiaheng Zhang, Zerui Cheng, Fan Zhang, Yupeng Zhang, Yongzheng Jia, Dan Boneh, and Dawn Song. zkBridge: Trustless Cross-chain Bridges Made Practical. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022: 29th Conference on Computer and Communications Security, pages 3003–3017. November 2022. ACM Press. DOI: 10.1145/3548606.3560652
[Yas12]
Masaya Yasuda. A GENERALIZATION OF THE ANOMALOUS ATTACK FOR THE ECDLP OVER Qp. International Journal of Pure and Applied Mathematics, 77(1):1–9, 2012.
[zca]
zcash. The Halo2 Book.
PDF
History
Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Michele Orrù, George Kadianakis, Mary Maller, and Greg Zaverucha, Beyond the Circuit. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/an-4c3c2h.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.