{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:14:55Z","timestamp":1778040895745,"version":"3.51.4"},"reference-count":48,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T00:00:00Z","timestamp":1759708800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,12,2]]},"abstract":"\n We present zkExp (Zero-Knowledge Succinct Exponentiation Proofs), the first zero-knowledge proof system achieving asymptotically efficient bounds for batched exponentiation:\n \n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n ~<\/mml:mo>\n <\/mml:mover>\n (<\/mml:mo>\n k<\/mml:mi>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n prover time,\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n verification time, and constant-size (160\u2013256 B) proofs. For statements\n \n \n \n y<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n \n g<\/mml:mi>\n \n \n x<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n (\n \n \n i<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n ) with private exponents\n \n \n \n x<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n , zkExp introduces four innovations to overcome long-standing scalability barriers: (1) trace-based square-and-multiply encoding, (2) lazy sumcheck for exponentiation constraints, (3) hybrid FFT decomposition reducing memory from\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n to\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n \u2113<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n , and (4) sliding-window batching enabling single-proof aggregation via KZG commitments. The protocol is computationally sound under the\n \n \n (<\/mml:mo>\n q<\/mml:mi>\n ,<\/mml:mo>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n -Generalized Diffie\u2013Hellman Exponent (GDHE) assumption and achieves computational zero-knowledge in the random oracle model. Proofs remain 160\u2013256 B regardless of parameter sizes, with constant verification (3.5 ms). For 4096-bit exponents, prover overhead is\n \n \n 16.3<\/mml:mn>\n \u00d7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n (dropping to\n \n \n 1.35<\/mml:mn>\n \u00d7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n in 1000-batch settings), while Ethereum verification costs\n \n \n ~<\/mml:mi>\n 267<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n gas for 1000 exponentiations,\n \n \n 10<\/mml:mn>\n \u00d7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n cheaper than ECDSA, with memory consumption below 1.1 MB. zkExp is the first protocol to match theoretical lower bounds for exponentiation proofs while enabling practical deployment in zero-knowledge rollups, anonymous credentials, and on-chain threshold cryptography.\n <\/jats:p>","DOI":"10.62056\/ahsg893y6","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["zkExp: Zero-Knowledge Succinct Exponentiation Proofs"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9612-8695","authenticated-orcid":false,"given":"Biniyam","family":"Deressa","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01aff2v68","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Waterloo","place":["200 University Ave. W., Waterloo, N2L 3G1, Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4103-7945","authenticated-orcid":false,"given":"M.","family":"Hasan","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01aff2v68","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Waterloo","place":["200 University Ave. W., Waterloo, N2L 3G1, Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:rivest1978method","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining Digital Signatures and Public-Key\n Cryptosystems","volume":"21","author":"Ronald L. Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref2:camenisch2001efficient","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-44987-6_7","article-title":"An Efficient System for Non-transferable Anonymous\n Credentials with Optional Anonymity Revocation","volume":"2045","author":"Jan Camenisch","year":"2001"},{"key":"ref3:zhang2016town","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1145\/2976749.2978326","article-title":"Town Crier: An Authenticated Data Feed for Smart Contracts","author":"Fan Zhang","year":"2016"},{"key":"ref4:schnorr1991efficient","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00196725","article-title":"Efficient Signature Generation by Smart Cards","volume":"4","author":"Claus-Peter Schnorr","year":"1991","journal-title":"J. Cryptol."},{"key":"ref5:cohen2019chia","volume-title":"The Chia Network Blockchain","author":"Bram Cohen","year":"2019"},{"key":"ref6:camenisch2007batch","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-72540-4_14","article-title":"Batch Verification of Short Signatures","volume":"4515","author":"Jan Camenisch","year":"2007"},{"key":"ref7:groth2016size","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","article-title":"On the Size of Pairing-Based Non-Interactive Arguments","volume":"9666","author":"Jens Groth","year":"2016"},{"key":"ref8:gabizon2019plonk","first-page":"953","article-title":"PLONK: Permutations over Lagrange-bases for Oecumenical\n Noninteractive Arguments of Knowledge","volume":"2019","author":"Ariel Gabizon","year":"2019","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref9:wahby2018doubly","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1109\/SP.2018.00060","article-title":"Doubly-Efficient zkSNARKs Without Trusted Setup","author":"Riad S Wahby","year":"2018"},{"key":"ref10:hoffmann2024practical","doi-asserted-by":"publisher","first-page":"9","DOI":"10.62056\/abvur-iuc","article-title":"Practical Batch Proofs of Exponentiation","volume":"2","author":"Charlotte Hoffmann","year":"2025","journal-title":"IACR Commun. Cryptol."},{"key":"ref11:abadi1987hiding","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/28395.28417","article-title":"On Hiding Information from an Oracle","author":"Mart\u00edn Abadi","year":"1987"},{"key":"ref12:bellare2009security","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00145-008-9028-8","article-title":"Security Proofs for Identity-Based Identification and\n Signature Schemes","volume":"22","author":"Mihir Bellare","year":"2009","journal-title":"J. Cryptol."},{"key":"ref13:boneh2018compact","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/978-3-030-03329-3_15","article-title":"Compact Multi-signatures for Smaller Blockchains","volume":"11273","author":"Dan Boneh","year":"2018"},{"key":"ref14:wesolowski2019efficient","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-030-17659-4_13","article-title":"Efficient Verifiable Delay Functions","volume":"11478","author":"Benjamin Wesolowski","year":"2019"},{"key":"ref15:block2021time","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-030-84259-8_5","article-title":"Time- and Space-Efficient Arguments from Groups of Unknown\n Order","volume":"12828","author":"Alexander R. Block","year":"2021"},{"key":"ref16:rotem2021simple","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-030-90456-2_13","article-title":"Simple and Efficient Batch Verification Techniques for\n Verifiable Delay Functions","volume":"13044","author":"Lior Rotem","year":"2021"},{"key":"ref17:bunz2018bulletproofs","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1109\/SP.2018.00020","article-title":"Bulletproofs: Short Proofs for Confidential Transactions\n and More","author":"Benedikt B\u00fcnz","year":"2018"},{"key":"ref18:ben2018scalable","first-page":"46","article-title":"Scalable, Transparent, and Post-Quantum Secure Computational\n Integrity","volume":"2018","author":"Eli Ben-Sasson","year":"2018","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref19:bunz2020transparent","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-030-45721-1_24","article-title":"Transparent SNARKs from DARK Compilers","volume":"12105","author":"Benedikt B\u00fcnz","year":"2020"},{"key":"ref20:setty2020spartan","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/978-3-030-56877-1_25","article-title":"Spartan: Efficient and General-Purpose zkSNARKs Without\n Trusted Setup","volume":"12172","author":"Srinath T. V. Setty","year":"2020"},{"key":"ref21:chiesa2020marlin","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1007\/978-3-030-45721-1_26","article-title":"Marlin: Preprocessing zkSNARKs with Universal and\n Updatable SRS","volume":"12105","author":"Alessandro Chiesa","year":"2020"},{"key":"ref22:bowe2019recursive","first-page":"1021","article-title":"Halo: Recursive Proof Composition without a Trusted\n Setup","volume":"2019","author":"Sean Bowe","year":"2019","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref23:kothapalli2022nova","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-031-15985-5_13","article-title":"Nova: Recursive Zero-Knowledge Arguments from Folding\n Schemes","volume":"13510","author":"Abhiram Kothapalli","year":"2022"},{"key":"ref24:hoffmann2019efficient","doi-asserted-by":"publisher","first-page":"2093","DOI":"10.1145\/3319535.3354251","article-title":"Efficient Zero-Knowledge Arguments in the Discrete Log\n Setting, Revisited","author":"Max Hoffmann","year":"2019"},{"key":"ref25:ben2019aurora","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-030-17653-2_4","article-title":"Aurora: Transparent Succinct Arguments for R1CS","volume":"11476","author":"Eli Ben-Sasson","year":"2019"},{"key":"ref26:boneh2019batching","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-030-26948-7_20","article-title":"Batching Techniques for Accumulators with Applications to\n IOPs and Stateless Blockchains","volume":"11692","author":"Dan Boneh","year":"2019"},{"key":"ref27:gailly2022snarkpack","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-031-18283-9_10","article-title":"SnarkPack: Practical SNARK Aggregation","volume":"13411","author":"Nicolas Gailly","year":"2022"},{"key":"ref28:zkmap2025","doi-asserted-by":"publisher","DOI":"10.62056\/angy11fgx","article-title":"zkMaP: Zero-Knowledge Succinct Non-Interactive Matrix\n Multiplication Proofs","volume":"2","author":"Biniyam Deressa","year":"2025","journal-title":"IACR Communications in Cryptology"},{"key":"ref29:fan2025speeding","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00145-025-09540-x","article-title":"Speeding Up Multi-scalar Multiplications for Pairing-Based\n zkSNARKs","volume":"38","author":"Xinxin Fan","year":"2025","journal-title":"J. Cryptol."},{"key":"ref30:goldreich2004foundations","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"The Foundations of Cryptography - Volume 2: Basic\n Applications","author":"Oded Goldreich","year":"2004"},{"key":"ref31:kate2010constant","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-17373-8_11","article-title":"Constant-Size Commitments to Polynomials and Their\n Applications","volume":"6477","author":"Aniket Kate","year":"2010"},{"key":"ref32:ben2013snarks","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","article-title":"SNARKs for C: Verifying Program Executions Succinctly and\n in Zero Knowledge","volume":"8043","author":"Eli Ben-Sasson","year":"2013"},{"key":"ref33:schwartz1980fast","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast Probabilistic Algorithms for Verification of Polynomial\n Identities","volume":"27","author":"Jacob T Schwartz","year":"1980","journal-title":"Journal of the ACM (JACM)"},{"key":"ref34:fiat1986prove","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","article-title":"How to Prove Yourself: Practical Solutions to Identification\n and Signature Problems","volume":"263","author":"Amos Fiat","year":"1986"},{"key":"ref35:fuchsbauer2018algebraic","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-319-96881-0_2","article-title":"The Algebraic Group Model and Its Applications","volume":"10991","author":"Georg Fuchsbauer","year":"2018"},{"key":"ref36:bellare1993random","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/168588.168596","article-title":"Random Oracles Are Practical: A Paradigm for Designing\n Efficient Protocols","author":"Mihir Bellare","year":"1993"},{"key":"ref37:bowe2017scalable","first-page":"1050","article-title":"Scalable Multi-party Computation for zk-SNARK\n Parameters in the Random Beacon Model","volume":"2017","author":"Sean Bowe","year":"2017","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref38:boneh2004short","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-540-24676-3_4","article-title":"Short Signatures Without Random Oracles","volume":"3027","author":"Dan Boneh","year":"2004"},{"key":"ref39:bunz2021proofs","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-030-92078-4_3","article-title":"Proofs for Inner Pairing Products and Applications","volume":"13092","author":"Benedikt B\u00fcnz","year":"2021"},{"key":"ref40:naor2003cryptographic","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-45146-4_6","article-title":"On Cryptographic Assumptions and Challenges","volume":"2729","author":"Moni Naor","year":"2003"},{"key":"ref41:cheon2010discrete","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s00145-009-9047-0","article-title":"Discrete Logarithm Problems with Auxiliary Inputs","volume":"23","author":"Jung Hee Cheon","year":"2010","journal-title":"J. Cryptol."},{"key":"ref42:shoup1997lower","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","article-title":"Lower Bounds for Discrete Logarithms and Related Problems","volume":"1233","author":"Victor Shoup","year":"1997"},{"key":"ref43:filecoin2020","volume-title":"Filecoin: A decentralized storage network","author":"Protocol Labs","year":"2020"},{"key":"ref44:Zcash","volume-title":"Zcash Protocol Specification","author":"Electric Coin Company","year":"2022"},{"key":"ref45:eip197","volume-title":"EIP-197: Precompiled contracts for optimal Ate pairing check\n on the elliptic curve alt_bn128","author":"Christian Reitwie\u00dfner","year":"2017"},{"key":"ref46:eip198","volume-title":"EIP-198: Big integer modular exponentiation (ModExp)\n precompile","author":"Vitalik Buterin","year":"2017"},{"key":"ref47:eip1559","volume-title":"EIP-1559: Fee market change for ETH 1.0 chain","author":"Vitalik Buterin","year":"2021"},{"key":"ref48:wood2014ethereum","first-page":"1","article-title":"Ethereum: A secure decentralised generalised transaction\n ledger","volume":"151","author":"Gavin Wood","year":"2014","journal-title":"Ethereum project yellow paper"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:00:44Z","timestamp":1778040044000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":48,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/ahsg893y6","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2025-10-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-4-25"}}