Paper 2013/109
Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces
Charanjit S. Jutla and Arnab Roy
Abstract
We define a novel notion of quasi-adaptive non-interactive zero knowledge (NIZK) proofs for probability distributions on parametrized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the language parameters. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of vector spaces over bilinear groups, we give quasi-adaptive computationally sound NIZKs that are shorter and more efficient than Groth-Sahai NIZKs. For many cryptographic applications quasi-adaptive NIZKs suffice, and our constructions can lead to significant improvements in the standard model. Our construction can be based on any k-linear assumption, and in particular under the eXternal Diffie Hellman (XDH) assumption our proofs are even competitive with Random-Oracle based Sigma-protocol NIZK proofs. We also show that our system can be extended to include integer tags in the defining equations, where the tags are provided adaptively by the adversary. This leads to applicability of our system to many applications that use tags, e.g. applications using Cramer-Shoup projective hash proofs. Our techniques also lead to the shortest known (ciphertext) fully secure identity based encryption (IBE) scheme under standard static assumptions (SXDH). Further, we also get a short publicly-verifiable CCA2-secure IBE scheme.
Note: Fixed small typo in definition of Strong QA-NIZK.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. Asiacrypt 2013
- Keywords
- NIZKGroth-Sahaibilinear pairingssignaturesdual-system IBEDLINSXDH
- Contact author(s)
- csjutla @ us ibm com
- History
- 2018-09-14: last of 7 revisions
- 2013-02-27: received
- See all versions
- Short URL
- https://ia.cr/2013/109
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/109, author = {Charanjit S. Jutla and Arnab Roy}, title = {Shorter Quasi-Adaptive {NIZK} Proofs for Linear Subspaces}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/109}, year = {2013}, url = {https://eprint.iacr.org/2013/109} }