**Statistical ZAPs from Group-Based Assumptions**

*Geoffroy Couteau and Shuichi Katsumata and 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 hidden-bit generator
(IHBG), which adapts the notion of hidden-bit generator to the plain model by
building upon the recent notion of statistically-hiding extractable
commitments. We provide a construction of IHBG from the explicit hardness of
the decision Diffie-Hellman assumption (where explicit refers to requiring an
explicit upper bound on the advantage of any polynomial-time adversary against
the assumption) and the existence of statistical ZAPs for a specific simple
language, building upon the recent construction of dual-mode hidden-bit
generator from (Libert et al., EUROCRYPT 2020). We provide two instantiations
of the underlying simple ZAP:
1. Using the recent statistical ZAP for the Diffie-Hellman language of
(Couteau and Hartmann, CRYPTO 2020), we obtain statistical ZAPs for NP
assuming (the explicit hardness of) DDH in $G_1$ and kernel-DH 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 key-dependent message
one-wayness 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
pairing-free groups.
Note that the latter is a search discrete-log-style falsifiable
assumption, incomparable to DDH (in particular, it is not known to imply
public-key encryption).

**Category / Keywords: **Zero knowledge, ZAP, Non-Interactive Zero-Knowledge, NIZK, Correlation-Intractability

**Date: **received 25 May 2021

**Contact author: **couteau at irif fr, shuichi katsumata000 at gmail com, sadeghi elahe99 at gmail com, bogdan ursu at inf ethz ch

**Available format(s): **PDF | BibTeX Citation

**Version: **20210528:091053 (All versions of this report)

**Short URL: **ia.cr/2021/688

[ Cryptology ePrint archive ]