{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T12:00:02Z","timestamp":1780056002502,"version":"3.54.0"},"reference-count":38,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T00:00:00Z","timestamp":1769731200000},"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":[[2026,4,17]]},"abstract":"<jats:p>In a  proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information.  In combination with zero-knowledge proof systems, PoKs play an important role in security protocols     such as in digital signatures and authentication schemes, as they enable a prover to demonstrate possession of certain information (such as a private key or a credential), without revealing it.     A PoK is formally defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to any accepting\u00a0prover.<\/jats:p>\n                  <jats:p>We extend this concept to the setting of a single classical verifier and multiple quantum provers and present the first  statistical zero-knowledge (ZK) PoK proof system for problems in QMA. To achieve this, we establish the PoK property for the ZK protocol of Broadbent, Mehta, and Zhao (TQC 2024), which applies to the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers' strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state, the verifier also certifies that provers have access to a quantum system, in particular, a ground state; this indicates a new level of verification for a proof of quantumness.<\/jats:p>","DOI":"10.62056\/a0txomja5","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":1,"title":["A classical proof of quantum knowledge for multi-prover interactive proof systems"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1911-0093","authenticated-orcid":false,"given":"Anne","family":"Broadbent","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03c4mmv16","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Ottawa","place":["Ottawa, Canada"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7374-7082","authenticated-orcid":false,"given":"Alex","family":"Grilo","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02en5vm52","id-type":"ROR","asserted-by":"publisher"}],"name":"Sorbonne Universit\u00e9","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9675-2566","authenticated-orcid":false,"given":"Nagisa","family":"Hara","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03c4mmv16","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Ottawa","place":["Ottawa, Canada"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6384-5196","authenticated-orcid":false,"given":"Arthur","family":"Mehta","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03c4mmv16","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Ottawa","place":["Ottawa, Canada"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:Aspect","doi-asserted-by":"publisher","first-page":"1804","DOI":"10.1103\/PhysRevLett.49.1804","article-title":"Experimental Test of Bell's Inequalities Using\n  Time-Varying Analyzers","volume":"49","author":"Alain Aspect","year":"1982","journal-title":"Physical Review Letters"},{"key":"ref2:HBD+15","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1038\/nature15759","article-title":"Loophole-free Bell inequality violation using electron\n  spins separated by 1.3 kilometres","volume":"526","author":"B. Hensen","year":"2015","journal-title":"Nature"},{"key":"ref3:VV14b","doi-asserted-by":"publisher","first-page":"140501","DOI":"10.1103\/PhysRevLett.113.140501","article-title":"Fully Device-Independent Quantum Key Distribution","volume":"113","author":"Umesh Vazirani","year":"2014","journal-title":"Physical Review Letters"},{"key":"ref4:RUV13","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1038\/nature12035","article-title":"Classical command of quantum systems","volume":"496","author":"Ben W. Reichardt","year":"2013","journal-title":"Nature"},{"key":"ref5:Gri19","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.28","article-title":"A Simple Protocol for Verifiable Delegation of Quantum\n  Computation in One Round","author":"Alex B. Grilo","year":"2019"},{"key":"ref6:BMZ24","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2024.12","article-title":"Quantum Delegation with an Off-The-Shelf Device","author":"Anne Broadbent","year":"2024"},{"key":"ref7:AN02arxiv","volume-title":"Quantum NP \u2013 A Survey","author":"Dorit Aharonov","year":"2002"},{"key":"ref8:BG22","doi-asserted-by":"publisher","first-page":"1400","DOI":"10.1137\/21M140729X","article-title":"QMA-Hardness of Consistency of Local Density Matrices with\n  Applications to Quantum Zero-Knowledge","volume":"51","author":"Anne Broadbent","year":"2022","journal-title":"SIAM Journal on Computing"},{"key":"ref9:CVZ20","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1007\/978-3-030-56877-1_28","article-title":"Non-interactive Zero-Knowledge Arguments for  QMA, with\n  Preprocessing","volume":"3","author":"Andrea Coladangelo","year":"2020"},{"key":"ref10:GSY19","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1109\/FOCS.2019.00044","article-title":"Perfect zero knowledge for quantum multiprover interactive\n  proofs","author":"Alex B. Grilo","year":"2019"},{"key":"ref11:MS24","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1145\/3618260.3649702","article-title":"Two Prover Perfect Zero Knowledge for $\\mathsf{MIP^*}$","author":"Kieran Mastel","year":"2024"},{"key":"ref12:CGJV19","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-030-17659-4_9","article-title":"Verifier-on-a-Leash: New Schemes for Verifiable Delegated\n  Quantum Computation, with Quasilinear Resources","volume":"3","author":"Andrea Coladangelo","year":"2019"},{"key":"ref13:GMR89","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","article-title":"The Knowledge Complexity of Interactive Proof Systems","volume":"18","author":"Shafi Goldwasser","year":"1989","journal-title":"SIAM Journal on Computing"},{"key":"ref14:TW87","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1109\/SFCS.1987.49","article-title":"Random self-reducibility and zero knowledge interactive\n  proofs of possession of information","author":"Martin Tompa","year":"1987"},{"key":"ref15:FFS88","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF02351717","article-title":"Zero-knowledge proofs of identity","volume":"1","author":"Uriel Feige","year":"1988","journal-title":"Journal of Cryptology"},{"key":"ref16:BG93","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/3-540-48071-4_28","article-title":"On Defining Proofs of Knowledge","author":"Mihir Bellare","year":"1993"},{"key":"ref17:Cha83","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-1-4757-0602-4_18","article-title":"Blind signatures for untraceable payments","author":"David Chaum","year":"1983"},{"key":"ref18:VZ21","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1007\/978-3-030-77886-6_22","article-title":"Classical Proofs of Quantum Knowledge","volume":"2","author":"Thomas Vidick","year":"2021"},{"key":"ref19:Mah18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1109\/FOCS.2018.00033","article-title":"Classical Verification of Quantum Computations","author":"Urmila Mahadev","year":"2018"},{"key":"ref20:Unr12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-29011-4_10","article-title":"Quantum Proofs of Knowledge","author":"Dominique Unruh","year":"2012"},{"key":"ref21:NV18","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1109\/FOCS.2018.00075","article-title":"Low-degree testing for quantum states, and a quantum\n  entangled games PCP for QMA","author":"Anand Natarajan","year":"2018"},{"key":"ref22:GH17","doi-asserted-by":"publisher","first-page":"1784","DOI":"10.1070\/sm8872","article-title":"Inverse and stability theorems for approximate\n  representations of finite groups","volume":"208","author":"W. T. Gowers","year":"2017","journal-title":"Sbornik: Mathematics"},{"key":"ref23:GKW15","doi-asserted-by":"publisher","first-page":"83040","DOI":"10.1088\/1367-2630\/17\/8\/083040","article-title":"Robustness and device independence of verifiable blind\n  quantum computing","volume":"17","author":"Alexandru Gheorghiu","year":"2015","journal-title":"New Journal of Physics"},{"key":"ref24:Mah18b","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1109\/FOCS.2018.00039","article-title":"Classical Homomorphic Encryption for Quantum Circuits","author":"Urmila Mahadev","year":"2018"},{"key":"ref25:DNM+24","doi-asserted-by":"publisher","first-page":"150604","DOI":"10.1103\/PhysRevLett.132.150604","article-title":"Verifiable Blind Quantum Computing with Trapped Ions and\n  Single Photons","volume":"132","author":"P. Drmota","year":"2024","journal-title":"Physical Review Letters"},{"key":"ref26:RY22","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.112","article-title":"Interactive Proofs for Synthesizing Quantum States and\n  Unitaries","author":"Gregory Rosenthal","year":"2022"},{"key":"ref27:MY23","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1109\/FOCS57990.2023.00082","article-title":"stateQIP =  statePSPACE","author":"Tony Metger","year":"2023"},{"key":"ref28:BEM+23arxiv","volume-title":"Unitary complexity and the Uhlmann Transformation\n  Problem","author":"John Bostanci","year":"2023"},{"key":"ref29:BI20","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-030-64381-2_4","article-title":"Quantum Encryption with Certified Deletion","volume":"3","author":"Anne Broadbent","year":"2020"},{"key":"ref30:KLVY23","doi-asserted-by":"publisher","first-page":"1617","DOI":"10.1145\/3564246.3585164","article-title":"Quantum Advantage from Any Non-local Game","author":"Yael Kalai","year":"2023"},{"key":"ref31:Mer90","doi-asserted-by":"publisher","first-page":"3373","DOI":"10.1103\/PhysRevLett.65.3373","article-title":"Simple unified form for the major no-hidden-variables\n  theorems","volume":"65","author":"N. David Mermin","year":"1990","journal-title":"Physical Review Letters"},{"key":"ref32:Per90","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0375-9601(90)90172-K","article-title":"Incompatible results of quantum measurements","volume":"151","author":"Asher Peres","year":"1990","journal-title":"Physics Letters A"},{"key":"ref33:WBMS16","doi-asserted-by":"publisher","first-page":"62121","DOI":"10.1103\/PhysRevA.93.062121","article-title":"Device-independent parallel self-testing of two singlets","volume":"93","author":"Xingyao Wu","year":"2016","journal-title":"Physical Review A"},{"key":"ref34:ksv02","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/047","volume-title":"Classical and Quantum Computation","author":"Alexei Yu. Kitaev","year":"2002"},{"key":"ref35:CM14","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1109\/FOCS.2014.21","article-title":"Complexity Classification of Local Hamiltonian Problems","author":"Tony S. Cubitt","year":"2014"},{"key":"ref36:Wat09b","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/060670997","article-title":"Zero-knowledge against quantum attacks","volume":"39","author":"John Watrous","year":"2009","journal-title":"SIAM Journal on Computing"},{"key":"ref37:NV17","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1145\/3055399.3055468","article-title":"A quantum linearity test for robustly verifying\n  entanglement","author":"Anand Natarajan","year":"2017"},{"key":"ref38:McK16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a003","article-title":"Interactive Proofs for $\\mathsf{BQP}$ via Self-Tested Graph\n  States","volume":"12","author":"Matthew McKague","year":"2016","journal-title":"Theory of Computing"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:03:30Z","timestamp":1778040210000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":38,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/a0txomja5","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":"2026-01-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-64"}}