International Association
for Cryptologic Research

Behzad Abdolmaleki , University of Sheffield

Céline Chevalier , CRED, Université Panthéon-Assas, Paris II, DIENS, École normale supérieure, PSL University, CNRS, INRIA

Ehsan Ebrahimi , University of Luxembourg

Giulio Malavolta , Bocconi University, Max-Planck Institute in Security and Privacy

Quoc-Huy Vu , Léonard de Vinci Pôle Universitaire, Research Center

DOI: 10.62056/a66ce0iuc

URL: https://cic.iacr.org/p/1/4/18

Search ePrint

Search Google

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 Sahai’s construction for SS-NIZK (in the CRS model) 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.