{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:15:11Z","timestamp":1778040911638,"version":"3.51.4"},"reference-count":49,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:00:00Z","timestamp":1759881600000},"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":"<jats:p>\n                    Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without the user revealing any extra information about themselves.  For example, a user who has received a digital passport credential can prove their \u201cage is\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mo>&gt;<\/mml:mo>\n                        <mml:mn>18<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    \u201d without revealing any other attributes such as their name or date of birth.\n                  <\/jats:p>\n                  <jats:p>Despite their clear application to privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale.  Part of the difficulty arises because schemes in the literature, such as BBS+, use new cryptographic primitives that require system-wide changes to existing issuer infrastructure.  In addition,  issuers often require digital identity credentials to be device-bound by incorporating the device\u2019s secure element into the presentation flow.  As a result, schemes like BBS+ require updates to the hardware on every user's device.<\/jats:p>\n                  <jats:p>We propose new ZK techniques which enable the construction of an anonymous credential scheme for the legacy Elliptic Curve Digital Signature Algorithm (ECDSA) signature scheme.  By adding efficient ZK arguments for statements about SHA-256 and document parsing for ISO-standardized identity formats, we construct the first ZK proof of posession of a credential that can be deployed without changing any issuer processes, without changes to mobile devices, and without requiring non-standard cryptographic assumptions.  Furthermore, our proof system itself only relies     on SHA-256 as its complexity assumption.<\/jats:p>\n                  <jats:p>Producing ZK proofs about ECDSA signatures has been a bottleneck for other ZK proof systems because standardized curves such as P256 use finite fields which do not support efficient number theoretic transforms.  We overcome this bottleneck by designing a ZK proof system around sumcheck and the Ligero argument system, by designing efficient methods for Reed-Solomon encoding over the required fields, and by designing specialized circuits for ECDSA.<\/jats:p>\n                  <jats:p>\n                    Our proofs for ECDSA can be generated in as little as\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mo>\u2248<\/mml:mo>\n                        <mml:mn>20<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    ms.  When incorporated into a fully standardized identity protocol such as the ISO MDOC standard, our system  can generate a zero-knowledge proof for the MDOC presentation flow in a few hundred ms on mobile devices. These advantages make our scheme a promising candidate for privacy-preserving digital identity applications.\n                  <\/jats:p>","DOI":"10.62056\/a3qjmpgxq","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":["Anonymous Credentials from ECDSA"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2648-2641","authenticated-orcid":false,"given":"Matteo","family":"Frigo","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00njsd438","id-type":"ROR","asserted-by":"publisher"}],"name":"Google","place":["Cambridge, MA, USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5362-469X","authenticated-orcid":false,"given":"abhi","family":"shelat","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00njsd438","id-type":"ROR","asserted-by":"publisher"}],"name":"Google","place":["Cambridge, MA, USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:bbs+","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45572-3_1","article-title":"Anonymous Attestation Using the Strong Diffie Hellman\n  Assumption Revisited","author":"Jan Camenisch","year":"2016"},{"key":"ref2:chaum85","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1145\/4372.4373","article-title":"Security without identification: Transaction systems to make\n  big brother obsolete","volume":"10","author":"David Chaum","year":"1985","journal-title":"Communications of the ACM"},{"key":"ref3:lrsw99","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46513-8_14","article-title":"Pseudonym systems","volume":"1758","author":"Anna Lysyanskaya","year":"1999"},{"key":"ref4:brands","volume-title":"Rethinking Public Key Infrastructure and Digital\n  Certificates","author":"Stefan Brands","year":"1999"},{"key":"ref5:cl01","doi-asserted-by":"publisher","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":"ref6:coco","volume-title":"C${\\emptyset}$C$\\emptyset$: A Framework for Building\n  Composable Zero-Knowledge Proofs","author":"Ahmed Kosba","year":"2015"},{"key":"ref7:Cinderella","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.22","article-title":"Cinderella: Turning Shabby X.509 Certificates into Elegant\n  Anonymous Credentials with the Magic of Verifiable Computation","author":"Antoine Delignat-Lavaud","year":"2016"},{"key":"ref8:zkcred","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179430","article-title":"zk-creds: Flexible Anonymous Credentials from zkSNARKs and\n  Existing Identity Infrastructure","author":"Michael Rosenberg","year":"2023"},{"key":"ref9:ligero","doi-asserted-by":"publisher","first-page":"3379","DOI":"10.1007\/s10623-023-01222-8","article-title":"Ligero: Lightweight Sublinear Arguments Without a Trusted\n  Setup","volume":"91","author":"Scott Ames","year":"2023","journal-title":"Des. Codes Cryptogr."},{"key":"ref10:hyrax","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00060","article-title":"Doubly-efficient zkSNARKs without trusted setup","author":"Riad S. Wahby","year":"2018"},{"key":"ref11:DP23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91134-7_4","article-title":"Succinct Arguments over Towers of Binary Fields","author":"Benjamin E. Diamond","year":"2025"},{"key":"ref12:DP24","volume-title":"Polylogarithmic Proofs for Multilinears over Binary Towers","author":"Benjamin E. Diamond","year":"2024"},{"key":"ref13:LCH14","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1109\/FOCS.2014.41","article-title":"Novel Polynomial Basis and Its Application to Reed-Solomon\n  Erasure Codes","author":"Sian-Jheng Lin","year":"2014"},{"key":"ref14:woo-zk","doi-asserted-by":"publisher","DOI":"10.1109\/SP61157.2025.00080","article-title":"Efficient Proofs of Possession for Legacy Signatures","author":"Anna Woo","year":"2025"},{"key":"ref15:lfkn","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","article-title":"Algebraic methods for interactive proof systems","volume":"39","author":"Carsten Lund","year":"1992","journal-title":"J. ACM"},{"key":"ref16:thaler-notes","doi-asserted-by":"crossref","DOI":"10.1561\/9781638281252","volume-title":"Proofs, Arguments, and Zero-Knowledge","author":"Justin Thaler","year":"2022"},{"key":"ref17:ip-zk","doi-asserted-by":"publisher","DOI":"10.5555\/88314.88333","article-title":"Everything Provable is Provable in Zero-Knowledge","volume":"403","author":"Michael Ben-Or","year":"1988"},{"key":"ref18:gkr","doi-asserted-by":"publisher","DOI":"10.1145\/269943","article-title":"Delegating computation: interactive proofs for muggles","author":"Shafi Goldwasser","year":"2008"},{"key":"ref19:CMT12","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/2090236.2090245","article-title":"Practical verified computation with streaming interactive\n  proofs","author":"Graham Cormode","year":"2012"},{"key":"ref20:thaler13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_5","article-title":"Time-optimal interactive proofs for circuit evaluation","volume":"8043","author":"Justin Thaler","year":"2013"},{"key":"ref21:wjbstww","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133984","article-title":"Full accounting for verifiable outsourcing","author":"Riad S Wahby","year":"2017"},{"key":"ref22:rbr19","volume-title":"eprint\/2018\/1004","author":"Ran Canetti","year":"2018"},{"key":"ref23:krs25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-032-01887-8_1","article-title":"How to Prove False Statements: Practical Attacks on\n  Fiat-Shamir","volume":"16005","author":"Dmitry Khovratovich","year":"2025"},{"key":"ref24:Gow92","doi-asserted-by":"crossref","first-page":"45","DOI":"10.33232\/BIMS.0028.45.52","article-title":"Cauchy's matrix, the Vandermonde matrix and polynomial\n  interpolation","volume":"28","author":"Roderick Gow","year":"1992","journal-title":"Bulletin of the Irish Mathematical Society"},{"key":"ref25:Nus80","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/TASSP.1980.1163372","article-title":"Fast polynomial transform algorithms for digital\n  convolution","volume":"28","author":"Henri J. Nussbaumer","year":"1980","journal-title":"IEEE Transactions on Acoustics, Speech, and Signal\n  Processing"},{"key":"ref26:Knu97","isbn-type":"print","volume-title":"The art of computer programming, volume 2 (3rd ed.):\n  seminumerical algorithms","author":"Donald E. Knuth","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0201896842"},{"key":"ref27:ZXZS19","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00052","article-title":"Transparent Polynomial Delegation and Its Applications to\n  Zero Knowledge Proof","author":"Jiaheng Zhang","year":"2019"},{"key":"ref28:SoJoBu87","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1109\/ICASSP.1987.1169490","article-title":"Real-valued algorithms for the FFT","volume":"12","author":"H. Sorensen","year":"1987"},{"key":"ref29:LANHC16","doi-asserted-by":"publisher","first-page":"6284","DOI":"10.1109\/TIT.2016.2608892","article-title":"Novel Polynomial Basis With Fast Fourier Transform and Its\n  Application to Reed\u2013Solomon Erasure Codes","volume":"62","author":"Sian-Jheng Lin","year":"2016","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref30:LCK+18","article-title":"Frobenius Additive Fast Fourier Transform","author":"Wen-Ding Li","year":"2018"},{"key":"ref31:vdH04","series-title":"ISSAC '04","isbn-type":"print","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1145\/1005285.1005327","article-title":"The truncated fourier transform and applications","author":"Joris van der Hoeven","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/158113827X"},{"key":"ref32:vzGG96","series-title":"ISSAC '96","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/236869.236882","article-title":"Arithmetic and factorization of polynomial over F2 (extended\n  abstract)","author":"Joachim von zur Gathen","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0897917960"},{"key":"ref33:Mat08","volume-title":"Fast Fourier transform algorithms with applications","author":"Todd Mateer","year":"2008"},{"key":"ref34:vdH05","volume-title":"Notes on the Truncated Fourier Transform","author":"Joris van der Hoeven","year":"2005"},{"key":"ref35:sec1","volume-title":"SEC 1: Elliptic Curve Cryptography, v2.0","author":"Certicom","year":"2009"},{"key":"ref36:RFC8949","series-title":"Request for Comments","doi-asserted-by":"publisher","DOI":"10.17487\/RFC8949","volume-title":"Concise Binary Object Representation (CBOR)","author":"Carsten Bormann","year":"2020"},{"key":"ref37:Ble90","volume-title":"Prefix Sums and Their Applications","author":"Guy\u00a0E. Blelloch","year":"1990"},{"key":"ref38:Skl60","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1109\/TEC.1960.5219822","article-title":"Conditional-Sum Addition Logic","volume":"9","author":"Jack Sklansky","year":"1960","journal-title":"IRE Trans. Electron. Comput."},{"key":"ref39:BK82","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/TC.1982.1675982","article-title":"A Regular Layout for Parallel Adders","volume":"C-31","author":"Brent","year":"1982","journal-title":"IEEE Transactions on Computers"},{"key":"ref40:brakedown","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_7","article-title":"Brakedown: Linear-time and field-agnostic SNARKs for R1CS","volume":"14082","author":"Alexander Golovnev","year":"2023"},{"key":"ref41:orion","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15985-5_11","article-title":"Orion: Zero Knowledge Proof with Linear Prover Time","volume":"13510","author":"Tiancheng Xie","year":"2022"},{"key":"ref42:ligetron","doi-asserted-by":"publisher","DOI":"10.1109\/SP54263.2024.00086","article-title":"Ligetron: Lightweight Scalable End-to-End Zero-Knowledge\n  Proofs Post-Quantum ZK-SNARKs on a Browser","author":"Ruihan Wang","year":"2024"},{"key":"ref43:binius","volume-title":"Binius implementation"},{"key":"ref44:stark","volume-title":"eprint\/2018\/046","author":"Eli Ben-Sasson","year":"2018"},{"key":"ref45:pairing-crypto","volume-title":"Pairing crypto BBS implementation","year":"2024"},{"key":"ref46:circom-ecdsa","volume-title":"Circom-ecdsa","author":"0xParc","year":"2022"},{"key":"ref47:spartan-ecdsa","author":"Personae","year":"2023"},{"key":"ref48:bckl07","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78524-8_20","article-title":"P-signatures and noninteractive anonymous credentials","volume":"4948","author":"Mira Belenkiy","year":"2008"},{"key":"ref49:iso-mdoc","volume-title":"Personal identification\u2014ISO-compliant driving\n  licence\u2014Part 5: Mobile driving licence (mDL) application","author":"ISO\/IEC FDIS 18013-5","year":"2021"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:01:34Z","timestamp":1778040094000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":49,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/a3qjmpgxq","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-08","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-52"}}