Paper 2023/1702

On Quantum Simulation-Soundness

Behzad Abdolmaleki, University of Sheffield, Sheffield, UK
Céline Chevalier, Université Panthéon-Assas, Paris II, France, École normale supérieure, PSL University, CNRS, INRIA, Paris, France
Ehsan Ebrahimi, University of Luxembourg, Esch-Sur-Alzette, Luxembourg
Giulio Malavolta, Bocconi University, Milan, Italy, Max-Planck Institute in Security and Privacy, Bochum, Germany
Quoc-Huy Vu, Léonard de Vinci Pôle Universitaire, Research Center, 92 916 Paris La Défense, France

Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition. We show a separation between post-quantum and quantum security of SS-NIZK, and prove that both Sahai’s construction for SS-NIZK (in the CRS model) and the Fiat-Shamir transformation (in the QROM) can be made quantumly-simulation-sound. As an immediate application of our new notion, we prove the security of the Naor-Yung paradigm in the quantum settings, with respect to a strong quantum IND-CCA security notion. This provides the quantum analogue of the classical dual key approach to prove the security of encryption schemes. Along the way, we introduce a new notion of quantum-query advantage functions, which may be used as a general framework to show classical/quantum separation for other cryptographic primitives, and it may be of independent interest.

Available format(s)
Publication info
Non-Interactive Zero-KnowledgeSimulation-SoundnessQuantum Security
Contact author(s)
abdolmaleki behzad @ yahoo com
celine chevalier @ ens fr
eebrahimi pqc @ gmail com
giulio malavolta @ hotmail it
quoc huy vu @ ens fr
2023-11-03: approved
2023-11-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Behzad Abdolmaleki and Céline Chevalier and Ehsan Ebrahimi and Giulio Malavolta and Quoc-Huy Vu},
      title = {On Quantum Simulation-Soundness},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1702},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.