Paper 2021/688
Statistical ZAPs from GroupBased Assumptions
Geoffroy Couteau, Shuichi Katsumata, Elahe Sadeghi, and Bogdan Ursu
Abstract
We put forth a template for constructing statistical ZAPs for NP. Our template compiles NIZKs for NP in the hidden bit model (which exist unconditionally) into statistical ZAPs using a new notion of interactive hiddenbit generator (IHBG), which adapts the notion of hiddenbit generator to the plain model by building upon the recent notion of statisticallyhiding extractable commitments. We provide a construction of IHBG from the explicit hardness of the decision DiffieHellman assumption (where explicit refers to requiring an explicit upper bound on the advantage of any polynomialtime adversary against the assumption) and the existence of statistical ZAPs for a specific simple language, building upon the recent construction of dualmode hiddenbit generator from (Libert et al., EUROCRYPT 2020). We provide two instantiations of the underlying simple ZAP: 1. Using the recent statistical ZAP for the DiffieHellman language of (Couteau and Hartmann, CRYPTO 2020), we obtain statistical ZAPs for NP assuming (the explicit hardness of) DDH in $G_1$ and kernelDH in $G_2$ (a search assumption which is weaker than DDH), where $(G_1,G_2)$ are groups equipped with an asymmetric pairing. This improves over the recent work of (Lombardi et al., EUROCRYPT 2020) which achieved a relaxed variant of statistical ZAP for NP, under a stronger assumption. 2. Using the recent work of (Couteau et al., EUROCRYPT 2020), we obtain statistical ZAPs for NP assuming the explicit hardness of DDH, 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^\secpar$ with probability better than $\poly(\secpar)/2^{(c + o(1)) \cdot \secpar}$, denoted $2^{c\secpar}$\OWKDM, for a constant c = 1/2, in pairingfree groups. Note that the latter is a search discretelogstyle falsifiable assumption, incomparable to DDH (in particular, it is not known to imply publickey encryption).
Metadata
 Available format(s)
 Publication info
 Preprint. Minor revision.
 Keywords
 Zero knowledgeZAPNonInteractive ZeroKnowledgeNIZKCorrelationIntractability
 Contact author(s)

couteau @ irif fr
shuichi katsumata000 @ gmail com
sadeghi elahe99 @ gmail com
bogdan ursu @ inf ethz ch  History
 20210528: received
 Short URL
 https://ia.cr/2021/688
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/688, author = {Geoffroy Couteau and Shuichi Katsumata and Elahe Sadeghi and Bogdan Ursu}, title = {Statistical ZAPs from GroupBased Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2021/688}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/688}}, url = {https://eprint.iacr.org/2021/688} }