Paper 2018/849

Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications

Masayuki Abe, Charanjit S. Jutla, Miyako Ohkubo, and Arnab Roy


We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. Specifically, our construction has $ O(\log Q) $ reduction to the SXDH, DLIN and matrix-DDH assumptions, where $ Q $ is the number of simulated proofs given out. The USS-QA-NIZK primitive has many applications, including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs. We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications with (almost) tight-security to standard assumptions such as SXDH and, more generally, $\D_k$-MDDH. Thus, we get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.

Note: Removed claim that our core construction is Structure-Preserving.

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2018
QA-NIZKsimulation-soundnesstight securitypublic-key encryptionCCAStructure-preserving signatures
Contact author(s)
arnabr @ gmail com
2019-02-07: last of 3 revisions
2018-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Masayuki Abe and Charanjit S.  Jutla and Miyako Ohkubo and Arnab Roy},
      title = {Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2018/849},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.