Non-interactive Zero-Knowledge in Pairing-Free Groups from Weaker Assumptions
We provide new constructions of non-interactive zero-knowledge arguments (\(\textsf {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 \(\textsf {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 all efficient functions, therefore obtaining an assumption that is (in spirit) falsifiable.