Paper 2020/535
NonInteractive ZeroKnowledge in PairingFree Groups from Weaker Assumptions
Geoffroy Couteau, Shuichi Katsumata, and Bogdan Ursu
Abstract
We provide two new constructions of noninteractive zeroknowledge arguments (NIZKs) for NP from discretelogarithmstyle 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 keydependent 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, nonfalsifiable assumption. In particular, even mild (polynomial) improvements over the current bestknown 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 publickey 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 keydependent message onewayness 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 bestknown 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 zeroknowledge 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 lowdepth pseudorandom generators (PRG). Combining our two results, we obtain a construction of (infinitelyoften) NIZKs for NP under the $2^{c\lambda}$OWKDM security of ElGamal with $c = 28/29+o(1)$ and the existence of lowdepth PRG, independently of whether CDH holds. To our knowledge, since neither OWKDM security of ElGamal nor lowdepth PRGs are known to imply public key encryption, this provides the first construction of NIZKs from concrete and falsifiable Minicryptstyle assumptions.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2020
 Keywords
 Noninteractive zeroknowledge argumentspairingfree groupsKDM security
 Contact author(s)

geoffroy couteau @ irif fr
shuichi katsumata @ aist go jp
bogdan ursu @ inf ethz ch  History
 20200507: received
 Short URL
 https://ia.cr/2020/535
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/535, author = {Geoffroy Couteau and Shuichi Katsumata and Bogdan Ursu}, title = {NonInteractive ZeroKnowledge in PairingFree Groups from Weaker Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2020/535}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/535}}, url = {https://eprint.iacr.org/2020/535} }