**Compact NIZKs from Standard Assumptions on Bilinear Maps**

*Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa*

**Abstract: **A non-interactive zero-knowledge (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 pairing-based NIZKs for all NP languages based on standard assumptions.
In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM'12) (GOS-NIZK) is still considered to be the state-of-the-art.
Although fairly efficient, one drawback of GOS-NIZK 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 follow-up works focusing on shortening the proof size of pairing-based NIZKs, however, thus far, all works come at the cost of relying either on a non-standard knowledge-type assumption or a non-static $q$-type assumption.
Specifically, improving the proof size of the original GOS-NIZK under the same standard assumption has remained as an open problem.

Our main result is a construction of a pairing-based 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 GOS-NIZK, our NIZK is a strict improvement on their proof size.

As by-products of our main result, we also obtain the following two results: (1) We construct a perfectly zero-knowledge 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 pairing-based NIPZK for a non-trivial 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 erasure-free 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 non-static $q$-type assumption.

The main building block for all of our NIZKs is a constrained signature scheme with decomposable online-offline 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.

**Category / Keywords: **foundations / non-interactive zero-knowledge, DLIN, attribute-based encryption, constrained signature

**Original Publication**** (with major differences): **IACR-EUROCRYPT-2020

**Date: **received 19 Feb 2020, last revised 1 Jun 2020

**Contact author: **shuichi katsumata at aist go jp,ryo nishimaki@gmail com,yamada-shota@aist go jp,takashi yamakawa ga@hco ntt co jp

**Available format(s): **PDF | BibTeX Citation

**Note: **Added remarks on NC1 decryptable SKE (6/2/2020)

**Version: **20200602:042026 (All versions of this report)

**Short URL: **ia.cr/2020/223

[ Cryptology ePrint archive ]