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. 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.

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

Original Publication (with minor differences): IACR-ASIACRYPT-2018

Date: received 7 Sep 2018, last revised 6 Feb 2019

Contact author: arnabr at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20190207:025738 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]