Cryptology ePrint Archive: Report 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.

Category / Keywords: QA-NIZK, simulation-soundness, tight security, public-key encryption, CCA, Structure-preserving signatures

Original Publication (in the same form): IACR-ASIACRYPT-2018

Date: received 7 Sep 2018, last revised 7 Sep 2018

Contact author: abe masayuki at lab ntt co jp, csjutla@us ibm com, m ohkubo@nict go jp, arnabr@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180914:153726 (All versions of this report)

Short URL: ia.cr/2018/849


[ Cryptology ePrint archive ]