Paper 2019/255
Designated Verifier/Prover and Preprocessing NIZKs from DiffieHellman Assumptions
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa
Abstract
In a noninteractive zeroknowledge (NIZK) proof, a prover can noninteractively convince a verifier of a statement without revealing any additional information. Thus far, numerous constructions of NIZKs have been provided in the common reference string (CRS) model (CRSNIZK) from various assumptions, however, it still remains a long standing open problem to construct them from tools such as pairingfree groups or lattices. Recently, Kim and Wu (CRYPTO'18) made great progress regarding this problem and constructed the first latticebased NIZK in a relaxed model called NIZKs in the preprocessing model (PPNIZKs). In this model, there is a trusted statementindependent preprocessing phase where secret information are generated for the prover and verifier. Depending on whether those secret information can be made public, PPNIZK captures CRSNIZK, designatedverifier NIZK (DVNIZK), and designatedprover NIZK (DPNIZK) as special cases. It was left as an open problem by Kim and Wu whether we can construct such NIZKs from weak paringfree group assumptions such as DDH. As a further matter, all constructions of NIZKs from DiffieHellman (DH) type assumptions (regardless of whether it is over a paringfree or paring group) require the proof size to have a multiplicativeoverhead $C \cdot \mathsf{poly}(\kappa)$, where $C$ is the size of the circuit that computes the $\mathbf{NP}$ relation. In this work, we make progress of constructing (DV, DP, PP)NIZKs with varying flavors from DHtype assumptions. Our results are summarized as follows: 1. DVNIZKs for $\mathbf{NP}$ from the CDH assumption over pairingfree groups. This is the first construction of such NIZKs on pairingfree groups and resolves the open problem posed by Kim and Wu (CRYPTO'18). 2. DPNIZKs for $\mathbf{NP}$ with short proof size from a DHtype assumption over pairing groups. Here, the proof size has an additiveoverhead $C+\mathsf{poly}(\kappa)$ rather then an multiplicativeoverhead $C \cdot \mathsf{poly}(\kappa)$. This is the first construction of such NIZKs (including CRSNIZKs) that does not rely on the LWE assumption, fullyhomomorphic encryption, indistinguishability obfuscation, or nonfalsifiable assumptions. 3. PPNIZK for $\mathbf{NP}$ with short proof size from the DDH assumption over pairingfree groups. This is the first PPNIZK that achieves a short proof size from a weak and static DHtype assumption such as DDH. Similarly to the above DPNIZK, the proof size is $C+\mathsf{poly}(\kappa)$. This too serves as a solution to the open problem posed by Kim and Wu (CRYPTO'18). Along the way, we construct two new homomorphic authentication (HomAuth) schemes which may be of independent interest.
Note: Added remarks on NC1 decryptable SKE (6/2/2020). Corrected an error in the proof of nonadaptive zeroknowledge in Appendix A (7/9/2019).
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2019
 Keywords
 Noninteractive zeroknowledge proofsDiffieHellman assumptionsHomomorphic signatures
 Contact author(s)

shuichi katsumata @ aist go jp
yamadashota @ aist go jp
takashi yamakawa ga @ hco ntt co jp
ryo nishimaki zk @ hco ntt co jp  History
 20200602: last of 3 revisions
 20190228: received
 See all versions
 Short URL
 https://ia.cr/2019/255
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/255, author = {Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa}, title = {Designated Verifier/Prover and Preprocessing NIZKs from DiffieHellman Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2019/255}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/255}}, url = {https://eprint.iacr.org/2019/255} }