Cryptology ePrint Archive: Report 2020/535

Non-Interactive Zero-Knowledge in Pairing-Free Groups from Weaker Assumptions

Geoffroy Couteau and Shuichi Katsumata and Bogdan Ursu

Abstract: We provide two new constructions of non-interactive zero-knowledge arguments (NIZKs) for NP from discrete-logarithm-style assumptions over cyclic groups, without relying on pairings. A previous construction from (Canetti et al., Eurocrypt'18) achieves such NIZKs under the assumption that no efficient adversary can break the key-dependent message (KDM) security of (additive) ElGamal with respect to all (even inefficient) functions over groups of size $2^\lambda$, with probability better than $\mathsf{poly}(\lambda)/2^{\lambda}$. This is an extremely strong, non-falsifiable assumption. In particular, even mild (polynomial) improvements over the current best-known attacks on the discrete logarithm problem would already contradict this assumption. (Canetti et al. STOC'19) describe how to improve the assumption to rely only on KDM security with respect to efficient functions while additionally assuming public-key encryption schemes, therefore obtaining an assumption that is (in spirit) falsifiable.

Our first construction improves this state of affairs. We provide a construction of NIZKs for NP under the CDH assumption together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size $2^\lambda$, with probability better than $\mathsf{poly}(\lambda)/2^{c\lambda}$ (denoted $2^{-c\lambda}$-OWKDM), for a constant $c = 3/4$. Unlike the previous assumption, our assumption leaves an exponential gap between the best-known attack and the required security guarantee.

Our second construction is interested in the case where CDH does not hold. Namely, as a second contribution, we construct an infinitely often NIZK argument system for NP (where soundness and zero-knowledge are only guaranteed to hold for infinitely many security parameters), under the assumption that CDH is easy together with the $2^{-c\lambda}$-OWKDM security of ElGamal with $c = 28/29+o(1)$ and the existence of low-depth pseudorandom generators (PRG).

Combining our two results, we obtain a construction of (infinitely-often) NIZKs for NP under the $2^{-c\lambda}$-OWKDM security of ElGamal with $c = 28/29+o(1)$ and the existence of low-depth PRG, independently of whether CDH holds. To our knowledge, since neither OWKDM security of ElGamal nor low-depth PRGs are known to imply public key encryption, this provides the first construction of NIZKs from concrete and falsifiable Minicrypt-style assumptions.

Category / Keywords: foundations / Non-interactive zero-knowledge arguments, pairing-free groups, KDM security

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

Date: received 7 May 2020

Contact author: geoffroy couteau at irif fr,shuichi katsumata@aist go jp,bogdan ursu@inf ethz ch

Available format(s): PDF | BibTeX Citation

Version: 20200507:204156 (All versions of this report)

Short URL: ia.cr/2020/535


[ Cryptology ePrint archive ]