Paper 2020/223
Compact NIZKs from Standard Assumptions on Bilinear Maps
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa
Abstract
A noninteractive zeroknowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus of this work is on exploring short pairingbased NIZKs for all NP languages based on standard assumptions. In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM'12) (GOSNIZK) is still considered to be the stateoftheart. Although fairly efficient, one drawback of GOSNIZK is that the proof size is multiplicative in the circuit size computing the NP relation. That is, the proof size grows by $O(C\lambda)$, where $C$ is the circuit for the NP relation and $\lambda$ is the security parameter. By now, there have been numerous followup works focusing on shortening the proof size of pairingbased NIZKs, however, thus far, all works come at the cost of relying either on a nonstandard knowledgetype assumption or a nonstatic $q$type assumption. Specifically, improving the proof size of the original GOSNIZK under the same standard assumption has remained as an open problem. Our main result is a construction of a pairingbased NIZK for all of NP whose proof size is additive in $C$, that is, the proof size only grows by $C +\poly(\lambda)$, based on the decisional linear (DLIN) assumption. Since the DLIN assumption is the same assumption underlying GOSNIZK, our NIZK is a strict improvement on their proof size. As byproducts of our main result, we also obtain the following two results: (1) We construct a perfectly zeroknowledge NIZK (NIPZK) for NP relations computable in NC1 with proof size $w \cdot \poly(\lambda)$ where $w$ is the witness length based on the DLIN assumption. This is the first pairingbased NIPZK for a nontrivial class of NP languages whose proof size is independent of $C$ based on a standard assumption. (2)~We construct a universally composable (UC) NIZK for NP relations computable in NC1 in the erasurefree adaptive setting whose proof size is $w \cdot \poly(\lambda)$ from the DLIN assumption. This is an improvement over the recent result of Katsumata, Nishimaki, Yamada, and Yamakawa (CRYPTO'19), which gave a similar result based on a nonstatic $q$type assumption. The main building block for all of our NIZKs is a constrained signature scheme with decomposable onlineoffline efficiency. This is a property which we newly introduce in this paper and construct from the DLIN assumption. We believe this construction is of an independent interest.
Note: Added remarks on NC1 decryptable SKE (6/2/2020)
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2020
 Keywords
 noninteractive zeroknowledgeDLINattributebased encryptionconstrained signature
 Contact author(s)

shuichi katsumata @ aist go jp
ryo nishimaki @ gmail com
yamadashota @ aist go jp
takashi yamakawa ga @ hco ntt co jp  History
 20200602: revised
 20200221: received
 See all versions
 Short URL
 https://ia.cr/2020/223
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/223, author = {Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa}, title = {Compact {NIZKs} from Standard Assumptions on Bilinear Maps}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/223}, year = {2020}, url = {https://eprint.iacr.org/2020/223} }