International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Masayuki Abe
Charanjit S. Jutla
Miyako Ohkubo
Arnab Roy
DOI: 10.1007/978-3-030-03326-2_21
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2018
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.
  title={Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications},
  booktitle={Advances in Cryptology – ASIACRYPT 2018},
  series={Lecture Notes in Computer Science},
  author={Masayuki Abe and Charanjit S. Jutla and Miyako Ohkubo and Arnab Roy},