Geoffroy Couteau
email: geoffroy.couteau@ens.fr

Shuichi Katsumata
email: shuichi.katsumata@aist.go.jp

Elahe Sadeghi
email: e.sadeghi95@student.sharif.edu

Bogdan Ursu
email: bogdan.ursu@inf.ethz.ch

Statistical ZAPs from Group-Based Assumptions

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: -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 G1 and kernel-DH in G2 (a search assumption which is weaker than DDH), where (G1, G2) 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. -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 λ with probability better than poly(λ)/2 (c+o(1))•λ , denoted 2 -cλ -OW-KDM, 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).

Introduction

Zero-knowledge proof systems, introduced in [START_REF] Goldwasser | The knowledge complexity of interactive proof systems[END_REF], are a fundamental cryptographic primitive, allowing a prover to convince a verifier of the veracity of a statement, while not divulging anything beyond whether the statement is true. Zero-knowledge proofs have countless applications. However, they suffer from strong lower bounds on the number of rounds of interactions required in their execution: they require at least three rounds of interactions [START_REF] Goldreich | Definitions and properties of zero-knowledge proof systems[END_REF]. Therefore, the dream result of proofs that consists of a single message from the prover to the verifier (NIZKs [4]) can only be achieved when assuming a trusted setup. Due to the importance of round-efficient zero-knowledge proofs, a large effort has been devoted to the construction of such proofs; yet, this trusted setup is often undesirable.

Witness-indistinguishability (WI) [18] is a natural relaxation of zero-knowledge, and is one of the most widely used privacy notions in proof systems. It provides the following guarantee: if there exist two witnesses (w 0 , w 1 ) for a statement x ∈ L , the verifier should not be able to distinguish an honest prover using w 0 from an honest prover using w 1 . Witness-indistinguishable proofs can replace zero-knowledge proofs in many of their applications. At the same time, their round complexity is not subject to any known lower bounds.

ZAPs. The work of Dwork and Naor [13] introduced (and constructed) ZAPs, which are two-message public-coin WI proof systems. These proof systems have several advantages: being public-coin, they are publicly verifiable (the validity of the proof can be verified solely by looking at the transcript). Furthermore, the first flow, which is just a uniformly random string, is inherently reusable for an arbitrary (polynomial) number of proofs on possibly different statements. ZAPs have proven to be important cryptographic primitives. By now, we have constructions of ZAPs from many standard assumptions, including trapdoor permutations (which is implied by factoring) [13], the decision linear assumption (DLIN) in bilinear maps [23], the (quasi-polynomial hardness of the) learning with error assumption [1,[START_REF] Goyal | Statistical zaps and new oblivious transfer protocols[END_REF][START_REF] Lombardi | 2-message publicly verifiable WI from (subexponential) LWE[END_REF], and also from more complex notions, such as indistinguishability obfuscation [3].

Statistical ZAP arguments. ZAPs were initially defined to satisfy unbounded soundness, and computational WI [13]. Statistical ZAP arguments provide the converse properties: computational soundness, and witness-indistinguishability against unbounded attackers. Unlike their computational WI counterpart, statistical ZAP arguments enjoy a very appealing property, that of everlasting security. Namely, soundness is an online security notion: as long as the prover cannot break soundness at the time where it produces the proof, security is guaranteed, even if the assumption it is based upon is later broken. On the other hand, WI and zero-knowledge should hold not only during the proof generation, but must continuously keep on holding in the future: compromising the assumptions underlying the WI property of proofs generated in the past at any point in the future would be sufficient to break privacy. Hence, targeting statistical privacy avoids being forced to assume the nonexistence of unforeseen cryptanalytic advances in the future.

Intriguingly, statistical ZAPs have proven much harder to construct than their computationally WI counterparts. In fact, for almost two decades after their introduction and until very recently, no construction of statistical ZAP argument was known, under any assumption. The situation changed very recently, with the construction of statistical ZAP arguments under the quasi-polynomial hardness of LWE, in two concurrent and independent works [1,[START_REF] Goyal | Statistical zaps and new oblivious transfer protocols[END_REF]. Still, these results leave open the question of whether statistical ZAPs can be based on any of the other cryptographic assumptions that computational ZAPs can be based on, such as factoring or pairing-based assumptions.

The very recent work of [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] comes very close to improving this state of affairs: they construct, from the quasi-polynomial hardness of the decision linear assumption in bilinear groups, ZAPs with private randomness. This primitive is essentially as versatile as a standard ZAP: while the verifier uses private coins, the proof remains publicly verifiable, and the first flow remains reusable. Yet, it still falls short of constructing true statistical ZAPs from pairing-based assumptions.

Our Result

In this work, we develop a new approach for constructing statistical ZAPs. At a high-level, our approach works by bootstrapping statistical ZAPs for simple languages to statistical ZAPs for NP, using a new primitive called interactive hidden-bits generator (IHBG), a plain-model variant of hiddenbits generators, which have been recently introduced in [9,[START_REF] Katsumata | Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions[END_REF][START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF][START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] for constructing NIZKs for NP from different assumptions. We provide two instantiations of our framework (in groups with or without pairings in the publicly verifiable setting), and obtain:

-Statistical ZAPs in pairing groups. A statistical ZAP argument for NP, assuming the explicit hardness 5 of the DDH assumption in G 1 and of the kernel Diffie-Hellman assumption in G 2 , where (G 1 , G 2 ) are groups equipped with an asymmetric pairing. The kernel Diffie-Hellman assumption is a standard search assumption in bilinear groups [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF][START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF], which is implied by (and is qualitatively weaker than) the DDH assumption. This improves over [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF], both in terms of assumption (we rely on a qualitatively weaker assumption, since [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] requires DDH both in G 1 and G 2 ) and of the primitive constructed (we achieve a true statistical ZAP argument, while [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] achieves a relaxed variant). -Statistical ZAPs in pairing-free groups. A statistical ZAP argument from NP, assuming explicit hardness of the DDH assumption in a pairing-free group G with log |G| ≈ λ 1/2 , and the assumption that no polynomial-time adversary can break the OW-KDM security of ElGamal with respect to efficient functions with success probability significantly better than 2 -λ/2 , denoted as 2 -λ/2 -OW-KDM security. Note that the best-known attack against such OW-KDM security of ElGamal succeeds with probability poly(λ) • 2 -λ . While non-standard, this is a falsifiable search assumption, and there is an exponential gap between the required security margin and the best known attack. Under the same KDM assumption, but assuming only the standard polynomial hardness of DDH, we also obtain statistical NIZKs (NISZKs) for NP in the common reference string (CRS) model (settling for computational NIZKs, we can further relax DDH to computational Diffie-Hellman). This builds upon and improves over the recent work of [10] which constructed computational NIZK arguments in the CRS model, under CDH and a stronger assumption: the 2 -3λ/4 -OW-KDM-hardness of ElGamal.

In all the above, the (decisional or kernel) Diffie-Hellman assumption can be replaced by any of its standard generalizations, namely the decisional k-Lin [START_REF] Hofheinz | Secure hybrid encryption from weakened key encapsulation[END_REF] and kernel k-Lin assumptions, or even more generally any assumption from the family of the (decisional or kernel) matrix Diffie-Hellman assumptions [15,[START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF].

Relation to [START_REF] Jain | Non-interactive zero knowledge from sub-exponential ddh[END_REF]. In a breakthrough work (very recently accepted at Eurocrypt '21), Jain and Zhengzhong have solved the long-standing open problem of basing NIZKs on a well-studied assumption in pairing-free groups (the subexponential hardness of DDH). Furthermore, their work also achieves a statistical ZAP under the same assumption. We clarify the relation of our work to theirs.

The results presented in our work have been obtained concurrently and independently of those presented in [START_REF] Jain | Non-interactive zero knowledge from sub-exponential ddh[END_REF]. However, we were made aware of the existence and content of [START_REF] Jain | Non-interactive zero knowledge from sub-exponential ddh[END_REF] while it was submitted to Eurocrypt (through private communication), and before we had completed the write-up of our paper. The techniques developed in our work are unrelated to those in [START_REF] Jain | Non-interactive zero knowledge from sub-exponential ddh[END_REF], and our results are complementary:

-We show that explicit hardness of DDH (or superpolynomial hardness of DDH, for any arbitrarily small superpolynomial function) gives statistical ZAPs in the pairing setting, and two-round statistical WI arguments in the pairing-free setting. In contrast, [START_REF] Jain | Non-interactive zero knowledge from sub-exponential ddh[END_REF] relies on the subexponential hardness of DDH (but does not need pairings to achieve public verifiability). -In the pairing-free setting, we also rely on an exponential search discrete-log-style hardness assumption, which is incomparable to subexponential DDH (albeit the latter is of course more standard).

In particular, our assumption is falsifiable, holds in the generic group model, and is not known to imply public-key encryption.

Still, although our results have been achieved concurrently and independently of theirs, we cannot (and do not) claim to achieve the first construction of a statistical ZAP from standard group-based assumptions, since their construction precedes ours.

Our Techniques

At the heart of our results is a construction of a new cryptographic primitive, which we call an interactive hidden-bits generator (IHBG). At a high level, an IHBG adapts the notion of hidden-bits generator (defined in the CRS model) recently introduced and studied in [9,[START_REF] Katsumata | Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions[END_REF][START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF][START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] to the plain model.

Dual-Mode Hidden-Bits Generators. More precisely, our starting point is the notion of a dualmode hidden-bits generator (HBG) from [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF]. In a dual-mode HBG, there are three algorithms: a CRS generation algorithm, a hidden-bits generator GenBits, and a verification algorithm VerifyBit. Given a CRS, the prover can, using GenBits, produce a short commitment c to a long, pseudorandom hidden-bit string ρ, as well as openings π i to all the bits ρ i of ρ. Then, VerifyBit takes as input the CRS, a short commitment, a position i, a value ρ i , and an opening certificate π i , and returns 0 or 1 depending on whether the opening is accepted. A dual-mode HBG must satisfy three properties:

-(Mode indistinguishability) the CRS can be generated in one of two modes, the hiding and the binding modes, which are computationally indistinguishable. -(Hiding) when the CRS is in hiding mode, the value ρ i at all non-opened positions i is statistically hidden, even given c and openings (ρ j , π j ) at all other positions.

-(Extractable) when the CRS is in binding mode, there exists an efficient extractor which can extract from c a string ρ such that no efficient prover can produce accepting openings for 1 -ρ i , for any position i.

As shown in [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF], and following related transformations in [9,[START_REF] Katsumata | Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions[END_REF][START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF], a dual-mode HBG can be used to convert a NIZK for NP in the hidden-bits model (which exists unconditionally) into a dualmode NIZK for NP in the CRS model (with statistical zero-knowledge when the HBG is used in hiding mode, and statistical soundness otherwise). These compilation techniques have their roots in the seminal works of Feige, Lapidot, and Shamir [16] and of Dwork and Naor [13].

Interactive Hidden-Bits Generators. The statistical NIZKs by Libert et al. [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF] crucially rely on the dual-mode feature of the HBG: the statistical binding property appears unavoidable to compile a NIZK in the hidden-bits model. Hence, obtaining statistical zero-knowledge is done by generating the CRS in hiding mode, but switching it to the binding mode when analyzing soundness. Of course, this standard technique is limited to the CRS model.

In an exciting recent work [START_REF] Kalai | Statistical witness indistinguishability (and more) in two messages[END_REF], Kalai, Khurana, and Sahai, building upon previous results and ideas from [2,[START_REF] Jain | Distinguisher-dependent simulation in two rounds and its applications[END_REF][START_REF] Khurana | How to achieve non-malleability in one or two rounds[END_REF], introduced an elegant and clever approach to partially emulate this "dual-mode feature" of the CRS model, but in the plain model. At a high level, they rely on statistically-hiding commitment schemes, which have the property that with some (negligible but not too small ) probability, they will become binding and extractable; furthermore, this event cannot be detected by the committer. This in turn allows to obtain statistical privacy (e.g. statistical witness indistinguishability), while allowing to use the extractability properties to show soundness, at the cost of having to rely on assumptions which rule out even inverse-superpolynomial distinguishing advantages. This approach proved fruitful and led to a successful line of work [1,[START_REF] Goyal | Statistical zaps and new oblivious transfer protocols[END_REF][START_REF] Lombardi | 2-message publicly verifiable WI from (subexponential) LWE[END_REF] on building statistical ZAPs in the plain model.

Intuitively, our notion of interactive hidden-bits generator simply adapts this technique to the notion of dual-mode hidden-bits generator. That is, an IHBG is a pair (GenBits, VerifyBit), similar to a dual-mode HBG, with the following core differences:

-GenBits takes as input a uniformly random string, which will correspond to the verifier message in the ZAP. -The non-opened values remain statistically hidden with overwhelming probability over the coins of VerifyBit, for any (possibly malicious) choice of the random string. -There exists a simulator which can produce simulated random coins (indistinguishable from true random coins) such that for any (possibly malicious) prover, with some not-too-small probability µ (e.g. inverse-superpolynomial) over the coins of the simulator, the hidden bit string ρ can be extracted from c.

Defining IHBG and Statistical ZAPs for NP. The above is of course very informal. Formally defining an interactive hidden-bits generator requires some care. In particular, we observe that the definition of extractability for statistically hiding extractable commitments in [1,[START_REF] Goyal | Statistical zaps and new oblivious transfer protocols[END_REF][START_REF] Lombardi | 2-message publicly verifiable WI from (subexponential) LWE[END_REF] do not suffice in our setting. At a high level, this is because these definition roughly say the following: the event that the commitments become extractable happens with probability µ, and whenever this event happens, the extracted value are guaranteed to be correct. However, this will not hold in our setting: given a tuple (c, {i, π i } i ) of a commitment and set of openings from a possibly malicious prover, the hidden-bit string ρ recovered by the extractor is correct if VerifyBit(c, i, 1 -ρ i , π i ) = ⊥ for all the opened positions i. Unfortunately, we can only guarantee that this will hold with overwhelming probability in our concrete construction, and not with probability 1. It turns out that, when building statistical ZAPs for NP, this is a crucial issue: in the soundness game of the ZAP construction from IHBG, the challenger will want extraction to succeed with probability µ even when conditioning on other checks being successful. A guaranteed correctness of extraction (conditioned on extraction succeeding) would ensure that this is the case, but an overwhelming probability of correctness does not, since conditioning on other events could arbitrarily change this probability.

To work around this issue, we adopt an approach closer in spirit to the definition of [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF]. We define µ-extractability as follows: an IHBG is µ-extractable if there exists an efficient simulator SimCoin and an efficient opener Open such that, for any PPT adversary A and any PPT distinguisher D, given simulated coins ( r, τ ) ← r SimCoin (where τ is an associated trapdoor for the opener), and a tuple (c, S, ρ * S , {π i } s , st) ← r A( r) where c is a short commitment, S is a set of positions, ρ * S are the values which A opens the position to, the π i are certificates of correct openings, and st is an arbitrary state, and letting ρ ← Open( r, c, τ ), the probability p 1 that VerifyBit( r, c, i, 1 -ρ i , π i ) returns ⊥ for all i ∈ S and at the same time the distinguisher D, given st, outputs 1, should satisfy

p 1 ≥ µ(λ) • (p 2 -negl(λ)),
where p 2 is the probability of the same event without the check that the procedure VerifyBit( r, c, i, 1ρ i , π i ) returns ⊥ for all i ∈ S. That is, µ-extractability requires that for any other efficient conditions that we were verifying, the probability that these conditions are still verified and that simultaneously, extraction succeeded and produced a correct output, should not decrease by a factor more than µ compared to the initial probability. This strong security notion is the key to capture the intuition that the extraction should succeed with probability µ essentially independently of everything else.

Given this notion of µ-extractable IHBG, we provide a natural construction of statistical ZAP for NP, which follows the standard template of using the IHBG to compile an unconditional NIZK for NP in the hidden-bits model, and formally prove that the resulting construction is a ZAP.

Constructing IHBG. It remains to construct IHBG with a statistical hiding property, satisfying the strong µ-extractability notion defined above. The first natural idea is to rely on the construction of dual-mode HBG from [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF], and to convert it into a plain model protocol by letting the verifier sample the CRS herself. However, this immediately runs into obstacles: nothing prevents the verifier from sampling the CRS in binding mode, breaking the statistical hiding property. To recover the statistical hiding property, we let the prover tweak the CRS sampled by the verifier in a way that simultaneously guarantee two things:

-With overwhelming probability over the coins of the prover, the tweaked CRS will be in hiding mode, yet -The tweak comes from a superpolynomial-size set, and by successfully guessing the tweak in advance, a simulator can engineer the sampled CRS (in a way that is indistinguishable from sampling a CRS honestly) such that the tweaked CRS will be in binding mode.

To achieve these two features, we rely on an elegant linear-algebra trick. In order to explain the idea, we first recall the high-level template of the construction of dual-mode HBG described in [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF]. Let m be the length of the hidden bit string. The LPWW construction works in a hard-discrete-log group G of order p with generator g. It has the following structure:

-The hiding CRS is g A , where A is a random full-rank matrix A ∈ Z (m+1)×(m+1) p .

-The binding CRS is g A , where A is a random rank-1 matrix in Z (m+1)×(m+1) p . Under the DDH assumption, the two modes are indistinguishable. Let a 0 , • • • , a m denote the columns of A. To provide a short commitment to a pseudorandom length-m hidden bit string, the prover picks a random length-(m + 1) vector y, and computes c = g y •a0 . Then, the i-th hidden bit is defined to be ρ i = HB(g y •ai ), where HB(•) is a hardcore bit function (e.g. a la Goldreich-Levin). Eventually, to prove correct opening of ρ i , given the commitment c and the CRS g A , the prover reveals c i = g y •ai and uses a NIZK to demonstrate the existence of a vector y such that c = g y •a0 and c i = g y •ai (from now on, we will call this language the LPWW language, L LPWW ).

Observe that when the CRS is in binding mode, we have a i = v i • a 0 for some value v i (since A has rank 1), hence the above language becomes essentially a DDH language. Adapting existing statistical NIZKs for the DDH language suffices to guarantee extractability in binding mode. On the other hand, when the CRS is in hiding mode, where A has full rank, any number of openings (of which there is at most m) g y •ai leak statistically no information about the unopened values (since A is of dimension (m + 1) × (m + 1)). This is because for any possible choice of values for the unopened positions, there exists a unique vector y that coincides with all the opened and unopened values when A is full rank. Hence, this guarantees statistical hiding. Now, the core idea to achieve statistical hiding and µ-extractability in our construction (where µ is some arbitrary fixed inverse-superpolynomial function) is to let the verifier sample and send g A herself, but to let the prover tweak this sample as follows: let I m+1 denote the identity matrix in

Z (m+1)×(m+1) p
. The prover picks a small exponent α at random from a subset of Z p of size ≈ 1/µ, e.g. by picking α as a random integer smaller than [1/µ], and using a natural encoding of integers in {0, • • • , p -1} as elements of Z p . Then, the prover defines the tweaked CRS g A to be g A-α•Im+1 , and uses this tweaked CRS in the dual-mode HBG construction of [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF]. 6To see why this tweak achieves exactly what we want, observe that the following holds:

-First, we show that with overwhelming probability 1 -(m + 1)µ, the matrix A has full rank. Indeed, if A does not have full rank, it means that there is a nonzero vector u in the kernel of A . But then, u • A = 0 rewrites to u • A = α • u -in equivalent terms, this means that α must be an eigenvalue of A. But since A can have at most m + 1 eigenvalues and α is randomly sampled from a set of size 1/µ, then this event can happen with probability at most (m + 1)µ. -Second, we sketch why µ-extractability holds. First, the simulator will guess a value α , and set

A ← M + α • I m+1
, where M is a rank-1 matrix. Observe that when the simulator guesses correctly, which happens with probability µ, it holds that g A is a binding CRS. Furthermore, under the assumption that no PPT adversary can distinguish DDH tuples from random tuples with probability better than µ•negl(λ), the replacement of truly random coins by simulated coins will not be detected. Hence, when further assuming that the ZAP for L LPWW guarantees a bound µ • negl(λ) on the probability that a malicious PPT prover breaks soundness, we can extract with probability almost µ a correct hidden-bit string. In Section 3, we will formally prove that µ-extractability holds with respect to an arbitrary PPT distinguisher D.

Summing up, the above provides a construction of IHBG (which in turns implies statistical ZAPs for NP), assuming the hardness of DDH with distinguishing advantage µ • negl(λ) for any PPT adversary and for any negligible functions µ and negl (an assumption in-between standard polynomial time hardness and superpolynomial time hardness, which is called explicit hardness in [1]), and the existence of statistical ZAPs for L LPWW with µ • negl(λ)-soundness.

Instantiating the Statistical ZAPs for L LPWW . Looking ahead, the formal analysis of our construction actually requires a slightly exotic notion of soundness: L LPWW is formally not a language, but a parametrized family of languages, and (adaptive) soundness must hold for parameters sampled uniformly at random from a specific subset of language parameters (which are those that correspond to A being of rank 1). We call a ZAP for the parameterized family of languages L LPWW IHBGfriendly when it satisfies this notion of soundness. We provide two instantiations for the underlying IHBG-friendly statistical ZAP.

Using pairings. First, we observe that the recent work of Couteau and Hartmann [8] provides a statistical ZAP for the DDH language, which extends directly to an IHBG-friendly statistical ZAP for the L LPWW language, under the standard kernel-DH assumption, in groups equipped with an asymmetric pairing. This leads to a statistical ZAP for NP under the explicit hardness of DDH in G 1 , and the explicit hardness of kernel-DH in G 2 , where (G 1 , G 2 ) are groups equipped with an asymmetric pairing.

Without pairings. Secondly, we revisit the recent construction of statistical NIZKs for the DDH language in pairing-free groups by Couteau, Katsumata, and Ursu [10]. Their construction relies on the assumption that no PPT algorithm can break the one-wayness of ElGamal against key-dependent message (OW-KDM) attacks with respect to efficient functions (i.e., the assumption that no PPT adversary can recover m from an ElGamal encryption of m, even when m is some efficiently computable function of the ElGamal secret key) with probability better than 2 -3λ/4+o(λ) (note that the best known PPT attack against this assumption, in appropriate groups, succeeds with probability 2 -λ+o(λ) ; furthermore, the restriction of KDM hardness to efficient functions of the secret key makes the assumption falsifiable "in spirit" -i.e., up to the negligible winning advantage). We denote this assumption the 2 -3λ/4 -OW-KDM hardness of ElGamal. We adapt the CKU construction to the LPWW language. Along the way, we put forth a modification of their construction which significantly improves the underlying assumption: we only need to assume that no PPT adversary can break the OW-KDM hardness of ElGamal with probability better than 2 -λ/2+o(λ) . This change directly improves the result of [10]. With this instantiation, and observing that this statistical NIZK is also a statistical ZAP when the verifier can choose the CRS, we obtain a statistical ZAP for NP in pairing-free groups under the explicit hardness of DDH, and the 2 -λ/2 -OW-KDM hardness of ElGamal (we note that the latter is incomparable to DDH: it is a search, discrete-logarithm-type assumption, which is not even known to imply public-key encryption).

A Direct Construction using Pairings

Eventually, we point out that if one is willing to rely on a stronger assumption, one of our two instantiations (the pairing-based instantiation) can be obtained from our techniques in a much more direct (and simple-in-hindsight) way, without going through the hidden-bit model. Specifically, the core idea for our IHBG construction is to modify the CRS of a dual-mode NIZK using a simple tweak, sampled from a small set by the prover, which guarantees that with overwhelming probability a maliciously sampled CRS will be in hiding mode (but it will be in binding mode in the case when the verifier guesses the tweak).

A similar tweak can be applied directly to the dual-mode NIZK of Groth, Ostrovsky, and Sahai [START_REF] Groth | Perfect non-interactive zero knowledge for NP[END_REF] instantiated with Groth-Sahai commitments [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. Briefly, a Groth-Sahai commitment is of the form (1, g m ) • u r • v s , where u, v are two random vectors of length two, and • denotes the coordinate-wise product (we write u r for (u r 1 , u r 2 ), where u = (u 1 , u 2 )). When the vectors (u, v) are random, the commitments are perfectly hiding; when v is in the span of u, they become perfectly binding. A GOS proof for circuit satisfiability, given a circuit C and a witness w such that C(w) = 1, works by committing to all bits of w, as well as to the bits on all wires during the evaluation of C(w). Then, the proof proceeds by showing that all commitments commit to bits, that all gate relations are satisfied (which reduces to proving that a linear combination of the committed input and output bitshomomorphically computed from the commitments -is itself a bit), and that the output commitment contains 1. All these proofs can be reduced to pairing-product equations, hence can be proven with a Groth-Sahai NIZK [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. Now, letting the verifier choose the CRS (u, v) themself, the prover can sample a small tweak z ← r [1/µ], and set the CRS to be (u , v ) = (u • (1, g z ), v • (1, g z )). For any adversarial choice of (u, v), (u , v ) will not be colinear except with negligible property; on the other hand, with probability µ, the verifier can guess the tweak z and cause (u , v ) to be in binding mode. To make the analysis work, we need to rely on the same notion of µ-extractability which we defined previously. This direct approach leads to a statistical ZAP for NP in groups (G 1 , G 2 ) equipped with an asymmetric pairing, assuming the explicit hardness of DDH in both G 1 and G 2 , a slightly stronger assumption compared to the one we obtain when going through the hidden-bit model. While simple in hindsight, this construction was apparently missed in previous works: the recent work of [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] achieved, under the same assumption, a strictly weaker result (a ZAPR argument for NP), using a considerably more involved and highly non-trivial construction.

Preliminaries

Notation. For integers n ≤ m, we write [m] for the set {1, • • • , m} and [n : m] for the set {n, n + 1, • • • , m}. With an abuse of notation, for r ∈ R ≥0 , we use [r] to denote [ r ]. For a string x ∈ {0, 1} m , set S ⊆ [m], and an integer i ∈ [m], denote x S as the subsequence of the bits of x indexed by the set S and x i as the i-th bit of x. We use bold fonts to denote column vectors over Z p or G such as

v = (v 1 , • • • , v n ) ∈ Z n
p and g = (g a1 , • • • , g an ) ∈ G n , respectively. We use capital bold fonts for matrices, e.g. M. Given a vector a, g a denotes the column vector whose components are the g ai ∈ G; we extend this notation to matrices of group elements g M in the natural way. With an abuse of notation, we define (g ) v to be the inner-product between the exponent of g and v, i.e., g i∈[n] aivi . For two vectors v and w, (v|w) denotes a matrix with columns v and w, and (v w) denotes a vector with v stacked on top of w. Moreover, let ker(v) denote the linear subspace of Z n p consisting of all vectors w satisfying v w = 0.

Hash Functions

We recall the definition of universal hash functions and define uniformity [START_REF] Håstad | A pseudorandom generator from any one-way function[END_REF].

Definition 1 (Universal Hash Function). An ensemble of a collection of hash functions H

= {H λ } λ = {{H : X λ → Y λ } H } λ is universal if for any x 0 , x 1 ∈ X λ such that x 0 = x 1 , we have Pr[H ← r H λ : H(x 0 ) = H(x 1 )] ≤ 1/|Y λ |.

Lemma 2 (Uniformity). Let an ensemble of a collection of hash functions H

= {H λ } λ = {{H : X λ → Y λ } H } λ be universal. Then, for all λ ∈ N, if |X λ | ≥ |Y λ | • λ ω(1) , the two distributions {H ← r H λ , x ← r X λ : (H, H(x))} and {H ← r H λ , y ← r Y λ : (H, y)} are negl(λ)-statistically close.

Hardness Assumptions

Let DHGen be a deterministic algorithm that on input 1 λ returns a description G = (G, p) where G is a cyclic group of prime order p. Let PGen be a deterministic algorithm that on input

1 λ returns a description PG = (G 1 , G 2 , G T , p) where (G 1 , G 2 , G T )
are cyclic groups of prime order p equipped with a bilinear pairing operation

• : G 1 × G 2 → G T .
Below, we recall the definition of the decision Diffie-Hellman assumption in a cyclic group, as well as the definition of the kernel Diffie-Hellman assumption in a pairing group. Following [1], we also consider the explicit hardness of the assumptions, where we say that an assumption has explicit µ-hardness if µ is an explicit bound on the advantage of any polynomial time adversary. Note that this notion of explicit hardness is stronger than standard polynomial hardness, but weaker than superpolynomial hardness 7 for any superpolynomial factor. Definition 3 (DDH Assumption). We say that the decisional Diffie-Hellman (DDH) assumption holds relative to DHGen if for all PPT adversaries A, it holds that Adv DDH (A) ≤ negl(λ), where

Adv DDH (A) = | Pr 1 ← A(1 λ , G, g, g α , g β , g γ ) -Pr 1 ← A(1 λ , G, g, g α , g β , g αβ ) |.
Here, note that G ← DHGen(1 λ ) and DHGen outputs a fixed group G per security parameter, and g ← r G, α, β, γ ← r Z p are chosen uniformly. Furthermore, let µ(λ) be an efficiently computable function. We say that the µ-explicit hardness of the DDH assumption holds relative to DHGen, if Adv DDH (A) ≤ µ(λ) for all PPT adversaries A.

We now recall the definition of the kernel Diffie-Hellman assumption in a pairing group. The kernel DH assumption is a standard search assumption in bilinear groups, introduced in [START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF] and used in several papers, e.g. [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF]. In particular, kernel Diffie-Hellman in a group G 2 is implied by (and is qualitatively weaker than) the DDH assumption in the same group.

Definition 4 (Kernel DH Assumption). We say that the kernel Diffie-Hellman (kerDH) assumption holds relative to PGen if for all PPT adversaries A, it holds that Adv kerDH (A) ≤ negl(λ), where

Adv kerDH (A) = Pr   PG ← PGen(1 λ ), (g 1 , g 2 ) ← r G 1 × G 2 , e ← r Z p , : (u, v) ∈ ker((1, e) ) ∧ v = 0 (g u 1 , g v 1 ) ← A(1 λ , PG, g 1 , g 2 , g e 2 )   .
Furthermore, let µ(λ) be an efficiently computable function. We say that the µ-explicit hardness of the kernel DH assumption holds relative to PGen, if Adv DDH (A) ≤ µ(λ) for all PPT adversaries A.

To see why the above is implied by DDH in G 2 , observe that on input (g, g α , g β , g γ ), an adversary against DDH can run the kernel DH adversary on input (g 1 , g, g α ), where g 1 ← r G 1 and e is implicitly set as α. It then gets a vector (g u 1 , g v 1 ) in G 2 1 from the kernel DH adversary such that (u, v) is in the kernel of (1, α). Now, if (g, g α , g β , g γ ) is a DDH tuple, then (u, v) is also in the kernel of (g β , g γ ) = (g, g α ) β , and this can be checked efficiently given (g u 1 , g v 1 ) with the help of the pairing operation.

Remark 5 (Extensions to Matrix Diffie-Hellman). For the sake of concreteness and simplicity, we state our results in this paper in terms of the DDH and kernel DH assumptions. However, all our results can be generalized to hold under the standard generalizations of the Diffie-Hellman assumption, namely the decisional k-Lin [START_REF] Hofheinz | Secure hybrid encryption from weakened key encapsulation[END_REF] and kernel k-Lin assumptions, or even more generally any assumption from the family of the (decisional or kernel) matrix Diffie-Hellman assumptions [15,[START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF].

One-Way KDM Security of ElGamal. The last hardness assumption we will use in this work states, in essence, that no PPT adversary can recover m given an ElGamal encryption of m, even when m might be an efficiently computable function of the ElGamal secret key, with probability significantly better than 2 -c•λ for some constant c < 1 (where λ is the logarithm of the group size). Note that the best known attack against this falsifiable search assumption succeeds with probability poly(λ)/2 λ . To formally introduce the assumption, we introduce a natural secret-key variant of ElGamal (which suffices for our construction and leads to a more conservative assumption compared to the public-key variant).

Definition 6 (Secret-Key ElGamal). Let G = { Gλ } λ be an ensemble of groups where each group Gλ is of order q such that log q ≈ λ. The natural (secret-key) variant of additive ElGamal with message space Z q consists of the following three PPT algorithms.

-Setup(1 λ ) : The setup algorithm outputs a public-parameter G ← r Gλ and a secret key

k ← r Z q . -Enc G(k, m) : The encryption algorithm samples R ← r G and outputs a ciphertext C = ( R, Rk • Gm ). -HalfDec(k, C) :
The half decryption algorithm parses C as ( C0 , C1 ) and outputs C1 / Ck 0 .

Throughout the paper, we omit the subscript when the meaning is clear. Note that the scheme does not allow for full decryption, but only for decryption "up to discrete logarithm": for every ( G, k, m), it holds that HalfDec(k, Enc G(k, m)) = Gm . One important property of the scheme is that it enjoys the notion of universality. Informally, the notion claims that the ciphertexts are not associated with a specific key, but rather, could have been an output of any key.

Definition 7 (Universality). For all λ ∈ N, G ∈ Gλ , and k * ∈ Z q , the ciphertexts of ElGamal satisfies

{ C : (k, m) ← r Z 2 q , C ← r Enc G(k, m)} = { C : m ← r Z q , C ← r Enc G(k * , m)} = U G2 .
Definition 8 (OW-KDM Security). Let F = {F λ } λ∈N be an ensemble of sets of functions where each F λ = {F u } u is a family of (possibly randomized) efficiently-computable functions. We say that ElGamal satisfies (one-query) δ-hard OW-KDM security with respect to F if for every F u ∈ F λ , superpolynomial function s, and every (non-uniform) PPT adversary A, it holds that

Pr ( G,k)←r Gλ ×Zq m←Fu( G,k) C←rEnc G (k,m) [A( G, C) = m] ≤ s(λ) • δ(λ).
When ElGamal satisfies δ-hard OW-KDM security for δ(λ) = 2 -(c+o(1))•λ for some constant c ∈ (0, 1], we say it is 2 -cλ -OW-KDM secure or more simply, strong OW-KDM secure.

The strong OW-KDM security of ElGamal was introduced in [6]. However, this work considered an extreme variant of the notion with c = 1 (that is, 2 -λ -OW-KDM), and where security was required to hold with respect to all functions (even inefficient ones). The more conservative variant (with c < 1 and a restriction to efficiently computable functions) was introduced in [10], which used it (with constant c = 3/4) to build correlation-intractable hash functions. In this work, we will rely on an even more conservative variant with c = 1/2.

ZAP

ZAP [13,14] is a public-coin two-move witness indistinguishable non-interactive argument. In this work, we focus on statistical ZAPs where witness indistinguishability holds unconditionally. Definition 9 (ZAP). A ZAP system Π ZAP for an NP language L = {L λ } λ with corresponding relation R = {R λ } λ with public-coin length (λ) is a tuple of PPT algorithms (Prove, Verify) defined as follows.

Prove(r, x, w) → π : The proving algorithm is given the public-coin r ∈ {0, 1} , a statement x, and a witness w, and outputs a proof π.

Verify(r, x, π) → or ⊥ : The verification algorithm is given the public-coin r ∈ {0, 1} , a statement x, and a proof π, and outputs for acceptance or ⊥ for rejection.

We additionally require the following properties to hold.

Correctness: For any λ ∈ N, r ∈ {0, 1} and (x, w) ∈ R λ , we have

Pr[Verify(r, x, Prove(r, x, w)) = ] = 1.
(Non-Adaptive) Computational Soundness: For any λ ∈ N, PPT adversary A, and any statement x ∈ L λ , we have

Pr[r ← {0, 1} , π ← r A(r, x) : Verify(r, x, π) = ] ≤ negl(λ).
(Adaptive) Statistical Witness Indistinguishability: For any λ ∈ N and unbounded adversary A = (A 0 , A 1 ), we have

Pr   (r, x, w 0 , w 1 , st) ← r A 0 (1 λ ) π 0 ← r Prove(r, x, w 0 ) : A 1 (st, π 0 ) = 1 ∧ (x, w 0 ) ∈ R λ ∧ (x, w 1 ) ∈ R λ   -Pr   (r, x, w 0 , w 1 , st) ← r A 0 (1 λ ) π 1 ← r Prove(r, x, w 1 ) : A 1 (st, π 1 ) = 1 ∧ (x, w 0 ) ∈ R λ ∧ (x, w 1 ) ∈ R λ   ≤ negl(λ).
Remark 10 (On Adaptive Soundness). In this work, we construct a ZAP that is non-adaptive computationally sound and adaptive statistical witness indistinguishable. This security property is in alignment with all the recent ZAPs (or ZAP with private randomness) [1,[START_REF] Goyal | Statistical zaps and new oblivious transfer protocols[END_REF][START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF]. Constructing ZAPs satisfying adaptive soundness and statistical witness indistinguishability seems to be difficult, where the former stipulates that the adversary can choose the statement x ∈ L after it sees the publiccoin r. Although we do not have any formal proofs of nonexistence of such ZAPs, we do have some evidence indicating the difficulty of obtaining them. In the context of NIZKs satisfying statistical zero-knowledge (NISZKs), Pass [START_REF] Pass | Unprovable security of perfect NIZK and non-interactive non-malleable commitments[END_REF] shows that there is no black-box reduction from the adaptive soundness of NISZK to a falsifiable assumption [START_REF] Gentry | Separating succinct non-interactive arguments from all falsifiable assumptions[END_REF][START_REF] Naor | On cryptographic assumptions and challenges (invited talk)[END_REF]. Owing to the similarity between ZAPs with statistical witness indistinguishability and NISZK, and the fact that the former turned out to be much more difficult to construct than the latter, we view it as an interesting open problem to construct adaptively sound proof systems.

NIZKs in the Hidden-Bits Model

We recall the notion of a NIZK in the hidden-bits model [17]. Definition 11. A non-interactive proof system Π HBM in the hidden-bits model for an NP language L = {L λ } λ with corresponding relation R = {R λ } λ with hidden-bits length m(λ) is a pair of PPT algorithms (Prove, Verify) defined as follows.

Prove(hb, x, w) → (I, π) : The proving algorithm is given a random bit string hb ∈ {0, 1} m and a statement x, and a witness w as inputs, and outputs a subset I ⊆ [m] together with a proof π. Verify(S, hb S , x, π) → or ⊥ : The verification algorithm is given a subset S ⊆ [m], a string hb S ∈ {0, 1} |S| , a statement x and a proof π as inputs, and outputs for acceptance or ⊥ for rejection.

We additionally require the following properties to hold. Correctness. For any λ ∈ N, (x, w) ∈ R λ , any hb ∈ {0, 1} m , and for (I, π) ← r Prove(hb, x, w), we have Verify(x, hb S , x, π) = . Statistical ε-Soundness. For any λ ∈ N and (possibly unbounded) adversary A, we have

Pr [hb ← r {0, 1} m , (x, S, π) ← r A(hb) : Verify(S, hb S , x, π) = ∧ x / ∈ L λ ] ≤ ε.
Perfect Zero-Knowledge. For any λ ∈ N and any (possibly unbounded) stateful adversary A, there exists a PPT8 zero-knowledge simulator Sim such that for every (x, w) ∈ R λ , the distributions {(S, hb S , π) : hb ← r {0, 1} m , (S, π) ← r Prove(hb, x, w)} and {Sim zk (x)} are perfectly indistinguishable.

We use the following result regarding the existence of NIZKs in the hidden-bits model [16].

Theorem 12 (NIZK for all of NP in the hidden-bits model). Let k = k(λ) be any positive integer-valued function. Then, unconditionally, there exists a non-interactive proof system Π HBM for any NP language L = {L λ } λ in the hidden-bits model that uses hb = k • poly(λ) hidden-bits with soundness error ≤ 2 -k•λ , where poly is a polynomial function related to the NP language L .

Correlation-Intractable Hash Functions

Finally, we recall the definition of correlation-intractable hash functions (CIH).

Definition 13 (Correlation Intractable Hash Function).

A collection

H = {H λ : K λ × I λ → O λ } λ of (efficient) keyed hash functions is a R-correlation intractable hash (CIH) family, with respect to a parameterized relation ensemble R = {R λ } λ = {{R λ,t ⊆ I λ × O λ } t∈T λ } λ , if
[(x, H λ (k, x)) ∈ R λ,t ] ≤ negl(λ).
Furthermore, let µ(λ) be an efficiently computable function. We say that the collection H satisfies (µ, R)-correlation intractability if the above probability is bounded by µ(λ) for all PPT adversaries A.

3 Interactive Hidden-Bits Generating Protocol and ZAPs for NP

In this section, we formally define an interactive hidden-bits generating (IHBG) protocol. Our definition builds on the definition of a (dual-mode) hidden-bits generator from [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF][START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] (and the similar notion of (designated-verifier) PRG [9,13,14]). The main difference is that we allow a two-round interaction between the hidden-bits generator and the verifier, while removing the common reference string. Below, we define a public-coin flavor of an IHBG protocol to allow for public verifiability and reusability of the message from the verifier.

Definition

We formalize the notion of an interactive hidden-bits generating (IHBG) protocol.

Definition 14 (Interactive Hidden-Bits Generating Protocol). Let s(λ) and m(λ) be positive valued polynomials. An interactive hidden-bits generating (IHBG) protocol Π IHBG with public-coin length (λ) is a tuple of efficient algorithms (GenBits, VerifyBit) defined as follows.

GenBits(1 λ , m, r) → (σ, ρ, {π i } i∈ [m] ) : The hidden-bits generator algorithm is given the security parameter 1 λ (in unary), a length m, a public-coin r ∈ {0, 1} and outputs a commitment σ ∈ {0, 1} s , a string ρ ∈ {0, 1} m , and a set of proofs {π i } i∈m . VerifyBit(r, σ, i, ρ i , π i ) → or ⊥: The verification algorithm is given a public-coin r ∈ {0, 1} , a commitment σ ∈ {0, 1} s , a bit ρ i ∈ {0, 1}, and a proof π i , and outputs for acceptance or ⊥ for rejection.

We additionally require the following properties to hold. Below, we assume that the security parameter is provided to all algorithms, and omit it for simplicity.

Correctness: For any λ ∈ N, j ∈ [m], and r ∈ {0, 1} , we have

Pr[(σ, ρ, {π i }) i∈[m] ← r GenBits(m, r) : VerifyBit(r, σ, j, ρ j , π j ) = ] = 1.
Succinctness: The commitment length s only depends on the security parameter, i.e., s(λ) = poly(λ), and in particular, does not depend on the length m of the generated bits.

µ-Extractability: There exists a PPT public-coin simulator SimCoin and a deterministic polynomialtime open algorithm Open such that for all polynomial m, the following two conditions hold. For an intuitive explanation for µ-successful extraction, we refer the readers to the technical overview in Section 1.2.

-(Public-Coin Indistinguishability) for any PPT adversary A, we have

| Pr[r ← r {0, 1} : A(m, r) = 1] -Pr[( r, τ ) ← r SimCoin(1 λ , m) : A(m, r) = 1]| ≤ negl(λ).
-(µ-Successful Extraction) for any PPT adversary A and any PPT distinguisher D, we have

Pr   ( r, τ ) ← r SimCoin(1 λ , m) (σ, S, ρ * S , {π i } i∈S , st) ← r A(m, r) ρ ← Open( r, σ, τ ) : D(st) = 1 ∧ ρ ∈ {0, 1} m ∧ ∀i ∈ S, VerifyBit( r, σ, i, 1 -ρ i , π i ) = ⊥   ≥ µ(λ) • Pr ( r, τ ) ← r SimCoin(1 λ , m) (σ, S, ρ * S , {π i } i∈S , st) ← r A(m, r) : D(st) = 1 -µ(λ) • negl(λ).
Statistical Hiding: For all polynomial m, public-coin r ∈ {0, 1} , and all unbounded adversaries A = (A 0 , A 1 ), there exists a (possibly unbounded) simulator Sim such that

Pr (σ, ρ, {π i } i∈[m] ) ← r GenBits(m, r) S ← r A 0 (ρ) : S ⊆ [m] ∧ A 1 (r, S, σ, ρ, {π i } i∈S ) = 1 - Pr ρ ← r {0, 1} m , S ← r A 0 (ρ) (σ, {π i } i∈S ) ← r Sim(m, r, S, ρ S ) : S ⊆ [m] ∧ A 1 (r, S, σ, ρ, {π i } i∈S ) = 1
≤ negl(λ).

ZAPs for NP from Interactive Hidden-Bits Generating Protocols

Here, we construct a ZAP for NP based on an IHBG protocol and a NIZK in the hidden-bits model, where the latter exists unconditionally.

Building Block. Let L be an NP language and R be its corresponding relation. 9 We construct a ZAP for L based on the following building blocks.

-Π IHBG = (GenBits, VerifyBit) is an interactive hidden-bits generating protocol. We assume it has public-coin length (λ), commitment length s(λ), and output length m(λ) (i.e., ρ ∈ {0, 1} m ). We further assume it satisfies µ(λ)-extractability. -Π HBM = (HBM.Prove, HBM.Verify) is a NIZK in the hidden-bits model for L . We assume the hidden-bits length is m(λ) and it is statistically ε HBM -sound, where ε HBM = 2 -s(λ) •µ(λ)•negl(λ). 10Construction. The construction of a ZAP for L with public-coin length (λ) = (λ)+m(λ), denoted as Π ZAP , is described as follows.

ZAP.Prove(r , x, w) : On input a public-coin r ∈ {0, 1} , a statement x and a witness w, parse it as (r, ∆) ← r such that r ∈ {0, 1} and ∆ ∈ {0, 1} m . Then run (σ, ρ, {π IHBG,i } i∈ [m] ) ← r GenBits(1 λ , m, r) and compute an HBM proof (S, π HBM ) ← r HBM.Prove(hb, x, w), where hb := ρ ⊕ ∆. Finally, output π ZAP = (σ, S, ρ S , {π IHBG,i } i∈S , π HBM ). ZAP.Verify(r , x, π ZAP ) : On input a public-coin r ∈ {0, 1} , a statement x and a proof π ZAP , parse it as (r, ∆) ← r such that r ∈ {0, 1} and ∆ ∈ {0, 1} m , and (σ, S, ρ S , {π IHBG,i } i∈S , π HBM ) ← π ZAP . Then, output if HBM.Verify(S, ρ S ⊕ ∆ S , x, π HBM ) = and VerifyBit(r, σ, i, ρ i , π IHBG,i ) = for all i ∈ S. Otherwise, output ⊥.

Security

Correctness of our ZAP follows from a routine check. Below, we show our ZAP satisfies non-adaptive computational soundness and adaptive statistical witness indistinguishability in Theorems 15 and 19.

Theorem 15 (Soundness). If Π IHBG is µ-extractable and Π HBM has statistical ε HBM -soundness, where ε HBM = 2 -s(λ) • µ(λ) • negl(λ), then Π ZAP has non-adaptive computational soundness.

Proof. Assume there exists a statement x ∈ L and a PPT adversary A against the non-adaptive computational soundness of Π ZAP with advantage ε. Below, we consider the following sequence of games between A and a challenger and denote E i as the event that the challenger outputs 1.

Game 1 : This is the real soundness game that proceeds as follows: The challenger first samples a public-coin r ← r {0, 1} and sends it to A. A then outputs a proof π * ZAP and sends it to the challenger. The challenger outputs 1 if ZAP.Verify(r , x, π * ZAP ) = , and outputs 0 otherwise. By definition Pr[E 1 ] = ε. Game 2 : This game is identical to the previous game except that the public-coin r ∈ {0, 1} is sampled differently. Let SimCoin be the PPT public-coin simulator of the IHBG protocol Π IHBG . Then, in this game, the challenger first runs ( r, τ ) ← r SimCoin(m) and samples ∆ ← r {0, 1} m , where r ∈ {0, 1} , and outputs the simulated public-coin r := ( r, ∆) ∈ {0, 1} . The rest is defined the same as in the previous game.

] -Pr[E 2 ]| ≤ negl(λ), hence Pr[E 2 ] ≥ ε -negl(λ).
Proof. The only difference between the two games is how the public-coin is generated. Let us consider the following adversary B against the public-coin indistinguishability of Π IHBG : B receives r ∈ {0, 1} from its challenger and samples ∆ ← r {0, 1} m . It then invokes A on input r = (r, ∆), and outputs 1 if the proof π ZAP output by A satisfies ZAP.Verify(r , x, π * ZAP ) = , and 0 otherwise. Since B perfectly simulates Game 1 (resp. Game 2 ) when r ← r {0, 1} (resp. (r, τ ) ← r SimCoin(m)), we have

|Pr[E 1 ] -Pr[E 2 ]| ≤ negl(λ).
Lemma 17. If Π IHBG is µ-extractable for all PPT adversary, then we have

Pr[E 3 ] ≥ µ(λ) • (Pr[E 2 ] - negl(λ)).
Proof. This follows from the µ-successful extractability of Π IHBG . Let us consider the following adversary B and distinguisher D against the µ-successful extractability: B on input m and r invokes A and simulates the challenger in Game 2 . When A outputs a forgery π * ZAP = (σ * , S * , ρ * S * , {π * IHBG,i } i∈S * , π * HBM ), B outputs (σ * , S * , ρ * S * , {π * IHBG,i } i∈S * , st), where st = ( r, π * ZAP ); D on input st, checks if ZAP.Verify( r, x, π * ZAP ) = , and outputs 1 if so and outputs 0 otherwise. Observe that the probability D outputs 1 is the same as the probability that event E 2 occurs. Below, we relate the probability that event E 3 occurs with the left hand side equation of µ-successful extractability.

The only difference between Game 2 and Game 3 is the check that ρ ∈ {0, 1} m and ρ * S * = ρ S * . Now, consider a variant Game 3 of Game 3 where, instead of checking ρ * S * = ρ S * , the challenger checks that for all i ∈ S * , it holds that VerifyBit( r, σ * , i, 1 -ρ i , π * IHBG,i ) = ⊥. Let E 3 be the event that the challenger outputs 1 in this variant. Observe that if event E 3 occurs then so does event E 3 . Indeed, whenever the challenger outputs 1 in E 3 , it holds in particular that

∀i ∈ S * , VerifyBit( r, σ * , i, ρ * i , π * i ) = , and ∀i ∈ S * , VerifyBit( r, σ * , i, 1 -ρ i , π * i ) = ⊥.
The latter implies that it can never hold, for any i ∈ S * , that ρ * i = 1 -ρ i ; hence, since we check ρ ∈ {0, 1} m in both events, whenever E 3 happens, it further holds that ρ * S * = ρ S * and E 3 therefore holds as well. In other terms,

Pr[E 3 ] ≥ Pr[E 3 ].
Therefore, by applying the µ-successful extractability of Π IHBG with respect to B and D, since the only difference between Game 2 and Game 3 is the check that ρ ∈ {0, 1} m and VerifyBit( r, σ * , i, 1 -

ρ i , π * IHBG,i ) = ⊥, we get Pr[E 3 ] ≥ µ(λ) • (Pr[E 2 ] -negl(λ)) ,
which concludes the proof of Lemma 17.

Lemma 18. If Π HBM is statistical ε HBM -sound, then we have

Pr[E 3 ] ≤ µ(λ) • negl(λ).
Proof. Let (σ * , S * , ρ * S * , {π * IHBG,i } i∈S * , π * HBM ) ← π * ZAP be A's output. When the challenger outputs 1 (i.e., event E 3 occurs), we have ρ * S * = ρ S * , where ρ ← Open( r, σ * , τ ), and HBM.Verify(S * , ρ * S * ⊕ ∆ S * , x, π * HBM ) = . For an any S * ⊆ [m] and ρ S * , if ∆ ← r {0, 1} m is sampled uniformly at random, then ρ S * ⊕ ∆ S * is distributed uniformly random. Then, by soundness of Π HBM , for a fixed ρ S * we have

Pr[HBM.Verify(S * , ρ S * ⊕ ∆ S * , x, π * HBM ) = ] ≤ ε HBM ,
where the probability is taken over the randomness of ∆, A, and the challenger, conditioned on A outputting ρ * S * that is consistent with ρ S * . Here, we do not include the condition x ∈ L in the above equation since we consider non-adaptive soundness for Π ZAP .

If we fix an arbitrary ( r, τ ), then for any commitment σ ∈ {0, 1} s the output of ρ ← Open( r, σ, τ ) is uniquely defined since Open is deterministic. Let us denote the unique ρ as ρ σ . Then, taking a union bound over all possible commitments σ ∈ {0, 1} s , we have

Pr[∃σ ∈ {0, 1} s.t. HBM.Verify(S * , ρ σ S * ⊕ ∆ S * , x, π * HBM ) = ] ≤ 2 s • ε HBM = µ(λ) • negl(λ).
Thus, we conclude

Pr[E 3 ] ≤ µ(λ) • negl(λ).
Putting everything together, this gives µ(λ)•(ε-negl(λ)) ≤ µ(λ)•negl(λ), which implies ε ≤ negl(λ). This concludes the proof.

Theorem 19 (Statistical Witness Indistinguishability). If Π IHBG is statistically hiding and Π HBM has perfect zero-knowledge, then Π ZAP is adaptive statistical witness indistinguishability.

Proof. We proceed with a sequence of games where the first (resp. last) corresponds to the game where the challenger uses witness w 0 (resp. w 1 ). Without loss of generality, we assume the adversary A = (A 0 , A 1 ) always outputs a statement x and witnesses w 0 and w 1 such that (x, w 0 ) ∈ R and (x, w 1 ) ∈ R. We denote E i as the event that A outputs 1 on input a proof π ZAP .

Game 1 : This is the real game where the challenger uses witness w 0 . Concretely, the challenger runs (r , x, w 0 , w 1 , st) ← r A 0 (1 λ ) and runs π 0 ← r ZAP.Prove(r , x, w 0 ). Here, recall ZAP.Prove constitutes of the following steps: The following two lemmas establish

1. Parse (r, ∆) ← r ; 2. Compute (σ, ρ, {π IHBG,i } i∈[m] ) ← r GenBits(m,
|Pr[E 1 ] -Pr[E 3 ]| ≤ negl(λ).
Since the game transition from Game 3 to Game 5 is identical to those from Game 3 to Game 1 except that the challenger uses w 1 instead of w 0 , we have

|Pr[E 3 ] -Pr[E 5 ]| ≤ negl(λ). Collecting the bounds, we obtain |Pr[E 1 ] -Pr[E 5 ]| ≤ negl(λ), thus completing the proof. Lemma 20. If Π IHBG is statistically hiding, then we have |Pr[E 1 ] -Pr[E 2 ]| ≤ negl(λ).
Proof. We construct an adversary B against the statistically hiding property of the IHBG protocol that simulates the view of A in either Game 1 or Game 2 depending on the challenge it receives. Since statistical hiding is defined with respect to any public-coin r ∈ {0, 1} , we can think B prepares r before seeing the hidden-bits ρ ∈ {0, 1} m . For clarity, we assume B consists of three unbounded algorithms (B 0 , B 0 , B 1 ), where B 0 prepares r and (B 0 , B 1 ) are as defined in Definition 14.

Description of B follows: B 0 runs (r , x, w 0 , w 1 , st) ← A 0 (1 λ ) and parses (r, ∆) ← r . It then outputs the public-coin r ∈ {0, 1} to the challenger. The challenger either runs (I) (σ, ρ, {π IHBG,i } i∈ [m] ) ← r GenBits(m, r) or (II) ρ ← r {0, 1} m and sends ρ to B 0 . B 0 then sets hb := ρ ⊕ ∆, runs (S, π HBM ) ← r HBM.Prove(hb, x, w 0 ), and sends the index set S ∈ [m] to the challenger. The challenger then provides B 1 with input (r, S, σ, ρ, {π IHBG,i } i∈S ). If the challenger ran (I) above, then it uses the already generated (σ, {π IHBG,i } i∈S ) and if the challenger ran (II) above, then it uses (σ, {π IHBG,i } i∈S ) ← r IHBG.Sim(m, r, S, ρ S ). B 1 then prepares the proof π ZAP = (σ, S, ρ S , {π IHBG,i } i∈S , π HBM ) and outputs whatever output by A 1 (st, π ZAP ).

It can be checked that B perfectly simulates the view of Game 1 (resp. Game 2 ) to A when the challenger runs (I) (resp. (II)). Therefore, assuming statistical hiding of the IHBG protocol, we have Proof. Fix an arbitrary ∆ ∈ {0, 1} m . Then, in Game 2 , we have (S, π HBM ) ← r HBM.Prove(hb, x, w 0 ) for a uniform random hb since hb := ρ ⊕ ∆ for a uniform random ρ ← r {0, 1} m . On the other hand, in Game 3 , we have (S, hb S , π HBM ) ← r HBM.Sim(x) and ρ S := hb S ⊕∆ S . By the perfect zero-knowledge of Π HBM , the distributions of (S, ρ S , π HBM ) are identical. Moreover, (σ, {π IHBG,i } i∈S ) are generated identically in both games. Therefore, the distribution of π ZAP = (σ, S, ρ S , {π IHBG,i } i∈S , π HBM ) is identical in both games. Thus, we have Pr[E 2 ] = Pr[E 3 ] as desired. 4 The LPWW Language L LPWW To instantiate the generic construction of statistical ZAP for NP given in Section 3, we will construct an IHBG which builds upon the dual-mode hidden-bit generator of Libert, Passelègue, Wee, and Wu [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF]. In this section, we first recall the specific parameterized language considered by [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF] (denoted as the LPWW language L LPWW ). We then introduce some tools related to this parameterized language: a specific type of statistical ZAP for L LPWW , which we call IHBG-friendly statistical ZAP, and a Σ-protocol for L LPWW .

|Pr[E 1 ] -Pr[E 2 ]| ≤ negl(λ) as desired.

Definition

Formally, we denote by L LPWW := {L LPWW,λ } λ the following family of parametrized languages: let G be a cyclic group of prime order p. We implicitly fix a vector length d ∈ N and a generator g ∈ G for each security parameter λ. 11 Let a set of parameter space Λ λ be (G d \{1}) 2 , where 1 := g 0 for 0 ∈ Z d p . Then, for any parameter par = (g v , g w ) ∈ Λ λ , we define L LPWW,λ = {L par LPWW,λ } par∈Λ λ such that L par LPWW,λ is the following parametrized language:

L par LPWW,λ := (g s , g u ) ∈ G 2 | ∃y ∈ Z d p s.t. g y v = g s ∧ g y w = g u .
Let Col(G d ) ⊂ Λ λ denote the set of elements of the form (g v , g α•v ) for some v = 0 and α ∈ Z * p , that is, the exponents form colinear vectors over (Z p ) d . Observe that for any par ∈ Col(G d ), L par LPWW,λ is a non-trivial Diffie-Hellman-style language (hence, L par LPWW is a sparse subset of Λ λ ); however, for any par ∈ Λ λ \Col(G d ), L par LPWW,λ is actually equal to G 2 (hence, L par LPWW,λ is a trivial language). Below, we may omit the security parameter and use the shorthand L LPWW = {L par LPWW } par∈Λ when the meaning is clear.

IHBG-Friendly Statistical ZAPs for the LPWW Language L LPWW

Looking ahead, our construction of IHBG in Section 5 will rely at its core on an adaptively secure statistical ZAP for the family of parametrized languages L LPWW = {L par LPWW } par∈Λ . More precisely, the statistical ZAP which we will use in our construction satisfies a variant of the standard notion of adaptive computational soundness (which we defined for a single language in Section 2): we require adaptive computational soundness to hold with respect to parameters par sampled uniformly from Col(G d ) ⊂ Λ (recall that Col(G d ) is the subset of parameters such that L par LPWW is nontrivial). In contrast, adaptive statistical witness indistinguishability must hold even for adversarially chosen parameters par ∈ Λ (hence, in a sense, WI is doubly-adaptive: with respect to the statement, and with respect to the language parameters). We call a statistical ZAP with these properties an IHBGfriendly statistical ZAP for L LPWW . We provide a formal definition below.

Definition. We formally introduce the notion of IHBG-friendly statistical ZAP for the family of parametrized languages L LPWW .

Definition 22 (IHBG-Friendly Statistical ZAP for L LPWW ). Let Λ λ = (G d \{1}) 2 be the parameter space for any λ ∈ N and consider the family of parameterized NP languages

L LPWW = {L LPWW,λ } λ = {{L par LPWW,λ } par∈Λ λ } λ , with associated witness relation R LPWW = {R LPWW,λ } λ = {{R par LPWW,λ } par∈Λ λ } λ .
Then, an IHBG-friendly ZAP system Π ZAP for L LPWW with with public-coin length (λ) is a tuple of PPT algorithms (Prove, Verify) defined as follows.

Prove(par, r, x, w) → π : The proving algorithm is given the parameters par ∈ Λ λ , the public-coin r ∈ {0, 1} , a statement x, and a witness w, and outputs a proof π. Verify(par, r, x, π) → or ⊥ : The verification algorithm is given the parameters par ∈ Λ λ , the publiccoin r ∈ {0, 1} , a statement x, and a proof π, and outputs for acceptance or ⊥ for rejection.

We additionally require the following properties to hold. (Doubly-Adaptive) Statistical Witness Indistinguishability: For any λ ∈ N and unbounded adversary A = (A 0 , A 1 ), we have Pr   (r, par, x, w 0 , w 1 , st) ← r A 0 (1 λ ) π ← r Prove(par, r, x, w 0 ) :

par ∈ Λ λ ∧ A 1 (st, π) = 1 ∧ (x, w 0 ) ∈ R par LPWW,λ ∧ (x, w 1 ) ∈ R par LPWW,λ   -Pr   (r, par, x, w 0 , w 1 , st) ← r A 0 (1 λ ) π ← r Prove(par, r, x, w 1 ) : par ∈ Λ λ ∧ A 1 (st, π) = 1 ∧ (x, w 0 ) ∈ R par LPWW,λ ∧ (x, w 1 ) ∈ R par LPWW,λ   ≤ negl(λ).
Building IHBG-Friendly Statistical ZAPs for L LPWW . In Section 6, we will provide two constructions of an IHBG-friendly statistical ZAPs for L LPWW , one in pairing groups (Theorem 40), and one in pairing-free groups (Theorem 46). Both constructions are obtained by compiling the Σprotocol for L LPWW described in Section 4.4 into an IHBG-friendly statistical ZAP for L LPWW . Below, we give an overview of the main lemmas regarding our two constructions whose proofs are provided in Section 6.

Pairing-Based Construction. The pairing-based construction builds upon the Couteau-Hartmann compiler from [8], which relies on the hardness of the kernel Diffie-Hellman assumption in a group G 2 (more generally, it can be based on the kernel k-Lin assumption in G 2 for any k), a standard search assumption (which is implied in particular by DDH in G 2 ) introduced in [START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF] and used in several works on pairing-based NIZKs, e.g. [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF].

Lemma 23. Let (G 1 , G 2 ) be bilinear-map groups equipped with an asymmetric pairing (implicitly parameterized by the security parameter λ). There exists an IHBG-friendly adaptive statistical ZAP for the family of parametrized languages L LPWW over G 1 which satisfies adaptive computational ε soundsoundness w.r.t. colinear parameters, and doubly-adaptive statistical witness indistinguishability, assuming the explicit ε sound -hardness of the kernel Diffie-Hellman assumption in G 2 .

Pairing-Free Construction. The pairing-free construction builds upon the compiler of [10]. The work of [10] build a correlation intractable hash function under the 2 -3λ/4 -OW-KDM security of ElGamal, which suffices to compile the above Σ-protocol into a statistical ZAP. We refine their approach and achieve a similar result under a weaker assumption, by managing to reduce the constant 3/4 to 1/2, that is, rely on the 2 -λ/2 -OW-KDM security of ElGamal. We note that the best known attack against this falsifiable search assumption succeeds with probability poly(λ)/2 λ .

Lemma 24. Let G be a group of order p such that λ ≈ 2 log p 2 . There exists an IHBG-friendly adaptive statistical ZAP for the family of parametrized languages L LPWW over G which satisfies adaptive computational ε sound -soundness w.r.t. colinear parameters for any ε sound = 2 -o( log p 2 ) , and doublyadaptive statistical witness indistinguishability, assuming the 2 -λ/2 -OW-KDM hardness of ElGamal over another group G of size | G| ≈ 2 λ .

Σ-protocols for Parameterized Families of Languages

To construct our IHBG-friendly statistical ZAPs for L LPWW , we rely on a Σ-protocol for the family of parameterized language L LPWW . Here, we recall the definition of Σ-protocols, adapted to a family of parametrized languages, rather than just one single language. A Σ-protocol is a three-move interactive proof between a prover P and a verifier V for a family of parameterized languages

L = {L λ } λ = {{L par λ } par∈Λ λ } λ with associated witness relation R = {R λ } λ = {{R par λ } par∈Λ λ } λ .
The prover sends an initial message α ∈ I λ for some commitment space I λ , the verifier responds with a random β ← r S λ for some challenge space S λ , and the prover concludes with a message γ. Lastly, the verifier outputs , if it accepts and ⊥ otherwise. We denote out P(par, x, w), V(par, x) as the final value output by the verifier and trans P(par, x, w), V(par, x) as the transcript (α, β, γ). A Σ-protocol is usually defined by three properties: completeness, special honest-verifier zero-knowledge, and special soundness (see for example [START_REF] Lindell | An efficient transform from sigma protocols to NIZK with a CRS and non-programmable random oracle[END_REF]). In this work, we will instead be interested in statistical witness indistinguishability even against malicious verifiers and adaptive soundness. The definitions follow.

Definition 25 (Completeness). For any λ ∈ N, par ∈ Λ λ and (x, w) ∈ R par λ , we have Pr[out P(par, x, w), V(par, x) = ] = 1.

Definition 26 (Statistical Witness Indistinguishability).

For any λ ∈ N, par ∈ Λ λ and (x, w 0 , w 1 ) such that (x, w 0 ) ∈ R par λ and (x, w 1 ) ∈ R par λ , and for any (possibly inefficient) cheating verifier V * , the two distributions trans P(par, x, w 0 ), V * (par, x) and trans P(par, x, w 1 ), V * (par, x) are statistically close. We say it is perfect witness indistinguishability when the two distributions are identical.

Definition 27 (Adaptive ρ-soundness). For any λ ∈ N, par ∈ Λ λ , any (possibly inefficient) cheating prover P * , and any first flow α, it holds that Pr[β ← r S λ ; (x, γ) ← r P * (par, α, β) : x ∈ L par λ ∧ V(par, x, α, β, γ) = ] ≤ ρ(λ).

A Σ-Protocol for the LPWW Language L LPWW

Fix some parameters par = (g v , g w ) ∈ Λ = (G d \{1}) 2 (implicitly parameterized by the security parameter λ). To match with the notations which we will use later when building an IHBG, we denote the dimension d in L par LPWW by m + 1. We consider a statement ( X, Ŷ ) := (g x, g ŷ ) ∈ L par LPWW and let y ∈ Z m+1 p be the prover witness (i.e., y is any vector over Z m+1 p such that y v = x and y w = ŷ).

Let n ∈ N be any positive integer. Then, a Σ-protocol for L LPWW = {L par LPWW } par∈Λ is provided in Figure 1. Correctness can be checked by routine calculation. Below, we prove statistical witness indistinguishability and adaptive soundness.

Prover Verifier ∀i ∈ [n] : zi ←$ Z m+1 p and set (Ri, Si) ← ((g ) z i , (h ) z i ) ∀i ∈ [n] : ei ←$ Z * p ∀i ∈ [n] : di ← ei • y + zi Check (g ) d i = Xe i • Ri and (h ) d i = Ŷ e i • Si, for i ∈ [n] {(Ri, Si)} i∈[n] { ei }i ∈ [n ] {di} i∈[n]
Fig. 1. Σ-protocol with statement ( X, Ŷ ) ∈ L par LPWW where par := (g, h) = (g v , g w ).

Lemma 28 (Perfect Witness Indistinguishability). The IHBG-friendly Σ-protocol for the family of parametrized languages L LPWW = {L par LPWW } par∈Λ in Figure 1 satisfies perfect witness indistinguishability.

Proof. Fix any par = (g v , g w ) ∈ Λ and statement ( X, Ŷ ) = (g x, g ŷ ) ∈ L par LPWW such that the set of witnesses W := {y ∈ Z m+1 p | y v = x ∧ y w = ŷ} is non-trivial, i.e., there exists at least two witnesses in W. Below, we only consider the case n = 1 since witness indistinguishability is closed under parallel repetition. First, notice that the distribution of the first message (R, S) is independent of the witnesses. This in particular implies that the output e of the (possibly inefficient) cheating verifier V * is also independent of the witnesses as well. Therefore, it suffices to show that the distribution of the third message d is identical for any witness y ∈ W conditioned on an arbitral fixed choice of (R, S) = (g r , g s ) and e. Let D z be the distribution of sampling a uniformly random z ∈ Z m+1 Proof. In case par ∈ Λ\Col(G d ), we have L par LPWW = G 2 so there exists no statement ( X, Ŷ ) / ∈ L par LPWW (see Section 4.1). Therefore, we only need to consider the case par ∈ Col(G d ). For any such par = (g v , g w ), we have v = 0 and w = α • v for some α ∈ Z * p . Now, fix any first flow {(R i , S i )} i∈[n] and let r i and s i be their exponents, respectively, i.e., R i = g ri and S i = g si and assume the adversary outputs ( X, Ŷ ) = (g x, g ŷ ) / ∈ L par LPWW . In order for the verifier to accept, the following must hold:

e i • ŷ + s i = e i • x • α + r i • α, for i ∈ [n], which implies that: ŷ -α • x = (α • r i -s i ) • e -1 i , for i ∈ [n]
We distinguish the following two cases:

1. If α • r i = s i for some i ∈ [n], then ŷ = α • x. This implies (g x, g ŷ ) ∈ L par LPWW . 2. If α • r i = s i for all i ∈ [n], then α•r1-s1 α•ri-si • e i = e 1 for i ∈ [n]
, which happens with probability at most ( 1 p-1 ) n-1 over the randomness of

(e i ) i∈[n] ← r (Z * p ) n .
We can ignore the first case since it does not lead to a valid cheating prover for adaptive soundness. In the second case, even a computationally unbounded cheating prover has at most ( 1 p-1 ) n-1 possibility of breaking adaptive soundness. Hence the statement follows.

Interactive Hidden-Bits Generating Protocols from the Explicit

Hardness of DDH and an IHBG-Friendly Statistical ZAPs for L LPWW

In this section, we construct an IHBG protocol based on explicit µ-hardness of the DDH assumption (over a pairing-free group, for a negligible function µ arbitrarily close to an inverse polynomial function) and an IHBG-friendly statistical ZAP for the language L LPWW , defined in Section 4, which is naturally induced from the (non-interactive) hidden-bits generator of Libert et al. [START_REF] Libert | New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more[END_REF].

Constructing the IHBG Protocol

Building Block. Our construction is parametrized by λ and µ(λ), and relies on the following building blocks: Construction. The construction of an IHBG protocol denoted as Π IHBG is described as follows. The commitment length is at most s(λ) = log 2 p + O(log 2 p) where (G, p) ← DHGen(1 λ ) (note that DHGen guarantees in particular p > λ ω (1) , which is needed to use the uniformity property of H). The output bit length m(λ) is an arbitrary large enough fixed polynomial poly(λ), and the public-coin length (λ) is m• +(m+2)• log 2 p . We rely on one more parameter ν(λ) and require the parameters to satisfy the following conditions:

-H = {H λ } λ = {{H : G → {0, 1}} H } λ is
-In order to prove statistical hiding, m(λ) • µ(λ) must be negligible; this holds by setting µ(λ) to be a negligible function. -For technical reasons in the hybrid games, we need a negligible gap between ν and µ; that is, ν(λ) is a negligible function satisfying µ(λ) = ν(λ) • negl(λ). -We also need 1/µ(λ) (and hence 1/ν(λ)) to be small compared to p (otherwise, assuming explicit µ-hardness of DDH over G does not make sense: a polynomial time attack with O(1/p) advantage against DDH trivially exists). In particular, µ(λ) can be set as an arbitrary close to an inverse polynomial, i.e., λ -ω (1) . Here, since 1/ν(λ) is small compared to p, any element z ∈ [1/ν(λ)] can be seen as an element of Z p .

We proceed with the description of the scheme. In the following we may omit the dependency on λ for better readability when the context is clear.

GenBits(1 λ , m, r) : On input the security parameter 1 λ , bit length m, and a public-coin r ∈ {0, 1} , parse ((r ZAP,i ) i∈ [m] , g, g M ) ← r, where g ∈ G and

M := (v|w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p
.12 Then sample z ← r [1/ν], and compute g M-z•Im+1 , where we denote

M := M -z • I m+1 = (v |w 1 | • • • |w m ) ∈ Z (m+1)×(m+1) p
. Further sample a random hash function H ← r H and a uniformly random seed y ← r Z m+1 p , and compute a commitment g s ← g y v , openings g ui ← g y w i , and the hidden bits ρ i ← H(g ui ) for all i ∈ [m]. For each i ∈ [m], set the language parameter par i := (g v , g w i ), statement x i := (g s , g ui ), and witness w := y for membership to the parametrized language L par i LPWW , and compute π ZAP,i ← r ZAP.Prove(par i , r ZAP,i , x i , w) and set π i = (g ui , π ZAP,i ). Finally, output the commitment σ := (H, g s , z) ∈ H × G × [1/ν], string ρ := (ρ i ) i∈ [m] ∈ {0, 1} m and the set of proofs {π i } i∈ [m] . VerifyBit(r, σ, i, ρ i , π i ) : Parse ((r ZAP,i ) i∈ [m] , g, g M ) ← r, (H, g s , z) ← σ, (g ui , π ZAP,i ) ← π i , and compute g M ← g M-zIm+1 . Then, set the language parameter as par i := (g v , g w i ) and the statement as x i := (g s , g ui ). Check ρ i = H(g ui ) and ZAP.Verify(par i , r ZAP,i , x i , π ZAP,i ) = .

Output if both check passes and otherwise output ⊥.

Succinctness The length of the commitment σ = (H, g s , z) only depends on the security parameter, and in particular, independent of m. This is because g s requires log 2 p bits, z requires log 2 (1/ν(λ)) ≤ log 2 p and the description of the universal hash function H requires at most O(log 2 p) bits.

Security

Correctness of our IHBG protocol can be verified by a routine check. Below, we show our IHBG protocol satisfies extractability and statistical hiding in the following Theorems 30 and 32.

Theorem 30 (Extractability). Consider µ(λ) an efficiently computable function, ε sound = ν(λ) m(λ) , and a negligible function ν(λ) such that µ(λ) = ν(λ) • negl(λ). If the IHBG-friendly ZAP for L LPWW is adaptively computational ε sound -sound w.r.t. colinear parameters and the DDH assumption is µexplicitly hard, then IHBG satisfies ν-extractability.

Proof. We show that our IHBG satisfies public-coin indistinguishability and µ-successful extraction. Public-Coin Indistinguishability. We first describe the PPT algorithm SimCoin. SimCoin starts by sampling g ← r G, v ← r Z m+1 p \{0} and α i ← r Z * p , for all i ∈ [m], and sets w i = α i v and [m] , g, g M ) as a binary string r ∈ {0, 1} . Finally, it outputs the simulated public-coin r and sets the trapdoor τ := ((α i ) i∈ [m] , z). Following textbook arguments, the following holds due to the polynomial hardness of DDH:

M := (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p . It then samples z ← r [1/ν], r ZAP,i ← r {0, 1} for all i ∈ [m]. It now computes M := M + z • I m+1 , interprets ((r ZAP,i ) i∈
Pr[r ← r {0, 1} : A(m, r) = 1] -Pr[( r, τ ) ← r SimCoin(1 λ , m) : A(m, r) = 1] ≤ negl(λ).
µ-Successful Extraction. We first describe the efficient, deterministic Open( r, σ, τ ) algorithm:

-Parse (H, g s , z) ← σ and ((α i ) i∈[m] , z) ← τ . -If z = z, then return ⊥. -Otherwise, for each bit i ∈ [m], compute ρ i := H(g s•αi ). -Return ρ = (ρ i ) i∈[m] ∈ {0, 1} m .
We proceed by a hybrid argument between PPT adversary A, PPT distinguisher D, and a challenger. We denote E i as the event that the challenger outputs 1 in Game i . Looking ahead, the probability of E occurring in the first and last games correspond to the probability of the left-hand and right-hand side of the ν-successful extraction, respectively. Game 0 : In this game, the challenger first runs ( r, τ ) ← SimCoin(1 λ , m) and invokes the adversary A on input (m, r). Once A replies with (σ, S, ρ * S , {π i } i∈S , st), the challenger computes ρ ← Open( r, σ, τ ). The challenger outputs 1 if the following holds: D(st) = 1, ρ ∈ {0, 1} m , and VerifyBit( r, σ, i, 1 -ρ i , π i ) = ⊥ for all i ∈ S. The probability the challenger outputs 1 corresponds to the left-hand side of the ν-successful extraction condition in Definition 14. Let us denote

Pr[E 0 ] := ε.
Below, we give the full description of the challenger, which receives as input the security parameter λ (in unary) and polynomial m, and proceeds as follows:

1

. g ← r G 2. v ← r Z m+1 p \{0} 3. α i ← r Z * p , for all i ∈ [m]. 4. w i ← α i v , for all i ∈ [m]. 5. M ← (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p . 6. z ← r [1/ν] 7. M ← M + z • I m+1 . 8. r ZAP,i ← r {0, 1} , for all i ∈ [m]
9. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 10. Set the extraction trapdoor as τ := ((α i ) i∈ [m] , z). 11. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 12. Run ρ ← Open( r, σ, τ ) and if ρ = ⊥, return 0. 13. Send st to D. If D replies with 0, return 0. 14. Check VerifyBit( r, σ, i, 1 -ρ i , π i ) = ⊥, for all i ∈ S. If not, return 0. 15. Return 1.

Game 1 : This game is defined identically to Game 0 , except that the challenger now performs an additional check whether z picked by the SimCoin algorithm is the same as the z it received from the adversary A. Since Open already makes this check, this is just a conceptual change and we have

Pr[E 1 ] = Pr[E 0 ].
Below, we give the full description of the challenger, where the red underline indicates the difference between the previous game:

1. g ← r G 2. v ← r Z m+1 p \{0} 3. α i ← r Z * p , for all i ∈ [m]. 4. w i ← α i v , for all i ∈ [m]. 5. M ← (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p . 6. z ← r [1/ν] 7. M ← M + z • I m+1 . 8. r ZAP,i ← r {0, 1} , for all i ∈ [m]
9. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 10. Set the extraction trapdoor as τ := ((α i ) i∈ [m] , z). 11. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 12. Parse (H, g s , z) ← σ. 13. If z = z, return 0. 14. Run ρ ← Open( r, σ, τ ) and if ρ = ⊥, return 0. 15. Send st to D. If D replies with 0, return 0. 16. Check VerifyBit( r, σ, i, 1 -ρ i , π i ) = ⊥, for all i ∈ S. If not, return 0. 17. Return 1.

Game 2 : This game is defined identically to Game 1 , except that the challenger does not verify whether for all i ∈ S, VerifyBit( r, σ, i, 1-ρ i , π i ) = ⊥. It still checks however, if ρ ∈ {0, 1} m (which is implied by the check z = z). We prove in Lemma 31 that assuming the IHBG-friendly ZAP for L LPWW is adaptively computational ε sound -sound w.r.t. colinear parameters, we have

| Pr[E 1 ] -Pr[E 2 ]| ≤ m • ε sound .
So as not to interrupt the main proof, we skip the proof of Lemma 31 to later. Below, we give the full description of the challenger:

1. g ← r G 2. v ← r Z m+1 p \{0} 3. α i ← r Z * p , for all i ∈ [m]. 4. w i ← α i v , for all i ∈ [m]. 5. M ← (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p . 6. z ← r [1/ν] 7. M ← M + z • I m+1 . 8. r ZAP,i ← r {0, 1} , for all i ∈ [m]
9. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 10. Set the extraction trapdoor as τ := ((α i ) i∈ [m] , z). 11. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 12. Parse (H, g s , z) ← σ. 13. If z = z, return 0. 14. Run ρ ← Open( r, σ, τ ) and if ρ = ⊥, return 0. 15. Send st to D. If D replies with 0, return 0. 16. Check VerifyBit( r, σ, i, 1 -ρ i , π i ) = ⊥, for all i ∈ S. If not, return 0. 17. Return 1.

Game 3 : This game is defined identically to Game 2 , except that the challenger no longer computes ρ ← Open( r, σ, τ ) and checks ρ = ⊥. Since in Game 2 , the check z = z (which is equivalent to the check ρ = ⊥) is done prior to calling Open, and because ρ is not used at any point in Game 2 , this is simply a syntactic change and the two games are equivalent and we have

Pr[E 2 ] = Pr[E 3 ].
Below, we give the full description of the challenger:

1. g ← r G 2. v ← r Z m+1 p \{0} 3. α i ← r Z * p , for all i ∈ [m]. 4. w i ← α i v , for all i ∈ [m]. 5. M ← (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p . 6. z ← r [1/ν] 7. M ← M + z • I m+1 . 8. r ZAP,i ← r {0, 1} , for all i ∈ [m]
9. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 10. Set the extraction trapdoor as τ := ((α i ) i∈ [m] , z). 11. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 12. Parse (H, g s , z) ← σ. 13. If z = z, return 0. 14. Run ρ ← Open( r, σ, τ ) and if ρ = ⊥, return 0. 15. Send st to D. If D replies with 0, return 0. 16. Return 1.

Game 4 : This game is defined identically to Game 3 , except that the challenger samples a uniformly random matrix M ← r Z (m+1)×(m+1) p rather than running SimCoin. As in Game 3 , the challenger still samples z ← r [1/ν] and checks whether z = z. Identically to the proof for public-coin indistinguishability, due to the µ-explicit hardness of DDH 13 , we have

| Pr[E 3 ] -Pr[E 4 ]| ≤ µ(λ).
Below, we give the full description of the challenger:

1. g ← r G 2. M ← r Z (m+1)×(m+1) p . 3. z ← r [1/ν] 4. M ← M + z • I m+1 . 5. r ZAP,i ← r {0, 1} , for all i ∈ [m]
6. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 7. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 8. Parse (H, g s , z) ← σ. 9. If z = z, return 0. 10. Send st to D. If D replies with 0, return 0. 11. Return 1.

Game 5 : This game is defined identically to Game 4 , except that the challenger directly samples a uniformly random matrix M ← r Z (m+1)×(m+1) p

. Since the distributions of M are identical in both Game 4 and Game 5 , we have

Pr[E 4 ] = Pr[E 5 ].
At this point, notice that z is information theoretically hidden from A and D. Therefore, the probability z = z is ν regardless of all the other randomness. The description of the challenger is as follows:

1. g ← r G 2. M ← r Z (m+1)×(m+1) p . 3. z ← r [1/ν] 4. M ← r Z (m+1)×(m+1) p . 5. r ZAP,i ← r {0, 1} , for all i ∈ [m]
6. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 7. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 8. Parse (H, g s , z) ← σ. 9. If z = z, return 0. 10. Send st to D. If D replies with 0, return 0. 11. Return 1.

Game 6 : This game is defined identically to Game 5 , except that matrix M is again computed as M ← M + z • I m+1 for some other z sampled uniformly and independently of z. Since matrix M remains uniformly random, the distributions of Game 5 and Game 6 are identical. Hence,

Pr[E 5 ] = Pr[E 6 ].
The description of the challenger is as follows:

1. g ← r G 2. M ← r Z (m+1)×(m+1) p . 3. z ← r [1/ν] 4. z ← r [1/ν] 5. M ← M + z • I m+1 . 6. r ZAP,i ← r {0, 1} , for all i ∈ [m]
7. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 8. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 9. Parse (H, g s , z) ← σ. 10. If z = z, return 0. 11. Send st to D. If D replies with 0, return 0. 12. Return 1.

Game 7 : This game is defined identically to Game 6 , except that matrix M is again chosen as a rank 1 matrix. (meaning that r is again generated as the output of SimCoin). Identically to the transition we made to move from Game 3 to Game 4 , due to the µ-explicit hardness of DDH, we have

| Pr[E 6 ] -Pr[E 7 ]| ≤ µ(λ)
.

The description of the challenger is as follows:

1. g ← r G 2. v ← r Z m+1 p \{0} 3. α i ← r Z * p , for all i ∈ [m]. 4. w i ← α i v , for all i ∈ [m]. 5. M ← (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p . 6. z ← r [1/ν] 7. z ← r [1/ν] 8. M ← M + z • I m+1 . 9. r ZAP,i ← r {0, 1} , for all i ∈ [m]
10. Set the simulated public-coin as r := ((r ZAP,i ) i∈ [m] , g, g M ) ∈ {0, 1} . 11. Set the extraction trapdoor as τ := ((α i ) i∈ [m] , z ). 12. Send (m, r) to A, which replies with (σ, S, ρ * S , {π i } i∈S , st). 13. Parse (H, g s , z) ← σ. By using the triangle inequality, we have therefore shown the following bound:

| Pr[E 0 ] -Pr[E 7 ]| ≤ 2 • µ(λ) + m • ε sound = ν(λ) • negl(λ),
where the equality comes from our choice of ε sound and ν(λ). Moreover, observe that in Game 7 , z is information theoretically hidden from A and D. Therefore, the probability of z = z is ν regardless of all the other randomness. Namely, we have the following: Proof. Observe that Game 1 and Game 2 will only differ in the event that VerifyBit( r, σ, i * , 1-ρ i * , π i * ) = for some i * ∈ S. Let us call this event F. Then we have

Pr[E 7 ] = Pr[z = z] • Pr ( r, τ ) ← r SimCoin(1 λ , m) (σ, S, ρ * S , {π i } i∈S , st) ← r A(m, r) : D(st) = 1 , = ν(λ) • Pr ( r, τ ) ← r SimCoin(1 λ , m) (σ, S, ρ * S , {π i } i∈S , st) ← r A(m,
| Pr[E 1 ] -Pr[E 2 ]| ≤ Pr[F]
. Below, we upper bound Pr[F] by constructing an adversary B, which runs A internally, against the adaptive computational ε sound -soundness w.r.t. colinear parameters of the IHBG-friendly ZAP for L LPWW . The description of B follows: 14B receives a random language parameter par = (g v , g w ) ∈ Col(G) and a public-coin r ZAP ∈ {0, 1} as the problem instance, where note that w = α • v for some α ∈ Z * p . 15 First, B samples a random index i * ← r [m] and sets par i * := par and r ZAP,i * := r ZAP , which implicitly sets w i * := w . It then further samples r ZAP,i ← r {0, 1} and α i ← r Z * p for all i ∈ [m]\{i * } and sets g w i = (g w ) αi . Note that B can compute everything without knowledge of the secret exponents (v , w ). B then samples z ← r [1/ν] and computes g M = g M +z•Im+1 , where M is implicitly set as

(v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p
. B sets the simulated public-coin of the Π IHBG as r = ((r ZAP,i ) i∈ [m] , g M ), and invokes A on input (m, r). When A outputs (σ, S, ρ * S , {π i } i∈S , st), B parses (H, g s , z) ← σ and (g u i * , π ZAP,i * ) ← π i * , and outputs its forged statement-proof pair as (x * := (g s , g u i * ), π * ZAP := π ZAP,i * ). We analyze the behavior of B. First, since the given language parameter par is a random element over Col(G), B perfectly simulates the view of A in both Game 1 and Game 2 . Next, we show x * = (g s , g u i * ) / ∈ L par LPWW . By contradiction, assume (g s , g u i * ) ∈ L par LPWW . Namely, there exists some y ∈ Z d p such that s = y v and u i * = y w. Now, due to the definition of the Open algorithm, we have

ρ i * = H(g α•s
). On the other hand, since VerifyBit( r, σ, i * , 1 -ρ i * , π i * ) = , we have 1 -ρ i * = H(g u i * ). However, since u i * = y w = α • y v = α • s, the output of the hash function H cannot be different. Therefore, we have x * = (g s , g u i * ) / ∈ L par LPWW . Then, since i * ∈ [m] is statistically hidden from A, conditioning on event F occuring, we have x * / ∈ L par LPWW and ZAP.Verify(par, r ZAP , x * , π * ZAP ) = with probability 1/m. Therefore, due to the adaptive computational sound -soundness w.r.t. colinear parameters of the IHBG-friendly ZAP, we obtain Pr[F] ≤ m • sound . This concludes the proof.

Theorem 32 (Statistical Hiding). If the IHBG-friendly ZAP for L LPWW is doubly-adaptive statistically witness indistinguishable, the hash function family H is universal, and ν(λ) is negligible, then Π IHBG is statistically hiding.

Proof. We first provide the description of the simulator Sim used to simulate the commitment σ and proof for opening {π i } i∈S below: Sim(m, r, S, ρ S ): On input a polynomial m, public-coin r, set S, and hidden-bits string ρ S , it proceeds as follows: : H(g (y ) w i ) = ρ i , for all i ∈ S} (inefficiently). 9. If Y = ∅, return 0. 10. y ← r Y . 11. g s ← g y v and g ui ← g y w i , for all i ∈ S. 12. Set the language parameter par i := (g v , g w i ) and the statement x i := (g s , g ui ) for the language L par i LPWW , for all i ∈ S. 13. π ZAP,i ← r ZAP.Prove(par i , r ZAP,i , x i , y), for all i ∈ S. 14. π i ← (g ui , π ZAP,i ), for all i ∈ S. 15. σ ← (H, g s , z). 16. Return (σ, {π i } i∈S ).

1. Parse ((r ZAP,i ) i∈[m] , g, g M ) ← r. 2. H ← r H. 3. z ← r [1/ν]. 4. g M ← g M-z•Im+1 . 5. Recover matrix M := (v |w 1 | • • • |w m ) ∈ Z (m+1)×(
We consider the following sequence of games between an unbounded adversary A = (A 0 , A 1 ) and a challenger, where the first and last games corresponding respectively to the honest game using GenBits and simulated game using Sim of the statistical-hiding property in Definition 14. We denote E i as the event that the challenger outputs 1 in Game i .

Game 0 : This game is the same as the real game where the challenger uses GenBits to generate the hidden-bits. By definition, we have Pr[E 0 ] = .

Below, we give the full description of the challenger, which receives as input the security parameter λ (in unary), polynomial m and public-coin r, and proceeds as follows:

1. Parse ((r ZAP,i ) i∈[m] , g, g M ) ← r. 2. H ← r H. 3. z ← r [1/ν]. 4. g M ← g M-z•Im+1 . 5. y ← Z m+1 p .
6. g s ← g y v and g ui ← g y w i , for all i ∈ S, where

M := (v |w 1 | • • • |w m ) ∈ Z (m+1)×(m+1) p . 7
. Set the language parameter par i := (g v , g w i ) and the statement x i := (g s , g ui ) for the language L par i LPWW , for all i ∈ S. 8. π ZAP,i ← r ZAP.Prove(par i , r ZAP,i , x i , y), for all i ∈ [m]. 9. π i ← (g ui , π ZAP,i ), for all i ∈ [m]. 10. σ ← (H, g s , z). 11. ρ i ← H(g ui ), for all i ∈ [m]. 12. Send ρ := (ρ i ) i∈ [m] to A 0 , which replies with a set S. If S ⊆ [m], return 0. 13. Send (r, S, ρ, σ, {π i } i∈S ) to A 1 . If A 1 replies with 1, return 1, otherwise, return 0.

Game 1 : This game is defined identically to Game 0 , except that GenBits is modified as follows:

Upon computing g M = g (v |w 1 |...|w m ) , the challenger recovers the discrete logarithms, obtaining v , w 1 , . . . , w m . Then, it picks (s u) ← r Z m+1 p and computes y = M -1 (s u), where we show M is invertible with overwhelming probability for our parameter choice ν and m. We later prove in Lemma 33 that we have

|Pr[E 0 ] -Pr[E 1 ]| ≤ (m + 1) • ν(λ).
The description of the challenger is as follows:

1. Parse ((r ZAP,i ) i∈ [m] , g, g M ) ← r. 8. Set the language parameter par i := (g v , g w i ) and the statement x i := (g s , g ui ) for the language L par i LPWW , where u i denotes the i-th entry of u, for all i ∈ [m]. 9. y ← M -1 (s u). 10. π ZAP,i ← r ZAP.Prove(par i , r ZAP,i , x i , y), for all i ∈ [m]. 11. π i ← (g ui , π ZAP,i ), for all i ∈ [m]. 12. σ ← (H, g s , z). 13. ρ i ← H(g ui ), for all i ∈ [m]. 14. Send ρ := (ρ i ) i∈ [m] to A 0 , which replies with a set S. If S ⊆ [m], return 0. 15. Send (r, S, ρ, σ, {π i } i∈S ) to A 1 . If A 1 replies with 1, return 1, otherwise, return 0.

Game 2 : This game is defined identically to Game 1 , except that u is sampled differently. First, the challenger picks u ← r Z m p , and then it samples u ← r {u ∈ Z m p : H(g u i ) = H(g u i ), for all i ∈ S}, which it can do since computing the set of all valid u can be done inefficiently. For completeness, we later formally prove in Lemma 34 that we have

Pr[E 1 ] = Pr[E 2 ].
The description of the challenger is as follows:

1. Parse ((r ZAP,i ) i∈ [m] , g, g M ) ← r.

2. H ← r H.

3. z ← r [1/ν]. 4. g M ← g M-z•Im+1 . 5. Recover M := (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p by brute force. 6. If M is not full-rank, return 0. 7. (s u ) ← r Z m+1 p . 8. ρ i ← H(g u i ), for all i ∈ [m]
, where u i denotes the i-th entry of u . 9. Send ρ := (ρ i ) i∈ [m] to A 0 , which replies with a set S. If S ⊆ [m], return 0. 10. Compute U = {u ∈ Z m p : H(g u i ) = ρ i , for all i ∈ S} (inefficiently). 11. u ← r U . 12. Set the language parameter par i := (g v , g w i ) and the statement x i := (g s , g ui ) for the language L

par i LPWW for all i ∈ [m]. 13. y ← M -1 (s u). 14. π ZAP,i ← r ZAP.Prove(par i , r ZAP,i , x i , y), for all i ∈ [m]. 15. π i ← (g ui , π ZAP,i ), for all i ∈ [m].
16. σ ← (H, g s , z). 17. Send (r, S, ρ, σ, {π i } i∈S ) to A 1 . If A 1 replies with 1, return 1, otherwise, return 0.

Game 3 : This game is defined identically to Game 2 , except for the hidden-bits generation procedure, which now first samples ρ ← r {0, 1} m and then uniformly randomly picks u such that H(g ui ) = ρ i for all i ∈ S, if such u exists. We later prove in Lemma 35 that, due to the statistical uniformity of the hash function, we have

| Pr[E 2 ] -Pr[E 3 ]| ≤ negl(λ).
The description of the challenger is as follows:

Game 4 : This game is defined identically to Game 3 , except that it only samples the necessary entries in u and samples an additional vector y r uniformly at random, conditioned on the fact that g (y r ) v = g s and g (y r ) w i = g ui , for all i ∈ S. Then, the proofs {π ZAP,i } i∈S are computed using witness y r instead of witness y. We later prove in Lemma 36 that, due to the doubly-adaptive statistical witness indistinguishability of the IHBG-friendly ZAP for L LPWW , we have

| Pr[E 3 ] -Pr[E 4 ]| ≤ negl(λ).
The description of the challenger is as follows, where note that Y s,u = ∅ is guaranteed in case the challenger hasn't returned 0:

1. Parse ((r ZAP,i ) i∈[m] , g, g M ) ← r. 2. H ← r H. 3. z ← r [1/ν]. 4. g M ← g M-z•Im+1 . 5. Recover M := (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p
by brute force. 6. If M is not full-rank, return 0. 7. ρ i ← {0, 1} m , for all i ∈ [m]. 8. Send ρ := (ρ i ) i∈ [m] to A 0 , which replies with a set S. If S ⊆ [m], return 0. 9. Compute U = {u ∈ Z S p : H(g u i ) = ρ i , for all i ∈ S} (inefficiently), where x ∈ Z S p is a vector of length |S| indexed by the elements in the set S 10. If U = ∅, return 0. 11. u ← r U . 12. s ← r Z p . 13. Set the language parameter par i := (g v , g w i ) and the statement x i := (g s , g ui ) for the language L par i LPWW , for all i ∈ S. 14. Compute Y s,u := {y ∈ Z m+1 p : g (y ) v = g s ∧ g (y ) w i = g ui , for all i ∈ S} (inefficiently). 15. y r ← r Y s,u . 16. π ZAP,i ← r ZAP.Prove(par i , r ZAP,i , x i , y r ), for all i ∈ S. 17. π i ← (g ui , π ZAP,i ), for all i ∈ S. 18. σ ← (H, g s , z). 19. Send (r, S, ρ, σ, {π i } i∈S ) to A 1 . If A 1 replies with 1, return 1, otherwise, return 0.

Game 5 This game is defined identically to Game 4 , except that it now first samples y uniformly at random, conditioned on the fact that H(g y w i ) = ρ i , for all i ∈ S. It then computes g s = g y v and g ui = g y w i for all i ∈ S. Namely, the order of operations is switched: in Game 4 , first u and s are sampled and y is determined afterwards, while in Game 5 , the challenger first samples y and only after it can compute u and s accordingly. We later prove in Lemma 37 that we have

Pr[E 4 ] = Pr[E 5 ].
The description of the challenger is as follows:

This concludes the proof of Lemma 23. Plugging this IHBG-friendly adaptive statistical ZAP for L LPWW into the construction of IHBG of Section 5 and combining it with the construction of statistical ZAP for NP from any IHBG from Section 3, we get our first main theorem:

Theorem 40 (Statistical ZAPs in Pairing Groups). Assume that the explicit µ-hardness of the DDH assumption holds in a group G 1 , and the explicit (µ/m)-hardness of the kernel Diffie-Hellman assumption holds in a group G 2 , where (G 1 , G 2 ) are groups equipped with a bilinear pairing, m is the output length of the IHBG protocol, and for any negligible function µ (which can be arbitrarily close to an inverse polynomial function). Then there exists an adaptive statistically witness indistinguishable ZAP for NP with non-adaptive computational soundness.

As we mentioned in the preliminaries, the above theorem can be easily generalized to hold under any of the more general family of Diffie-Hellman assumption, such as the (decisional and kernel) matrix Diffie-Hellman assumption [15,[START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF] (which includes for example the k-Lin assumption from [START_REF] Hofheinz | Secure hybrid encryption from weakened key encapsulation[END_REF]).

6.2 Second Construction: a Statistical ZAP for L LPWW in Pairing-Free Groups A Correlation-Intractable Hash Function for R LPWW . Let λ be the security parameter. We consider a group G of order q(λ) with log q ≈ λ. Let Trunc : G → {0, 1} λ/2 be the function which, on input a group element G ∈ G, parses it as a log q -bit string and returns the first λ/2 bits of its input. We consider the following hash function H : G2 × Z q → {0, 1} λ/2 based on secret key ElGamal:

-Sampling the key: sample ( G, k, m) ← r G × Z 2 q and set the hash key as C ← r Enc G(k, m). Note that the key distribution is exactly the uniform distribution over G2 due to universality (see Definition 7).

-Evaluating H( C, •) : H( C, x) = Trunc(HalfDec(x, C)).
Correlation-Intractability of H. Fix a parameter n ∈ N. Consider a group G of order p(λ) with log p ≈ λ/2n. Fix a parameter t ∈ Z * p and define the set of parameters

Λ t := {(g v , g t•v )} v∈Z m+1 p \{0} ⊂ Λ = (G d \{1})
where α := {(R i , S i )} i∈[n] , β := {e i } i∈[n]
, and γ := {d i } i∈[n] in Figure 1. Here, the above relation can also be described alternatively using the following (inefficient) randomized function:

f t (α; z) : G 2n × Z * p → (Z * p ) n ((R i , S i ) i∈[n] , z) → (z, ((log (R t 1 /S1) (R t i /S i )) • z) i∈[2,n] )
.

Given this function, it is straightforward (albeit tedious) to check that the relation rewrites to

R sparse LPWW,t = {(α, β) ∈ G 2n × (Z * p ) n : ∃z ∈ Z * p , f t (α; z) = β}.
The following is the main contribution of this section.

Theorem 41. Assume that ElGamal satisfies 2 -λ/2 -OW-KDM security with respect to efficient functions. Let R sparse LPWW = {R sparse LPWW,λ } λ = {{R sparse LPWW,λ,t } t∈Z * p } λ be the family of parameterized sparse relation induced by L LPWW . Then the hash family H = {H : G2 × Z q → {0, 1} λ/2 } λ satisfies (ε, R sparse LPWW )correlation intractability for every negligible function ε satisfying ε(λ) = 2 -o(λ) .

Remark 42. Theorem 41 should be compared to Theorem 24 from [10]: in [10], the authors restricted their attention to a Σ-protocol with only two parallel repetitions (the language we consider is also different, but this does not matter for the conclusion -both the DDH language from [10] and the LPWW language could be used in their construction). As a consequence, they could only build a correlation-intractable hash function for their relation from the 2 -3λ/4 -OW-KDM hardness of ElGamal. By considering the general case of n parallel repetitions, and adjusting n appropriately, we significantly strenghthen their conclusion and manage to rely on the 2 -λ/2 -OW-KDM hardness of ElGamal. By Definition 8, this means that no PPT adversary has significantly better advantage than 2 -(1/2+o(1))•λ , where the o(1) in the exponent can be made smaller than 1/λ ε for any constant ε < 1. Beyond this simple generalization, our analysis is essentially identical to that of [10]; we provide it below for the sake of completeness.

Proof. Toward proving the above theorem, we first establish the main lemma on which the proof will be based: Lemma 43. Let A be an adrversary against the (ε, R sparse LPWW )-correlation intractability of H. Then, it holds for some t ∈ Z * p that:

Pr ( G,a * ,m)←r G×Z 2 q C←rEnc G (a * ,m) [A( G, C) = a * |(a * , H( C, a * )) ∈ R sparse LPWW,t ] ≥ ε(λ) 2 λ 2 •(1+ 1 n ) .
Proof. The proof is almost identical to the proof of [10], generalized to handle an arbitrary number n of parallel repetitions. We provide it for completeness. If H is a CIH for R sparse LPWW , then there exists

t ∈ Z * p such that Pr   ( G, k, m) ← r G × Z 2 q C ← r Enc G(k, m) : (a, H( C, a)) ∈ R sparse LPWW,t a ← r A( G, C)   ≥ ε(λ).
Consider sampling independently a random input a * ← r Z q . Then we have:

Pr   ( G, k, m) ← r G × Z 2 q a * ← r Z q : A( G, C) = a * ∧ (a * , H( C, a * )) ∈ R sparse LPWW,t C ← r Enc G(k, m)   ≥ ε(λ) 2 λ ,
Using the (perfect) universality of ElGamal, this becomes

Pr   ( G, m) ← r G × Z q a * ← r Z q : A( G, C) = a * ∧ (a * , H( C, a * )) ∈ R sparse LPWW,t C ← r Enc G(a * , m)   ≥ ε(λ) 2 λ .
We now introduce another (inefficient) randomized function α t :

α t ( G, a; z 1 , z 2 ) : G × Z q × {0, 1} λ/2 × Z * p → Z q ( G, a; z 1 , z 2 ) → dlog G(f t (a; z 2 )||z 1 )
Using this function α t , the previous inequality can be rewritten as Furthermore, it holds that for any i,

Pr   ( G, m) ← r G × Z q a * ← r Z q : A( G, C) = a * ∧ ∃(z 1 , z 2 ), m = α t ( G, a * ; z 1 , z 2 ) C ← r Enc G(a * , m)   ≥ ε(λ) 2 λ ,
Pr m←rZq [∃(z 1 , z 2 ), m = α t ( G, i; z 1 , z 2 )] ≤ 2 -λ 2 •(1-1 n ) .
Indeed, the statement is equivalent to "∃(z 1 , z 2 ), Gm = f t (i; z 2 )||z 1 ", which further translates to "there exists z 2 ∈ Z * p such that the first half of the bits of Gm are equal to f t (i; z 2 )". Since a random string from {0, 1} λ/2 is equal to f t (i; z 2 ) with probability 2 -λ/2 for a fixed z 2 , by taking a union bound over all possible values of z 2 ∈ Z * p , where |Z * p | = 2 λ/2n , we get the result. Hence, we get: .

Pr   ( G, a * ) ← r G × Z q m ← r S t, G,a * : A( G, C) = a * C ← r Enc G(a * , m)   ≥ 2 -λ 2 •(1-1 n ) • q-1 i=0
This concludes the proof of the lemma.

It remains to show that this implies a contradiction to the OW-KDM security of ElGamal for efficient functions. The above can be rewritten as Pr ( G,a * )←r G×Zq m←rαt( G,a * ) C←rEnc G(a * ,m)

[A( G, C) = a * ] ≥ ε(λ) 2 λ 2 •(1+ 1 n ) , (1)
with α t : G × Z q × {0, 1} λ/2 × Z * p → Z q , such that α t ( G, a; z 1 , z 2 ) = dlog G(f t (a; z 2 )||z 1 ). This naturally translates to an adversary against the OW-KDM security of ElGamal where m is sampled as α t ( G, a * ; z 1 , z 2 ), but the main difficulty is that α t is not an efficiently computable function. To get around this apparent issue, we use the exact same strategy as [10]. Define the (randomized) efficiently computable function f -1 t as follows: ((e i ) i∈[n] ; (r i ) i∈[n] , s 1 ) → (g r1 , g s1 , (g ri , g

e i (t•r 1 -s 1 ) e 1

-t•ri ) i≥2 ).

Furthermore, define F t to be the following (efficient, randomized) function:

F t ( G, m; z) : G × Z q × {0, 1} λ 2 •(1+ 1
n ) → Z q ( G, m; z) → f -1 t (Trunc( Gm ); z), .

Let A be the previous adversary, which satisfies Equation (1). Consider the distribution of ( G, a * , m) where we first sample ( G, a * ) ← r G × Z p and set m ← r α t ( G, a * ). Then, this is equivalent the distribution where we first sample ( G, m) ← r G × Z q and then set a * ← r F t ( G, m). Therefore, we have IHBG-Friendly Statistical ZAP for L LPWW in Pairing-Free Groups. Equipped with the above correlation-intractable hash function, we are now ready to give our construction of our IHBG-friendly statistical ZAP. We note that this construction will actually satisfy a stronger soundness notion than required for an IHBG-friendly ZAP: adaptive computational soundness will hold for any parameters (an not just only for parameters sampled uniformly from Col(G d )). 16 Let G be a group of order p, and let G be a group of order q such that log q ≈ λ ≈ 2 log p 2 . Let Π Σ be the Σ-protocol for L LPWW , with repetition parameter n = log p . Let P 1 , P 2 and V be the corresponding algorithms for the first and second move of the prover and the verifier, respectively. let H : G2 × Z q → {0, 1} λ/2 be the correlation intractable hash function constructed above.

Pr

Construction. The construction of an IHBG-friendly statistical ZAP for L LPWW with public coin length = 2 log q , denoted as Π ZAP , is described as follows.

-ZAP.Prove(par, r, x, w) : On input parameters par = (g, h), a public coin r ∈ {0, 1} , a statement

x := (X, Y ) ∈ L LPWW and a witness w := y such that (X, Y ) = ((g ) y , (h ) y ), run α ← r P 1 (par, x, w) and compute β = H(r, α), where r provides the description of the CIH hash H. Parse β as an element of (Z * p ) n , and further run γ ← r P 2 (par, x, w, α, β). Finally, output π ZAP = (α, γ). -ZAP.Verify(par, r, x, π ZAP ) : On input parameters par = (g, h), a public coin r ∈ {0, 1} , a statement x, and a proof π ZAP , parse π ZAP as (α, γ) ← π ZAP . Then, compute β = H(r, α) and output if V (par, x, α, β, γ) = . Otherwise, output ⊥.

Completeness follows from the completeness of the underlying Σ-protocol.

Lemma 44. For any parametrized language L par LPWW over G, the above construction satisfies doublyadaptive perfect witness indistinguishability.

Proof. As for the previous construction, this follows directly from the adaptive statistical witness indistinguishability of the underlying Σ-protocol: any attack against the witness indistinguishability of the above construction can be trivially lifted to an attack on the underlying Σ-protocol (with the same advantage), by simulating the ZAP prover by feeding the Σ-protocol prover the challenge β = H(r, α), where r is any public-coin and α is the first flow from the Σ-protocol prover.

Lemma 45. For any parametrized language L par LPWW over G, the above construction satisfies adaptive computational ε sound -soundness w.r.t. colinear parameters par ∈ Col(G d ) under the (ε sound , R sparse LPWW )correlation-intractability of H.

Proof. Suppose there exists a PPT adversary A against the adaptive computational ε sound soundness of the above construction. Then there exists some par ∈ Col(G d ) such that Pr[r ← {0, 1} , (x, π) ← r A(par, r) : x ∈ L par ∧ Verify(par, r, x, π) = ] ≤ sound .

Let t be such that par = (g v , g t•v ). Parse (X, Y ) ← x and (α, γ) ← π. Then, since x ∈ L par LPWW and (α, β, γ) is an accepting proof, we have (α, β) ∈ R sparse LPWW,t . Thus, using A, we can construct a PPT adversary A such that Pr k←r G2 α←rA(k)

[(α, H(k, α)) ∈ R sparse LPWW,t ] ≥ ε sound .

However, this contradicts the (ε sound , R sparse LPWW )-correlation intractability of our hash function.

This concludes the proof of Lemma 24. Plugging this IHBG-friendly adaptive statistical ZAP for L LPWW into the construction of IHBG of Section 5 and combining it with the construction of statistical ZAP for NP from any IHBG from Section 3, we get our second main theorem:

Theorem 46 (Statistical ZAPs in Pairing-Free Groups). Assume that the explicit µ-hardness of the DDH assumption holds in a group G of order p for any negligible function µ (which can be arbitrarily close to an inverse polynomial function), and that the 2 -λ/2 -OW-KDM security of ElGamal holds over a group G of order q such that log q ≈ λ ≈ 2 log p 2 . Then there exists an adaptive statistically witness indistinguishable ZAP for NP with non-adaptive computational soundness.

As we mentioned in the preliminaries, the above theorem can be easily generalized to hold under any of the more general family of Diffie-Hellman assumption, such as the (decisional and kernel) matrix Diffie-Hellman assumption [15,[START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF] (which includes for example the k-Lin assumption from [START_REF] Hofheinz | Secure hybrid encryption from weakened key encapsulation[END_REF]).

r); 3 . 2 :

 32 (S, π HBM ) ← r HBM.Prove(hb, x, w 0 ), where hb := ρ ⊕ ∆; 4. Output π ZAP = (σ, S, ρ S , {π IHBG,i } i∈S , π HBM ). By definition, we have Pr[A 1 (st, π ZAP )] = Pr[E 0 ]. Game We modify how the challenger computes the proof π ZAP . It uses the (possibly unbounded) simulator IHBG.Sim guaranteed by the statistically hiding property of IHBG to simulate the proofs {π IHBG,i } i∈S for the opening of the hidden-bits. Concretely, the challenger performs the following instead of running ZAP.Prove(r , x, w 0 ), where the red underline indicates the difference between the previous game. 1. Parse (r, ∆) ← r ; 2. Sample ρ ← r {0, 1} m ; 3. (S, π HBM ) ← r HBM.Prove(hb, x, w 0 ), where hb := ρ ⊕ ∆; 4. (σ, {π IHBG,i } i∈S ) ← r IHBG.Sim(m, r, S, ρ S ); 5. Output π ZAP = (σ, S, ρ S , {π IHBG,i } i∈S , π HBM ).

Game 3 : 4 : 5 :

 345 We further modify how the challenger computes the proof π ZAP . It uses the zero-knowledge simulator HBM.Sim guaranteed by the perfect zero-knowledge of the NIZK in the hidden-bits model to compute the proof π HBM . Concretely, the challenger performs the following, where the red underline indicates the difference between the previous game. Here, notice that the challenger no longer uses the witness w 0 .1. Parse (r, ∆) ← r ; 2. (S, hb S , π HBM ) ← r HBM.Sim(x); 3. ρ S ← hb S ⊕ ∆ S ; 4. (σ, {π IHBG,i } i∈S ) ← r IHBG.Sim(m, r, S, ρ S ) 5. Output π ZAP = (σ, S, ρ S , {π IHBG,i } i∈S , π HBM ). Game We undo the change we made to move from Game 2 to Game 3 , except that the challenger uses witness w 1 instead of w 0 to compute π HBM in Item 3 of Game 2 . Game We undo the change we made to move from Game 1 to Game 2 . This game is the real game where the challenger uses witness w 1 .

Lemma 21 .

 21 If Π HBM has perfect zero-knowledge, then we have Pr[E 2 ] = Pr[E 3 ].

  Correctness: For any λ ∈ N, r ∈ {0, 1} , par ∈ Λ λ , and (x, w) ∈ R par LPWW,λ , we have Pr[Verify(par, r, x, Prove(par, r, x, w)) = ] = 1. (Adaptive) Computational ε sound -Soundness w.r.t. Colinear Parameters: For any λ ∈ N and PPT adversary A, we have Pr par ← r Col(G d ), r ← {0, 1} , (x, π) ← r A(par, r) :x ∈ L par LPWW,λ ∧ Verify(par, r, x, π) = ≤ sound .

p

  conditioned on v z = r and w z = s. Then, for any witness y ∈ W, the third message d follows the distribution D y d where we first sample z ← r D z and output d ← e • y + z. Observe that by the definition of D z , the probability of any d being sampled form D y d and D y d for any two witnesses y, y ∈ W is identical. In particular, we have D y d = D y d for any y, y ∈ W. Combining all the arguments together, the statement follows.Lemma 29 (Adaptive Soundness). The IHBG-friendly Σ-protocol for the family of parametrized languages L LPWW = {L par LPWW } par∈Λ in Figure1satisfies adaptive ( 1 p-1 ) n-1 -soundness.

  a family of universal hash functions with description size of at most O(log 2 p) bits, where G and p are implicitly parameterized by the security parameter.-Π ZAP = (ZAP.Prove, ZAP.Verify) is an IHBG-friendly ZAP for the parametrized family of languages L LPWW = {L LPWW,λ } λ = {{L par LPWW,λ } par∈Λ λ } λ with public-coin length (λ), satisfying adaptive computational sound -soundness w.r.t. colinear parameters for sound = µ(λ) m(λ) and doubly-adaptive statistical witness indistinguishability. Here, we set the vector length parameter d(λ) in L LPWW,λ to m(λ) + 1, where m(λ) is the polynomial output bit length of the IHBG protocol defined below.

14 .

 14 If z = z, return 0. 15. Send st to D. If D replies with 0, return 0. 16. Return 1.

= 1 .

 1 Now notice that this corresponds to the probability in the right-hand side of the ν-successful extraction condition in Definition 14. Since Pr[E 0 ] corresponded to the probability in the left-hand side, this completes the proof of the theorem. It only remains to prove Lemma 31 below. Lemma 31. If the IHBG-friendly ZAP for L LPWW is adaptively computational ε sound -sound w.r.t. colinear parameters, then we have | Pr[E 1 ] -Pr[E 2 ]| ≤ m • ε sound .

2 .

 2 H ← r H. 3. z ← r [1/ν]. 4. g M ← g M-z•Im+1 . 5. Recover M := (v |w 1 | . . . |w m ) ∈ Z (m+1)×(m+1) p by brute force. 6. If M is not full-rank, return 0. 7. (s u) ← r Z m+1 p .

m

  since given C ← r Enc G(a * , m), it holds that(a * , H( C, a * )) ∈ R sparse LPWW,t ⇐⇒ Trunc(HalfDec(a * , C)) = f t (a * ; z 2 ) (for some z 2 ) ⇐⇒ Trunc( Gm ) = f t (a * ; z 2 ) ⇐⇒ ∃z 1 , z 2 , Gm = f t (a * ; z 2 )||z 1 ⇐⇒ ∃z 1 , z 2 , m = α t ( G, a * ; z 1 , z 2 ). Let S t, G,a * := {α t ( G, a * ; z 1 , z 2 ) : (z 1 , z 2 ) ∈ {0, 1} λ/2 × Z * p }be the set of elements in G (i.e., nontruncated challenge) for which there exists an accepting last flow and word with a * as the first flow. Now, observe that the probability in the statement becomes:Pr   ( G, a * ) ← r G × Z q m ← r S t, G,a * : A( G, C) = a * C ← r Enc G(a * , m) ← r S t, G,i : A( G, C) = i C ← r Enc G(i, m) [a * = i] • Pr ( G, m) ← r G × Z q : A( G, C) = i C ← r Enc G(i, m) ∧ (∃z 1 , z 2 , m = α t ( G, i; z 1 , z 2 ))Pr[( G, m) ← r G × Z q : ∃z 1 , z 2 , m = α t ( G, i; z 1 , z 2 )]

= 2 -λ 2 •( 1 - 1 n

 2211 Pr a * ←rZq [a * = i] • Pr ( G, m) ← r G × Z q : A( G, C) = i C ← r Enc G(i, m) ∧ (∃(z 1 , z 2 ), m = α t ( G, i; z 1 , z 2 )) ) • Pr ( G, m, a * ) ← r G × Z 2 q : A( G, C) = a * C ← r Enc G(a * , m) ∧ (∃(z 1 , z 2 ), m = α t ( G, a * ; z 1 , z 2

f - 1 t

 1 ((e i ) i∈[n] ; (r i ) i∈[n] , s 1 ) := (Z * p ) n × Z n+1 p → G 2n

(.,

  G,k)←r G×Zq a * ←rFt( G,k) C←rEnc G(a * ,k) [A( G, C) = a * ] ≥ εWe can now build an adversary B against the OW-KDM security of ElGamal for efficient functions as follows: on input ( G, C), B parses C as ( C0 , C1 ). B sets G ← C0 and C ← ( G, C1 ). Then, B runs A( G , C ) and outputs whatever A outputs. Observe that the distributions{( G, C) : ( G, k) ← r G × Z q , a * ← r F t ( G, k), C ← r Enc G(a * , k)},which corresponds to the experiment in the previous probability, and{( C0 , ( G, C1 )) : ( G, k) ← r G × Z q , a * ← r F t ( G, k), ( C0 , C1 ) ← r Enc G(k, a * )} are identical. Therefore, Pr ( G,k)←r G×Zq a * ←rFt( G,k) C←rEnc G(k,a * ) [B( G, C) = a * ] ≥ ε(λ)which contradicts the (one-query) 2 -(1+1/n)λ/2-o(λ) -hardness of OW-KDM security of ElGamal with respect to the family of (efficient, randomized) functions {F t } t (recall that ε(λ) = 2 -o(λ) ). To conclude the proof of Theorem 41, it remains to pick an appropriate value of n (note that we cannot just set n = λ since λ = 2n log p depends on n). Setting e.g. n = O(log p) gives 1/n = O(1/ √ λ) = o(1), thus concluding the proof.

  for every (nonuniform) PPT adversary A and t ∈ T λ , it holds that

	Pr k←rK λ
	x←rA(k)

  Game 3 : This game is identical to the previous game except that the challenger checks an additional condition regarding π * ZAP output by A. Let Open be the efficient deterministic open algorithm of the IHBG protocol Π IHBG . Then, in this game, when A outputs π

* ZAP , the challenger first parses (σ * , S * , ρ * S * , {π * IHBG,i } i∈S * , π * HBM ) ← π * ZAP and runs ρ ← Open( r, σ * , τ ). It then outputs 1 if ZAP.Verify(r , x, π * ZAP ) = , ρ ∈ {0, 1} m , and ρ * S * = ρ S * , and 0 otherwise. The following Lemmas 16 to 18 establish Pr[E 1 ] = ε ≤ negl(λ), thus completing the proof. Lemma 16. If Π IHBG is µ-extractable for all PPT adversary, then we have |Pr[E 1

  m+1) p by brute force. 6. If M is not full-rank, return ⊥. 7. ρ i ← {0, 1} m , for all i ∈ [m]. 8. Compute Y := {y ∈ Z m+1 p

  2 implicitly parameterized by the security parameter λ. Define R sparse LPWW = {R sparse LPWW,t } t∈Z *

p to be the natural sparse relation associated to the Σ-protocol of Section 4.4 for the parametrized family of languages L LPWW , with repetition parameter n. That is,

R sparse LPWW,t := {(α, β) ∈ G 2n × (Z * p ) n : ∃x, γ, par ∈ Λ t s.t. x / ∈ L par LPWW ∧ V (x, α, β, γ) = },

Explicit hardness in[1] assumes that there exists an explicit bound µ on the advantage of any polynomial time adversary against the assumption. In particular, this is a weaker requirement than superpolynomial hardness, for any arbitrarily small superpolynomial function. We note that previous works on statistical ZAPs using quasi-polynomial hardness[1,[START_REF] Goyal | Statistical zaps and new oblivious transfer protocols[END_REF][START_REF] Lombardi | 2-message publicly verifiable WI from (subexponential) LWE[END_REF][START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] can instead use explicit hardness.

There is an obvious additional necessary change: when proving correctness of an opening, the statistical NIZK for L LPWW is replaced by a statistical ZAP for L LPWW .

Note that we can also relax the definition to allow for an unbounded zero-knowledge simulator.

Although L and R are parameterized by the security parameter λ, we omit them throughout the paper for better readability whenever the meaning is clear.

Here, m can be set sufficiently large for both Π IHBG and Π HBM so that the existence of Π HBM is guaranteed unconditionally by Theorem 12.

To be precise, g ∈ G will be sampled for each security parameter λ and the family of parameterized language L LPWW,λ is defined with respect to such generator g. For better readability, we may make the random sampling of g implicit when the context is clear.

Note the algorithm only has knowledge of the encodings g M , and does not know the discrete logarithms M themselves.

Note that we need µ-explicit hardness rather than the standard polynomial hardness to provide a stricter bound between Pr[E3] and Pr[E4].

Note that B does not need to invoke D below since event F can be checked without the output of D.

To be precise, we assume a random group generator g ∈ G is also provided to B as part of the challenge, which B uses to simulate the view of A.

Geoffroy Couteau, Shuichi Katsumata, Elahe Sadeghi, and Bogdan Ursu

We defined the weaker soundness notion since that was all we required to construct the IHBG protocol, and moreover, it was what we could construct from the kernel DH assumption.

Finally, notice that Game 5 is equivalent to first sampling ρ ← r {0, 1} m , running S ← r A 0 (ρ), (σ, {π i } i∈S ) ← r Sim(m, r, S, ρ S ), and checking whether S ⊆ [m] and A 1 (r, S, ρ, σ, {π i } i∈S ) = 1. In particular, Game 5 corresponds to the simulated game using Sim of the statistical-hiding property. Combining all the arguments and using the triangle inequality, we have therefore shown the following bound:

where the equality comes from the fact that m is polynomial and ν is negligible. This completes the proof of the theorem. It remains to prove Lemmas 33 to 37. Proof. The only difference between the two games occurs when the matrix M is not full-rank. Namely, when matrix M is full-rank, this means that M and M -1 correspond to bijective linear functions. Therefore, since (s u) ← r Z m+1 p is uniformly random, vector y is also uniformly distributed in Z m+1 p and the distributions in Game 0 and Game 1 are identical.

It remains to show that the matrix M is full-rank with overwhelming probability 1 -(m + 1) • ν. Assume that M = M -z • I m+1 was not full-rank, then there exists a vector t in the right kernel of M , meaning that M t = 0. But then, Mt = z • t, which means that t is an eigenvector and z is a eigenvalue of M. Matrix M has at most m + 1 eigenvalues. Since z ← r [1/ν] is uniformly random, the probability that z is an eigenvalue is at most (m + 1) • ν (which happens in the worse-case scenario in which all m + 1 eigenvalues of M are in the set [1/ν]).

Proof. The distributions of u in Game 1 and in Game 2 are identical. The only difference is that in In Game 2 , the sampling of u is performed in two stages: the challenger first picks a vector u ← r Z m p , computes ρ i ← H(g u i ), and after sending ρ to A 0 , it receives the set S. Afterwards, the challenger samples u ← r {u ∈ Z m p : H(g u i ) = ρ i , for all i ∈ S}. It is clear that the resulting distribution of u is identical to those of Game 1 .

Proof. Notice that Game 2 and Game 3 are identical conditioned on the set U in Game 3 being nonempty. Therefore, we upper bound the probability of U being empty in Game 3 . For a fixed H ∈ H and ρ 1 ∈ {0, 1}, define the set generates the proof π ZAP,j for j ∈ [i + 1 : m] ∩ S using witness y as in Game 3 and the proofs for j ∈ [i] ∩ S using witness y r as in Game 4 . Noticing that we do not need to generate any proofs for j ∈ [m]\S, we have Game 0 3 = Game 3 and Game m 3 = Game 4 . We prove that the output distribution of A changes negligibly by transitioning from Game i * 3 to Game i * +1 3 for all i * ∈ [0 : m -1]. Let B be an adversary against the doubly-adaptive statistically witness indistinguishability of the IHBG-friendly ZAP that internally runs A defined as follows: On input the security parameter in unary 1 λ , B runs identically up to Item 13 as the challenger in Game 3 . It then computes y and y r as in Item 14 in Game 3 and Item 14 in Game 4 , respectively. B generates π ZAP,i using witness y for i ∈ [i * + 2 : m] ∩ S and using witness y r for i ∈ [i * ] ∩ S. B then sets st as all its internal state and sends (r ZAP,i * , par i * , x i * , y, y r , st) to the challenger of the IHBG-friendly ZAP witness indistinguishability game, and receives back π * ZAP . Finally, B sets π ZAP,i * +1 := π * ZAP if i * ∈ S and simulates the rest of the challenger in Game 3 and outputs whatever output by A 1 . It can be checked that B perfectly simulates Game i * 3 and Game i * +1 3 when witnesses y and y r are used to create π * ZAP , respectively. Therefore, by a standard hybrid argument over m-games, we conclude the proof.

Proof. It suffices to prove that the distribution of (u, s, y) in Game 4 and Game 5 are identical. First, we focus on the case that M is full-rank since otherwise the challenger implicitly sets (u, s, y) = (⊥, ⊥, ⊥) in both games. Conditioning on M being full-rank, we have the set U in Game 4 is empty if and only if the set Y in Game 5 is empty. Therefore, we can further focus on the case that U in Game 4 is non-empty. Now, notice that since M is full-rank, the sets {Y s,u } (s,u)∈Zp×U are disjoint and all have the same size for a fixed choice of H, M, S, and ρ. Therefore, since Y in Game 5 is identical to (s,u)∈Zp×U Y s,u , the distribution of first sampling (s, u) ← r Z p × U and sampling y ← r Y s,u is identical to first sampling y ← r Y and then setting (s, (u i ) i∈S ) = (y v , (y w i ) i∈S ). We complete the proof by taking the probability over the other variables.

IHBG-Friendly Statistical ZAPs for L LPWW

In this section, we provide two instantiations for the IHBG-friendly statistical ZAP used in the construction of IHBG from the previous section, one in pairing groups, and one in pairing-free groups. These constructions and their analysis constitute the proofs of Lemma 23 and Lemma 24.

First Construction: a Statistical ZAP for L LPWW in Pairing Groups

For this construction, we employ the Couteau-Hartmann compiler from [8]. The high-level idea of the compiler is very simple: assume that the family of parametrized languages L LPWW = {L par LPWW } par∈Λ is defined over a group G 1 , such that there exists another group G 2 and an asymmetric pairing from

Then, the Couteau-Hartmann compiler converts a Σ-protocol with linear answer for the target language into a statistical ZAP by parsing the random message of the verifier as a pair (g 2 , g e 2 )

, where e is seen as some random verifier challenge for the Σ-protocol. The compiled ZAP is constructed by computing the first flow of the Σ-protocol normally, and the last flow (which is a linear function of the challenge e with coefficients known to the prover) "in the exponent of g 2 " using (g 2 , g e 2 ). The verification step is carried out using a pairing. Below, we adapt this compiler to the family of parameterized languages L LPWW and prove its security. Construction. Let (G 1 , G 2 ) be elliptic curves equipped with an asymmetric pairing • : G 1 × G e → G T , where G 1 and G 2 both have prime order p. We extend the definition of • to vectors in the conventional manner. Let g 1 be a generator of G 1 and d be a vector length parameter. Let par = (g, h) ∈ Λ = (G d 1 \{1}) 2 be the language parameters. We will rely on the Σ-protocol from Section 4.4 with repetition parameter n = 1. In particular, we do not require to rely on the adaptive soundness of the Σ-protocol (i.e., Lemma 29) to achieve adaptive soundness (looking ahead, higher value of n (i.e., adaptive soundness of the Σ-protocol) will only be useful in our pairing-free instantiation). The construction of a ZAP for L LPWW over G 1 with public coin length = 2 log |G 2 | , denoted as Π ZAP , is described as follows.

-ZAP.Prove(par, r , x, w) : On input parameters par = (g, h) ∈ Λ, a public coin r ∈ {0, 1} , a statement x := (X, Y ) ∈ L par LPWW and a witness w := y ∈ Z d p such that (X, Y ) = ((g ) y , (h ) y ), parse r as (g 2 , g e 2 ) ∈ G 2 2 and proceed as follows:

p and set (R, S) ← ((g ) z , (h ) z ). Note that this corresponds to computing the first flow of the prover in the Σ-protocol from Section 4.4, with n = 1.

Note that this corresponds to computing the last flow of the prover in the Σ-protocol from Section 4.4, in the exponent domain of G 2 .

• Output π ZAP = (R, S, g d 2 ). -ZAP.Verify(par, r, x, π ZAP ) : On input parameters par = (g, h) ∈ Λ, a public coin r ∈ {0, 1} , a statement x = (X, Y ), and a proof π ZAP , parse π ZAP as (R, S, g d 2 ), and parse r as

Note that this corresponds to executing the verification procedure of the Σ-protocol from Section 4.4 (with n = 1), but using the pairings to emulate the exponentiations of (g , h ) and (X, Y ) (which are all over G 1 ) by d and e respectively, since the latter are now only known in the exponent of g 2 .

Completeness follows directly from the completeness of the underlying Σ-protocol.

Lemma 38. For any parametrized language L par LPWW over G 1 , Π ZAP satisfies doubly-adaptive perfect witness indistinguishability.

Proof. This follows directly from the perfect witness indistinguishability of the underlying Σ-protocol. Indeed, if there exists a (possibly) inefficient cheating adversary A = (A 0 , A 1 ) against the doublyadaptive perfect witness indistinguishability of the above ZAP, then it can be lifted to an attack against the perfect witness indistinguishability of the Σ-protocol as follows: first run A 0 to get the parameters par ∈ Λ, the first flow r = (g 2 , g e 2 ) ∈ G 2 2 , and statement-witnesses pair (x, w 0 , w 1 ), and state st. Then, extract e ∈ Z * p by brute force search of the discrete logarithm and send par and (x, w 0 ) (and (x, w 1 )) to the prover in the Σ-protocol. Upon receiving the first flow (R, S) of the prover, send the challenge e. Upon receiving the last flow d, lift it to the exponent of g 2 and feed A 1 with (R, S, g d 2 , st). Output whatever A 1 output; it is immediate to check that this translate to an attack against the witness indistinguishability of the Σ-protocol with exactly the same advantage as A.

Lemma 39. For a randomly sampled parametrized language L par LPWW over G 1 , Π ZAP satisfies adaptive computational ε sound -soundness w.r.t. colinear parameters par ∈ Col(G d 1 ) under the explicit ε soundhardness of the kernel Diffie-Hellman assumption in G 2 .

Proof. Let A be an efficient adversary against the adaptive computational ε sound -soundness w.r.t. colinear parameters of Π ZAP :

, r ← {0, 1} , (x, π ZAP ) ← r A(par, r) : x ∈ L par LPWW ∧ Verify(par, r, x, π ZAP ) = ] > ε sound . We build an adversary against the explicit ε sound -hardness of the kernel Diffie-Hellman assumption in G 2 as follows: the reduction receives (G 1 , G 2 , G T , p, g 1 , g 2 , g e 2 ) from the challenger for the kernel Diffie-Hellman assumption. It samples par by picking

, and sets r to be (g 2 , g e 2 ). Note that par is perfectly distributed as a random sample from Col(G d 1 ), and r is perfectly distributed as in Π ZAP . Then, it gets (x, π ZAP ) ← A(par, r) from the ZAP adversary A, and parses x as (X, Y ) and π ZAP as (R, S, g d 2 )

. By definition of A and since par and r are distributed exactly as in the soundness game, it holds with probability at least ε sound that (X, Y ) ∈ L par LPWW and Verify(par, r, x, π ZAP ) = , i.e. we have the following three equations:

• (S • g 2 ). Now, since h = g s , and using the bilinearity of the pairing, we get from the last two equations that 1 = (X s /Y • g e 2 ) • (R s /S • g 2 ) = (R s /S, X s /Y ) • (g 2 , g e 2 ) and therefore the vector (R s /S, X s /Y ), which the reduction can efficiently compute, is of the form (g u 1 , g v 2 ) where (u, v) is in the kernel of (1, e) and v = 0 (since X s /Y = g 0 1 ); hence, the reduction outputs (R s /S, X s /Y ) and breaks the kernel Diffie-Hellman assumption with probability at least ε sound .

Table of Contents