International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Geoffroy Couteau , CNRS, IRIF, Université Paris-Diderot, France
Shuichi Katsumata , AIST, Japan
Bogdan Ursu , ETH Zurich, Switzerland
Download:
DOI: 10.1007/978-3-030-45727-3_15 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: We provide 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 $\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. 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 $\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. We also analyse whether we could build NIZKs when CDH does not hold. 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 $2^{-c\lambda}$-OWKDM security of ElGamal with $c = 28/29+o(1)$, together with the existence of low-depth pseudorandom generators.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30250,
  title={Non-Interactive Zero-Knowledge in Pairing-Free Groups from Weaker Assumptions},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Non-interactive zero-knowledge arguments;pairing-free group;KDM security},
  volume={12105},
  doi={10.1007/978-3-030-45727-3_15},
  author={Geoffroy Couteau and Shuichi Katsumata and Bogdan Ursu},
  year=2020
}