Quantum Merkle Trees

Quantum Merkle Trees

Time Stamp: June 18, 2024 6:58 AM
Quantum Merkle Trees PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Lijie Chen1 and Ramis Movassagh2,3

1Miller Institute for Basic Research in Science, University of California, Berkeley, CA, 94720, USA
2Google Quantum AI, Venice, CA, 90291, USA
3IBM Quantum, MIT-IBM Watson AI Lab, Cambridge, MA, 02142, USA

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

Abstract

Committing to information is a central task in cryptography, where a party (typically called a prover) stores a piece of information (e.g., a bit string) with the promise of not changing it. This information can be accessed by another party (typically called the verifier), who can later learn the information and verify that it was not meddled with. Merkle trees [1] are a well-known construction for doing so in a succinct manner, in which the verifier can learn any part of the information by receiving a short proof from the honest prover. Despite its significance in classical cryptography, there was no quantum analog of the Merkle tree. A direct generalization using the Quantum Random Oracle Model (QROM) [2] does not seem to be secure. In this work, we propose the $textit{quantum Merkle tree}$. It is based on what we call the $textit{Quantum Haar Random Oracle Model}$ (QHROM). In QHROM, both the prover and the verifier have access to a $Haar$ random quantum oracle $G$ and its inverse.
Using the quantum Merkle tree, we propose a succinct quantum argument for the Gap-$k$-Local-Hamiltonian problem. Assuming the Quantum PCP conjecture is true, this succinct argument extends to all of QMA. This work raises a number of interesting open research problems.

â–º BibTeX data

â–º References

[1] Ralph C. Merkle. “A digital signature based on a conventional encryption function”. In Advances in Cryptology – CRYPTO ’87, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings. Volume 293 of Lecture Notes in Computer Science, pages 369–378. Springer (1987).
https:/​/​doi.org/​10.1007/​3-540-48184-2_32

[2] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. “Random oracles in a quantum world”. In 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. Volume 7073 of Lecture Notes in Computer Science, pages 41–69. Springer (2011).
https:/​/​doi.org/​10.1007/​978-3-642-25385-0_3

[3] Gilles Brassard, David Chaum, and Claude Crépeau. “Minimum disclosure proofs of knowledge”. J. Comput. Syst. Sci. 37, 156–189 (1988).
https:/​/​doi.org/​10.1016/​0022-0000(88)90005-0

[4] Joe Kilian. “A note on efficient zero-knowledge proofs and arguments (extended abstract)”. In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada. Pages 723–732. ACM (1992). url: https:/​/​doi.org/​10.1145/​129712.129782.
https:/​/​doi.org/​10.1145/​129712.129782

[5] Silvio Micali. “Computationally sound proofs”. SIAM J. Comput. 30, 1253–1298 (2000). url: https:/​/​doi.org/​10.1137/​S0097539795284959.
https:/​/​doi.org/​10.1137/​S0097539795284959

[6] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. “Interactive oracle proofs”. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography – 14th International Conference, TCC 2016-B, Beijing, China, October 31 – November 3, 2016, Proceedings, Part II. Volume 9986 of Lecture Notes in Computer Science, pages 31–60. (2016). url: https:/​/​doi.org/​10.1007/​978-3-662-53644-5_2.
https:/​/​doi.org/​10.1007/​978-3-662-53644-5_2

[7] Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. “Succinct arguments in the quantum random oracle model”. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography – 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II. Volume 11892 of Lecture Notes in Computer Science, pages 1–29. Springer (2019). url: https:/​/​doi.org/​10.1007/​978-3-030-36033-7_1.
https:/​/​doi.org/​10.1007/​978-3-030-36033-7_1

[8] Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. “Post-quantum succinct arguments: Breaking the quantum rewinding barrier”. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. Pages 49–58. IEEE (2021).
https:/​/​doi.org/​10.1109/​FOCS52979.2021.00014

[9] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. “Pseudorandom quantum states”. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018 – 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III. Volume 10993 of Lecture Notes in Computer Science, pages 126–152. Springer (2018).
https:/​/​doi.org/​10.1007/​978-3-319-96878-0_5

[10] Fernando GSL Brandao, Aram W Harrow, and MichaÅ‚ Horodecki. “Local random quantum circuits are approximate polynomial-designs”. Communications in Mathematical Physics 346, 397–434 (2016). url: https:/​/​doi.org/​10.1007/​s00220-016-2706-8.
https:/​/​doi.org/​10.1007/​s00220-016-2706-8

[11] Mark Zhandry. “How to record quantum queries, and applications to quantum indifferentiability”. In Advances in Cryptology – CRYPTO 2019 – 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II. Volume 11693 of Lecture Notes in Computer Science, pages 239–268. Springer (2019).
https:/​/​doi.org/​10.1007/​978-3-030-26951-7_9

[12] Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. “Commitments to quantum states”. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023. Pages 1579–1588. ACM (2023).
https:/​/​doi.org/​10.1145/​3564246.3585198

[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] Andrea Coladangelo, Thomas Vidick, and Tina Zhang. “Non-interactive zero-knowledge arguments for qma, with preprocessing”. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020 – 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part III. Volume 12172 of Lecture Notes in Computer Science, pages 799–828. Springer (2020).
https:/​/​doi.org/​10.1007/​978-3-030-56877-1_28

[15] Anne Broadbent and 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

[16] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh V. Vazirani. “The detectability lemma and quantum gap amplification”. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 – June 2, 2009. Pages 417–426. ACM (2009).
https:/​/​doi.org/​10.1145/​1536414.1536472

[17] Dorit Aharonov, Itai Arad, and Thomas Vidick. “Guest column: the quantum PCP conjecture”. SIGACT News 44, 47–79 (2013). url: https:/​/​doi.org/​10.1145/​2491533.2491549.
https:/​/​doi.org/​10.1145/​2491533.2491549

[18] Lane P Hughston, Richard Jozsa, and William K Wootters. “A complete classification of quantum ensembles having a given density matrix”. Physics Letters A 183, 14–18 (1993). url: https:/​/​doi.org/​10.1016/​0375-9601(93)90880-9.
https:/​/​doi.org/​10.1016/​0375-9601(93)90880-9

Cited by

[1] Ramis Movassagh, “The hardness of random quantum circuits”, Nature Physics 19 11, 1719 (2023).

[2] Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry, “Commitments to Quantum States”, arXiv:2210.05138, (2022).

[3] Charles Yuan and Michael Carbin, “Tower: Data Structures in Quantum Superposition”, arXiv:2205.10255, (2022).

[4] Lijie Chen and Ramis Movassagh, “Making Quantum Local Verifiers Simulable with Potential Applications to Zero-Knowledge”, arXiv:2209.10798, (2022).

[5] Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin, “A Note on the Common Haar State Model”, arXiv:2404.05227, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-06-18 11:08:06). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2024-06-18 11:08:03: Could not fetch cited-by data for 10.22331/q-2024-06-18-1380 from Crossref. This is normal if the DOI was registered recently.

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.

Time Stamp:

More from Quantum Journal