The Round Complexity of Proofs in the Bounded Quantum Storage Model

Alex B. Grilo; Philippe Lamontagne

doi:10.62056/a6n56c0kr

The Round Complexity of Proofs in the Bounded Quantum Storage Model

Authors

Alex B. Grilo, Philippe Lamontagne

Alex B. Grilo

Sorbonne Université, CNRS, LIP6, France

Philippe Lamontagne

National Research Council Canada, Canada
Université de Montréal, Canada
Philippe dot Lamontagne2 at cnrc-nrc dot gc dot ca

Abstract

The round complexity of interactive proof systems is a key question of practical and theoretical relevance in complexity theory and cryptography. Moreover, results such as QIP = QIP(3) (STOC'00) show that quantum resources significantly help in such a task.

In this work, we initiate the study of round compression of protocols in the bounded quantum storage model (BQSM). In this model, the malicious parties have a bounded quantum memory and they cannot store the all the qubits that are transmitted in the protocol.

Our main results in this setting are the following:

There is a non-interactive (statistical) witness indistinguishable proof for any language in NP (and even QMA) in BQSM in the plain model. We notice that in this protocol, only the memory of the verifier is bounded.
Any classical proof system can be compressed in a two-message quantum proof system in BQSM. Moreover, if the original proof system is zero-knowledge, the quantum protocol is zero-knowledge too. In this result, we assume that the prover has bounded memory.

Finally, we give evidence towards the “tightness” of our results. First, we show that NIZK in the plain model against BQS adversaries is unlikely with standard techniques. Second, we prove that without the BQS model there is no 2–message zero-knowledge quantum interactive proof, even under computational assumptions.

References

[ABF⁺16]

Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, and Michael St. Jules. Computational Security of Quantum Encryption. In Anderson C.A. Nascimento and Paulo Barreto, editors, Information Theoretic Security, pages 47–71. 2016. Springer International Publishing. DOI: 10.1007/978-3-319-49175-2_3

Google Scholar ePrint

[AG22]

Prabhanjan Ananth and Alex B. Grilo. Post-Quantum Zero-Knowledge with Space-Bounded Simulation. 2022.

Google Scholar ePrint

[BDG⁺13]

Nir Bitansky, Dana Dachman-Soled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana López-Alt, and Daniel Wichs. Why "Fiat-Shamir for Proofs" Lacks a Proof. In Amit Sahai, editor, Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 182–201. 2013. Springer. DOI: 10.1007/978-3-642-36594-2_11

Google Scholar ePrint

[BFGS13]

Niek J. Bouman, Serge Fehr, Carlos González-Guillén, and Christian Schaffner. An All-But-One Entropic Uncertainty Relation, and Application to Password-Based Identification. In Kazuo Iwama, Yasuhito Kawano, and Mio Murao, editors, Theory of Quantum Computation, Communication, and Cryptography, pages 29–44. 2013. Springer. DOI: 10.1007/978-3-642-35656-8_3

Google Scholar ePrint

[BFM88]

Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-knowledge and Its Applications. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 103–112. 1988. ACM. DOI: 10.1145/62212.62222

Google Scholar ePrint

[BG22]

Anne Broadbent and Alex Bredariol Grilo. QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge. SIAM Journal on Computing, 51(4):1400-1450, 2022. DOI: 10.1137/21M140729X

Google Scholar ePrint

[BKS23]

James Bartusek, Dakshita Khurana, and Akshayaram Srinivasan. Secure Computation with Shared EPR Pairs. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, pages 224–257. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-38554-4_8

Google Scholar ePrint

[BM90]

Mihir Bellare and Silvio Micali. Non-Interactive Oblivious Transfer and Applications. In Gilles Brassard, editor, Advances in Cryptology — CRYPTO’ 89 Proceedings, pages 547–557. 1990. Springer. DOI: 10.1007/0-387-34805-0_48

Google Scholar ePrint

[BOV03]

Boaz Barak, Shien Jin Ong, and Salil Vadhan. Derandomization in Cryptography. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, pages 299–315. 2003. Springer. DOI: 10.1007/978-3-540-45146-4_18

Google Scholar ePrint

[BP15]

Nir Bitansky and Omer Paneth. ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography, pages 401–427. 2015. Springer. DOI: 10.1007/978-3-662-46497-7_16

Google Scholar ePrint

[BS06]

Mohammed Barhoush and Louis Salvail. Powerful Primitives in the Bounded Quantum Storage Model. 2023-06-06.

Google Scholar ePrint

[CVZ20]

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, pages 799–828. 2020. Springer International Publishing. DOI: 10.1007/978-3-030-56877-1_28

Google Scholar ePrint

[DFLS16]

Frédéric Dupuis, Serge Fehr, Philippe Lamontagne, and Louis Salvail. Adaptive Versus Non-Adaptive Strategies in the Quantum Setting with Applications. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, pages 33–59. 2016. Springer. DOI: 10.1007/978-3-662-53015-3_2

Google Scholar ePrint

[DFR⁺07]

Ivan B. Damgård, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner. A Tight High-Order Entropic Quantum Uncertainty Relation with Applications. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007, pages 360–378. 2007. Springer. DOI: 10.1007/978-3-540-74143-5_20

Google Scholar ePrint

[DFSS07]

Ivan B. DamgÅrd, Serge Fehr, Louis Salvail, and Christian Schaffner. Secure Identification and QKD in the Bounded-Quantum-Storage Model. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings, pages 342–359. 2007. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-74143-5_19

Google Scholar ePrint

[DFSS08]

Ivan B. DamgÅrd, Serge Fehr, Louis Salvail, and Christian Schaffner. Cryptography in the Bounded-Quantum-Storage Model. SIAM Journal on Computing, 37(6):1865-1890, 2008. DOI: 10.1137/060651343

Google Scholar ePrint

[DFW02]

Frédéric Dupuis, Omar Fawzi, and Stephanie Wehner. Entanglement Sampling and Applications. IEEE Transactions on Information Theory, 61(2):1093–1112, 2015-02. Conference Name: IEEE Transactions on Information Theory DOI: 10.1109/TIT.2014.2371464

Google Scholar ePrint

[DLS12]

Frédéric Dupuis, Philippe Lamontagne, and Louis Salvail. Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared Entanglement. 2022-09-12.

Google Scholar ePrint

[FS09]

Serge Fehr and Christian Schaffner. Composing Quantum Protocols in a Classical Environment. In Omer Reingold, editor, Theory of Cryptography, pages 350–367. 2009. Springer. DOI: 10.1007/978-3-642-00457-5_21

Google Scholar ePrint

[FS87]

Amos Fiat and Adi Shamir. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, Advances in Cryptology — CRYPTO' 86, pages 186–194. 1987. Springer Berlin Heidelberg.

Google Scholar ePrint

[FS90a]

U. Feige and A. Shamir. Witness indistinguishable and witness hiding protocols. In Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90, pages 416–426. 1990. ACM Press. DOI: 10.1145/100216.100272

Google Scholar ePrint

[FS90b]

U. Feige and A. Shamir. Zero Knowledge Proofs of Knowledge in Two Rounds. In Gilles Brassard, editor, Advances in Cryptology — CRYPTO’ 89 Proceedings, pages 526–544. 1990. Springer. DOI: 10.1007/0-387-34805-0_46

Google Scholar ePrint

[GK03]

Shafi Goldwasser and Yael Tauman Kalai. On the (In)security of the Fiat-Shamir Paradigm. In 44th Symposium on Foundations of Computer Science *FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 102–113. 2003. IEEE Computer Society. DOI: 10.1109/SFCS.2003.1238185

Google Scholar ePrint

[GK96]

given-i=Oded family=Goldreich given=Oded. and given-i=Hugo family=Krawczyk given=Hugo.. On the Composition of Zero-Knowledge Proof Systems. SIAM Journal on Computing, 25(1):169–192, 1996. DOI: 10.1137/S0097539791220688

Google Scholar ePrint

[GKR15]

Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating Computation: Interactive Proofs for Muggles. J. ACM, 62(4):27:1–27:64, 2015. DOI: 10.1145/2699436

Google Scholar ePrint

[GMW86]

Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 174-187. 1986. DOI: 10.1109/SFCS.1986.47

Google Scholar ePrint

[GO01]

Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1–32, 1994-12-01. DOI: 10.1007/BF00195207

Google Scholar ePrint

[GOS06]

Jens Groth, Rafail Ostrovsky, and Amit Sahai. Non-Interactive Zaps and New Techniques for NIZK. In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, pages 97–111. 2006. Springer. DOI: 10.1007/11818175_6

Google Scholar ePrint

[KMO90]

Joe Kilian, Silvio Micali, and Rafail Ostrovsky. Minimum Resource Zero-Knowledge Proofs. In Gilles Brassard, editor, Advances in Cryptology — CRYPTO’ 89 Proceedings, pages 545–546. 1990. Springer. DOI: 10.1007/0-387-34805-0_47

Google Scholar ePrint

[KW00]

Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 608–617. 2000. DOI: 10.1145/335305.335387

Google Scholar ePrint

[KWW03]

R. Konig, S. Wehner, and J. Wullschleger. Unconditional Security From Noisy Quantum Storage. IEEE Transactions on Information Theory, 58(3):1962–1984, 2012-03. Conference Name: IEEE Transactions on Information Theory DOI: 10.1109/TIT.2011.2177772

Google Scholar ePrint

[LC01]

Hoi-Kwong Lo and H. F. Chau. Why quantum bit commitment and ideal quantum coin tossing are impossible. Physica D: Nonlinear Phenomena, 120(1):177–187, 1998-09-01. DOI: 10.1016/S0167-2789(98)00053-0

Google Scholar ePrint

[LFKN92]

Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. J. ACM, 39(4):859–868, 1992. DOI: 10.1145/146585.146605

Google Scholar ePrint

[May28]

Dominic Mayers. Unconditionally Secure Quantum Bit Commitment is Impossible. Physical Review Letters, 78(17):3414–3417, 1997-04-28. Publisher: American Physical Society DOI: 10.1103/PhysRevLett.78.3414

Google Scholar ePrint

[MY22]

Tomoyuki Morimae and Takashi Yamakawa. Classically Verifiable NIZK for QMA with Preprocessing. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV, volume 13794 of Lecture Notes in Computer Science, pages 599–627. 2022. Springer. DOI: 10.1007/978-3-031-22972-5_21

Google Scholar ePrint

[PS19]

Chris Peikert and Sina Shiehian. Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I, volume 11692, pages 89–114. 2019. Springer. DOI: 10.1007/978-3-030-26948-7_4

Google Scholar ePrint

[RRR21]

Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-Round Interactive Proofs for Delegating Computation. SIAM J. Comput., 50(3), 2021. DOI: 10.1137/16M1096773

Google Scholar ePrint

[Sha92]

Adi Shamir. IP = PSPACE. J. ACM, 39(4), 1992. DOI: 10.1145/146585.146609

Google Scholar ePrint

[Shm21]

Omri Shmueli. Multi-Theorem Designated-Verifier NIZK for QMA. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 375–405. 2021. Springer International Publishing. DOI: 10.1007/978-3-030-84242-0_14

Google Scholar ePrint

[STW09]

Christian Schaffner, Barbara M. Terhal, and Stephanie Wehner. Robust cryptography in the noisy-quantum-storage model. Quantum Information & Computation, 9(11):963–996, 2009.

Google Scholar ePrint

[Unr11]

Dominique Unruh. Concurrent Composition in the Bounded Quantum Storage Model. In Kenneth G. Paterson, editor, Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, pages 467–486. 2011. Springer. DOI: 10.1007/978-3-642-20465-4_26

Google Scholar ePrint

[Wat01]

John Watrous. Zero-Knowledge against Quantum Attacks. SIAM Journal on Computing, 39(1):25–58, 2009-01-01. Publisher: Society for Industrial and Applied Mathematics DOI: 10.1137/060670997

Google Scholar ePrint

[WST05]

Stephanie Wehner, Christian Schaffner, and Barbara M. Terhal. Cryptography from Noisy Storage. Physical Review Letters, 100(22):220502, 2008-06-05. Publisher: American Physical Society DOI: 10.1103/PhysRevLett.100.220502

Google Scholar ePrint

[WW08]

Stephanie Wehner and Jürg Wullschleger. Composable Security in the Bounded-Quantum-Storage Model. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, pages 604–615. 2008. Springer. DOI: 10.1007/978-3-540-70583-3_49

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a6n56c0kr

History

Submitted: 2024-10-07
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Alex B. Grilo and Philippe Lamontagne, The Round Complexity of Proofs in the Bounded Quantum Storage Model. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a6n56c0kr.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/a6n56c0kr,
         author={Alex B. Grilo and Philippe Lamontagne},
         title={The Round Complexity of Proofs in the Bounded Quantum Storage Model},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/a6n56c0kr},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Alex B. Grilo
AU  - Philippe Lamontagne
PY  - 2025
TI  - The Round Complexity of Proofs in the Bounded Quantum Storage Model
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/a6n56c0kr
UR  - https://doi.org/10.62056/a6n56c0kr
AB  - <p>  The round complexity of interactive proof systems is a key question   of practical and theoretical relevance in complexity theory and   cryptography. Moreover, results such as QIP = QIP(3) (STOC'00) show   that quantum resources significantly help in such a task.</p><p>  In this work, we initiate the study of round compression of   protocols in the bounded quantum storage model (BQSM). In this   model, the malicious parties have a bounded quantum memory and they   cannot store the all the qubits that are transmitted in the   protocol.</p><p>  Our main results in this setting are the following:   </p><ol>   <li>There is a non-interactive (statistical) witness indistinguishable     proof for any language in NP (and even QMA) in BQSM in the plain model. We notice that in this     protocol, only the memory of the verifier is bounded.   </li><li>Any classical proof system can be compressed in a two-message     quantum proof system in BQSM. Moreover, if the original proof system is     zero-knowledge, the quantum protocol is zero-knowledge too. In this result,     we assume that the prover has bounded memory.   </li></ol><p>   Finally, we give evidence towards the “tightness” of our results.   First, we show that NIZK in the plain model against BQS adversaries   is unlikely with standard techniques. Second, we prove that without   the BQS model there is no 2–message zero-knowledge quantum   interactive proof, even under computational assumptions. </p>
ER  -

Alex B. Grilo and Philippe Lamontagne, The Round Complexity of Proofs in the Bounded Quantum Storage Model. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a6n56c0kr.