Paper 2024/836

The Round Complexity of Proofs in the Bounded Quantum Storage Model

Alex B. Grilo, Sorbonne University, French National Centre for Scientific Research, Laboratoire de Recherche en Informatique de Paris 6
Philippe Lamontagne, National Research Council Canada, University of Montreal
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: 1. 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. 2. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Zero-knowledgequantum cryptographyround reduction
Contact author(s)
alex bredariol-grilo @ lip6 fr
philippe Lamontagne2 @ cnrc-nrc gc ca
History
2024-05-31: approved
2024-05-28: received
See all versions
Short URL
https://ia.cr/2024/836
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/836,
      author = {Alex B. Grilo and Philippe Lamontagne},
      title = {The Round Complexity of Proofs in the Bounded Quantum Storage Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/836},
      year = {2024},
      url = {https://eprint.iacr.org/2024/836}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.