Paper 2018/877

On QA-NIZK in the BPK Model

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

Abstract

Recently, Bellare et al. defined subversion-resistance (security in the case the CRS creator may be malicious) for NIZK. In particular, a Sub-ZK NIZK is zero-knowledge, even in the case of subverted CRS. We study Sub-ZK QA-NIZKs, where the CRS can depend on the language parameter. First, we observe that subversion zero-knowledge (Sub-ZK) in the CRS model corresponds to no-auxiliary-string non-black-box NIZK in the Bare Public Key model, and hence, the use of non-black-box techniques is needed to obtain Sub-ZK. Second, we give a precise definition of Sub-ZK QA-NIZKs that are (knowledge-)sound if the language parameter but not the CRS is subverted and zero-knowledge even if both are subverted. Third, we prove that the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee is Sub-ZK under a new knowledge assumption that by itself is secure in (a weaker version of) the algebraic group model. Depending on the parameter setting, it is (knowledge-)sound under different non-falsifiable assumptions, some of which do not belong to the family of knowledge assumptions.

Note: 14 Feb 2020: this eprint corresponds to the version accepted to PKC 2020. It is very different from the older eprint: we now achieve security also in the case the language parameter is subverted ("Sub-PAR soundness/knowledge-soundness"), we additionally prove knowledge-soundness in the case the language-parameter matrix is full-rank. We also use somewhat different assumptions: in particular, Sub-PAR (knowledge-)soundness relies on interactive non-falsifiable assumptions, that are markedly different from knowledge assumptions that are used in the case of SNARKs. 19 Feb 2019: 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.17 May 2019: This version has a bit more common terminology. Somewhat better comparison with the previous work.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in PKC 2020
Keywords
Bare public key modelno-auxiliary-string zero knowledgenon-black-box zero knowledgeQA-NIZKsubversion-security
Contact author(s)
helger lipmaa @ gmail com
History
2020-02-14: last of 3 revisions
2018-09-23: received
See all versions
Short URL
https://ia.cr/2018/877
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/877,
      author = {Behzad Abdolmaleki and Helger Lipmaa and Janno Siim and Michał Zając},
      title = {On QA-NIZK in the BPK Model},
      howpublished = {Cryptology ePrint Archive, Paper 2018/877},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/877}},
      url = {https://eprint.iacr.org/2018/877}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.