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

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.