Paper 2018/849
Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications
Masayuki Abe and Charanjit S. Jutla and Miyako Ohkubo and Arnab Roy
Abstract
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. In particular, under the SXDH assumption, the USS-QA-NIZK proof size is only seventeen group elements with a factor $O(\log{Q})$ loss in security reduction to SXDH. 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, $\mathcal 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.
Metadata
- Available format(s)
- Publication info
- Published by the IACR in ASIACRYPT 2018
- Keywords
- QA-NIZKsimulation-soundnesstight securitypublic-key encryptionCCAStructure-preserving signatures
- Contact author(s)
-
abe masayuki @ lab ntt co jp
csjutla @ us ibm com
m ohkubo @ nict go jp
arnabr @ gmail com - History
- 2019-02-07: last of 3 revisions
- 2018-09-14: received
- See all versions
- Short URL
- https://ia.cr/2018/849
- License
-
CC BY