MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

Andrea Coladangelo; Ruta Jawale; Dakshita Khurana; Giulio Malavolta; Hendrik Waldner

doi:10.22331/q-2026-07-15-2161

MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

Andrea Coladangelo¹, Ruta Jawale², Dakshita Khurana³, Giulio Malavolta⁴, and Hendrik Waldner⁵

¹University of Washington
²University of Illinois, Urbana-Champaign
³University of Illinois, Urbana-Champaign and NTT Research
⁴Bocconi University
⁵CISPA

Published:	2026-07-15, volume 10, page 2161
Editor:	Tomoyuki Morimae
Eprint:	arXiv:2506.22961v2
Doi:	https://doi.org/10.22331/q-2026-07-15-2161
Citation:	Quantum 10, 2161 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The MPC-in-the-head technique (Ishai et al., STOC 2007) is a celebrated method to build zero-knowledge protocols with desirable theoretical properties and high practical efficiency. This technique has generated a large body of research and has influenced the design of real-world post-quantum cryptographic signatures. In this work, we present a generalization of the MPC-in-the-head paradigm to the quantum setting, where the MPC is running a quantum computation. As an application of our framework, we propose a new approach to build zero-knowledge protocols where security holds even against a verifier that can obtain a superposition of transcripts. This notion was pioneered by Damgard et al., who built a zero-knowledge protocol for NP (in the common reference string model) secure against superposition attacks, by relying on perfectly hiding and unconditionally binding dual-mode commitments. Unfortunately, no such commitments are known from standard cryptographic assumptions. In this work we revisit this problem, and present two new three-round protocols in the common reference string model: (i) A zero-knowledge argument for NP, whose security reduces to the standard learning with errors (LWE) problem. (ii) A zero-knowledge argument for QMA from the same assumption.

► BibTeX data

@article{Coladangelo2026mpcinquantumhead,
  doi = {10.22331/q-2026-07-15-2161},
  url = {https://doi.org/10.22331/q-2026-07-15-2161},
  title = {{MPC} in the {Q}uantum {H}ead (or: {S}uperposition-{S}ecure ({Q}uantum) {Z}ero-{K}nowledge)},
  author = {Coladangelo, Andrea and Jawale, Ruta and Khurana, Dakshita and Malavolta, Giulio and Waldner, Hendrik},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2161},
  month = jul,
  year = {2026}
}

► References

[1] Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung, ``Non-interactive Classical Verification of Quantum Computation'' Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III 12552, 153-180 (2020).
https://doi.org/10.1007/978-3-030-64381-2_6

[2] Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba, ``On Quantum Chosen-Ciphertext Attacks and Learning with Errors'' Cryptogr. 4, 10 (2020).
https://doi.org/10.3390/CRYPTOGRAPHY4010010

[3] James Bartusekand Giulio Malavolta ``Indistinguishability Obfuscation of Null Quantum Circuits and Applications'' 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA 215, 15:1–15:13 (2022).
https://doi.org/10.4230/LIPIcs.ITCS.2022.15

[4] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson, ``Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)'' Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA 1–10 (1988).
https://doi.org/10.1145/62212.62213

[5] Rishabh Bhadauria, Zhiyong Fang, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Tiancheng Xie, and Yupeng Zhang, ``Ligero++: A New Optimized Sublinear IOP'' CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9-13, 2020 2025–2038 (2020).
https://doi.org/10.1145/3372297.3417893

[6] Ritam Bhaumik, Xavier Bonnetain, André Chailloux, Gaëtan Leurent, María Naya-Plasencia, André Schrottenloher, and Yannick Seurin, ``QCB: Efficient Quantum-Secure Authenticated Encryption'' Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part I 668–698 (2021).
https://doi.org/10.1007/978-3-030-92062-3_23

[7] Dan Bonehand Mark Zhandry ``Quantum-Secure Message Authentication Codes'' Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 7881, 592–608 (2013).
https://doi.org/10.1007/978-3-642-38348-9_35

[8] Dan Bonehand Mark Zhandry ``Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World'' Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II 8043, 361–379 (2013).
https://doi.org/10.1007/978-3-642-40084-1_21

[9] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry, ``Random Oracles in a Quantum World'' Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 7073, 41–69 (2011).
https://doi.org/10.1007/978-3-642-25385-0_3

[10] Zvika Brakerskiand Nir Magrafta ``Real-Valued Somewhat-Pseudorandom Unitaries'' Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceedings, Part II 36–59 (2024).
https://doi.org/10.1007/978-3-031-78017-2_2

[11] Zvika Brakerskiand Omri Shmueli ``Scalable Pseudorandom Quantum States'' Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part II 417–440 (2020).
https://doi.org/10.1007/978-3-030-56880-1_15

[12] Anne Broadbentand Alex Bredariol Grilo ``QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge'' SIAM J. Comput. 51, 1400–1450 (2022).
https://doi.org/10.1137/21M140729X

[13] Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous, ``Zero-Knowledge Proof Systems for QMA'' SIAM J. Comput. 49, 245–283 (2020).
https://doi.org/10.1137/18M1193530

[14] André Chailloux ``Tight quantum security of the Fiat-Shamir transform for commit-and-open identification schemes with applications to post-quantum signature schemes'' CoRR abs/1906.05415 (2019).
https://doi.org/10.48550/arXiv.1906.05415
arXiv:1906.05415

[15] 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'' Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017 1825–1842 (2017).
https://doi.org/10.1145/3133956.3133997

[16] Kai-Min Chung, Yi Lee, Han-Hsuan Lin, and Xiaodi Wu, ``Constant-Round Blind Classical Verification of Quantum Sampling'' Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III 707–736 (2022).
https://doi.org/10.1007/978-3-031-07082-2_25

[17] Claude Crepeau, Daniel Gottesman, and Adam Smith, ``Secure Multi-party Quantum Computing'' (2002).
https://doi.org/10.48550/ARXIV.QUANT-PH/0206138
https://arxiv.org/abs/quant-ph/0206138

[18] Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner, ``Improving the Security of Quantum Protocols via Commit-and-Open'' Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings 408–427 (2009).
https://doi.org/10.1007/978-3-642-03356-8_24

[19] Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, and Louis Salvail, ``Superposition Attacks on Cryptographic Protocols'' Information Theoretic Security - 7th International Conference, ICITS 2013, Singapore, November 28-30, 2013, Proceedings 8317, 142–161 (2013).
https://doi.org/10.1007/978-3-319-04268-8_9

[20] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner, ``Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model'' Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II 11693, 356–383 (2019).
https://doi.org/10.1007/978-3-030-26951-7_13

[21] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner, ``Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM'' Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II 729–757 (2022).
https://doi.org/10.1007/978-3-031-15979-4_25

[22] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner, ``Online-Extractability in the Quantum Random-Oracle Model'' Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III 13277, 677–706 (2022).
https://doi.org/10.1007/978-3-031-07082-2_24

[23] Uriel Feige, Dror Lapidot, and Adi Shamir, ``Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract)'' 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I 308–317 (1990).
https://doi.org/10.1109/FSCS.1990.89549

[24] Tommaso Gagliardoni, Andreas Hülsing, and Christian Schaffner, ``Semantic Security and Indistinguishability in the Quantum World'' Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III 9816, 60–89 (2016).
https://doi.org/10.1007/978-3-662-53015-3_3

[25] Sumegha Garg, Henry Yuen, and Mark Zhandry, ``New Security Notions and Feasibility Results for Authentication of Quantum Data'' Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II 10402, 342–371 (2017).
https://doi.org/10.1007/978-3-319-63715-0_12

[26] Irene Giacomelli, Jesper Madsen, and Claudio Orlandi, ``ZKBoo: Faster Zero-Knowledge for Boolean Circuits'' 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016 1069–1083 (2016).

[27] Oded Goldreich, Silvio Micali, and Avi Wigderson, ``How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority'' Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA 218–229 (1987).
https://doi.org/10.1145/28395.28420

[28] J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten, ``Lest We Remember: Cold Boot Attacks on Encryption Keys'' Proceedings of the 17th USENIX Security Symposium, July 28-August 1, 2008, San Jose, CA, USA 45–60 (2008).
https://doi.org/10.1145/1506409.1506429

[29] Michael Hutterand Jörn-Marc Schmidt ``The Temperature Side Channel and Heating Fault Attacks'' Smart Card Research and Advanced Applications - 12th International Conference, CARDIS 2013, Berlin, Germany, November 27-29, 2013. Revised Selected Papers 8419, 219–235 (2013).
https://doi.org/10.1007/978-3-319-08302-5_15

[30] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai, ``Zero-Knowledge Proofs from Secure Multiparty Computation'' SIAM J. Comput. 39, 1121–1152 (2009).
https://doi.org/10.1137/080725398

[31] Zhengfeng Ji, Yi-Kai Liu, and Fang Song, ``Pseudorandom Quantum States'' Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III 10993, 126–152 (2018).
https://doi.org/10.1007/978-3-319-96878-0_5

[32] Elham Kashefi, Luka Music, and Petros Wallden, ``The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation'' CoRR abs/1703.03754 (2017).
https://doi.org/10.48550/ARXIV.1703.03754
arXiv:1703.03754

[33] Jonathan Katz, Vladimir Kolesnikov, and Xiao Wang, ``Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures'' Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018 525–537 (2018).
https://doi.org/10.1145/3243734.3243805

[34] Julia Kempe, Alexei Y. Kitaev, and Oded Regev, ``The Complexity of the Local Hamiltonian Problem'' SIAM J. Comput. 35, 1070–1097 (2006).
https://doi.org/10.1137/S0097539704445226

[35] Julia Kempeand Oded Regev ``3-local Hamiltonian is QMA-complete'' Quantum Inf. Comput. 3, 258–264 (2003).
https://doi.org/10.26421/QIC3.3-7

[36] Alexei Y. Kitaev, A. H. Shen, and Mikhail N. Vyalyi, ``Classical and Quantum Computation'' American Mathematical Society (2002).
https://bookstore.ams.org/gsm-47/

[37] Alex Lombardiand Luke Schaeffer ``A Note on Key Agreement and Non-Interactive Commitments'' IACR Cryptol. ePrint Arch. 2019, 279 (2019).
https://eprint.iacr.org/2019/279

[38] Chris Peikert, Vinod Vaikuntanathan, and Brent Waters, ``A Framework for Efficient and Composable Oblivious Transfer'' Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings 5157, 554–571 (2008).
https://doi.org/10.1007/978-3-540-85174-5_31

[39] Adam Smith ``Multi-party Quantum Computation'' CoRR abs/0111030 (2026).
https://doi.org/10.48550/ARXIV.QUANT-PH/0111030
arXiv:0111030

[40] Fabian Wiesnerand Anna Pappa ``Verified delegated quantum computation requires techniques beyond cut-and-choose'' CoRR abs/2603.09368 (2026).
https://doi.org/10.48550/ARXIV.2603.09368
arXiv:2603.09368

[41] Fabian Wiesner, Ziad Chaoui, Diana Kessler, Anna Pappa, and Martti Karvonen, ``Why cut-and-choose quantum state verification cannot be both efficient and secure'' IACR Communications in Cryptology 2 (2026).
https://doi.org/10.62056/ay11c3c2h

[42] Salessawi Ferede Yitbarek, Misiker Tadesse Aga, Reetuparna Das, and Todd M. Austin, ``Cold Boot Attacks are Still Hot: Security Analysis of Memory Scramblers in Modern Processors'' 2017 IEEE International Symposium on High Performance Computer Architecture, HPCA 2017, Austin, TX, USA, February 4-8, 2017 313–324 (2017).
https://doi.org/10.1109/HPCA.2017.10

[43] Mark Zhandry ``How to Construct Quantum Random Functions'' 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 679–687 (2012).
https://doi.org/10.1109/FOCS.2012.37

[44] Mark Zhandry ``Secure Identity-Based Encryption in the Quantum Random Oracle Model'' Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings 7417, 758–775 (2012).
https://doi.org/10.1007/978-3-642-32009-5_44

Cited by

Could not fetch Crossref cited-by data during last attempt 2026-07-15 13:49:15: Could not fetch cited-by data for 10.22331/q-2026-07-15-2161 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2026-07-15 13:49:15).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.