Tightly-Secure Simulation-Sound Quasi-Adaptive NIZK Arguments

Abstract

Quasi-adaptive non-interactive zero-knowledge (QA-NIZK) arguments are fundamental cryptographic primitives widely used in privacy-preserving technologies such as anonymous credentials, group signatures, e-cash, and blockchain-based applications. We present the first tightly secure unbounded simulation sound quasi-adaptive non-interactive zero-knowledge argument system from simple assumptions. The construction has a security loss ofO(1), a compact common reference string, constant size proofs, and its security relies on the hardness of the well-known SXDH assumption. Our result improves state-of-the-art (Couteau and Hartmann, CRYPTO 2020) in terms of the proof size (about three times), a lower security loss, and also with respect to the underlying hardness assumptions. The tight security reduction enables shorter key-length recommendations, leading to improved concrete efficiency. Our main technical contribution is a novel proof technique inspired by the randomization technique of the Naor-Yung double-encryption paradigm and the adaptive partitioning due to Hofheinz (EUROCRYPT 2017).