{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T00:56:53Z","timestamp":1775091413050,"version":"3.50.1"},"reference-count":56,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T00:00:00Z","timestamp":1734393600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We explore the cryptographic power of arbitrary shared physical resources. The most general such resource is access to a fresh entangled quantum state at the outset of each protocol execution. We call this the Common Reference Quantum State (CRQS)<\/mml:mtext><\/mml:mrow><\/mml:math> model, in analogy to the well-known Common Reference String (CRS)<\/mml:mtext><\/mml:mrow><\/mml:math>. The CRQS model is a natural generalization of the CRS model but appears to be more powerful: in the two-party setting, a CRQS can sometimes exhibit properties associated with a Random Oracle queried once by measuring a maximally entangled state in one of many mutually unbiased bases. We formalize this notion as a Weak One-Time Random Oracle (WOTRO)<\/mml:mtext><\/mml:mrow><\/mml:math>, where we only ask of the m<\/mml:mi><\/mml:math>-bit output to have some randomness when conditioned on the n<\/mml:mi><\/mml:math>-bit input.We show that when n<\/mml:mi>&#x2212;<\/mml:mo>m<\/mml:mi>&#x2208;<\/mml:mo>&#x03C9;<\/mml:mi>(<\/mml:mo>lg<\/mml:mi>&#x2061;<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math>, any protocol for WOTRO in the CRQS model can be attacked by an (inefficient) adversary. Moreover, our adversary is efficiently simulatable, which rules out the possibility of proving the computational security of a scheme by a fully black-box reduction to a cryptographic game assumption. On the other hand, we introduce a non-game quantum assumption for hash functions that implies WOTRO in the CRQS model (where the CRQS consists only of EPR pairs). We first build a statistically secure WOTRO protocol where m<\/mml:mi>=<\/mml:mo>n<\/mml:mi><\/mml:math>, then hash the output.The impossibility of WOTRO has the following consequences. First, we show the fully-black-box impossibility of a q<\/mml:mi>u<\/mml:mi>a<\/mml:mi>n<\/mml:mi>t<\/mml:mi>u<\/mml:mi>m<\/mml:mi><\/mml:math> Fiat-Shamir transform, extending the impossibility result of Bitansky et al. (TCC 2013) to the CRQS model. Second, we show a fully-black-box impossibility result for a strenghtened version of quantum lightning (Zhandry, Eurocrypt 2019) where quantum bolts have an additional parameter that cannot be changed without generating new bolts. Our results also apply to 2<\/mml:mn><\/mml:math>-message protocols in the plain model.<\/jats:p>","DOI":"10.22331\/q-2024-12-17-1568","type":"journal-article","created":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T13:55:11Z","timestamp":1734443711000},"page":"1568","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared Entanglement"],"prefix":"10.22331","volume":"8","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Dupuis","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al (DIRO), Montr\u00e9al, Canada"}]},{"given":"Philippe","family":"Lamontagne","sequence":"additional","affiliation":[{"name":"National Research Council Canada, Ottawa, Canada"},{"name":"Universit\u00e9 de Montr\u00e9al (DIRO), Montr\u00e9al, Canada"}]},{"given":"Louis","family":"Salvail","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al (DIRO), Montr\u00e9al, Canada"}]}],"member":"9598","published-online":{"date-parts":[[2024,12,17]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Prabhanjan Ananthand Alex B. Grilo ``Post-Quantum Zero-Knowledge with Space-Bounded Simulation'' (2022).","DOI":"10.48550\/arXiv.2210.06093"},{"key":"1","doi-asserted-by":"publisher","unstructured":"P.K Aravind ``Bell's theorem without inequalities and only two distant observers'' Foundations of Physics Letters 15, 397\u2013405 (2002).","DOI":"10.1023\/A:1021272729475"},{"key":"2","doi-asserted-by":"publisher","unstructured":"P.K Aravind ``A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities'' (2003).","DOI":"10.48550\/arXiv.quant-ph\/0206070"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Andris Ambainis, Ansis Rosmanis, and Dominique Unruh, ``Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding'' Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on 474\u2013483 (2014).","DOI":"10.1109\/FOCS.2014.57"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Rudolph Ahlswedeand Andreas Winter ``Strong converse for identification via quantum channels'' IEEE Transactions on Information Theory 48, 569\u2013579 (2002).","DOI":"10.1109\/18.985947"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Paul Baecher, Christina Brzuska, and Marc Fischlin, ``Notions of Black-Box Reductions, Revisited'' Advances in Cryptology - ASIACRYPT 2013 296\u2013315 (2013).","DOI":"10.1007\/978-3-642-42033-7_16"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Anne Broadbent, and Alain Tapp, ``Quantum Pseudo-Telepathy'' Foundations of Physics 35, 1877\u20131907 (2005).","DOI":"10.1007\/s10701-005-7353-4"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Manuel Blum, Paul Feldman, and Silvio Micali, ``Non-interactive Zero-knowledge and Its Applications'' Proc. Twentieth Annual ACM Symposium on Theory of Computing 103\u2013112 (1988).","DOI":"10.1145\/62212.62222"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Nir Bitansky, Sanjam Garg, and Daniel Wichs, ``Why Fiat-Shamir for proofs lacks a proof'' (2012).","DOI":"10.1007\/978-3-642-36594-2_11"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Nir Bitansky, Dana Dachman-Soled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana L\u00f3pez-Alt, and Daniel Wichs, ``Why ``fiat-shamir for proofs'' lacks a proof'' Theory of Cryptography Conference 182\u2013201 (2013).","DOI":"10.1007\/978-3-642-36594-2_11"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Manuel Blum, Alfredo De Santis, Silvio Micali, and Giuseppe Persiano, ``Noninteractive Zero-Knowledge'' SIAM Journal on Computing 20, 1084\u20131118 (1991).","DOI":"10.1137\/0220068"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Boaz Barak, Yehuda Lindell, and Salil Vadhan, ``Lower bounds for non-black-box zero knowledge'' Journal of Computer and System Sciences 72, 321\u2013391 (2006).","DOI":"10.1016\/j.jcss.2005.06.010"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Mihir Bellareand Phillip Rogaway ``Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols'' Proc. 1st ACM Conference on Computer and Communications Security 62\u201373 (1993).","DOI":"10.1145\/168588.168596"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Harry Buhrmanand Ronald de Wolf ``Lower Bounds for Quantum Search and Derandomization'' (1998).","DOI":"10.48550\/arXiv.quant-ph\/9811046"},{"key":"14","unstructured":"Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, and Ron D. Rothblum, ``Fiat-Shamir From Simpler Assumptions'' Cryptology ePrint Archive, Report 2018\/1004 (2018) https:\/\/ia.cr\/2018\/1004."},{"key":"15","doi-asserted-by":"publisher","unstructured":"R. Canetti ``Universally Composable Security: A New Paradigm for Cryptographic Protocols'' Proc. 42Nd IEEE Symposium on Foundations of Computer Science 136\u2013(2001).","DOI":"10.1109\/SFCS.2001.959888"},{"key":"16","doi-asserted-by":"crossref","unstructured":"Eric A. Carlen ``Trace inequalities and quantum entropy: An introductory course'' (2010).","DOI":"10.1090\/conm\/529\/10428"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Ran Canettiand Marc Fischlin ``Universally Composable Commitments'' Proc. CRYPTO 19\u201340 (2001).","DOI":"10.1007\/3-540-44647-8_2"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Ran Canetti, Oded Goldreich, and Shai Halevi, ``The Random Oracle Methodology, Revisited'' J. ACM 51, 557\u2013594 (2004).","DOI":"10.1145\/1008731.1008734"},{"key":"19","unstructured":"Ronald Cramer ``Modular Design of Secure yet Practical Cryptographic Protocols'' thesis (1996)."},{"key":"20","doi-asserted-by":"publisher","unstructured":"Andrea W. Coladangelo, Thomas G. Vidick, and Tina Zhang, ``Non-Interactive Zero-Knowledge Arguments for QMA, with preprocessing'' (2020).","DOI":"10.1007\/978-3-030-56877-1_28"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Shujiao Caoand Rui Xue ``The Gap Is Sensitive to Size of Preimages: Collapsing Property Doesn't Go Beyond Quantum Collision-Resistance for Preimages Bounded Hash Functions'' Advances in Cryptology \u2013 CRYPTO 2022 564\u2013595 (2022).","DOI":"10.1007\/978-3-031-15982-4_19"},{"key":"22","unstructured":"Dana Dachman-Soled, Abhishek Jain, Yael Tauman Kalai, and Adriana Lopez-Alt, ``On the (In)security of the Fiat-Shamir Paradigm, Revisited'' Cryptology ePrint Archive, Report 2012\/706 (2012) https:\/\/eprint.iacr.org\/2012\/706."},{"key":"23","unstructured":"Ivan Damg\u00e5rd ``On Sigma-protocols'' (2010)."},{"key":"24","doi-asserted-by":"publisher","unstructured":"Pierre Deligne ``La conjecture de Weil : I'' Publications Math\u00e9matiques de l'IH\u00c9S 43, 273\u2013307 (1974).","DOI":"10.1007\/BF02684373"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Ivan Damg\u00e5rd, Serge Fehr, and Louis Salvail, ``Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks'' Proc. CRYPTO 254\u2013272 (2004).","DOI":"10.1007\/978-3-540-28628-8_16"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Ivan Damg\u00e5rdand Jesper Buus Nielsen ``Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor'' Proc. CRYPTO 581\u2013596 (2002).","DOI":"10.1007\/3-540-45708-9_37"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner, ``Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model'' Proc. CRYPTO 356\u2013383 (2019).","DOI":"10.1007\/978-3-030-26951-7_13"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Yevgeniy Dodis, Thomas Ristenpart, and Salil Vadhan, ``Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources'' Proc. TCC 618\u2013635 (2012).","DOI":"10.1007\/978-3-642-28914-9_35"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Marc Fischlin ``Communication-Efficient Non-interactive Proofs of Knowledge with Online Extractors'' Proc. CRYPTO 152\u2013168 (2005).","DOI":"10.1007\/11535218_10"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Amos Fiatand Adi Shamir ``How To Prove Yourself: Practical Solutions to Identification and Signature Problems'' (1986).","DOI":"10.1007\/3-540-47721-7_12"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Shafi Goldwasserand Yael Tauman Kalai ``On the (In)Security of the Fiat-Shamir Paradigm'' Proc. FOCS 102\u2013(2003).","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Oded Goldreichand Yair Oren ``Definitions and Properties of Zero-knowledge Proof Systems'' J. Cryptol. 7, 1\u201332 (1994).","DOI":"10.1007\/BF00195207"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Craig Gentryand Daniel Wichs ``Separating Succinct Non-interactive Arguments from All Falsifiable Assumptions'' Proc. STOC 99\u2013108 (2011).","DOI":"10.1145\/1993636.1993651"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Iftach Haitnerand Thomas Holenstein ``On the (Im)Possibility of Key Dependent Encryption'' Proc. TCC 202\u2013219 (2009).","DOI":"10.1007\/978-3-642-00457-5_13"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Akinori Hosoyamadaand Takashi Yamakawa ``Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness'' Advances in Cryptology \u2013 ASIACRYPT 2020 3\u201332 (2020).","DOI":"10.1007\/978-3-030-64837-4_1"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Russell Impagliazzoand Steven Rudich ``Limits on the Provable Consequences of One-Way Permutations'' Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA 44\u201361 (1989).","DOI":"10.1145\/73007.73012"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Andreas Klappeneckerand Martin R\u00f6tteler ``Constructions of Mutually Unbiased Bases'' Finite Fields and Applications 137\u2013144 (2004).","DOI":"10.1007\/978-3-540-24633-6_10"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Yael Tauman Kalai, Guy N. Rothblum, and Ron D. Rothblum, ``From Obfuscation to the Security of Fiat-Shamir for Proofs'' CRYPTO 224\u2013251 (2017).","DOI":"10.1007\/978-3-319-63715-0_8"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Qipeng Liuand Mark Zhandry ``Revisiting Post-quantum Fiat-Shamir'' Proc. CRYPTO 326\u2013355 (2019).","DOI":"10.1007\/978-3-030-26951-7_12"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Tomoyuki Morimae, Barak Nehoran, and Takashi Yamakawa, ``Unconditionally Secure Commitments with Quantum Auxiliary Inputs'' Advances in Cryptology \u2013 CRYPTO 2024 59\u201392 (2024).","DOI":"10.1007\/978-3-031-68394-7_3"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Tomoyuki Morimaeand Takashi Yamakawa ``Classically Verifiable NIZK for QMA with Preprocessing'' Advances in Cryptology \u2013 ASIACRYPT 2022 599\u2013627 (2022).","DOI":"10.1007\/978-3-031-22972-5_21"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Moni Naor ``On Cryptographic Assumptions and Challenges'' Proc. CRYPTO 2003 2729, 96\u2013109 (2003) Invited paper.","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Sandu Popescuand Daniel Rohrlich ``Thermodynamics and the measure of entanglement'' Phys. Rev. A 56, R3319\u2013R3321 (1997).","DOI":"10.1103\/PhysRevA.56.R3319"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Chris Peikertand Sina Shiehian ``Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors'' Proc. CRYPTO 89\u2013114 (2019).","DOI":"10.1007\/978-3-030-26948-7_4"},{"key":"45","doi-asserted-by":"publisher","unstructured":"David Pointchevaland Jacques Stern ``Security Proofs for Signature Schemes'' Proc. EUROCRYPT 387\u2013398 (1996).","DOI":"10.1007\/3-540-68339-9_33"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Luowen Qian ``Unconditionally Secure Quantum Commitments with Preprocessing'' Advances in Cryptology \u2013 CRYPTO 2024 38\u201358 (2024).","DOI":"10.1007\/978-3-031-68394-7_2"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Bhaskar Roberts ``Security Analysis of Quantum Lightning'' LNCS Advances in Cryptology \u2013 EUROCRYPT 2021 12697, 562\u2013567 (2021).","DOI":"10.1007\/978-3-030-77886-6_19"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Omer Reingold, Luca Trevisan, and Salil Vadhan, ``Notions of Reducibility between Cryptographic Primitives'' Theory of Cryptography 1\u201320 (2004).","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Julian Schwinger ``Unitary Operator Bases'' Proc. National Academy of Sciences 46, 570\u2013579 (1960).","DOI":"10.1073\/pnas.46.4.570"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Claus-Peter Schnorr ``Efficient Identification and Signatures for Smart Cards'' Proc. CRYPTO 435, 239\u2013252 (1989).","DOI":"10.1007\/0-387-34805-0_22"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Yannick Seurin ``On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model'' EUROCRYPT 7237, 554\u2013571 (2012).","DOI":"10.1007\/978-3-642-29011-4_33"},{"key":"52","doi-asserted-by":"publisher","unstructured":"John Watrous ``PSPACE has constant-round quantum interactive proof systems'' Theoretical Computer Science 292, 575\u2013588 (2003).","DOI":"10.1016\/S0304-3975(01)00375-9"},{"key":"53","doi-asserted-by":"publisher","unstructured":"William K Woottersand Brian D Fields ``Optimal state-determination by mutually unbiased measurements'' Annals of Physics 191, 363\u2013381 (1989).","DOI":"10.1016\/0003-4916(89)90322-9"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Daniel Wichs ``Barriers in cryptography with weak, correlated and leaky sources'' Proceedings of the 4th conference on Innovations in Theoretical Computer Science 111\u2013126 (2013).","DOI":"10.1145\/2422436.2422451"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Mark Zhandry ``Quantum Lightning Never Strikes the Same State Twice'' Advances in Cryptology \u2013 EUROCRYPT 2019 408\u2013438 (2019).","DOI":"10.1007\/978-3-030-17659-4_14"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-17-1568\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T13:55:29Z","timestamp":1734443729000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-17-1568\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,17]]},"references-count":56,"URL":"https:\/\/doi.org\/10.22331\/q-2024-12-17-1568","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,17]]},"article-number":"1568"}}