Geoffroy Couteau
email: geoffroy.couteau@ens.fr

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

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

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

Keywords: Non-interactive zero-knowledge arguments, pairing-free groups, KDM security

We provide two new constructions of non-interactive zero-knowledge arguments (NIZKs) for NP from discrete-logarithm-style assumptions over cyclic groups, without relying on pairings. A previous construction from (Canetti et al., Eurocrypt'18) achieves such NIZKs under the assumption that no efficient adversary can break the key-dependent message (KDM) security of (additive) ElGamal with respect to all (even inefficient) functions over groups of size 2 λ , with probability better than poly(λ)/2 λ . This is an extremely strong, non-falsifiable assumption. In particular, even mild (polynomial) improvements over the current best known attacks on the discrete logarithm problem would already contradict this assumption. (Canetti et al. STOC'19) describe how to improve the assumption to rely only on KDM security with respect to efficient functions while additionally assuming public-key encryption schemes, therefore obtaining an assumption that is (in spirit) falsifiable. Our first construction improves this state of affairs. We provide a construction of NIZKs for NP under the CDH assumption together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size 2 λ , with probability better than poly(λ)/2 cλ (denoted 2 -cλ -OW-KDM), for a constant c = 3/4. Unlike the previous assumption, our assumption leaves an exponential gap between the best known attack and the required security guarantee. Our second construction is interested in the case where CDH does not hold. Namely, as a second contribution, we construct an infinitely often NIZK argument system for NP (where soundness and zero-knowledge are only guaranteed to hold for infinitely many security parameters), under the assumption that CDH is easy together with the 2 -cλ -OW-KDM security of ElGamal with c = 28/29 + o(1) and the existence of low-depth pseudorandom generators (PRG). Combining our two results, we obtain a construction of (infinitely-often) NIZKs for NP under the 2 -cλ -OW-KDM security of ElGamal with c = 28/29 + o(1) and the existence of low-depth PRG, independently of whether CDH holds. To our knowledge, since neither OW-KDM security of ElGamal nor low-depth PRGs are known to imply public key encryption, this provides the first construction of NIZKs from concrete and falsifiable Minicrypt-style assumptions.

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. When the proof consists of a single message from prover to the verifier, this results in a non-interactive zero-knowledge proof system (NIZK) [START_REF] Blum | Non-interactive zero-knowledge and its applications (extended abstract)[END_REF]. Due to their large number of applications in cryptography, NIZKs enjoy particular interest, ranging from efficient implementations to feasibility results.

On Building NIZKs from Concrete Assumptions. While one-way functions are known to be necessary [START_REF] Ostrovsky | One-way functions are essential for non-trivial zero-knowledge[END_REF] and sufficient [START_REF] Goldreich | Proofs that yield nothing but their validity and a methodology of cryptographic protocol design[END_REF] for zero-knowledge proof systems, the exact relation of NIZKs to other cryptographic assumptions and primitives is considerably less clear. NIZKs are known to exist in the plain model only for trivial languages [START_REF] Oren | On the cunning power of cheating verifiers: Some observations about zero knowledge proofs[END_REF]. To circumvent this issue, cryptographers design NIZKs in the common reference string (CRS) model, where a common reference string is honestly generated beforehand in a setup phase and is given to both prover and verifier. A large body of work has been dedicated to the construction of NIZKs in the CRS model from various cryptographic assumptions. As a result, NIZKs are known to exist from a wide range of assumptions, from pairing groups [START_REF] Groth | Perfect non-interactive zero knowledge for NP[END_REF][START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], factorization assumptions [START_REF] Blum | Non-interactive zero-knowledge and its applications (extended abstract)[END_REF][START_REF] Feige | Multiple non-interactive zero knowledge proofs based on a single random string[END_REF], and indistinguishability obfuscation [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF], to circularlysecure LWE [START_REF] Canetti | Fiat-Shamir: from practice to theory[END_REF] and plain LWE [START_REF] Peikert | Noninteractive zero knowledge for NP from (plain) learning with errors[END_REF]. Yet, in spite of three decades of efforts, it remains an intriguing open question whether one can construct NIZKs from discrete-logarithm-style assumptions (without relying on pairing groups), which are among the most well-established assumptions in cryptography.

Here, the only known result is the recent work of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF], which constructs NIZKs under the exponential key-dependent message security of ElGamal with respect to all (even inefficient) functions. While this is a remarkable stepping stone, it remains an extremely strong and non-standard assumption. Therefore, an important question remains open:

"Is it possible to build NIZKs from (weaker) discrete-logarithm-style assumptions?" NIZKs and Public-Key Encryption. While it is known that one-way functions are a minimal assumption for zero-knowledge proofs [START_REF] Ong | Zero knowledge and soundness are symmetric[END_REF][START_REF] Ostrovsky | One-way functions are essential for non-trivial zero-knowledge[END_REF], the situation concerning NIZKs is much less clear. In particular, almost all known concrete constructions of NIZKs to date rely on assumptions which are known to imply public-key encryption (PKE) (such as factorization, pairing-based assumptions, indistinguishability obfuscation, and LWE variants). We are aware of only two exceptions to the above:

-NIZKs built on top of an interactive protocol, through the Fiat-Shamir transform, are "plausibly secure" when the hash function is instantiated with e.g. SHA3. Hence, these NIZKs are secure under the tautological assumption that they cannot be broken, and this assumption is not known to imply PKE (since no structure is required from the hash function). -The construction of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] relies on the assumption that it is infeasible to recover k given (g a , g ak+f (k) )

(with more than a polynomial advantage over the random guess), for every (even inefficient) function f . This is an extremely strong, non-falsifiable assumption.

The first of these two exceptions is essentially a restatement of our inability to show that NIZKs imply PKE, while the second requires a very strong and non-falsifiable assumption. This situation is somewhat unsatisfying, and we view it as an important open question to base NIZKs on concrete "Minicrypt-style" assumptions (i.e. assumptions not known to imply PKE), while avoiding extreme non-falsifiable assumptions.

"Is it possible to build NIZKs from (better, concrete) symmetric-style assumptions?"

In fact, the bigger picture is unclear, even for relaxations of NIZKs such as designated-verifier NIZKs (which are known based on DDH groups [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF][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], factorization [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF], or LPN [START_REF] Lombardi | New constructions of reusable designated-verifier NIZKs[END_REF] with a noise rate that implies PKE). The only known positive results are preprocessing NIZKs (where the prover and the verifier share a secret key) from flavors of LPN not known to imply PKE [START_REF] Boyle | Compressing vector OLE[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators: Silent OT extension and more[END_REF] and designated-prover NIZKs based on SIS [START_REF] Kim | Multi-theorem preprocessing NIZKs from lattices[END_REF]. Interestingly, we note that although the assumption of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] is not known to imply PKE, a slight strengthening of the assumption would: assuming that it is hard to recover k given (g a , g k , g ak+f (k) ) (note the additional g k term) for any (even inefficient) f already implies PKE: setting f such that g f (k) = Encode(k) where Encode is some efficiently invertible encoding of k into a group element, we get that the assumption implies CDH (which itself is known to imply PKE). Indeed, a CDH adversary could, given (g a , g k ), compute g ak and retrieve Decode(g f (k) ) = k from g ak+f (k) . This illustrates the fact that the power of unfalsifiable assumptions of this form, allowing f to be arbitrary, can be hard to estimate, and that classifying them as plausible Minicrypt candidate assumptions is quite shaky.

NIZKs from Correlation Intractability. Our work follows the blueprint of a recent line of research, which seeks to compile interactive protocols into NIZKs using the Fiat-Shamir paradigm [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF], by instantiating the underlying hash function by a correlation-intractable hash function. Informally, a correlation-intractable hash function (CIH) with respect to a relation R is a hash function such that it is infeasible to find an input x satisfying (x, H(x)) ∈ R. CIH have been introduced in [START_REF] Canetti | The random oracle methodology, revisited[END_REF], where it was also shown that correlation-intractability for all sparse relations suffices to instantiate the Fiat-Shamir paradigm. Despite some impossibility results [START_REF] Bitansky | Why "Fiat-Shamir for proofs" lacks a proof[END_REF], a recent line of work has shown how to construct CIH for various sparse relations of interest [START_REF] Canetti | Fiat-Shamir: from practice to theory[END_REF][START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF][START_REF] Holmgren | Cryptographic hashing from strong one-way functions (or: One-way product functions and their applications)[END_REF][START_REF] Kalai | From obfuscation to the security of Fiat-Shamir for proofs[END_REF][START_REF] Peikert | Noninteractive zero knowledge for NP from (plain) learning with errors[END_REF], obtaining NIZKs from new assumptions. Out of these works, [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] relies on the exponential key-dependent messages (KDM) security for all (even inefficient) functions of an encryption scheme with universal ciphertexts, which can be instantiated over pairing-free groups with a suitable variant of ElGamal; unfortunately, this is an extremely strong assumption, which has several undesirable features. In this paper, we seek to improve the result of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] and to construct NIZKs for NP from weaker assumptions over pairing-free groups.

On the Strong-KDM Security Assumption of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF]. The construction of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] relies on the following assumption over cyclic groups: let G be a group of order p ≈ 2 λ with a generator g. Then, for any probabilistic polynomial time adversary A, any function F : Z p → Z p in a family of (possibly inefficient) functions F, and any superpolynomial function s, it holds that

Pr (a,k)←rZ 2 p A g, g a , g ak+F (k) = k ≤ s(λ) 2 λ .
While this assumption is not contradicted by known attacks on the discrete logarithm problem over suitably chosen elliptic curves, it is an extremely strong assumption, with several undesirable features:

-Optimality. Optimal security means that every PPT adversary has advantage at most λ O(1) /2 λ . 4The above assumption requires optimal security, which is equivalent to assuming that no improvement (by more than polynomial factors) to the best known existing attack will ever be found. Hence, even mild cryptanalytic improvements would already contradict the above assumption. -Non-Falsifiablity. The above assumption is not falsifiable, in the sense of [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], since it might not be possible to efficiently check whether an adversary breaks the assumption with respect to some specific inefficient function. However, [START_REF] Canetti | Fiat-Shamir: from practice to theory[END_REF] notes that it is possible to construct NIZKs even when the functions f considered in the assumption are efficient by additionally assuming public-key encryption.

Insecurity with Auxiliary Inputs. In the same spirit as knowledge of exponent assumptions, which are known to become insecure (under obfuscation-style assumptions) when auxiliary inputs are allowed, unfalsifiable flavors of KDM security have been recently shown to be insecure as soon as auxiliary inputs are allowed, assuming that LWE is hard and one-way permutations exist [START_REF] Freitag | Impossibility of strong kdm security with auxiliary input[END_REF]. While this does not directly contradict the unfalsifiable flavor of the assumption above, it makes it very sensitive to any side information an adversary might have access to when it is used in a higher-level application.

Our Contribution

We propose two new constructions of NIZKs, improving over the NIZK of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] in terms of the underlying assumption. As noted in [START_REF] Canetti | Fiat-Shamir: from practice to theory[END_REF], the assumption in [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] can be improved to consider only efficient functions by additionally assuming public-key encryption and thus construct NIZKs based on a falsifiable-style notion of KDM-security 5 . In this work, we remove the need of relying on optimal security of the underlying assumption, while maintaining the falsifiable flavor of KDM security. We note that our second construction satisfies a weaker notion of security, infinitely-often security, where soundness and zero-knowledge are only required to hold for infinitely many security parameters. For a discussion on the notion of infinitely-often security and its usage in cryptography, please refer to Appendix A.

In more detail, the assumption at the core of our new construction is a strong flavor of the OW-KDM security of ElGamal: given a group G of size ≈ 2 λ with generator g, the 2 -cλ -OW-KDM assumption states that for a family of (randomized) efficient functions F, any PPT adversary receiving an ElGamal ciphertext encrypting F (k) (in the exponent) with the key k is unable to recover the plaintext with advantage greater than s(λ)/2 cλ , for any superpolynomial function s:

Pr (k,a)←rZ 2 q m←rF (k) [A(g, g a , g ak+m ) = k] ≤ s(λ) 2 cλ for some c ∈ [0, 1].
The value c determines the strength of the assumption: c = 1 corresponds to assuming optimal security (as in [START_REF] Canetti | Fiat-Shamir: from practice to theory[END_REF][START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF]), while smaller values of c leave a gap between the success probability of the best known attacks and the success probability that can be tolerated by the assumption. In particular, a constant c < 1 indicates that the assumption can stand even exponential improvements in the success probability of the best known attacks. We propose two new NIZK constructions:

1. Our first construction assumes the hardness of CDH. Then, further assuming the 2 -cλ -OW-KDM security of ElGamal with c = 3/4, we propose an adaptively-sound adaptively-multi-theorem NIZK for all of NP. Both soundness and zero knowledge are computational, the first is implied by OW-KDM, while the second is implied by CDH. 2. Our second construction aims at analyzing the complementary landscape. More precisely, we investigate the possibility of building NIZKs in groups where CDH does not hold. Then, further assuming the 2 -cλ -OW-KDM security of ElGamal with c = 28/29 + o(1), together with the assumption that Goldreich's PRG [START_REF] Goldreich | Candidate one-way functions based on expander graphs[END_REF] instantiated under the Lombardi-Vaikuntanathan predicate [START_REF] Lombardi | Minimizing the complexity of goldreich's pseudorandom generator[END_REF] is secure up to some (arbitrarily small) polynomial stretch 6 , we propose an adaptively-sound, adaptively-multitheorem zero-knowledge (infinitely often) NIZK for all of NP. Both soundness and zero knowledge are computational, the first is implied by OW-KDM, while the second is implied by OW-KDM and the pseudorandomness of Goldreich's PRG.

As a direct consequence, combining the above two results, we obtain a construction of (infinitelyoften) NIZKs for NP under the same assumptions, independently of whether CDH holds. Since both our OW-KDM assumption and the existence of low-depth PRGs are not known to imply PKE, this provides (to our knowledge) the first NIZK construction from a concrete falsifiable (in spirit) Minicrypt-style assumption. In both constructions, an important effort is devoted to obtaining the smallest possible constant c, to minimize the strength of the underlying assumption. We view it as an interesting open problem to further minimize the value of c, especially in our second construction.

Our Techniques -First Construction

Both our constructions follow a similar footprint: we start from a Σ-protocol for a carefully chosen, but limited language. We compile this Σ-protocol using a correlation-intractable (CI) hash function into a NIZK for the same limited language. Then we use different techniques to bootstrap this restricted NIZK to NIZK for all of NP, by using them to build a verifiable pseudorandom generator (VPRG) [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF][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], which in turns leads to NIZKs for NP. Our approach is inspired by [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF]. Their strategy is to design a correlation-intractable (CI) hash function based on a scheme with universal ciphertexts, which they use to transform an underlying sigma protocol into a NIZK. In their case, the interactive protocol is the one in [START_REF] Feige | Multiple noninteractive zero knowledge proofs under general assumptions[END_REF]Section 2.1]. We diverge from this approach by applying the CI hash function to a sigma protocol for a more restricted, but still expressive enough language (which we bootstrap later to a full-fledged NIZK through VPRGs). Looking ahead, the parameters of the KDM security assumption are intrinsically tied to the ratio between the size of the first flow of the sigma protocol and its adaptive soundness. By allowing the underlying sigma protocol to support only a more restricted language, we expand the field of potential candidates and eventually identify a protocol with a better first flow/soundness ratio. Our initial attempt is to start with the standard Σ-protocol for the Diffie-Hellman relation L DH , described in figure 1. Choose a cyclic group G of prime order p, along with two generators g and h. The relation consists of all pairs of group elements of the form (g x , h x ). To transform the sigma protocol into a NIZK for L DH , the idea of the CI framework is to apply the Fiat-Shamir transform, but instead of using random oracles, the random oracle is replaced with a CI hash function. Σ-protocol for the Diffie-Hellman language for the word (g, h, X = g x , Y = h y ). This is a variant of a protocol by [START_REF] Abdalla | Tightly-secure signatures from lossy identification schemes[END_REF] CI Hash Functions. A CI hash function H for a specific relation R is a function for which it is hard to find an input α, such that (α, H(α)) ∈ R. Consider the case where the initial relation is sparse, meaning that for every α, the number of potential β's satisfying (α, β) ∈ R is negligible. Then, the above sigma protocol can be transformed into a NIZK by asking the prover to generate the second flow himself, by running e = H(R, S). The verifier will only accept if the resulting transcript is accepting and also e = H(R, S). From the correlation intractability of H, even a malicious prover will be unable to cheat by finding a properly chosen initial flow (R, S), such that ((R, S), H(R, S)) ∈ R (this also holds because the sparsity of the relation R is bounded by the soundness error of the sigma protocol, which is negligible).

Choice of H. To construct the hash, we choose a function closely related to the one used in [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF], where the (keyed) hash H K (x) interprets the input x as a decryption key and the key K as a ciphertext, and returns Dec x (K). For our instantiation, we crucially rely on a specific property of the additive variant of ElGamal (which is, informally, that keys and plaintexts are "interchangeable"). Since additive ElGamal does not provide efficient decryption (the decryption procedure recovers only Gm , and we cannot guarantee that m will be small in our construction), we modify the CI hash of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF] so that it returns Trunc( Gm ), where Trunc is some function that parses its input as a bitstring and truncates it appropriately. More precisely, we pick a second cyclic group G of order q, generated by G where log q = 2 log p . The CI function is keyed by key C = ( C0 , C1 ), where ( C0 , C1 ) ← r G2 . Then, we define:

H ( C0, C1) (α) = first log p bits of C1 / Cα 0 .
Parameters. This protocol has 1 p soundness and the size of the first flow is 2 log p , which translates into a 2 -λ/2 -KDM assumption for the CI hash function. Unfortunately, this Σ-protocol does not satisfy adaptive soundness (that is, given an honestly-generated first flow and challenge, there always exist words that are not in the relation, for which there exists an accepting third flow). Adaptive soundness is a crucial requirement for bootstrapping our first NIZK to cover all NP statements. Fortunately, performing a parallel repetition of the Σ-protocol yields adaptive soundness, albeit at the cost of worser parameters in our assumption (c = 3/4).

Reduction to KDM for Efficient Functions. The above construction reduces to the KDM security of ElGamal, but only with respect to an inefficient function f , which maps first flows to accepting challenges. (Note that computing the unique accepting challenge e from a first flow (R, S) amounts to solving the discrete logarithm problem.) From here, we leverage the fact that an ElGamal encryption ( Gr , Gkr+m ) of a plaintext m with key k, with respect to a generator G, can be equivalently seen as an ElGamal encryption of a plaintext k with the key m with respect to the generator Gr . Building upon this observation and the fact that f -1 is efficient, we show that the security of our NIZK for the DDH language can in fact be reduced to the KDM security of ElGamal with respect to the efficient function f -1 .

From NIZK DH for L DH to a NIZK for all of NP. In this step, we use an idea from [START_REF] Dwork | Zaps and their applications[END_REF] (that was slightly generalized and implicitly employed in recent works [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF][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]). We use the NIZK DH for the L DH relation to construct a verifiable pseudo-random generator (VPRG), which we then in turn use to instantiate the hidden bits model of [START_REF] Feige | Multiple noninteractive zero knowledge proofs under general assumptions[END_REF], to obtain NIZKs for all of NP. Intuitively, a VPRG is a pseudorandom generator with the additional property that one can compute proofs for any individual bit of the output, certifying that the bit is consistent with a commitment of the initial seed. Let G be a cyclic group of order p, the VPRG public parameters will consist of m + 1 group elements (g, h 1 , . . . , h m ). Seeds are elements τ ← r Z p , and committing to a seed is Commit(τ ) = g τ . The i th output bit of the VPRG is of the form B(g τ , h τ i ), where B is the Goldreich-Levin hardcore bit. Now notice than we can actually certify this as a correctly computed bit, by noticing that (g τ , h τ i ) ∈ L DH and computing a proof using our NIZK DH . (additionally, we need to output h τ i as well, so that the verifier can compute B(g τ , h τ i ) itself). Intuitively, this VPRG satisfies the following security properties:

1. Binding: if x i is the i th output of the VPRG with respect to a seed τ , one should not be able to certify bit 1 -x i . This is implied in our construction by the soundness of NIZK DH . 2. Hiding: An adversary should not be able to recover the i th output of the VPRG, even if it received all the other output bits and proofs certifying that they are correct. In our construction, this property reduces to the CDH assumption.

NIZK for all of NP through the Hidden-Bit Model. In this model [START_REF] Feige | Multiple noninteractive zero knowledge proofs under general assumptions[END_REF], the prover and the verifier benefit from having access to a common reference string with special properties. The bits of the common reference string are initially hidden from the verifier. When proving a statement, the prover can decide to selectively reveal some bits of the common reference string, which allows the verifier to check the proof. The work of [START_REF] Feige | Multiple noninteractive zero knowledge proofs under general assumptions[END_REF] has showed that NIZKs exist unconditionally in this model. The VPRG we construct allows us to simulate the hidden-bits model on the prover side. Initially, all bits are hidden from the verifier from the hiding property of the VPRG. Subsequently, the prover can decide to reveal several bits, which corresponds to computing VPRG proofs.

Our Techniques -Second Construction

The previous construction relies on the CDH assumption. In our second construction, we take the complementary road: we seek to construct NIZKs for NP under the strong KDM security of ElGamal assuming that CDH does not hold. Together with our first construction, this implies a NIZK for NP that does not rely on the CDH assumption (albeit with an infinitely-often security notion). To this end, we also seek to build a VPRG.

Self-Pairing. First, we notice that if CDH does not hold, there exists an efficient adversary solving it with non-negligible advantage. We use previous results by [START_REF] Maurer | Diffie-Hellman oracles[END_REF][START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] to amplify the success probability of this adversary to obtain a self-pairing map. Since from the definition of CDH, the adversary is only guaranteed to succeed on infinitely-many security parameters, our NIZK will be secure only on infinitely-many security parameters. This self-pairing will allow us to perform homomorphic computations and to evaluate bounded integer arithmetic circuits in the exponent. Our core idea, informally, is to rely on this self-pairing to let the parties homomorphically evaluate a pseudorandom generator in the exponent: at a high level, given a (bit-by-bit) commitment c to the seed, the parties can homomorphically compute, using the self-pairing, a commitment c i to the i-th output bit of the PRG (for all i). Then, the prover will open a given PRG value by providing a NIZK proof of correct opening.

A Commitment from Short-Exponent Discrete Logarithm. To instantiate this idea, we introduce a new commitment scheme which is perfectly binding, and which is hiding under the shortexponent discrete logarithm assumption (which states that given g x for a random but short x, it is infeasible to retrieve x). This does not introduce any new assumption, as we further show that the short-exponent discrete logarithm assumption is implied by the strong OW-KDM security of ElGamal. Furthermore, we carefully design this commitment scheme so that it suffices, to convince the verifier that the opening was correct, to demonstrate that the randomness r of the commitment is almost short. By almost short, we mean that there exists short values (u, v) such that v • r = u mod p. This turns out to be a crucial property, since the language of group elements with almost-short exponents is precisely one for which we are able to build a NIZK under the 2 -cλ -OW-KDM security of ElGamal, for some c < 1.

A Σ-protocol for Almost-Short Exponents. Let G be a cyclic group of p elements. We consider a simple Σ-protocol for proving that a word g x has a short exponent, i.e. writing x as an integer yields a number ≤ 2 , for some carefully chosen < log p . Our protocol has a similar shape to the sigma protocol used in the previous construction, and is described in figure 3. However, we are unable to directly prove soundness, meaning that a malicious prover can convince the verifier of the validity of words g x , where x is not short. Fortunately, we are able to ensure that if g x is accepted, then x = u • v -1 , where u and v are themselves short. We denote this as the language L α,β of (α, β)-almost-short elements:

L α,β = {g x | x = u • v -1 ∈ Z p , u ∈ [-2 α , 2 α ], v ∈ [0, 2 β ]}.
Our Σ-protocol is somewhat atypical, in the honest run the prover must start with a word of the form g x and a short witness x (notice that if x is short it belongs to the almost-short language). However, when proving soundness, we only safeguard membership to the larger almost-short set of words; therefore, there is a gap between the correctness requirement, and the soundness guarantees (this is similar to some lattice constructions using the Fiat-Shamir with aborts paradigm, for example [START_REF] Lyubashevsky | One-shot verifiable encryption from lattices[END_REF]).

NIZK AS for the Language of Almost-Short Exponents. We will design another CI hash function, closely related to the one we built for the first construction, to transform the Σ-protocol above into a NIZK for the almost-short exponent language. This CI hash function will additionally employ a 2-universal hash function, which we use to reduce the security loss in our security analysis and achieve a better parameter c for the OW-KDM assumption. Now, equipped with our NIZK AS , we only need one final tool before moving on to our VPRG.

A Low-Depth Local PRG. Equipped with the above tools, it remains to find a suitable PRG to be used in our construction. For correctness, we need to ensure that no overflow occurs during the homomorphic operations in the exponent; therefore, we must pick the group size large enough so that the homomorphic PRG evaluation does not cause an overflow. Since picking a larger group translates into a larger security loss in our reduction, we seek to rely on a PRG (with some arbitrary small polynomial stretch) that has a minimal arithmetic degree. Fortunately, such PRGs were recently studied in [START_REF] Lombardi | Minimizing the complexity of goldreich's pseudorandom generator[END_REF], which exhibits a PRG with arithmetic degree 3 which provably resists a large class of attacks for a stretch up to 1.25 -ε. Combining this low-degree PRG with our new commitment scheme and our NIZK for the almost-short language yields a VPRG in groups where CDH does not hold, hence NIZKs for NP.

Wrapping Up. Combining our first and second construction, we get the following: assume that ElGamal is 2 -cλ -OW-KDM secure with respect to efficient functions (with c = 28/29 + o(1)), and that the previous PRG is secure. Then either CDH holds, in which case our first construction implies a NIZK for NP, or CDH does not hold, in which case our second construction implies an (infinitely-often) NIZK for NP. Therefore, under a PRG assumption and the strong OW-KDM security of ElGamal, we prove the existence of an infinitely-often NIZK for NP (but our proof is non-constructive, in that it does not tell which of the two candidate constructions is actually secure; only that one is).

Organization

Section 2 introduces necessary preliminaries and Section 3 introduces an algorithm for performing homomorphic computation in the exponent under the assumption that CDH is easy. Section 4 presents our first NIZK construction (assuming that CDH is hard) and Section 5 contains our second construction (assuming that CDH is easy). Finally, in Section 6, we summarize the consequence of our two constructions.

Preliminaries

Notation. Throughout this paper, λ denotes the security parameter. A probabilistic polynomial time algorithm (PPT, also denoted efficient algorithm) runs in time polynomial in the (implicit) security parameter λ. A function f is negligible if for any positive polynomial p there exists a bound

B > 0 such that, for any integer k ≥ B, |f (k)| ≤ 1/|p(k)|. We will write f (λ) ≈ 0 to indicate that f is a negligible function of λ; we also write f (λ) ≈ g(λ) for |f (λ) -g(λ)| ≈ 0.
An event occurs with overwhelming probability p when p ≈ 1. Given a finite set S, the notation x ← r S means a uniformly random assignment of an element of S to the variable x. For a positive integer n, m such that n < m, we denote by

[n] the set {1, • • • , n}, by [±n] the set {-n, • • • , n}, and by [n, m) the set {n, n + 1, • • • , m -1}.
Given an element x of a set Z p for prime p, we denote by int(x) the integer x ∈ [±(p -1)/2] such that x = x mod p. When manipulating elements (x, y) of Z p , we will generally abuse the notation and write x ≤ y for int(x) ≤ int(y).

The Computational Diffie-Hellman Assumption. 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. Then the computational Diffie-Hellman assumption is defined as follows.

Definition 1 (CDH Assumption). We say that the computational Diffie-Hellman (CDH) assumption holds relative to DHGen if for all PPT adversaries A,

Pr G ← DHGen(1 λ ), g ← r G, α, β ← r Z p : g αβ ← r A(1 λ , G, g, g α , g β ) ≤ negl(λ).
Here, note that DHGen outputs a fixed group G per security parameter.

Non-Interactive Zero-Knowledge

A (publicly-verifiable) non-interactive zero-knowledge (NIZK) argument system for an NP relation R, with associated language L (R) = {x | ∃w, (x, w) ∈ R} is a 3-tuple of efficient algorithms (Setup, Prove, Verify), where Setup outputs a common reference string, Prove(crs, x, w), given the crs, a word x, and a witness w, outputs a proof π, and Verify(crs, x, π), on input the crs, a word x, and a proof π, outputs a bit indicating whether the proof is accepted or not. A NIZK argument system satisfies the following: completeness, adaptive soundness, and selective single-theorem zero-knowledge properties:

(we let R λ denote the set R ∩ ({0, 1} λ × {0, 1} * )).
-A non-interactive argument system (Setup, Prove, Verify) for an NP relation R satisfies completeness if for every (x, w) ∈ R,

Pr[crs ← r Setup(1 |x| ), π ← Prove(crs, x, w) : Verify(crs, x, π) = 1] ≈ 1.
-A non-interactive argument system (Setup, Prove, Verify) for an NP relation R satisfies adaptive soundness if for any PPT A,

Pr crs ← r Setup(1 λ ), (x, π) ← r A(crs) : Verify(crs, x, π) = 1 ∧ x / ∈ L ≈ 0.
-A non-interactive argument system (Setup, Prove, Verify) for an NP relation R satisfies (computational, statistical) selective single-theorem zero-knowledge if there exists a PPT simulator Sim such that for every

(x, w) ∈ R, the distribution {(crs, π) : crs ← r Setup(1 λ ), π ← Prove(crs, x, w)} and {(crs, π) : (crs, π) ← r Sim(x)} are (computationally, statistically) indistinguishable.
-Furthermore, we say it satisfies (computational, statistical) adaptive multi-theorem zero-knowledge if for all (computational, statistical) A, there exists a PPT simulator

Sim = (Sim 1 , Sim 2 ) such that if we run crs ← r Setup(1 λ ) and (crs, τ ) ← r Sim 1 (1 λ ), then we have | Pr[A O0(crs,•,•) (crs) = 1] -Pr[A O1(crs,τ,•,•) (crs) = 1]| ≈ 0, where O 0 (crs, x, w) outputs Prove(crs, x, w) if (x, w) ∈ R and ⊥ otherwise, and O 1 (crs, τ, x, w) outputs Sim 2 (crs, τ, x) if (x, w) ∈ R and ⊥ otherwise.
We use the following result regarding the existence of NIZKs in the hidden-bits model (HBM). Since the full definition of NIZK in the HBM will not be required in our work, we refer the readers to [START_REF] Feige | Multiple non-interactive zero knowledge proofs based on a single random string[END_REF] for more details.

Theorem 2 (NIZK for all of NP in the HBM). Let λ denote the security parameter and let k = k(λ) be any positive integer-valued function. Then, unconditionally, there exists NIZK proof systems for any NP language L in the HBM that uses hb = k • poly(λ) hidden bits with soundness error ≤ 2 -k•λ , where λ denotes the security parameter and poly is a function related to the NP language L (and independent of k).

Verifiable Pseudorandom Generators

Definition 3 (Verifiable Pseudorandom Generator). Let δ(λ) and s(λ) be positive valued polynomials. A (δ(λ), s(λ))-verifiable pseudorandom generator (VPRG) is a four-tuple of efficient algorithms (Setup, Stretch, Prove, Verify) such that -Setup(1 λ , m), on input the security parameter (in unary) and a polynomial bound m(λ) ≥ s(λ) 1+δ(λ) , outputs a set of public parameters pp (which contains 1 λ ); -Stretch(pp), on input the public parameters pp, outputs a triple (pvk, x, aux), where pvk is a public verification key of length s(λ), x is an m-bit pseudorandom string, and aux is an auxiliary information; -Prove(pp, aux, i), on input the public parameters pp, auxiliary informations aux,

an index i ∈ [m],
outputs a proof π; -Verify(pp, pvk, i, b, π), on input the public parameters pp, a public verification key pvk, an index i ∈ [m], a bit b, and a proof π, outputs a bit β;

which is in addition complete, hiding, and binding, as defined below.

Definition 4 (Completeness of a VPRG). For any i ∈ [m], a complete DVPRG scheme (Setup, Stretch, Prove, Verify) satisfies:

Pr   pp ← r Setup(1 λ , m), (pvk, x, aux) ← r Stretch(pp), : Verify(pp, pvk, i, x i , π) = 1 π ← r Prove(pp, aux, i),   ≈ 1.
Note that our definition of VPRG is slightly relaxed than what is considered in [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF][START_REF] Dwork | Zaps and their applications[END_REF][START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF], in that, we do not require the size of s(λ) to be independent of m(λ). This relaxation still allows us to construct NIZKs for NP as long as the stretch δ(λ) is larger than some positive constant.

Definition 5 (Binding Property of a VPRG).

A VPRG is binding if there exists a (possibly inefficient) extractor Ext such that for any PPT A, it holds that

Pr   pp ← r Setup(1 λ , m), (pvk, i, π) ← r A(pp), : Verify(pp, pvk, i, 1 -x i , π) = 1 x ← Ext(pp, pvk)   ≈ 0.
Note that, following [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF][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], we consider a significantly weaker flavor of binding compared to [START_REF] Dwork | Zaps and their applications[END_REF], which still allows to construct NIZKs for NP.

Definition 6 (Hiding Property of a VPRG). A VPRG scheme (Setup, Stretch, Prove, Verify) is hiding if for any i ∈ [m] and any PPT adversary A that outputs bits, it holds that:

Pr   pp ← r Setup(1 λ , m), (pvk, x, aux) ← r Stretch(pp), : A(pp, pvk, i, (x j , π j ) j =i ) = x i (π j ← r Prove(pp, aux, j)) j   ≈ 1/2.
The following shows that VPRG with a sufficient stretch can be used to construct NIZKs for all of NP.

Theorem 7 ((δ, s)-VPRGs ⇒ NIZKs for all of NP). Fix an NIZK proof system for any NP language L in the HBM that uses hb = hb(λ) hidden bits with soundness error ≤ 2 -λ where hb ≥ λ w.l.o.g. Suppose that a (δ(λ), s(λ))-verifiable pseudorandom generator where s(λ) ≥ max{λ, (hb 2 /λ) 1/δ(λ) } exits. Then, there exist adaptively sound and adaptively multi-theorem zero-knowledge NIZK arguments for the NP relation L .

We provide a proof sketch below for completeness. Note that since existence of an NIZK in the HBM for any NP language L is implied by Theorem 2, the above shows that VPRGs with some mild condition on δ(λ) and s(λ) implies existence of an NIZK for any NP language L .

Proof. This is a direct consequence of [START_REF] Feige | Multiple non-interactive zero knowledge proofs based on a single random string[END_REF] and [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF]. It can be checked from Theorem 16 of [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF] that we can combine the NIZK in the HBM for the NP relation L with any VPRG that satisfies s 1+δ > (1 + s/λ)hb + hb 2 /λ in order to construct an adaptive single-theorem non-interactive witness indistinguishable (NIWI) argument for the NP relation L . Working out the equation and taking into account that s needs to be at least λ-bits, we can see the condition on s in our statement is sufficient. Then, by using [START_REF] Feige | Multiple non-interactive zero knowledge proofs based on a single random string[END_REF], we can convert an adaptive single-theorem NIWI into an adaptive multi-theorem NIZK assuming the existence of pseudorandom generators (which are by definition implied by VPRGs).

Correlation-Intractable Hash Functions

We recall the definition of correlation intractability [START_REF] Canetti | The random oracle methodology, revisited[END_REF].

Definition 8 (Correlation Intractable Hash Function). A collection H = {H

λ : K λ × I λ → O λ } λ∈N of (efficient) keyed hash functions is a R-correlation intractable hash (CIH) family, with respect to a relation ensemble R = {R λ ⊆ I λ × O λ }, if for every (non-uniform) PPT adversary A, it holds that Pr k←rK λ x←rA(k) [(x, H λ (k, x)) ∈ R λ ] = negl(λ).
For CIH to be useful as a building block for NIZK, we require an additional property referred to as programmability [START_REF] Canetti | Fiat-Shamir: from practice to theory[END_REF].

Definition 9 (Programmability). A collection H = {H λ : K λ × I λ → O λ } λ∈N
of (efficient) keyed hash functions is called programmable if there exists an efficient algorithm, which given x ∈ I λ and y ∈ O λ , outputs a uniformly random key k from K λ , such that H λ (k, x) = y.

Finally, we define the standard notion of sparsity.

Definition 10 (Sparsity). For any relation ensemble

R = {R λ ⊆ I λ × O λ }, we say that R is ρ(•)- sparse if for λ ∈ N and any x ∈ I λ , Pr y←rO λ [(x, y) ∈ R λ ] ≤ ρ(λ). When ρ(λ) = negl(λ)
, we simply say it is sparse.

In the following, whenever the meaning is clear, we omit the subscripts for better readability.

Σ-Protocol

We recall the definition of Σ-protocols from [START_REF] Lindell | An efficient transform from sigma protocols to NIZK with a CRS and non-programmable random oracle[END_REF]. A Σ-protocol is a three-move interactive proof between a prover P and a verifier V for a language L , where the prover sends an initial message α, the verifier responds with a random β ← r S λ for some challenge space S λ , and the prover concludes with a message γ. Lastly, the verifier outputs 1, if it accepts and 0 otherwise. Three properties we require from a Σ-protocol are completeness, special honest-verifier zero-knowledge, and adaptive soundness.

Definition 11 (Completeness). A Σ-protocol for a relation R with prover P and verifier

V is complete, if Pr[out P(x, w), V(x) = 1|(x, w) ∈ R] = 1.
Definition 12 (Special honest-verifier zero-knowledge). A Σ-protocol for a relation R is special honest-verifier zero-knowledge, if there exists a polynomial-time simulator Sim such that the distributions Sim(x, β) and P(x, w), V(x) are statistically close for any (x, w) ∈ R, β ∈ S λ , where the honest protocol is conditioned on V choosing β.

Definition 13 (Adaptive soundness). A Σ-protocol for a relation R is ρ(•)-adaptive sound, if for any (possibly inefficient) cheating prover P * and any first flow α, it holds that

Pr[β ← r S λ ; (x, γ) ← r P * (α, β) : ∃x ∈ L ∧ V (x, α, β, γ) = 1] ≤ ρ(λ). When ρ(λ) = negl(λ)
, we simply say it is adaptive sound.

In the above notion, when the cheating P * does not have the freedom to choose the word x, we say it is selectively sound. Note that a selective soundness is implied by the standard notion of special soundness of the Σ-protocol. The following lemma is due to [START_REF] Kalai | From obfuscation to the security of Fiat-Shamir for proofs[END_REF], which at a high level claims that any adaptive sound Σ-protocol induces a natural sparse relation. Lemma 14. Let Π be an arbitrary ρ(•)-adaptive sound Σ-protocol for a language L . Then, the following relation induced by the Σ-protocol Π is ρ(•)-parse:

R sparse = {(α, β) : ∃x, γ s.t. x ∈ L ∧ V (x, α, β, γ) = 1}.

Secret Key Variant of ElGamal

Definition 15 (Secret Key ElGamal). Let G = { Gλ } λ∈N 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 λ ) : output public-parameter G ← r Gλ and secret key k

← r Z q . -Enc G(k, m) : pick R ← r G and output C = ( R, Rk • Gm ).
-HalfDec(k, C) : parse C as ( C0 , C1 ) and output 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 16 (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 17 (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) δ-OW-KDM security with respect to F if for every F u ∈ F λ , every 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(λ) • δ(λ).
If ElGamal satisfies δ-OW-KDM security with δ(λ) = 2 -cλ for some constant c ∈ (0, 1], then we say it is strong OW-KDM secure.

Low-Depth Pseudorandom Generators

Definition. A pseudorandom generator is a deterministic process that expands a short random seed into a longer sequence, so that no efficient adversary can distinguish this sequence from a uniformly random string of the same length:

Definition 18 (Pseudorandom Generator). A m(n)-stretch pseudorandom generator, for a polynomial m, is a pair of PPT algorithms (PRG.Setup, PRG.Eval) where PRG.Setup(1 n ) outputs some public parameters pp, which are implicitly given as input to PRG.Eval, and PRG.Eval(x), on input a seed x ∈ {0, 1} n , outputs a string y ∈ {0, 1} m(n) . It satisfies the following security notion: for any probabilistic polynomial-time adversary A and every large enough n,

Pr[pp ← r PRG.Setup(1 n ), y ← r {0, 1} m(n) : A(pp, y) = 1] ≈ Pr[pp ← r PRG.Setup(1 n ), x ← r {0, 1} n , y ← PRG.Eval(x) : A(pp, y) = 1] A pseudorandom
, • • • , x σ m d )).
The Lombardi-Vaikuntanathan (LV) Predicate. For concreteness, we will rely on Goldreich PRG instantiated with the following predicate:

P LV (x 1 , x 2 , x 3 , x 4 , x 5 ) = x 1 ⊕ x 2 ⊕ (x 1 ⊕ x 3 )(x 2 ⊕ x 4 ) ⊕ x 5 .
This predicate leads to a PRG with locality five. This predicate was introduced and studied in [START_REF] Lombardi | Minimizing the complexity of goldreich's pseudorandom generator[END_REF], were it was shown that it provably resists all F 2 -linear attacks, as well as all attacks using the SDP hierarchies (such as the Lassere-Parrilo sum-of-squares hierarchy), when stretching n bits to n 1.25-ε bits. In addition, this predicate enjoys an optimaly low arithmetic degree, since it can be computed by the following degree 3 polynomial over the integers:

P LV (x 1 , x 2 , x 3 , x 4 , x 5 ) = x 5 + (x 1 (x 4 -1) + x 2 (x 1 + x 3 -1) -x 3 x 4 ) • (2x 5 -1) .

(In)Security of the CDH Assumption and Homomorphic Computation in the Exponent

In this section, we show how to perform homomorphic computations in the exponent using a CDH solver. The content in this section will mainly be used in Section 5, where we construct NIZK from the insecurity of CDH. Therefore, a reader may safely skip this section and come back when necessary.

Background: CDH Solver

Looking ahead, we will be considering the case where CDH does not hold in Section 5. Then, we are able to use a CDH solver to construct a self-bilinear map algorithm. To this end, we (informally) require the CDH solver to always be correct when solving the CDH problem. Maurer and Wolf [START_REF] Maurer | Diffie-Hellman oracles[END_REF] and Shoup [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] independently showed that a CDH solver with non-negligible advantage can be amplified to a CDH solver with 1 -δ advantage for arbitrary 0 < δ < 1. Below, we provide Shoup's result as it is slightly more efficient.

Lemma 19 (Amplifying CDH Solver). Assume the CDH assumption relative to DHGen does not hold; that is, assume there exists a PPT adversary A , a polynomial ν(λ) such that for infinitely many λ ∈ N,

Pr[g αβ ← r A (1 λ , G, g, g α , g β )] > 1/ν(λ),
where G ← DHGen(1 λ ) and the probability is taken over the random choices of A and (g, α, β).

Then, for any δ(λ), with 0 < δ(λ) < 1, we can construct an algorithm A such that Pr[

g αβ ← r A(1 λ , G, g, g α , g β )] > 1 -δ(λ)
[∀(g, α, β) ∈ G × Z 2 p : g αβ ← r A(1 λ , G, g, g α , g β )] > 1 -2 -cλ
where the probability is taken over the randomness of A. We call such a PPT adversary A as a strong CDH solver with advantage 1 -2 -cλ .

Homomorphic Computation in the Exponent

We prepare some tools to compute a function in the exponent assuming CDH is easy.

Integer Arithmetic Circuits. An integer arithmetic circuit (IAC) C : Z n → Z is specified by a directed acyclic graph (DAG) where the vertices of C are called gates. We call gates of in-degree 0 as input gates (or simply input) and the gate of out-degree 0 as an output gate (or simply output). In this work, we consider circuits with addition gates, multiplication gates, and the one-input gate g : z → -z. The size of C is the number of gates excluding the input and output gates. The degree of C is the degree of the multivariate polynomial it computes.

Algorithms for Homomorphic Computation. Using a (strong) CDH solver, we are able to homomorphically compute in the exponent.

Theorem 21. Let {C λ } λ∈N be an ensemble of sets of IAC where each circuit in C λ has input length n = n(λ) and size L = L(λ). Let the CDH assumption relative to DHGen be easy. Moreover, let S ⊂ N be the infinite set of security parameters for which a strong CDH solver exists. Then there exists a PPT algorithm EvalCom and a deterministic polytime algorithm EvalOpen with the following properties for all λ ∈ S:

-EvalCom(C, g 1 , • • • , g n ) → h: on input an IAC C ∈ C λ and (g 1 , • • • , g n ) ∈ G, it outputs h ∈ G. -EvalOpen(C, z 1 , b 1 , • • • , z n , b n ) → z: on input an IAC C ∈ C λ and ((z 1 , b 1 ), • • • , (z n , b n )) ∈ (Z × {0, 1}) n , it outputs z ∈ Z. -Let ( , t) ∈ N 2 such that + t > 2L 2 . Further, assume p = |G| to be greater than L( + t) • log 2 B
where

B = max C∈C λ ,(bi∈{0,1})i C(b 1 , • • • , b n ). Let b i ∈ {0, 1} and w i ∈ [-2 , 2 ] for all i ∈ [n].
Then, for any C ∈ C λ with degree D and

g i = g wi+2 +t bi , if we run h ← r EvalCom(C, g 1 , • • • , g n ),
we have

dlog g h = w * +2 (D+1)( +t) •C(b 1 , • • • , b n ), where w * ∈ [±(2 D( +L+t+2) )] and EvalOpen(C, (w i , b i ) i≤n ) = w * , except with negligible probability 2 -λ .
Proof. EvalCom evaluates the IAC in a gate-by-gate fashion, using a strong CDH solver with advantage 1 -2 -λ . We describe below the procedures that EvalCom uses for each gate. The inputs for each gates are of the form g 0 = g w0+2 0 +t b0 and g 1 = g w1+2 1 +t b1 , where w 0 ∈ [-2 0 , 2 0 ] and

w 1 ∈ [-2 1 , 2 1 ] and (b 0 , b 1 ) ∈ Z 2 .
Here, b 0 and b 1 are the intermediate values computed by the IAC and we assume without loss of generality that 0 are 1 are known. Note that in case we consider the inversion gate, which only has one input, we only consider the terms with subscript 0.

Inversions. On input g 0 = g w0+2 0 +t b0 , output g -1 0 = g w +2 0 +t (-b0) , with w = -w 0 ∈ [-2 0 , 2 0 ]. Addition gates.

-Input. g 0 = g w0+2 0 +t b0 and g 1 = g w1+2 1 +t b1 . Assume without loss of generality that 0 ≥ 1 .

-Computation.

h ← g w0+2 0 +t b0 g w1+2 1 +t b1 2 0 -1 = g w+2 0 +t (b0+b1) ,

with w = w 0 + 2 0-1 w 1 ∈ [±(2 0+1 )].
Multiplication gates.

-Input. g 0 = g w0+2 0 +t b0 and g 1 = g w1+2 1 +t b1 .

-Computation. Use the strong CDH solver to compute h = g (w0+2 0 +t b0)(w1+2 1 +t b1) .

We have h = g w+2 0 + 1 +2t (b0b1) , with

w = w 0 (w 1 + 2 1 +t b 1 ) + w 1 (2 0 +t b 0 ) ∈ [±(2 0 + 1 + 2 0 + 1 +t • (b 0 + b 1 ))] ∈ [±2 0+ 1+t+D+1 ],
where the last equation follows since we have b 0 , b 1 ≤ 2 D-1 for any internal wire values of a degree-D IAC when the initial inputs to the IAC are bits.

Using a simple induction argument, it can be checked that if the input to EvalCom is given by (g i = g wi+2 +t bi ) i≤n with w i ∈ [-2 , 2 ] and b i ∈ {0, 1} for i = 1 to n, then it holds that

dlog g h = w * + 2 (D+1)( +t) • C(b 1 , • • • , b n ), where w * ∈ [±(2 D( +L+t+2) )],
except with probability at most 2 -λ . The bound on the probability is due to the fact that for 1 -2 λ fraction of the randomness used by the strong CDH solver, it correctly solves the CDH problem for any pairs of input. Eventually, EvalOpen is straightforward: on input (w i , b i ) i≤n , it follows the above procedures, computing directly with the exponents, to get the "w part" of dlog g (h).

Bounded Integer Arithmetic Circuits. The above bounds can be improved when the intermediate values of the b i are guaranteed to remain small. While the above bound uses the straighforward b i ≤ 2 D-1 , in our specific application it will always be the case that any intermediate b i belongs to [±1]. In this case, the bound on w for the multiplication gate becomes w ∈ [±2 0+ 1+t+2 ]. When this is the case, by induction, it holds that h = g w+2 D( +t) C(b1,••• ,bn) , where w ∈ [±(2 D( +L)+(D-1)(t+2) )], except with probability at most 2 -λ .

NIZK based on the Security of CDH and Strong OW-KDM Security of ElGamal

In this section, we describe a construction of a NIZK from the strong OW-KDM security of ElGamal with respect to efficient functions by assuming the CDH problem is hard to solve. We first provide a NIZK for the specific language of the Diffie-Hellman (DH) language. This is done by constructing a CIH based on the strong OW-KDM security of ElGamal for the natural sparse relation induced by the Σ-protocol for DH languages. We then show that such a NIZK for the DH language allows us to construct a VPRG, which in return, allows us to construct a NIZK for all of NP by Theorem 7.

4.1 Σ-Protocol for the Diffie-Hellman Language Definition 22 (Diffie-Hellman Language). Let G be a group with prime order p. We define the Diffie-Hellman (DH) language L DH,t parameterized by t ∈ Z * p as

L DH,t = {(g, h, g x , h x ) : g, h ∈ G, x ∈ Z p , dlog g h = t}.
Below we recall the standard Σ-protocol for the DH relation (with parallel repetition). Here, the word is (g, h, X, Y ) ∈ L DH,t where (X, Y ) = (g x , h x ).

Prover Verifier (r1, r2) ←r Z 2 p and set (R1, S1) = (g

r 1 , h r 1 ) (R2, S2) = (g r 2 , h r 2 ) (e1, e2) ←r (Z * p ) 2 d1 = e1 • x + r1 d2 = e2 • x + r2 Check g d i = X e i • Ri and h d i = Y e i • Si, for i ∈ {1, 2} (R1, S1, R2, S2) e1, e2 d1, d2
Fig. 2. Σ-protocol for the Diffie-Hellman language for the word (g, h, X = g x , Y = h x ).

The above Σ-protocol achieves the standard notion of correctness and special honest-verifier zeroknowledge. Adaptive soundness is covered by the following lemma.

Lemma 23 (Adaptive Soundness). The Σ-protocol in Figure 2 satisfies 1 p-1 -adaptive soundness.

Proof. Let the word be (X = g x , Y = g y ). For i ∈ {1, 2}, let s i be the exponent of S i , i.e. S i = g si .

In order for the verifier to accept, the following must hold:

e i • y = r i • t + e i • x • t -s i , for i ∈ {1, 2},
which implies that:

y = t(ri+ei•x)-si ei = t•ri-si ei + t • x, for i ∈ {1, 2}
We distinguish the following two cases:

1. If t • r i = s i for either i ∈ {1, 2}, then y = t • x and the word is in the language.

2. If t • r i = s i for both i ∈ {1, 2}, then t•r1-s1 t•r2-s2 • e 2 = e 1 , which happens with probability at most 1 p-1 over the randomness of (e 1 , e 2 ) ← r (Z 2 p ) * .

We can ignore the first case since it does not lead to a valid cheating prover for adaptive soundness.

In the second case, a cheating prover has at most 1 p-1 possibility of breaking adaptive soundness. Hence the statement follows.

Correlation-Intractable Hash Function H

Let λ be a 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 :

-Sampling the key: pick ( G, k, m) ← r G × Z 2 q and set the key as C ← r Enc G(k, m). Note that the key distribution is exactly the uniform distribution over G2 .

-

Evaluating H λ ( C, •) : H λ ( C, x) = Trunc(HalfDec(x, C)).
Below, we omit the subscript on H for simplicity.

Correlation-Intractability of H. Consider a group G of order p(λ) with log p ≈ λ/4. Then the output of H can be interpreted as two elements of G. Fix a parameter t ∈ Z * p . Define R λ,t to be the natural sparse relation associated to the language L DH,t (see Lemma 14). That is,

R λ,t = {(α, β) ∈ G 4 × (Z * p ) 2 : ∃x, γ s.t. x / ∈ L DH,t ∧ V (x, α, β, γ) = accept}.
Here, the above relation can also be described alternatively using the following (inefficient) randomized function (which follows from the argument within the proof of Lemma 23 ):

f t (a; z) : G 4 × Z * p → (Z * p ) 2 (R 1 , S 1 , R 2 , S 2 ) × z → (z, log (R t 1 /S1) (R t 2 /S 2 ) • z)
.

The following is the main contribution of this section.

Theorem 24. Assume that ElGamal satisfies 2 -3λ/4 -OW-KDM security with respect to efficient functions. Then the hash family

{H : G2 × Z q → {0, 1} λ/2 } λ is correlation-intractable with respect to R H := {R λ := {R λ,t } t } λ .
Proof. We prove the theorem in two steps. We first show that an adversary against the correlation intractability of H can be shown to be an adversary against the OW-KDM security of ElGamal with respect to inefficient functions. We then show via the symmetry of messages and secret keys of ElGamal to conclude that such an adversary can indeed be used to break OW-KDM security of ElGamal with respect to efficient functions. The first step is summarized in the following lemma. The proof follows closely the approach of [START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF], but simplifies some steps of the proof and makes the exact security loss explicit.

Lemma 25. Let A be an adversary against the R H -correlation intractability of H with (non-negligible) advantage ε(λ). Then, for some t ∈ Z * p , it holds that:

Pr ( G,a * ,m)←r G×Z 2 q C←rEnc G (a * ,m) [A( G, C) = a * |(a * , H( C, a * )) ∈ R λ,t ] ≥ ε(λ) 2 3λ/4 .
Proof. By assumption, we have the following for some R λ,t ∈ R λ .

Pr   ( G, k, m) ← r G × Z 2 q C ← r Enc G(k, m) : (a, H( C, a)) ∈ R λ,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 λ,t C ← r Enc G(k, m)   ≥ ε(λ) 2 λ ,
since this is exactly the probability that A wins the correlation intractability game and A( G, C) = a * . 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 λ,t C ← r Enc G(a * , m)   ≥ ε(λ) 2 λ .
We now introduce another (inefficient) randomized function α t :

α t : 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

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 λ , since given C ← r Enc G(a * , m), it holds that (a * , H( C, a * )) ∈ R λ,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 ) ← r {0, 1} λ/2 × Z *
p } be the set of challenges for which there exists an accepting last flow and word, such that a * is the first flow. Now, observe that our probability becomes:

Pr   ( G, a * ) ← r G × Z q m ← r S t, G,a * : A( G, C) = a * C ← r Enc G(a * , m)   = q-1 i=0 Pr a * ←rZq [a * = i] • Pr   G ← r G m ← r S t, G,i : A( G, C) = i C ← r Enc G(i, m)   ≥ q-1 i=0 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) ← r G × Z q : ∃z 1 , z 2 , m = α t ( G, i; z 1 , z 2 )]
Furthermore, it is straightforward to check that for any i,

Pr m←rZq [∃(z 1 , z 2 ), m = α t ( G, i; z 1 , z 2 )] ≤ 2 -λ/4 .
The statement is equivalent to "∃(z 1 , z 2 ), Gm = f t (i; z 2 )||z 1 ", which further translates to the "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 1 ∈ Z * p , where |Z * p | = 2 λ/4 , 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 λ/4 • q-1 i=0 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 )) = 2 λ/4 • 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 )) = ε(λ) 2 3λ/4 .
This concludes the proof of the lemma.

Given Lemma 25, it remains to show that this implies a contradiction to the OW-KDM security of ElGamal for efficient functions. The main difficulty here is that 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 3λ/4 . (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 ). which naturally translates to an adversary against the KDM security of ElGamal where m is sampled as α t ( G, a * ; z 1 , z 2 ), which is not an efficiently computable function. We show below how to get around this apparent issue. Define the (randomized) efficiently computable function f -1 t as follows:

f -1 t (e 1 , e 2 ; r 1 , r 2 , s 1 ) := (Z * p ) 2 × G 3 → G 4 (e 1 , e 2 ; r 1 , r 2 , s 1 ) → (g r1 , g s1 , g r2 , g e 2 (t•r 1 -s 1 ) e 1 -t•r2 ).
Furthermore, define F t to be the following (efficient, randomized) function:

F t : G × Z q × {0, 1} λ/2 → Z q ( G, m; z) → f -1 t (Trunc( Gm ); z), .
where we assume in case the first λ/4-bits of Trunc( Gm ) corresponds to 0 ∈ Z p , then it outputs some fixed element in Z q . Consider now the distribution obtained by sampling ( G, a * ) ← r G × Z q , m ← r α t ( G, a * ), and outputting C ← r Enc G(a * , m). Observe that we obtain the same distribution (up to some negligible difference) by first sampling ( G, m) ← r G × Z q , setting k ← r F t ( G, m), and outputting C ← r Enc G(k, m). We build upon this observation to construct, using A, an adversary against the one-query OW-KDM security of ElGamal with respect to the class of (efficient, randomized) functions {F t } t . Let A be the previous adversary, which satisfies Equation 1. By our observation above, this can be rewritten as

Pr ( G,k)←r G×Zq a * ←rFt( G,k) C←rEnc G(a * ,k) [A( G, C) = a * ] ≥ ε(λ) 2 3λ/4 .
We build an adversary B against the OW-KDM security of ElGamal 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 * ] ≥ ε(λ) 2 3λ/4 ,
which contradicts the (one-query) 2 -3λ/4 -OW-KDM security of ElGamal with respect to the family of (efficient, randomized) functions {F t } t . This concludes the proof of Theorem 24.

NIZK for L DH via R H -Correlation-Intractability

Lemma 26. Our R H -correlation intractable hash function family is programmable.

Proof. Given x ∈ Z q , y ∈ {0, 1} λ/2 , programming a key means efficiently sampling C uniformly from the set S = { C ∈ Z 2 q : Trunc(HalfDec(x, C)) = y}. We do this by sampling z ← r {0, 1} λ/2 , and then computing W ∈ G as the group element corresponding to the bitstring y z. Now choose C0 ← r G, compute C1 = Rx • W , and output C = ( C0 , C1 ). We output a particular C from S with probability 1 2 3λ/2 , which is exactly 1 |S| . Theorem 27 (NIZK for L DH ). Assume there exists a programmable correlation intractable hash family for relation R H . Then, there exists an adaptively sound and selective single-theorem zeroknowledge NIZK argument system for the Diffie-Hellman language L DH,t for any t ∈ Z * p . Moreover, our NIZK is independent of the value t and all algorithms can be run oblivious of the value t.

Proof. Fix t ∈ Z * p . Let Π DH,t Σ be the Σ-protocol for the DH language L DH,t = {(g, h, g τ , h τ ) : g, h ∈ G, τ ∈ Z p , dlog g h = t} depicted in Figure 2. Let P 1 , P 2 , and V be the corresponding algorithms for the first and second move of the prover Prove Σ and the verifier Verify Σ , respectively. Then, our NIZK for L DH,t is defined as follows:

-Setup DH (1 λ ) : sample a key k ← r K for the CIH hash H and output crs := k.

-Prove DH (crs, x, w) : on input word x := (g, h, X, Y ) ∈ L DH,t and witness w := τ ∈ Z p such that (X, Y ) = (g τ , h τ ), run α ← r P 1 (x, w) and compute β = H(k, α). If β ∈ (Z * p ) 2 , then output ⊥. Otherwise, further run γ ← r P 2 (x, w, α, β). Finally, output π = (α, γ).

-Verify DH (crs, x, π) : parse (α, γ) ← π. Compute β = H(k, α) and return V (x, α, β, γ).

Completeness of our NIZK follows from the completeness of the underlying Σ-protocol and noticing that with overwhelming probability over the choice of crs = k, we have H(k, α) ∈ (Z * p ) 2 . We proceed to show adaptive soundness and selective single-theorem zero-knowledge.

Adaptive Soundness. Suppose there exists a PPT cheating prover P * for the NIZK, that is,

Pr k←rK,crs:=k (x,π)←rP * (crs) [Verify DH (crs, x, π) = 1] ≥ (λ)
for a non-negligible (λ). Parse (g, h, X, Y ) ← x and (α, γ) ← π. Then, since x ∈ L DH,t and (α, β, γ) is an accepting proof, we have (α, β) ∈ R λ,t ∈ R H . Thus, using P * , we can construct a PPT adversary A such that

Pr k←rK α←rA(k) [(α, H(k, α)) ∈ R λ,t ] ≥ (λ).
However, this contradicts the correlation intractability of our hash function. Hence, (λ) is negligible, thus completing the proof.

Selective Single-Theorem ZK. This is a direct consequence of the special honest-verifier zeroknowledge property of the underlying Σ-protocol and the programmability of our CIH (see Lemma 26). In particular, on input a word x ∈ L DH,t , the ZK simulator Sim proceeds as follows: It samples β ← r (Z * p ) 2 and runs the ZK simulator for the Σ-protocol (α, β, γ) ← r Sim Σ (x, β). It then samples a uniformly random key k from K such that H(k, α) = β. Finally, it outputs (crs := k, π := (α, γ)). It can be checked that this is statistically indistinguishable from the real-world execution. This completes the proof.

As stated in Theorem 27, our NIZK for L DH,t is agnostic of the value of t ∈ Z * p , since the value of t is only significant during the security proof. Therefore, whenever the meaning is clear, we will drop the subscript t and simply state it as an NIZK for L DH . The important thing to keep in mind is that for each crs generated by Setup DH , it is only adaptive secure for L DH,t with a fixed t. That is, A cannot adaptively chose t after seeing crs.

VPRG from NIZK for L DH

Our construction relies on the CDH assumption and the NIZK argument system (Setup DH , Prove DH , Verify DH ) for L DH from the previous section. We prepare a predicate B : G 2 → {0, 1} satisfying the following property: given (g a , g b ), computing B(g b , g ab ) should be as hard (up to polynomial factors) as computing (g b , g ab ). Note that this implies that distinguishing B(g b , g ab ) from a random bit given random tuple (g a , g b ) is as hard as solving CDH. One way to instantiate such a predicate is to use the Goldreich-Levin hard-core predicate [START_REF] Goldreich | A hard-core predicate for all one-way functions[END_REF].

Construction. Let m := m(λ) be an arbitrary polynomial. Our construction of VPRG proceeds as follows:

-Setup(1 λ , m) : run G = (G, p) ← r DHGen(1 λ ) and sample g ← r G. Further, for i = 1 to m, pick h i ← r G and generate crs i ← r Setup DH (1 λ ). Finally, output pp = (g, (h i , crs i ) i≤m ). -Stretch(pp) : pick τ ← r Z p , set pvk ← g τ , and for i = 1 to m, set x i ← B(pvk, h τ i ). Output (pvk, x = (x i ) i≤m , aux = τ ).

-Prove(pp, aux, i) : set τ := aux and run

π DH i ← r Prove DH (crs i , (g, h i , pvk, h τ i ), τ ). Output π = (h τ i , π DH i ). -Verify(pp, pvk, i, b, π) : parse (u, π DH ) ← π. If b = B(pvk, u), then return Verify DH (crs i , (g, h i , pvk, u), π DH ).
Otherwise, return 0.

Security Analysis. Correctness of the VPRG follows from the correctness of the underlying NIZK.

In addition, the size of the verification key g τ is p, and in particular, is independent of m. Hence, we can set the stretch δ := δ(λ) to be an arbitrary polynomial, where we can set m = s 1+δ by definition.

Theorem 28. If the CDH assumption holds relative to DHGen and the NIZK argument system for the Diffie-Hellman language L DH is adaptive sound and selective single-theorem, then the above construction provides a (δ, s)-VPRG that is binding and hiding, where δ is an arbitrary polynomial in the security parameter λ and s = |G|.

The binding property is shown by guessing the position where the adversary forges an opening, and showing that this implies an adversary against the adaptive soundness of the NIZK for DDH. Hiding relies on a careful modification of the CRS generation, together with the zero-knowledge property of the NIZK for DDH. We provide a complete proof below.

Proof. We provide a proof of binding and hiding.

Binding. Assume there exists a PPT adversary A that breaks the binding property with nonnegligible probability with respect to the inefficient extractor Ext defined as follows: on input (pp, pvk), Ext first computes the exponent τ such that pvk = g τ and then outputs (x i = B(pvk, h τ i )) i≤m . Then, for any t ∈ Z * p , we construct a PPT adversary B that breaks adaptive soundness of NIZK for the language L DH,t with advantage /m which forms a contradiction. The description of B on input crs is as follows:

B(crs): randomly pick i * ← r [m]. Then, sample g ← r G, h i ← r G, and generate crs i ← r Setup DH (1 λ ) for i ∈ [m]\{i * }.
Set h i * := g t and crs i * := crs and output pp = (g, (h i , crs i ) i≤m ) to A. When A outputs (pvk, i , π), check i = i * . If not, abort. Otherwise, parse (u, π DH ) ← π and output

(x = (g, h i * , pvk, u), π = π DH ).
We analyze the success probability of B. Let us condition on i = i * , which happens with probability 1/m. Let pvk = g τ . When A succeeds in breaking the binding property, then B(g τ , h τ i * ) = B(g τ , u), where the left hand side is the output of the (inefficient) extractor Ext. In particular, this implies h τ i * = u. Therefore, (g, h i * , pvk = g τ , u) ∈ L DH,t . Hence, B breaks adaptive soundness with probability /m.

Hiding. Consider a PPT adversary A that takes part in the hiding property experiment. We show that any A must have negligible advantage assuming selective single-theorem ZK and the CDH assumption. To this end, consider the following sequence of hybrids. Below, we fix i

* ∈ [m].
H 0 : This is the real experiment. Namely, we run pp ← r Setup(1 λ , m), (pvk, x, aux) ← r Stretch(pp), (π i ← r Prove(pp, aux, i)) i , and provide A with (pp, pvk, i * , (x i , π i ) i =i * ). H 1 : This experiment is identical to H 0 except that we modify how we sample (g, (h i ) i≤m ). Namely, we first sample g, h i * ← r G, τ ← r Z p , and set pvk := g τ . We then continue to sample r i ← r Z p and set h i := g ri for i ∈ [m]\{i * }. Note that the generation of (crs i ) i≤m is postponed after pvk = g τ and (g, (h i ) i≤m ) are generated. H 2 : This experiment is identical to H 1 except that we use the ZK simulator to generate crs i and π i for all i ∈ [m]. Namely, we run m-parallel runs of the (selective single-theorem) ZK simulator to generate m-pairs of crs and proof:

(crs i , π DH i ) ← r Sim((g, h i , X, Y i )) for i ∈ [m]
, where X = g τ and Y i = X ri . Notice that at this point, we only require knowledge of τ when setting pvk.

It can be seen that the advantage of A in experiment H 0 and H 1 is exactly the same since the distributions of the input to A are identical in both experiment. Moreover, going over m-hybrids, it is clear that H 1 and H 2 are computationally indistinguishable assuming the selective single-theorem ZK property of NIZK. Finally, we end the proof by showing that an algorithm A that wins in experiment H 2 can be use to distinguish the hard core bit of the DH tuple, which is hard as solving the CDH problem. Namely, given (g, g a , g b ) it is hard to distinguish B(g b , g ab ) from random.

Let B be an adversary that tries to distinguish the hard core bit of the DH tuple: On input (g, g a , g b ), B sets g := g, h i * := g a , pvk := g b , where B implicitly sets τ = b. Then, B simply runs the experiment in H 2 with A, which it can since knowledge of a or b are not required. When A(pp, pvk, i * , (x i , π i ) i =i * ) outputs a bit d, B outputs it as its guess for B(g b , g ab ). Since B(g b , g ab ) = B(pvk, h τ i * ), B's advantage is the same as A's advantage against experiment H 2 . Due to the hardness of the CDH problem, we conclude that A has negligible advantage against H 2 , hence also against experiment H 0 . This concludes the proof.

As a direct consequence of Theorems 7, 24, 27, and 28, the following is obtained.

Theorem 29. Assume that the CDH assumption holds relative to DHGen and that ElGamal satisfies 2 -3λ/4 -OW-KDM security with respect to efficient functions, then there exists an adaptive sound and adaptive multi-theorem NIZK for all of NP.

NIZK from Insecurity of CDH and Strong OW-KDM Security of ElGamal

In this section, we describe a construction of an infinitely often NIZK from the strong OW-KDM security of ElGamal with respect to efficient functions by assuming that the CDH problem is easy to solve. We first provide a NIZK for the specific language of the almost-short language. This is done by constructing a CIH based on the strong OW-KDM security of ElGamal for the natural sparse relation induced by the Σ-protocol for the almost-short language. We then show that such a NIZK for the almost-short language along with the short-exponent discrete-log (SEDL) assumption allows us to construct a VPRG, which in return, allows us to construct an (infinitely often) NIZK for all of NP by Theorem 7. Note that, as we will show, SEDL is not an extra assumption since it follows from the strong OW-KDM security of ElGamal.

Σ-Protocol for the Language of Almost-Short Elements

In this section, we introduce the language L α,β of elements of G with (α, β)-almost-short exponents to be the subset of G containing elements of the form g x where x is almost-short. We say that x is (α, β)-almost-short if there exists a short value v ∈ [2 β ] such that vx is short as well: vx

∈ [±2 α ].
More formally:

Definition 30 ((α, β)-Almost-Shortness). Let G be a group of prime order p. We define L α,β over G with respect to the generator g ∈ G to be the language of (α, β)-almost-short elements as:

L α,β = {g x | x = u • v -1 ∈ Z p , int(u) ∈ [±2 α ], int(v) ∈ [2 β ]}.
A Σ-Protocol for the Almost-Short Language. We start by introducing a simple Σ-protocol for proving membership of an element g x ∈ G to L α,β . The protocol satisfies the following relaxed notion of correctness: an honest prover is guaranteed to produce an accepting proof if the input word g x is such that x ≤ 2 (with log p ), but soundness only guarantees that the word actually belongs to L ,c , where c is the challenge length, and > c + + κ, for some statistical security parameter κ. 7 The protocol is represented on Figure 3. Note that it only satisfies selective soundness. We prove the following lemmas: Lemma 31 (Correctness). If x ∈ [0, 2 ], and > max{c, } + κ, then the Σ-protocol from Figure 3 is correct (and the verifier accepts with probability greater than 1 -1 2 κ ).

Prover Verifier

r ←r [±2 -1 ] e ←r [2 c ] d = e • x + r Check g d = g r • (g x ) e and int(d) ∈ [±2 -1 ]
g r e d Fig. 3. Σ-protocol for the almost-shortness language, for the word g x . In a honest run, the prover possesses a short witness x ∈ [0, 2 ] Sim(g x )

d ←r [±2 -1 ] e ←r [2 c ] g r ← g d /(g x ) e
Return (g r , e, d).

Fig. 4. Simulator for the almost-shortness sigma protocol in figure 3.

Proof. It is immediate by inspection that the first check

g d = g r • (g x ) e holds. Moreover, since x ∈ [0, 2 ], r ← r [±2 ]
, and e ← r [2 c ], int(d) will always be greater than -2 . Let us upper bound the probability for which int(d) > 2 . Fixing on the worst choice of x = 2 and e = 2 c , the probability that int(d) > 2 is (2 + 2 c + 1)/(2 ) over the random choice of r. Hence, if ≥ κ + 1 + max{ , c}, then the verifier will accept with probability greater than 1 -1 2 κ . Lemma 32 (Selective Soundness). If X / ∈ L ,c , then the probability that the verifier accepts is at most ], which implies that g x indeed belongs to L ,c Note that this implies, in particular, that for any word X / ∈ L ,c and for any first flow R = g r , there exists at most a single challenge e ∈ [2 c ] for which there exists a d such that (R, e, d) is an accepting transcript.

Lemma 33 (Honest-Verifier Zero-Knowledge). When > c + + κ and x ∈ [0, 2 ), the Σprotocol in Figure 3 is honest-verifier zero-knowledge for words in x ∈ [0, 2 ]. In particular, the statistical distance between honest transcripts and those produced by the simulator in Figure 4is

{(r, d) : d ← r [-2 -1 , 2 -1 -2 +c ], r := d + xe} and {(r, d) : r ← r [-2 -1 + xe, 2 -1 -2 +c + xe], d := r -xe}.
Since this holds for any e and x, the distribution

D 1 conditioned on r ∈ [-2 -1 + xe, 2 -1 -2 +c + xe] and the distribution D 2 conditioned on d ∈ [-2 -1 , 2 -1 -2 +c ] are identical.
Observing that such distributions are at most statistical distance 2 +c /2 -1 each from D 1 and D 2 , respectively, the statistical distance between D 1 and D 2 is at most

2 +c+1 /2 -1 ≥ 2 κ .
Adaptive Soundness. The above protocol only enjoys selective soundness, which does not suffice in our context. As for our previous construction, however, adaptive soundness can be obtained using sufficiently many parallel repetitions of the underlying Σ-protocol, via standard complexity leveraging: since there are p possible words g x , if the above Σ-protocol is amplified N -times with N ≥ log p /c, then it is p/2 N •c -adaptively sound. We denote Π N (p, , κ, c) the Σ-protocol obtained by repeating N times in parallel the above Σ-protocol for L ,c , with = + c + κ + 1. When (p, , κ, c) are clear from the context, we simply denote it Π N .

Admissible First Flow. Given a Σ-protocol for a language L , we say that a candidate first flow a is (adaptively) admissible if there exists a word X / ∈ L , a challenge e, and an answer d, such that (a, e, d) form an accepting transcript for X. Note that in Π N , there are p N possible first flows, but only p • 2 N ( +c) admissible first flows, since an admissible first flow is of the form (g di /(g x ) ei ) i≤N , for some d i ∈ [±2 -1 ], e i ∈ [2 c ], and g x ∈ G.

Correlation-Intractable Hash Function

Let λ be a security parameter and fix parameters (N (λ), c(λ), p(λ), (λ), κ(λ)). We consider a group G of order q(λ) with log q ≈ λ, and a group G of order p(λ). Let Trunc : G → {0, 1} N •c be the function which, on input a group element G ∈ G, parses it as a log q -bit string and returns the first N • c bits of its input. Let h : G N → {0, 1} λ be a 2-universal hash function, for a security parameter λ which will be defined afterward. We consider the following hash function

H λ : G2 × G N → {0, 1} N •c : -Sampling the key: pick ( G, k, m) ← r G × Z 2
q and set the key as C ← r Enc G(k, m). Note that the key distribution is exactly the uniform distribution over G2 .

-

Evaluating H λ ( C, •) : H λ ( C, x) = Trunc (HalfDec(h(x), C)).
Setting the Security Parameter λ. Let R λ (N, c, p, , κ) = R λ be the natural sparse relation associated to the language L ,c over G with respect to a generator g ∈ G, where = + c + κ (see Lemma 14). That is,

R λ = {(a, b) ∈ G N × {0, 1} N •c : ∃X, d s.t. X / ∈ L ,c ∧ V (X, a, b, c) = accept},
where V is the verifier from the Σ-protocol for the language L ,c in Figure 3. The purpose of the 2-universal hash function h in our correlation-intractable hash H λ is to compress the size of the first flow to λ bits, without significantly decreasing the winning probability of the adversary. The core observation is that when the adversary manages to output a such that (a, H λ ( C, a)) ∈ R λ , then a must at least be an admissible first flow. Since there are at most p • 2 N ( +c) admissible first flows, we set λ ← log p +N ( +c)+κ, where κ is some statistical security parameter. Then, the 2-universality of h guarantees that, except with probability at most 2 -κ over the random choice of the hash key, all possible λ-bit strings will have at most a single admissible preimage a. In the following, we denote by Invh the (inefficient) function which, on input a λ-bit string s, outputs the unique admissible preimage of s (or ⊥ if s has no admissible preimage).

Correlation-Intractability of H .

Theorem 34. Fix parameters (N (λ), c(λ), p(λ), (λ), κ(λ)). Assume that ElGamal satisfies p -1 • 2 N c-λ -OW-KDM security with respect to efficient functions. Then the hash family

{H λ : G2 × G N → {0, 1} N •c } λ is correlation-intractable with respect to R H := {R λ (N, c, p, , κ)} λ = {R λ } λ .
The structure of the proof is similar to the proof of Theorem 24, the core difference being that we rely on a 2-universal hash function to compress the size of the first flow, and only guess the compressed hash; then, we rely on the fact the 2-universal hash is injective with high probability over the set of admissible first flow. The formal proof is given below.

Proof. The structure of the proof is similar to the proof of Theorem 24. Let A be an adversary against the correlation intractability of H λ , that is, there is a non-negligible ε such that

Pr   ( G, k, m) ← r G × Z 2 q C ← r Enc G(k, m) : (a, H λ ( C, a)) ∈ R λ a ← r A( G, C)   ≥ ε(λ).
Recall that previously, at this step we sampled independently at random an input a * ← r G N . However, in the current context, this would be wasteful as most a are not admissible; instead, we design a more optimized strategy, where a is hashed down to h(a), and we only guess the (smaller) value of h(a), which is injective (w.h.p.) over the set of admissible first flows. Using the definition of H λ ,

Pr   ( G, k, m) ← r G × {0, 1} λ × Z q C ← r Enc G(k, m) : (a, Trunc ( C1 / Ch(a) 0 )) ∈ R λ a ← r A( G, C)   ≥ ε(λ).
We now sample independently a uniformly random value v * in {0, 1} λ :

Pr     ( G, k, m) ← r G × {0, 1} λ × Z q C ← r Enc G(k, m) : (a, Trunc ( C1 / Cv * 0 )) ∈ R λ a ← r A( G, C) ∧ h(a) = v * v * ← r {0, 1} λ     ≥ ε(λ) 2 λ .
Using the universality of ElGamal:

Pr   ( G, v * , m) ← r G × {0, 1} λ × Z q C ← r Enc G(v * , m) : (a, Trunc ( Gm )) ∈ R λ a ← r A( G, C) ∧ h(a) = v *   ≥ ε(λ) 2 λ ,
where we use the fact that now C1 / Cv * 0 = Gm . This gives,

Pr ( G, v * , m) ← r G × {0, 1} λ × Z q : (Invh(v * ), Trunc ( Gm )) ∈ R λ C ← r Enc G(v * , m) ∧ A( G, C) = Invh(v * ) ≥ ε(λ) 2 λ . Now, denote D( G, a * ) the uniform distribution of m over Z q conditioned on (a * , Trunc ( Gm )) ∈ R λ . Observe that Pr   ( G, v * ) ← r G × {0, 1} λ m ← r D( G, Invh(v * )) : A( G, C) = Invh(v * ) C ← r Enc G(v * , m)   = i∈{0,1} λ Pr v * ←r{0,1} λ [v * = i] • Pr   G ← r G m ← r D( G, Invh(v * )) : A( G, C) = Invh(v * ) C ← r Enc G(v * , m)   ≥ i∈{0,1} λ Pr v * ←r{0,1} λ [v * = i] • Pr ( G, m) ← r G × Z q : A( G, C) = Invh(i) C ← r Enc G(i, m) ∧(Invh(i), Trunc ( Gm )) ∈ R λ Pr[( G, m) ← r G × Z q : (Invh(i), Trunc ( Gm )) ∈ R λ ]
Furthermore, for any i ∈ {0, 1} λ ,

Pr[( G, m) ← r G × Z q : (Invh(i), Trunc ( Gm )) ∈ R λ ] ≤ p/2 N c ,
by the adaptive soundness of Π N since Trunc ( Gm ) is distributed uniformly random over {0, 1} N •c (see Definition 13 and Lemma 14). Hence:

Pr   ( G, v * ) ← r G × {0, 1} λ m ← r D( G, Invh(v * )) : A( G, C) = Invh(v * ) C ← r Enc G(v * , m)   ≥ 2 N c p • i∈{0,1} λ Pr v * ←r{0,1} λ [v * = i] • Pr ( G, m) ← r G × Z q : A( G, C) = Invh(i * ) C ← r Enc G(i * , m) ∧(Invh(i * ), Trunc ( Gm )) ∈ R λ = 2 N c p • Pr ( G, v * , m) ← r G × {0, 1} λ × Z q : A( G, C) = Invh(v * ) C ← r Enc G(v * , m) ∧(Invh(v * ), Trunc ( Gm )) ∈ R λ ≥ 2 N c • ε(λ) p • 2 λ .
Let A be an algorithm that, on input ( G, C), outputs h(A( G, C)). From the above inequality, we get:

Pr   ( G, v * ) ← r G × {0, 1} λ m ← r D( G, Invh(v * )) : A ( G, C) = v * C ← r Enc G(v * , m)   ≥ 2 N c • ε(λ) p • 2 λ .
From there, we can apply the same strategy as before to show that there exists an algorithm B such that

Pr ( G,k)←r G×Zq x * ←rF par ( G,k) C←rEnc G (k,x * ) [B( G, C) = x * ] ≥ 2 N c • ε(λ) p • 2 λ
where

F par : G × Z q × ×{0, 1} N c-(λ+ log p ) → Z q ( G, m; z) → (f ) -1 par (Trunc( Gm ); z),
where f par is the (inefficient, randomized) function that, on input a first flow a, samples a uniformly random challenge e conditioned on (a, e) ∈ R λ (or ⊥ when there is no such e), and (f ) -1 par is the (efficient, randomized) function that, given a challenge e, compute a uniformly random a subject to (a, e) ∈ R λ . That is, on input

(e 1 , • • • , e N ) ∈ [2 c ] N , (f ) -1 par picks uniformly random (d 1 , • • • , d N ) ∈ [±2 -1 ] N , a uniformly random word X / ∈ L ,c
, and outputs (g di • X -ei ) i≤N .

5.3

NIZK for the almost-short Language via R H -Correlation-Intractability Lemma 35. Our R H -correlation intractable hash function family is programmable.

The proof is essentially identical to the proof for R H .

Theorem 36 (NIZK for the almost-short language L ,c ). Assume there exists a programmable correlation intractable hash family for the relation R H . Then, there exists an adaptive sound and selective single-theorem zero-knowledge NIZK argument system for the almost-short language L ,c .

The proof of adaptive soundness and selective single-theorem zero-knowledge are essentially identical to the proof of Theorem 27. We only provide an explicit description of the NIZK proof system. Let Π N be the Σ-protocol for the AS language L ,c depicted in Figure 3. Let P 1 , P 2 , and V be the corresponding algorithms for the first and second move of the prover Prove AS and the verifier Verify AS , respectively. Then, our NIZK for L ,c is defined as follows:

-Setup AS (1 λ ) : sample a key k ← r K for the CIH hash H and output crs = k.

-Prove AS (crs, x, w) : on input word x ∈ L ,c and witness w ∈ [START_REF] Alekhnovich | Exponential lower bounds for the running time of dpll algorithms on satisfiable formulas[END_REF] such that x = g w , run α ← r P 1 (x, w) and compute β = H(k, α). Then, further run γ ← r P 2 (x, w, α, β). Finally, output π AS = (α, γ). -Verify AS (crs, x, π AS ) : parse (α, γ) ← π. Compute β = H(k, α) and return V (x, α, β, γ).

A Commitment Scheme from the Short-Exponent Discrete Logarithm Assumption

Before providing our VPRG construction, we introduce one last set of tools. We first introduce the T -short-exponent discrete-logarithm (T -SEDL) assumption and then provide a simple commitment scheme based on T -SEDL.

Definition 37. The T -SEDL assumption over an abelian group G of order p with respect to the generator g states that for every PPT A,

Pr[x ← r [p/T ], h ← g x : A(h) = x] ≈ 0.
It is well known that under the T -SEDL assumption, it is infeasible to distinguish {g x | x ← r [p/T ]} from the uniform distribution over G [START_REF] Koshiba | Short exponent Diffie-Hellman problems[END_REF].

A Commitment from T -SEDL. A commitment scheme is a pair of algorithms (Commit, Open) such that given (c, d) ← r Commit(m), c hides m (more formally, no adversary can distinguish whether c was output by Commit(m) or Commit(m ), for two messages (m, m ) of their choice), but d binds the committer to m (more formally, no adversary can find (c, d, d , m, m ) with m = m such that Open(c, d, m) = Open(c, d , m ) = 1). We now introduce the bit commitment scheme that will underly our construction. Let G be a group of order p. Fix some integers ( , k). Commit(b), on input a bit b, picks w ← r {0, 1} and outputs com = g w+2 k b . Opening the commitment is done by revealing w. The commitment is perfectly binding, and hiding under the p/2 -SEDL assumption.

From T -SEDL to Strong OW-KDM Security of ElGamal. We now show that the T -SEDL assumption is already implied by the strong OW-KDM security of ElGamal (in fact, even by the assumption that no PPT can solve the discrete logarithm assumption with probability better than 1/T ); since our final construction will rely (in particular) on both assumptions, this shows that T -SEDL will be redundant with our other assumptions. Proof. Suppose that there exists a PPT adversary A which breaks the T -SEDL assumption over G with probability ε. Then we have:

Pr[x ← r [p/T ] : A(g x ) = x] ≥ ε =⇒ Pr[x ← r Z p : A(g x ) = x | x ≤ p/T ] ≥ ε =⇒ Pr[x ← r Z p : A(g x ) = x ∧ x ≤ p/T ] ≥ ε • Pr[x ← r Z p : x ≤ p/T ] =⇒ Pr[x ← r Z p : A(g x ) = x] ≥ ε/T
Therefore, A also solves the standard discrete logarithm assumption, with probability at least ε/T . From there, it is straighforward to build an adversary that breaks the OW-KDM security of ElGamal (with respect to any efficient function) with the same probability ε/T .

Binding Property with Almost-Short Randomness. A useful property of the above commitment, which will play a crucial role in our construction, is that it remains computationally binding if instead of revealing w, the opener reveals b and proves (using any computationally binding argument) that com • g -2 k b ∈ L α,β , provided that k ≥ α + 2 and under some condition on the size p of the group. We elaborate below. Lemma 39. Let com = g w+2 α+2 b be a commitment to b, where g w ∈ L α,β . Further assume that p > 2 α+2β+4 . Then no computationally bounded prover can produce an accepting argument that g w+2 α+2 ∈ L α,β .

Looking ahead, we will use this lemma together with a NIZK with relaxed correctness for the language L α,β to guarantee correct opening of the above commitment. The relaxed correctness requirement is the same as in Section 5.1 and will be satisfied when the commitment is constructed honestly.

Proof. Let com ∈ G be any group element. We prove that it can never simultaneously hold that com ∈ L α,β and com • g 2 α+2 ∈ L α,β . Assume toward contradiction that both com and com • g 2 α+2 belong to L α,β . Let x ← dlog g (com). Then we have:

x = u • v -1 mod p for some u ∈ [±2 α ], v ∈ [2 β ], x + 2 α+2 = u • (v ) -1 mod p for some u ∈ [±2 α ], v ∈ [2 β ].
Hence, uv -1 + 2 α+2 = u (v ) -1 mod p, which gives v (u + 2 α+2 v) = u v mod p. However, since p > 2 α+2β+4 , we have that this equation holds over the integers as well. This implies (still using the bound on p) that v (u + 2

α+2 v) = u v ≤ 2 α v. However, u + 2 α+2 v ≥ 2 α+2 v -2 α > 2 α v (since v ≥ 1)
. Therefore, we also get 2 α v < v (u + 2 α+2 v) (since v ≥ 1), which is a contradiction. Therefore, no bounded prover can provide an accepting argument of membership in L α,β (with any computationally sound argument system) for both com and com • g 2 α+2 .

A VPRG from NIZK for the Almost Short Language and the SEDL Assumption

With the tools we introduced, we are now ready to present our construction of a VPRG in a group where CDH is insecure.

Intuition of the Construction. 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. Assume that CDH does not hold with respect to DHGen. Then, from Section 3, Theorem 21, there exists and efficient "self-pairing" algorithm (EvalCom, EvalOpen) over (G, p) = DHGen(1 λ ) with negligible error probability, for infinitely many security parameters λ. In particular, it can compute (constant depth) integer arithmetic circuits (IAC) in the exponent. We will use this self-pairing algorithm to build a VPRG over DHGen, which will satisfy correctness, binding, and hiding for infinitely many security parameters.

We set (PRG.Setup, PRG.Eval) to be Goldreich's PRG instantiated with the LV predicate; let PRG i be IAC that computes, given a seed

(s 1 , • • • , s n ) as input, the i-th output bit of PRG.Eval(s 1 , • • • , s n ).
Observe that PRG i is a degree-3 integer arithmetic circuit with 9 gates (ignoring the subtractions by a constant, which are "for free"), where all intermediate values belong to [±1] provided that the inputs to the IAC are bits. We fix an arbitrary small positive constant δ PRG < 0.25, such that Goldreich's PRG instantiated with the LV predicate is conjectured to be secure when stretching n bits to m = n 1+δ PRG bits.

Fix integers (l, t, κ, c). The high-level intuition of our VPRG is relatively simple. The commitment to the seed (s

1 , • • • , s n ) is a bit-by-bit commitment (com 1 , • • • , com n ),
with the commitment scheme given in Section 5.4, which computationally hides the seed under the short-exponent discrete logarithm assumption. The pseudorandom string is simply PRG.Eval(pp, (s 1 , • • • , s n )). Given the commitment to the seed, both parties will use the strong CDH solver, which exists since we assume that CDH does not hold over G. By Theorem 21 of the supplementary material, the parties can both use

EvalCom(PRG i , com 1 , • • • , com n ) for i = 1 to m = n 1+δ PRG . For each such i, denoting com i = g wi+2 l+t si with w i ∈ [±2 l ] and s i ∈ {0, 1}, the parties get com * i ← EvalCom(PRG i , (g wj +2 l+t sj ) j≤n ) = g w * i +2 3(l+t) PRGi(s1,••• ,sn) , with w * i ∈ [±(2 3l+2t+31 )]. Let ← 3l + 2t + 31 and ← + κ + c + 1. Let b i ← PRG i (s 1 , • • • , s n ).
We set t = 34 + κ + c, which guarantees that + 2 = 3(l + t). Therefore, we have com * i = g w * i +2 +2 bi . To provably open the i-th bit of the pseudorandom string to the bit b i , the prover reveals b i , and both parties homomorphically compute g w * i from com * i . It remains for the prover to demonstrate that he revealed the right value b i , which he does using a NIZK to prove that g w * i belongs to L ,c (which he can do since w * i ∈ [±2 ]). More precisely, we will use the CIH from Section 5.2 to compile the Σ-protocol for the language L ,c from Section 5.1, with challenge length c, into a NIZK. Since + 2 = 3(l + t), and using Lemma 39 from Section 5.4, this uniquely binds the prover to b i .

Parameters and Assumptions. Due to the large number of parameters involved in our construction, and to make it more readable, we summarize our parameters and the constraints they must satisfy in Table 1. The parameters are set as follows: To apply Lemma 39, we must pick p such that log p > + 2c + 4 = 3l + 5c + 3κ + 104, where l is such that the p/2 l -SEDL assumption holds over G, and κ is a statistical security parameter. Choosing c to be polynomially larger than l + κ, we have = 3c + o(c), and we can set p such that log p = 5c + o(c). Therefore, setting the number of parallel repetitions of the Σ-protocol for L ,c to N = 6, we get λ = 5c + 6( + c) + o(c) = 29c + o(c). In turns, this gives p -1 • 2 N c-λ = 2 -28c-o(c) = 2 -(28/29+o(1))λ . Therefore, the adaptive soundness of our NIZK for L ,c reduces to the 2 -(28/29+o(1))λ -OW-KDM security of ElGamal (over the group G of size q ≈ 2 λ ) w.r.t. efficient functions. Observe that with this choice of parameters, it holds that p/2 l = 2 O( √ log p) , hence the p/2 l -SEDL assumption is implied by the 2 -O( √ log p) -OW-KDM security of ElGamal over G, which is clearly implied by the 2 -(28/29+o(1)) log p -OW-KDM security of ElGamal over G.

Construction. Let NIZK AS = (Setup AS , Prove AS , Verify AS ) be a NIZK for the almost-short language L ,c over the group generator DHGen where the CDH problem is insecure. Given a security parameter n for the VPRG, we set l(n) = κ(n) = n and c(n) = n 2 (so that κ + l = o(c)). We set

Parameters Definition

Constraints

c(n) bit-length of challenge space for the Σ-protocol p(n) size of G p > 2 +2c+4 q(n) size of G q ≈ 2 λ N (n)
number of parallel repetitions of the Σ-protocol p/2 ( (n), (n), λ(n), p(n)) as described previously, and s(n) = n • log p . Let m = m(n) be n 1+δ PRG . Our construction of VPRG proceeds as follows:

-

Setup(1 n , m) : run G = (G, p) ← r DHGen(1 λ(n) ) and sample g ← r G. 9 Further, for i = 1 to m, generate crs i ← r Setup AS (1 λ(n) ) and pp PRG ← r PRG.Setup(1 n ). Finally, output pp = (g, (crs i ) i≤m , pp PRG ). -Stretch(pp) : pick a seed seed = (s 1 , • • • , s n ) ← r {0, 1} n for PRG. For i = 1 to n, pick w i ← r [2 l ] and compute com i ← g wi+2 l+t si . Output pvk ← (com 1 , • • • , com n ), x = PRG.Eval(seed), and aux ← (seed, w 1 , • • • , w n ). -Prove(pp, aux, i) : compute com * i ← EvalCom(PRG i , (com 1 , • • • , com n )) and w * i ← EvalOpen(PRG i , (w 1 , s 1 ), • • • , (w n , s n )). Set x i = PRG i (seed), X i = com * i /g 2 l+t xi and run π AS i ← Prove AS (crs i , X i , w * i ). Output π = π AS i . -Verify(pp, pvk, i, b, π) : compute com * i ← EvalCom(PRG i , (com 1 , • • • , com n )) and set X = com * i /g 2 l+t b . Output Verify AS (crs i , X, π).
Setting (δ(n), s(n)) for VPRG. Before going into the security proofs, let us assess the parameter values of δ(n) and s(n) of our VPRG. First, we have m(n) = n 1+δ PRG where the constant δ PRG is the stretch of the underlying PRG that can be set arbitrary within 0 < δ PRG < 0.25. The size of the verification key is s(n) := n • log p , and in particular, s(n) ≤ n 1+δ PRG /2 for all sufficiently large n. Therefore, by setting δ(n) := δ PRG /3, we conclude s

(n) 1+δ(n) ≤ (n 1+δ PRG /2 ) 1+δ PRG /3 = n 1+δ PRG = m(n). Specifically, we have a (s(n) = n • log p , δ(n) = δ PRG /3)-VPRG.
Theorem 40. If the p/2 l -SEDL assumption holds relative to DHGen, CDH does not hold relative to DHGen, PRG is a secure pseudorandom generator stretching n bits to n 1+δ PRG bits for some arbitrarily small positive constant δ PRG , and the NIZK argument system for the almost language L (n),c(n) is adaptive sound and selective single-theorem zero-knowledge, where (n) and c(n) are chosen as described above, then our construction provides an (s(n), δ PRG /3)-VPRG (with s(n) = n • log p ) that is binding and hiding.

The proof of binding is very similar to the proof of Theoremn 28. For the hiding property, in a first hybrids, we first simulate all NIZK proofs, still providing correct openings. Then, we replace the commitment to the seed by random group elements, which is indistinguishable from the previous hybrids under the short-exponent discrete logarithm assumption. Eventually, we replace the PRG values by random bits, which is indistinguishable under the pseudorandomness of the PRG. In the last game, the value of all opened bits is perfectly independent of the value of the unopened bit, hence the advantage of the adversary is 0. The formal proof is given below.

Proof. Correctness of the VPRG follows from the correctness of the underlying NIZK and the (overwhelming) correctness of algorithm Eval and EvalOpen. In particular, due to our parameter setting, it will hold with overwhelming probability that the values g w * i , computed using EvalCom on the public verification key (com 1 , • • • , com n ) generated by an honest prover, belong to L ,c . We provide a proof of binding and hiding below.

Binding. Assume there exists a PPT adversary A that breaks the binding property with nonnegligible probability with respect to an inefficient extractor Ext defined below. Then, we construct a PPT adversary B that breaks adaptive soundness of NIZK for the almost-short language L ,c over a group G with respect to the generator g ∈ G advantage /m which forms a contradiction. We first provide the description of the extractor Ext.

Ext(pp, pvk) : parse (com 1 , • • • , com n ) ← pvk. For i = 1 to m, do the following: compute com * i and check whether com * i ∈ L ,c or com * i /g 2 +t ∈ L ,c . If the former holds set x i = 0, if the latter holds set x i = 1, and if both of them does not hold randomly set x i ← r {0, 1}. Here, note that by the unconditionally binding property of the commitment, only at most one condition will hold. Finally, output x = (x 1 , • • • , x m ).

Then, the description of B on input crs is as follows. We analyze the success probability of B. Let us condition on j = j, which happens with probability 1/m. Let pvk = (com 1 , • • • , com n ) and set com * j ← Eval(PRG j , (com 1 , • • • , com n )). First, consider the case com * j ∈ L ,c . Then by definition of Ext, it will output x j = 0. Therefore, if A succeeds in breaking the binding property, then it will output a proof π which Verify(pp, pvk, i, 1, π) = 1, which in particular means that π is an accepting proof for the word X = com * j /g 2 +t ∈ L ,c . Hence, B successfully breaks adaptive soundness. The same is true for the case com * j /g 2 +t ∈ L ,c . Finally, in case com * j ∈ L ,c and com * j /g 2 +t ∈ L ,c , since A outputs a valid proof π for which it should not open correctly to any bit, whatever output by B will break adaptive soundness. In conclusion, B will break adaptive soundness with probability /m.

Hiding. Consider a PPT adversary A that takes part in the hiding property experiment. We show that any A must have negligible advantage assuming selective single-theorem ZK and the T -SEDL assumption for T = p/2 l . To this end, consider the following sequence of hybrids. Below, we fix j ∈ [m].

H 0 : This is the real experiment. Namely, we run pp ← r Setup(1 λ , m), (pvk, x, aux) ← r Stretch(pp), (π i ← r Prove(pp, aux, i)) i , and provide A with (pp, pvk, i, (x i , π i ) i =j ). In experiment H m+n , the seed of the PRG is information theoretically hidden from A since all input to A are created independent of the value of the seed. Therefore, in experiment H m+n , A has advantage exactly 0. Therefore, due to the above hybrids, we conclude that A has only negligible probability in breaking the hiding property.

Finally, since the above is an (s(n), δ(n))-VPRG for a constant δ(n) = δ PRG /3, by setting n large enough, we can satisfy the condition required in Theorem 7 for constructing NIZKs for all of NP. In particular, as a consequence of Theorem 7, 34, 36, and 40, the following is obtained.

Theorem 41. Assume that the CDH assumption does not hold relative to DHGen, that ElGamal satisfies 2 -(28/29+o(1))λ -OW-KDM security with respect to efficient functions, and that Goldreich's PRG instantiated with the LV predicate is secure for some (arbitrarily small) polynomial stretch. Then there exists an infinitely often adaptive sound and adaptive multi-theorem NIZK for all of NP.

6 Wrapping Up -io-NIZKs for NP from Symmetric Assumptions

We now have all the tools to prove the main theorem of this work, which we recall below: Theorem 42. Assume that ElGamal satisfies 2 -(28/29+o(1))λ -OW-KDM security with respect to efficient functions, and that Goldreich's PRG instantiated with the LV predicate is secure for some (arbitrarily small) polynomial stretch. Then there exists an adaptively sound and adaptive multi-theorem infinitely-often NIZK for NP, whose multi-theorem zero-knowledge property holds against uniform adversaries.

Note that the above two assumptions are not known to imply public-key encryption; therefore, we obtain the first candidate (infinitely-often) NIZK from concrete assumptions which are not known to imply public-key encryption. Note also that in our construction, we actually rely on the 2 -(28/29+o(1))λ -OW-KDM security of ElGamal for two different security parameters -one corresponding to the group G (which we use to instantiate the NIZK for the almost-short language) and one corresponding to the group G (which we use to get a hiding commitment scheme).

Proof. We consider two complementary cases:

1. If there exists a group generator DHGen relative to which the CDH assumption (Definition 1) holds. Then by Theorem 28 and assuming that ElGamal satisfies 2 -(3/4+o(1))λ -OW-KDM security with respect to efficient functions (which is in particular implied by the first assumption of Theorem 42), there exists an adaptively sound and adaptive multi-theorem NIZK proof system for NP.

2. If for every group generator DHGen, the CDH assumption does not hold, then by Theorem 41, this means that (under the two assumptions of Theorem 42) there exists a (δ, n)-VPRG which is correct, binding, and hiding for infinitely-many security parameters n (namely, those for which CDH does not holds over DHGen(1 λ(n) )). Therefore, by Theorem 7, there exists an infinitely-often adaptively sound and adaptively multi-theorem zero-knowledge NIZK arguments for NP.

This concludes the proof of the theorem.

Considerations on Uniformity.

A discussion is in order regarding the uniformity of the algorithms involved in the above construction. Generally, the CDH assumption is stated for non-uniform adversaries; however, in our construction, this would mean that the strong CDH solver is itself a nonuniform algorithm. To obtain a NIZK with uniform algorithms, one must make the case distinction depending on whether the uniform CDH assumption holds. But this means, in particular, that we can only conclude that (under the 2 -(28/29+o(1))λ -OW-KDM security of ElGamal and the security of the LV PRG) there exists an infinitely-often NIZK whose zero-knowledge property holds against uniform adversaries. An alternative strategy to build a NIZK following the above approach is to allow the Setup algorithm of the NIZK proof system to be nonuniform (i.e., generated by a family of polynomial time circuits). In this case, the CRS can contain, for any security parameter λ, an indication of whether CDH holds for this security parameter, and if it does not, provide a polynomial-size circuit which breaks it. In this case, the NIZK construction is actually secure for all security parameters λ, and the prover and verifier remain uniform algorithms. This gives the following corollary: Corollary 43. Assume that ElGamal satisfies 2 -(28/29+o(1))λ -OW-KDM security with respect to efficient functions, and that Goldreich's PRG instantiated with the LV predicate is secure for some (arbitrarily small) polynomial stretch. Then there exists an adaptively sound and adaptive multi-theorem NIZK for NP with a nonuniform Setup algorithm.

(

  Fig.1. Σ-protocol for the Diffie-Hellman language for the word (g, h, X = g x , Y = h y ). This is a variant of a protocol by[START_REF] Abdalla | Tightly-secure signatures from lossy identification schemes[END_REF]

  for the same infinite set of λ's as of A . In addition, A runs A at most O(ν(λ) -1 • log(1/δ(λ))) and performs an additional O(ν(λ) • log(1/δ(λ)) • log p + (log p) 2 ) group operations where p = |G|. Remark 20 (Strong CDH Solver). As a consequence of Lemma 19, if the CDH assumption relative to DHGen does not hold, then by setting δ(λ) := 2 -cλ • 2 -3 log p for any c > 0 and taking the union bound, we can construct a PPT adversary A such that Pr

1

 1

2 c

 2 Proof. Assume the malicious prover can answer two distinct challenges e, e with d, d and convinces the verifier to accept in both cases. Then d -d = x(e -e ), which implies that x = (d -d ) • (e -e ) -1 . Assume without loss of generality that e > e , then (d -d ) ∈ [±2 ] and (e -e ) ∈ [2 c

1 2 κ . 8

 8 Proof. Let x ∈ [0, 2 ]. To prove the lemma, it suffices to show that the distribution D 1 = (r, e, d) generated by an honest run of the protocol and the distribution D 2 = (r, e, d) of simulated ones are statistically close. Let us fix e ∈ [2 c ]. Then, the following two distributions are statistically close:

Lemma 38 .

 38 Assume that ElGamal satisfies (1/T )-OW-KDM security with respect to efficient functions. Then the T -SEDL assumption holds.

B

  (crs): randomly pick j ← r [m]. Then, generate crs j ← r Setup AS (1 λ (n)) for i ∈ [m]\{j}. Set crs j := crs and output pp = (g, (crs i ) i≤m ) to A. When A outputs (pvk, j , π), check j = j. If not, abort. Otherwise, parse (com 1 , • • • , com n ) ← pvk and compute com * j ← Eval(PRG j , (com 1 , • • • , com n )).Then, set b * ∈ {0, 1} to be the unique bit for which Verify(pp, pvk, i, b * , π) outputs 1, where if no such b * exists it aborts.10 Finally, set X = com * j /g 2 +t b * and output (x = X, π = π).

  H k (for k = 1, • • • , m): This experiment is identical to H k-1 except for how we construct (crs k , π AS k ). Namely, we set com * k ← Eval(PRG j , (com 1 , • • • , com n ))and runs the ZK simulator to generate(crs k , π AS k ) ← r Sim(com * k ).Due to the selective single-theorem ZK property of NIZK AS , the difference in the advantage of A in H k-1 and H k is negligible.H m+k (for k = 1, • • • , n):This experiment is identical to H m+k-1 except for how we construct com k in pvk. Namely, we randomly sample com k ← G, while we set com = g w k +2 l+t s k in the previous experiment. Due to the T -SEDL assumption with T = p/2 l , the difference in the advantage of A in H k-1 and H k is negligible.

Table 1 .

 1 List of parameters. All parameters are a function of the security parameter n.

	N c < 2 -c

In the case of DDH groups, the best known generic PPT adversary is Pollard's rho algorithm[START_REF] Pollalrd | A monte oarlo method for factorization[END_REF], which runs in time O(2 λ/2 ) and has constant success probability. However, restricted to polynomial time, it only provides a polynomial advantage over randomly guessing the discrete logarithm. Moreover, it is known[START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] that no generic algorithm with T oracle queries can have better success probability than O T 2 2 λ .

More precisely, these assumptions are falsifiable in spirit in the sense that they can be modeled as an efficient game with a challenger, but the winning condition can occur with exponentially small probability.

The security of Goldreich's PRG is a well-established and widely studied assumption, which provably resists large classes of attacks[START_REF] Alekhnovich | Exponential lower bounds for the running time of dpll algorithms on satisfiable formulas[END_REF][START_REF] Applebaum | Algebraic attacks against random local functions and their countermeasures[END_REF][START_REF] Couteau | On the concrete security of Goldreich's pseudorandom generator[END_REF][START_REF] Mossel | On e-biased generators in NC0[END_REF][START_REF] Odonnell | Goldreich's prg: evidence for near-optimal polynomial stretch[END_REF].

This is similar in spirit to various Σ-protocols for lattice-based relations, where the Σ-protocol proves knowledge of a short preimage, but the protocol has some slackness, i.e., a gap between the shortness needed for the honest proof to be accepted, and the shortness actually guaranteed by the soundness property.

To be precise, this does not meet the definition of our honest-verifier zero-knowledge since we only consider a small set of L ,c . However, this notion suffices for our application.

We remark that we assume the CDH problem is insecure over the group G for the specific parameter λ(n).

Here, we implicitly use the fact that our NIZK will not verify the same proof against two distinct words.

Acknowledgements

Shuichi Katsumata was supported by JST CREST Grant Number JPMJCR19F6. Geoffroy Couteau and Bogdan Ursu were supported by ERC PREP-CRYPTO Grant Agreement ID 724307. We would like to thank Dennis Hofheinz for valuable discussions and contributions to the early stages of this work. We are also grateful for the comments received from the anonymous reviewers of this paper.

Supplementary Material

A On Infinitely-Often Security

On Infinitely-Often Non-Interactive Zero-Knowledge Arguments. An infinitely often noninteractive zero-knowledge argument systems (io-NIZK) is a non-interactive zero-knowledge argument system where soundness and zero-knowledge are relaxed to hold for infinitely many security parameters, but not necessarily for all large enough security parameters. Infinitely-often cryptographic primitives are relatively common in the literature. Intuitively, the notion of an infinitely-often primitive shows up naturally as soon as a cryptographic primitive uses constructively the assumption that another cryptographic primitive is insecure. Indeed, the standard security formulation for a primitive is the following: for every PPT adversary A and all large enough security parameters λ (id est, for all λ except a finite number of them), A has probability negligible in λ to solve some problem parametrized by λ. Hence, when using constructively the insecurity of such an assumption, we only obtain the guarantee that there exists an adversary A that solves some problem parametrized by λ (with non-negligible probability) for infinitely many security parameters λ. This infinitely-often versus almost-everywhere issue is usually regarded as an artifact of the way we define cryptographic primitives.

Related Works on Infinitely-Often Primitives. The work of [START_REF] Haitner | Computational two-party correlation: A dichotomy for key-agreement protocols[END_REF] builds infinitely-often key agreement based on 2-party protocols which are correlated in a non trivial way. The work of [START_REF] Maji | On the computational complexity of coin flipping[END_REF] builds infinitely often one-way functions from the existence of a constant-round weak coin-flipping protocol. [START_REF] Deng | Magic adversaries versus individual reduction: Science wins either way[END_REF] shows that either the Feige-Shamir protocol is concurrent zero-knowledge, or injective one-way functions imply an infinitely often key agreement. The work of [START_REF] Zhandry | Quantum lightning never strikes the same state twice[END_REF] shows that a collisionresistant hash function is either "collapsing", or it implies infinitely often quantum lightning schemes. The work of [START_REF] Reingold | Notions of reducibility between cryptographic primitives[END_REF] shows that if there is a reduction of key-agreement to OWFs, then there exists a mildly-blackbox reduction of infinitely often key-agreement to OWFs. Eventually, the approach in the recent work of [START_REF] Pass | A round-collapse theorem for computationally-sound protocols; or, tfnp is hard (on average) in pessiland[END_REF] is closer in spirit to our work; the authors show a round-collapsing theorem for computational power, making a case distinction based on the existence of infinitely-often one-way function.