Paper 2022/1380

Post-Quantum Zero-Knowledge with Space-Bounded Simulation

Prabhanjan Ananth, University of California, Santa Barbara
Alex B. Grilo, Laboratoire de Recherche en Informatique de Paris 6

The traditional definition of quantum zero-knowledge stipulates that the knowledge gained by any quantum polynomial-time verifier in an interactive protocol can be simulated by a quantum polynomial-time algorithm. One drawback of this definition is that it allows the simulator to consume significantly more computational resources than the verifier. We argue that this drawback renders the existing notion of quantum zero-knowledge not viable for certain settings, especially when dealing with near-term quantum devices. In this work, we initiate a fine-grained notion of post-quantum zero-knowledge that is more compatible with near-term quantum devices. We introduce the notion of $(s,f)$ space-bounded quantum zero-knowledge. In this new notion, we require that an $s$-qubit malicious verifier can be simulated by a quantum polynomial-time algorithm that uses at most $f(s)$-qubits, for some function $f(\cdot)$, and no restriction on the amount of the classical memory consumed by either the verifier or the simulator. We explore this notion and establish both positive and negative results: - For verifiers with logarithmic quantum space $s$ and (arbitrary) polynomial classical space, we show that $(s,f)$-space-bounded QZK, for $f(s)=2s$, can be achieved based on the existence of post-quantum one-way functions. Moreover, our protocol runs in constant rounds. - For verifiers with super-logarithmic quantum space $s$, assuming the existence of post-quantum secure one-way functions, we show that $(s,f)$-space-bounded QZK protocols, with fully black-box simulation (classical analogue of black-box simulation) can only be achieved for languages in BQP.

Available format(s)
Publication info
zero-knowledge post-quantum security space-bounded
Contact author(s)
prabhanjan @ cs ucsb edu
alex bredariol-grilo @ lip6 fr
2022-10-14: approved
2022-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Alex B. Grilo},
      title = {Post-Quantum Zero-Knowledge with Space-Bounded Simulation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1380},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.