Paper 2018/877

On QA-NIZK in the BPK Model

Behzad Abdolmaleki and Helger Lipmaa and Janno Siim and Michał Zając

Abstract

While the CRS model is widely accepted for construction of non-interactive zero-knowledge (NIZK) proofs, from the practical viewpoint, a very important question is to minimize the trust needed from the creators of the CRS. Recently, Bellare \emph{et al.} defined subversion-resistance (security in the case the CRS creator may be malicious) for NIZK. In particular, an S-ZK NIZK is zero knowledge even in the case of subverted CRS. We propose new definitions for S-ZK Quasi-Adaptive NIZKs (QA-NIZKs) where the CRS can depend on the language parameter. First, we observe that subversion zero knowledge (S-ZK) in the CRS model corresponds to no-auxiliary-string non-black-box NIZK (also known as nonuniform NIZK) in the Bare Public Key (BPK) model. Due to well-known impossibility results, this observation provides a simple proof that the use of non-black-box techniques is needed to obtain S-ZK. Second, we show that the language parameter $\varrho$ must be generated honestly. Importantly, this emphasizes the difference of $\varrho$ and the CRS. Third, we prove that the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee (after possibly adding some new elements to its public key) is nonuniform zero knowledge in the BPK model under a novel knowledge assumption that is secure in the subversion generic bilinear group model of Bellare et al. Hence, S-ZK can be achieved (almost) for free and is thus arguably the correct security definition for QA-NIZKs.

Note: This version is substantially updated: the main new protocol is better explained (and the case k = 2 is simplified), the security proof is different, etc.