Geoffroy Couteau

Dennis Hofheinz

Designated-verifier pseudorandom generators, and their applications

Keywords: non-interactive zero-knowledge, computational Diffie-Hellman, learning with errors, verifiable pseudorandom generators

We provide a generic construction of non-interactive zero-knowledge (NIZK) schemes. Our construction is a refinement of Dwork and Naor's (FOCS 2000) implementation of the hidden bits model using verifiable pseudorandom generators (VPRGs). Our refinement simplifies their construction and relaxes the necessary assumptions considerably. As a result of this conceptual improvement, we obtain interesting new instantiations:

-A designated-verifier NIZK (with unbounded soundness) based on the computational Diffie-Hellman (CDH) problem. If a pairing is available, this NIZK becomes publicly verifiable. This constitutes the first fully secure CDH-based designated-verifier NIZKs (and more generally, the first fully secure designated-verifier NIZK from a non-generic assumption which does not already imply publicly-verifiable NIZKs), and it answers an open problem recently raised by Kim and Wu (CRYPTO 2018). -A NIZK based on the learning with errors (LWE) assumption, and assuming a noninteractive witness-indistinguishable (NIWI) proof system for bounded distance decoding (BDD). This simplifies and improves upon a recent NIZK from LWE that assumes a NIZK for BDD (Rothblum et al., PKC 2019).

Introduction

Zero-knowledge proof systems allow a prover to convince someone of the truth of a statement, without revealing anything beyond the fact that the statement is true. After their introduction in the seminal work of Goldwasser, Micali, and Rackoff [GMR89], they have proven to be a fundamental primitive in cryptography. Among them, non-interactive zero-knowledge proofs [BFM88] (NIZK proofs), where the proof consists of a single flow from the prover to the verifier, are of particular interest, in part due to their tremendous number of applications in cryptographic primitives and protocols, and in part due to the theoretical and technical challenges that they represent.

On Building Non-Interactive Zero-Knowledge Proofs. It is known that zero-knowledge proofs for arbitrary NP languages can be constructed from any one-way function [GMW86], and that this is a minimal assumption [OW93,Vad04,OV07]. In contrast, non-interactive zero-knowledge proofs have proven to be considerably harder to construct. NIZKs in the plain model can only exist for trivial languages [Ore87]; therefore, NIZKs for non-trivial languages are typically constructed in the common reference string model, where the prover and the verifier are given access to a common string honestly generated ahead of time in a setup phase. Generic constructions of NIZK proof systems for NP in the CRS model have been described from primitives such as doubly-enhanced trapdoor permutations [FLS90], invariant signatures [GO93], and verifiable pseudorandom generators [DN00], where the last two are known to be also necessary for NIZKs. However, concrete instantiations of these primitives are currently known only from factorization-related assumption [BFM88], pairing-based assumptions [CHK03], and indistinguishability obfuscation [BP15,CL18] (together with injective oneway functions). More recently, direct constructions of NIZKs in the CRS model have been given from pairings [GOS06b, GOS06a, GS08], or from strong and less-understood assumptions such as indistinguishability obfuscation [SW14, BP15] and exponentially-strong KDM-secure encryption [CCRR18].

A fundamental and intriguing open question remains: is it possible to build NIZKs from other classical and well-established assumptions, such as discrete-logarithm-type assumptions, or latticebased assumptions? Faced with the difficulty of tackling this hard problem upfront, the researchers have investigated indirect approaches, which can be divided into two main categories: the bottom-up approach, and the top-down approach.

The Bottom-Up Approach. This line of research fundamentally asks the following: starting from classical assumptions, either generic (OWF, public-key encryption) or concrete (CDH, LWE), how close to full-fledged NIZKs in the CRS model can we get, in terms of functionality? Early results in this direction have established the existence of NIZKs for NP in the preprocessing model (where the prover and the verifier execute ahead of time a preprocessing phase to generate respectively a secret proving key and a secret verification) assuming any one-way function [DMP90], and designated-verifier NIZKs for NP (where anyone can compute a proof, but a secret verification key is required to verify a proof) from any semantically-secure public-key encryption scheme [PsV06]. In addition to requiring the prover and/or the verifier to hold a secret key, these early results all suffered from a severe limitation: they only achieve a bounded form of soundness, where forging a proof for an incorrect statement is hard only if the prover is not given access to a verification oracle. This strongly limits their usability as a replacement for full-fledged NIZKs in most applications. More recently, various NIZK proof systems with unbounded soundness have been proposed, from the LPN assumption in the preprocessing model [BCGI18], from strong form of partially homomorphic encryption in the designated-verifier setting [CC18], and from LWE in the designated-prover setting [KW18] (where a secret key is required to compute a proof but anyone can verify a proof; the latter work also implies a NIZK with unbounded soundness in the preprocessing model from a strong variant of the Diffie-Hellman assumption). A slightly different approach was taken in [BCPW15], where the authors introduce (and construct from the DDH assumption) implicit zero-knowledge proofs, which are not NIZKs, but can replace them in applications related to secure computation.

The Top-Down Approach. This line of research tackles the problem from another angle: sticking with the goal of building full-fledged NIZKs in the CRS model, it attempts to identify the minimal "missing piece" which would allow to build NIZKs from classical assumptions. The work of [PV08] conjectured that a NIZK proof system for a specific language (GapSVP) would allow to build a NIZK proof system for all of NP from lattice assumptions, and the work of [RSS19] almost confirmed this conjecture, by establishing that a non-interactive zero-knowledge proof for a specific language (bounded distance decoding, BDD) would imply the existence of a full-fledged NIZK proof system for NP in the CRS model, from the LWE assumption.

Our Contribution

In this paper, we revisit the problem of building non-interactive zero-knowledge proofs for NP from classical assumptions, investigating both the bottom-up approach and the top-down approach.

Our starting point is a fresh view on the work [DN00] of Dwork and Naor. In a nutshell, they construct a NIZK proof for NP by implementing the hidden bits model (HBM, [FLS90]) using a tool they call verifiable pseudorandom generator (VPRG). 1 Intuitively, a VPRG is a pseudorandom generator (PRG) that allows to selectively prove that certain parts of the PRG output are consistent (relative to a commitment to the PRG input).

In the first part of our work, we relax the definition of VPRGs, and show that the relaxed definition is still sufficient to implement the HBM (and thus to obtain NIZK proofs for NP). Unlike the definition of [DN00], our definition also generalizes to the designated-verifier setting. In the second part of our work, we show that our new definition allows for considerably simple and new instantiations, both in the designated-verifier and standard (publicly verifiable) setting. We obtain instantiations from computational assumptions which were so far not known to imply NIZKs for NP. Specifically, we provide:

-A designated-verifier NIZK (DVNIZK) system for NP from the CDH assumption (with adaptive unbounded soundness and adaptive multi-theorem zero-knowledge). If the underlying group allows for a (symmetric) pairing, our construction can be made publicly verifiable. This is the first DVNIZK for NP from a concrete (i.e., non-generic) assumption that is not already known to imply publicly verifiable NIZKs for NP. Our result resolves an open problem recently raised by Kim and Wu in [KW18], regarding the possibility of building multi-theorem NIZKs from DDH in the preprocessing model. Note that our result achieves a strictly stronger form of NIZK and under a weaker assumption. -A NIZK system for NP (satisfying adaptive soundness and adaptive multi-theorem zero-knowledge) that assumes LWE and a non-interactive witness-indistinguishable proof system Π for BDD. If Π is designated-verifier, resp. publicly verifiable, then so is our NIZK system for NP. Our scheme improves the mentioned work of [RSS19] that requires non-interactive zero-knowledge proof system for BDD. (We comment below on what allows us to avoid the need for simulation inherent in the approach of [RSS19].)

1.2 Our approach

The proof system of Dwork and Naor. To outline our conceptual contribution, we provide more background on the definitions and model of Dwork and Naor [DN00]. First, the hidden bits model (HBM) is an abstract model of computation for a prover and a verifier that allows to formulate the NIZK protocol for graph Hamiltonicity from [FLS90] in a convenient way. In the HBM, the prover receives an ideally random string hb = (hb i ) t i=1 ∈ {0, 1} t of bits, as well as an NP-statement x with witness w. In order to prove x, the prover then selects a subset S ⊂ [t] of bit indices and auxiliary information M . The verifier is then invoked with hb[S] = (hb i ) i∈S and M , and outputs 1 if it is convinced of the truth of x. [FLS90] provide a NIZK proof in the HBM that is statistically sound and statistically zero-knowledge. (Of course, at least one of those properties will have to become computational when implementing the HBM.)

Now Dwork and Naor [DN00] implement the HBM using VPRGs. Formally, a VPRG is a pseudorandom generator G : {0, 1} λ → {0, 1} m which allows to construct commitments pvk to seeds (i.e., G-inputs) s and publicly verifiable openings of individual bits of G(s) (relative to pvk). [DN00] require the following:

1. pvk information-theoretically determines a unique value y in the image of G, 2. valid openings to bits not consistent with the y determined by pvk do not exist, and 3. an opening computationally leaks nothing about unopened bits of y. Given a VPRG, [DN00] implement the HBM as follows. The prover initially selects a seed s $ ← {0, 1} λ and then generates a commitment pvk to s. This implicitly sets hb = G(s). After selecting S, the prover then sends to the verifier pvk and an opening of hb [S].

Observe that this protocol may still allow the prover to cheat by choosing a "bad" seed s that might allow breaking soundness. However, since the HBM protocol of [FLS90] is statistically sound, there can be only comparatively few "bad" HBM strings hb that allow cheating. Hence, the probability that there exists a seed s such that hb = G(s) is bad will be negligible.2 Our conceptual improvement. We show that points 1. and 2. from the VPRG definition can be simplified. Specifically:

-We require that pvk uniquely determines some y, but we do not require that y is in the image of G. Instead, we require that the bitlength |pvk| of pvk is short (i.e., independent of m). Observe that now up to 2 |pvk| "bad" y (and thus "bad" hb) might exist. However, since |pvk| is still short (compared to m), essentially the original proof strategy of [FLS90] applies. -We only require that it is computationally infeasible to come up with an opening not consistent with y. This relaxation requires a careful tracking of "bad events" during the security proof, but is essentially compatible with the proof strategy from [DN00]. Our first change allows us to omit an explicit proof of consistency of pvk that was necessary in [DN00]. This simplification will be highly useful in our concrete instantiations. Furthermore, our second change allows to consider designated-verifier NIZKs. Indeed, observe that the original requirement 2. above states that no valid openings inconsistent with y exist. This excludes designated-verifier realizations of VPRGs in which the verifier secret key can be used to forge proofs. However, since most existing DVNIZK proofs have this property (otherwise, they could be made publicly verifiable by making the secret verification key public), they are not helpful to construct VPRGs in the sense of [DN00]. In contrast, our relaxation is compatible with existing DVNIZKs (and indeed our first VPRG instantiation crucially relies on DVNIZKs).

Concrete constructions.

We offer two VPRG constructions from concrete assumptions. The first construction assumes a CDH group G = g of (not necessarily prime) order n. A seed is an exponent s ∈ Z n , and a commitment to s is g s . Given public

u i , v i ∈ G (for i ∈ [t]), the i-th bit G(s) i of the PRG image is B(u s i , v s i )
, where B is a hard-core predicate of the CDH function. A proof π i that certifies a given G(s) i consists of u s i , v s i , as well as proofs that both (g, g s , u i , u s i ) and (g, g s , v i , v s i ) are Diffie-Hellman tuples. In a designated-verifier setting, such proofs are known from hash proof systems [CS02, CKS08]. Alternatively, a symmetric pairing G × G → G T can be used to check the Diffie-Hellman property of these tuples even without explicit proof.

Our second construction assumes LWE and uses the notion of homomorphic commitments from [GVW15]. These commitments have a "dual-mode" flavor, much like the commitments from [DN02, GS08]. Specifically, under LWE, the public parameters of these commitments can be switched between a "binding" mode (in which commitments are perfectly binding) and a "hiding" mode (in which commitments are statistically hiding). Furthermore, given a commitment com s to s, it is possible to publicly compute a commitment com C(s) to C(s) for any (a-priori bounded) circuit C.

In our construction, we will assume any PRG G, and set com s to be a commitment to a PRG seed s ∈ {0, 1} λ . Let G i be a circuit that computes the i-th bit of G. An opening of the i-th bit is then an opening of the commitment com Gi(s) to G i (s). (Note that com Gi(s) can be publicly computed from com s .) Unfortunately, in the construction of [GVW15], the opening of commitments may reveal sensitive information about intermediate computation results (or even about s in our case).

Hence, we will have to assume an additional proof system to open commitments without revealing additional information. For the commitments of [GVW15], the corresponding language is the language of a BDD problem. Fortunately, the strong secrecy properties of these commitments allow us to restrict ourselves to a witness-indistinguishable (and not necessarily zero-knowledge) proof system for BDD.3

Relation to [RSS19]. We note that recently, [RSS19] established a reduction from NIZKs for NP from LWE to the existence of an NIZK for BDD, also through implementing the HBM. Informally, and casting the construction of their work in the language of VPRGs,4 the core reason why a NIZK was required in [RSS19] is the need for a consistency proof for pvk (as in [DN00]). Since the consistency of pvk is a unique-witness relation, and since the proof must hide predicates of the seed, it does not seem feasible to replace this NIZK, e.g., by a NIWI or a witness-hiding proof. We note that although NIWIs for NP imply the existence of NIZKs for NP, it is not clear whether a NIWI for a simple language such as BDD can be used to build a NIZK for BDD.

Relation to [Abu13]. We also note that Abusalah [Abu13] also implements the HBM using Diffie-Hellman-related assumptions (such as CDH in a pairing-friendly group). However, he does not follow the PRG-based paradigm of [DN00] that we refine. Instead, he directly generalizes the original HBM implementation of [FLS90] to generalizations of trapdoor permutations.

Concurrent Works

Concurrently and independently to our work, two other works [QRW19,KNYY19] have achieved a result comparable to the first of our two main contributions, namely, designated-verifier non-interactive zero-knowledge proofs for NP from CDH. In all three works, the construction proceeds in a comparable way, by designing a CDH-based primitive which allows to compile the hidden-bit model into a designated-verifier NIZK. We summarize below the main differences between our works.

-The work of [QRW19] provides in addition a construction of malicious designated-verifier NIZK for NP, where the setup consists of an (honestly generated) common random string and the verifier then gets to choose his own (potentially malicious) public/secret key pair to generate and verify proofs. The assumption underlying their construction is a stronger "one-more type" variant of CDH (i.e., the hardness of solving n + 1 CDH challenges given n calls to an oracle solving CDH). -The work of [KNYY19] provides two relatively different additional constructions of NIZKs: a designated-prover NIZK for NP with proofs of size |C| + poly(λ) (where C is the circuit checking the NP relation), under a strong Diffie-Hellman-type assumption over pairing groups, and a preprocessing NIZK for NP with proofs of size |C| + poly(λ) from the DDH assumption over pairing-free groups. -The construction of NIZKs for NP assuming LWE and a NIWI for BDD is new to our work.

Organization

Section 2 introduces necessary preliminaries about non-interactive proof systems. Section 3 formally introduces designated-verifier pseudorandom generators, and defines their security properties. Section 4 provides a generic construction of a (designated-verifier) non-interactive zero-knowledge proof system for NP from our relaxed and generalized notion of DVPRGs, by instantiating the hidden bit model. Section 5 provides two instantiations of DVPRGs, from the CDH assumption in arbitrary group, and from the LWE assumption assuming in addition a NIWI proof system for BDD (where the resulting scheme is publicly verifiable iff the NIWI scheme is publicly verifiable). Eventually, Appendix A of the supplementary material introduces another security notion for DVPRGs, the consistency, which provides a useful tool to analyze their security.

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)|. An event occurs with overwhelming probability when its probability is at least 1 -negl(λ) for a negligible function negl. Given a finite set S, the notation x $ ← S means a uniformly random assignment of an element of S to the variable x. We represent adversaries as interactive probabilistic Turing machines; the notation Adv O indicates that the machine Adv is given oracle access to O. Adversaries will sometimes output an arbitrary state st to capture stateful interactions. For an integer n, [n] denotes the set of integers from 1 to n. Given a string x of length n, we denote by x i its ith bit (for any i ≤ n), and by x[S] the subsequence of the bits of x indexed by a subset S of [n].

Non-Interactive Zero-Knowledge

We recall the definition of non-interactive zero-knowledge (NIZK) proofs and argument.

Definition 1 (Non-Interactive Zero-Knowledge Argument System). A non-interactive zeroknowledge argument system for an NP-language L with relation R L is a triple of probabilistic polynomial-time algorithms (Setup, Prove, Verify) such that -Setup(1 λ ), outputs a common reference string crs and a trapdoor T , -Prove(crs, x, w), on input the crs crs, a word x, and a witness w, outputs a proof π, -Verify(crs, x, π, T ), on input the crs crs, a word x, a proof π, and the trapdoor T , outputs b ∈ {0, 1}, which satisfies the completeness, soundness, and zero-knowledge properties defined below.

If the trapdoor T of the non-interactive proof system is set to ⊥ (or, alternatively, if it is included in the crs), we call the argument system publicly verifiable. Otherwise, we call it a designated-verifier non-interactive argument system. If the soundness guarantee holds with respect to computationally unbounded adversary, we have a NIZK proof system.

Definition 2 (Perfect Completeness). A non-interactive argument system (Setup, Prove, Verify) for an NP-language L with witness relation R L satisfies perfect completeness if for every x ∈ L and every witness w such that R L (x, w) = 1,

Pr[(crs, T ) $ ← Setup(1 λ ), π ← Prove(crs, x, w) : Verify(crs, x, π, T ) = 1] = 1.
The soundness notion can come in several flavors: it is non-adaptive if the adversary must decide on a word on which to forge a proof before the common reference string is drawn, and it is adaptive if the adversary can dynamically choose the word given the common reference string. We will consider a strong variant of adaptive soundness, denoted unbounded adaptive soundness, where the adversary is given oracle access to a verification oracle. Note that in the publicly-verifiable setting, this is equivalent to the standard soundness notion, where the adversary must forge a valid proof on an incorrect statement without the help of any oracle. However, in the designated-verifier setting, this is a strictly stronger notion: the standard soundness notion only guarantees, in this setting, that the argument system remains sound as long as the prover receives at most logarithmically many feedback on previous proofs. On the other hand, if the argument system satisfies unbounded soundness, its soundness is maintained even if the adversary receives an arbitrary (polynomial) number of feedback on previous proofs.

Definition 3 (Unbounded Adaptive Soundness). A non-interactive argument system (Setup, Prove, Verify) for an NP-language L with relation R L satisfies unbounded adaptive soundness if for any PPT A,

Pr (crs, T ) $ ← Setup(1 λ ), (x, π) $ ← A O(crs,•,•,T ) (crs) : Verify(crs, x, π, T ) = 1 ∧ x / ∈ L ≈ 0,
where A can make polynomially many queries to an oracle O(crs, •, •, T ) which, on input (x, π), outputs Verify(crs, x, π, T ).

We now define zero-knowledge, which can again come in several flavors. We will consider adaptive zero-knowledge argument systems, where the adversary is allowed to pick a word on which to forge a proof after seeing the common reference string. We will also distinguish single-theorem zero-knowledge, in which the prover generates a single proof (and the length of the common reference string can be larger than the length of the statement to prove) and multi-theorem zero-knowledge (where the adversary can adaptively ask for polynomially many proofs on arbitrary pairs (x, w) for the same common reference string).

Definition 4 (Adaptive Single-Theorem Zero-Knowledge). A non-interactive argument system (Setup, Prove, Verify) for an NP-language L with relation R L satisfies (adaptive) single-theorem zero-knowledge if for any stateful PPT algorithm A, there exists a simulator (Sim 0 , Sim 1 ) such that

Pr    (crs, T ) $ ← Setup(1 λ ), (x, w) $ ← A(crs, T ), : (R L (x, w) = 1) ∧ (A(π) = 1) π $ ← Prove(crs, x, w)    - Pr    (crs, T ) $ ← Sim 0 (1 λ ), (x, w) $ ← A(crs, T ), : (R L (x, w) = 1) ∧ (A(π) = 1) π $ ← Sim 1 (crs, T , x)    ≈ 0.
Definition 5 (Adaptive Multi-Theorem Zero-Knowledge). A non-interactive argument system (Setup, Prove, Verify) for an NP-language L with relation R L satisfies (adaptive) multi-theorem zero-knowledge if for any stateful PPT algorithm A, there exists a simulator (Sim 0 , Sim 1 ) such that A has negligible advantage in distinguishing the experiments Exp zk,0

A (1 λ ) and Exp zk,1 A (1 λ ) given on Figure 1.

Note that O sim is only given the witness w to artificially enforce that A queries only words x in the language L .

Zero-knowledge is a strong, simulation-style security notion. A common relaxation of zero-knowledge to an indistinguishability-based security notion is known as witness-indistinguishability.

Definition 6 (Computational Witness-Indistinguishability). A non-interactive proof system (Setup, Prove, Verify) for an NP-language L with relation R L is (computationally) witness-indistin-

Exp zk,0 A (1 λ ) : (crs, T ) $ ← Setup(1 λ ) return b $ ← A Oprove(crs,•,•) (crs) Oprove(crs, x, w) : if R L (x, w) = 1 then return Prove(crs, x, w) else return ⊥ end if Exp zk,1 A (1 λ ) : (crs, T ) $ ← Sim0(1 λ ) return b $ ← A O sim (crs,T ,•,•) (crs) O sim (crs, T , x, w) : if R L (x, w) = 1 then return Sim1(crs, T , x) else return ⊥ end if Fig. 1. Experiments Exp zk,0
A (1 λ ) and Exp zk,1 A (1 λ ), and oracles Oprove(crs, x, w) and O sim (crs, T , x, w), for the (adaptive) multi-theorem zero-knowledge property of a non-interactive argument system. A outputs b ∈ {0, 1}.

guishable if for any PPT algorithm A,

Pr    (crs, T ) $ ← Setup(1 λ ), A(crs, π) = 1 (x, w 0 , w 1 ) $ ← A(crs), : ∧R L (x, w 0 ) = 1 π $ ← Prove(crs, x, w 0 ) ∧R L (x, w 1 ) = 1    -Pr    (crs, T ) $ ← Setup(1 λ ), A(crs, π) = 1 (x, w 0 , w 1 ) $ ← A(crs), : ∧R L (x, w 0 ) = 1 π $ ← Prove(crs, x, w 1 ) ∧R L (x, w 1 ) = 1    ≈ 0
We call such a proof system a non-interactive witness-indistinguishable (NIWI) proof system.

It is known that the existence of a NIWI proof system for NP implies the existence of a NIZK proof system for NP in the CRS model [FLS90]. However, this does not extend to proof systems for specific languages: the existence of a NIWI proof system for a language L does not generally imply the existence of a NIZK proof system in the CRS model for the same language.

3 Designated-Verifier Pseudorandom Generators Verifiable pseudorandom generators (VPRG) have been introduced in the seminal paper of Dwork and Naor [DN00], as a tool to construct non-interactive witness-indistinguishable proofs and NIZKs in the CRS model. Informally, a VPRG enhances a PRG with verifiability properties: the prover can compute a kind commitment to the seed (called the verification key), and issue proofs that a given position i of the pseudorandom string stretched from the committed seed is equal to a given bit. Furthermore, this proof does not leak anything about the output values at positions j = i.

In this section, we revisit the notion of verifiable pseudorandom generators. Toward our goal of building VPRGs from new assumptions, we significantly weaken the binding property of VPRGs (which states, informally, that the verification key binds the prover to the seed) to a security notion that is simpler to achieve and still allows to build NIZKs in the CRS model, and we extend the definition to the more general setting of designated-verifier VPRGs (DVPRGs) (this strictly encompasses public VPRGs since we recover the standard notion by restricting the secret verification key to be ⊥).

On Defining DVPRGs

A natural attempt to define the binding property of a DVPRG would be as follows: it should be infeasible, for any polytime adversary, to output two accepting proofs π 0 and π 1 that a given output of the PRG is equal to 0 and 1 respectively (relative to the same committed parameters) . However, this security notion turns out to be too weak for the construction of non-interactive witness-indistinguishable proofs from VPRG of [DN00]. Intuitively, this stems from the fact that a cheating prover will never send more than a single proof for a given output, hence we cannot extract two contradictory proofs from this adversary. Instead, the argument of [DN00] crucially rely on the following stronger definition: a VPRG is binding if for every (possibly malicious) public verification key pvk, there exists a single associated string x in the range of the stretching algorithm of the DVPRG, and for any accepting proof π of correct opening to a subset y[I] of the bits of a string y, it must hold that y

[I] = x[I].
Unfortunately, this binding property turns out to be too strong for our purpose. The reason is that we seek to build candidate DVPRGs from assumptions such as LWE, where natural approaches lead to schemes where there exists malicious public verification keys associated to strings which are not in the range of the DVPRG, and which cannot be distinguished from honest verification keys (typically, in our LWE-based construction, an honest verification key will be a list of LWE samples, which are indistinguishable from random samples). A comparable issue arose in the work of [RSS19], which tackled this issue by appending to the verification key (or, in their language, the public key of an obliviously-sampleable encryption scheme) a NIZK proof of validity.

Instead, we opt for a different approach and introduce a weaker binding property for DVPRGs, which does not require assuming any specific structure of the public verification key beyond its length. Namely, we consider the following notion: a DVPRG is binding if there exists a (possibly inefficient) extractor Ext such that no PPT adversary can output a triple (pvk, i, π) where π is a proof of correct opening of position i to 1 -x i , and x = Ext(pvk). Note that our definition does only consider verification keys generated by a computationally bounded adversary (instead of arbitrary pvk), and does not require pvk to be in the range of the DVPRG. This binding notion would in fact be trivial to achieve without further constraints (e.g. one could define pvk to be a sequence of extractable commitments to each bits of the pseudorandom string stretched from the seed), hence we further require that pvk must be short (of size s(λ), for a polynomial s independent of the stretch of the DVPRG). Afterward, we prove that this weaker notion still suffices to build NIZKs for NP in the CRS model.

Generalizing to the designated-verifier setting, where verification can involve a secret-verification key, we strengthen the above property to the unbounded binding property, which states that no PPT adversary can produce a triple (pvk, i, π) as above, even given oracle access to a verification oracle (which has the secret verification key hardcoded). We note that the above weakening of the binding notion is also necessary for our generalization to the designated-verifier setting: in this setting, the stronger binding notion of [DN00] does typically not hold, since there always exists accepting proofs of opening to an incorrect bit (if this was not the case, we could safely make the secret verification key public, since it would not allow to find proofs of opening to incorrect values); however, it is infeasible to find such proof (without knowing the secret verification key). Below, we formally introduce designatedverifier pseudorandom generators and the corresponding security notions.

Definition

Definition 7 (Designated-Verifier Pseudorandom Generator). A designated-verifier pseudorandom generator (DVPRG) 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 bound m(λ) = poly(λ), outputs a pair (pp, T ) where pp is a set of public parameters (which contains 1 λ ), and T is a trapdoor; -Stretch(pp), on input the public parameters, outputs a triple (pvk, x, aux), where pvk is a public verification key of polynomial length s(λ) independent of m, x is an m-bit pseudorandom string, and aux is an auxiliary information; -Prove(pp, aux, i), on input the public parameters, auxiliary informations aux,

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

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

Note that the above definition also captures publicly verifiable pseudorandom generators, which are DVPRGs where we restrict Setup(1 λ , m) to always output pairs of the form (pp, ⊥).

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

Pr    (pp, T ) $ ← Setup(1 λ , m), (pvk, x, aux) $ ← Stretch(pp), : Verify(pp, pvk, T , i, x i , π) = 1 π $ ← Prove(pp, aux, i),    = 1.
We now define the binding property of a DVPRG. We consider a flavor of the binding property which is significantly weaker than the one considered in [DN00], yet still suffices for the application to NIZKs (see the discussion in Section 3.1).

Definition 9 (Binding Property of a DVPRG). Let (Setup, Stretch, Prove, Verify) be a DVPRG. A DVPRG is binding if there exists a (possibly inefficient) extractor Ext such that for any PPT A, it holds that

Pr   (pp, T ) $ ← Setup(1 λ , m), (pvk, i, π) $ ← A(pp), : Verify(pp, pvk, T , i, 1 -x i , π) = 1 x ← Ext(pvk)   ≈ 0.
As for non-interactive zero-knowledge proofs, the designated-verifier setting requires to explicitly consider whether the adversary is given access to a verification oracle. We therefore extend the above definition and consider the unbounded binding property:

Definition 10 (Unbounded Binding Property of a DVPRG). Let (Setup, Stretch, Prove, Verify) be a DVPRG. A DVPRG satisfies unbounded binding if there exists a (possibly inefficient) extractor Ext such that for any PPT A, it holds that

Pr   (pp, T ) $ ← Setup(1 λ , m), (pvk, i, π) $ ← A Verify(pp,•,T ,•,•,•) (pp), : Verify(pp, pvk, T , i, 1 -x i , π) = 1 x ← Ext(pvk)   ≈ 0.
Note that in the case of publicly verifiable pseudorandom generators, where T is set to ⊥, this security notion is equivalent to the binding property.

We now define equivocability. Intuitively, it states that no computationally bounded adversary can distinguish honestly generated proofs of correctness for bits of the pseudorandom sequence from simulated proofs (using T ) of opening to true random bits.

Definition 11 (Equivocability of a DVPRG). A designated-verifier pseudorandom generator (Setup, Stretch, Prove, Equivocate, Verify) is equivocable if there are two additional algorithms (SimSetup, Equivocate) such that -SimSetup(1 λ , m), on input the security parameter in unary, outputs a triple (pp, T , T s ), -Equivocate(pp, pvk, i, b, T s ), on input the public parameters, a public verification key pvk, an index i ∈ [m], a bit b, and a simulation trapdoor T s , outputs a simulated proof π ; such that the following distributions are computationally indistinguishable:

   (pp, T ) $ ← Setup(1 λ , m), (pvk, x, aux) $ ← Stretch(pp) π $ ← (Prove(pp, aux, i)) i : (pp, pvk, T , x, π)    = D 0 ≈    (pp, T , T s ) $ ← SimSetup(1 λ , m), (pvk, x , aux) $ ← Stretch(pp), x $ ← {0, 1} m , π $ ← (Equivocate(pp, pvk, i, x i , T s )) i : (pp, pvk, T , x, π)    = D 1 .
A weaker variant of equivocability is the following hiding property, which states that an adversary cannot guess the value of a particular output (with non-negligible advantage over the random guess), even if he is given the values of all other outputs together with proofs of correct opening. This notion is implied by the equivocability property, and it suffices for for the Dwork and Naor construction of a NIZK proof system for NP; however, equivocable DVPRGs allow for a simpler and more direct construction of NIZKs, without having to rely on the FLS transform which constructs NIZKs from NIWI [FLS90].

Definition 12 (Hiding Property of a DVPRG). A DVPRG 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, T ) $ ← Setup(1 λ , m), (pvk, x, aux) $ ← Stretch(pp), : A(pp, pvk, i, (x j , π j ) j =i ) = x i (π j $ ← Prove(pp, aux, j)) j    ≈ 1/2.
Eventually, we define an additional security notion, the consistency, which will prove useful to analyze the unbounded binding property of one of our candidates:

Definition 13 (Consistency of a DVPRG). Given a DVPRG (Setup, Stretch, Prove, Verify) and a pair (pp, T ) = Setup(1 λ , m; r) for some random coin r, we define for any ε the set ε-Good(r) to be the set of 4-tuples (pvk, i, π, x i ) satisfying

Pr T $ ← Dist(r) : Verify(pp, pvk, T , i, x i , π) = 1 ≥ ε,
where Dist(r) samples random pairs (pp , T ) with Setup(1 λ , m) subject to the constraint pp = pp, and outputs T . Note that for any ε ≥ ε, it holds that ε -Good(r) ⊂ ε-Good(r). Then, we say that a DVPRG is consistent if there exists a negligible function ε such that for any PPT adversary A,

Pr r $ ← R, (pp, T ) ← Setup(1 λ , m; r), (pvk, i, π, b) $ ← A(pp) : (pvk, i, π, b) ∈ ε-Good(r) \ 1-Good(r) ≈ 0.
In Appendix A of the supplementary material, we prove the following:

Theorem 14. Let G = (Setup, Stretch, Prove, Verify) be a binding and consistent DVPRG, such that for any r, the distribution Dist(r) is efficiently sampleable. Then G is unbounded binding.

4 DVNIZK Proof for NP from DVPRG

The Hidden Bit Model, and HB Proofs

The hidden bit model is an ideal formalization of a scenario in which both the prover and the verifier have access to a long string of hidden random bits (let us denote with hb the random bits and t = t(λ) the length of the hidden string). In this idealized model, the prover can send to the verifier a subset S ⊂ [t] of the positions of the hidden bits (together with additional informations). The verifier is restricted to inspecting only the bits of hb residing in the locations specified by the prover, while the prover can see hb entirely.

Definition 15. A non-interactive proof system HB in the hidden bit model is a pair of PPT algorithms (HB.Prove, HB.Verify) such that -HB.Prove(hb, x, w), on input a random bit string hb ∈ {0, 1} t , and a word x ∈ L with witness w, outputs a subset S ⊂ [t] together with a string M of auxiliary informations, -HB.Verify(x, hb[S], M ), on input a word x, the subsequence of hb indexed by S, and an auxiliary information M , outputs b ∈ {0, 1}, which satisfies the following perfect completeness, ε-soundness, and (adaptive, single-theorem) zeroknowledge properties:

-Perfect Completeness. For any x ∈ L with witness w, any hb ∈ {0, 1} t , and for (S, M ) $ ← HB.Prove(hb, x, w), it holds that HB.Verify(x, hb[S], M ) = 1.

ε-Soundness. For any (possibly unbounded) adversary A,

Pr hb $ ← {0, 1} t , (x, S, M ) $ ← A(hb) : HB.Verify(x, hb[S], M ) = 1 ∧ x / ∈ L ≤ ε.
-Single-Theorem Zero-Knowledge. For any (possibly unbounded) stateful adversary A, there exists a simulator (Sim zk , Sim zk ) such that for every x ∈ L and any w satisfying R L (x, w) = 1,

• the distributions , S, M ) without a witness, and find a completion of the hidden string hb given a witness w, which is identically distributed to an honestly generated hidden string and proof with w.

{(hb[S]
Note that in the hidden bit model, the parties do not have access to a common random string, but to a string of bits which are perfectly hidden to the verifier until the prover opens a subsequence of them. Therefore, the adaptive and non-adaptive formulations of zero-knowledge are equivalent since the verifier does not get to see anything about hb before producing a word x with a witness w (put differently, it is equivalent to define zero-knowledge for all x ∈ L or with respect to adversarially chosen x). Examples of non-interactive proof systems in the hidden-bit model can be found in [FLS90, KP98]. We stress that the security of these proof systems is unconditional (although a specific implementation of the HB model can involve cryptography).

A DVNIZK for NP from any DVPRG

We describe on Figure 2 a general transformation that converts any (unconditional) proof system in the HB model into a DVNIZK for the same language, given any DVPRG. The DVNIZK inherits the specificities of the DVPRG: it satisfies unbounded soundness and/or statistical soundness whenever the DVPRG is unbounded binding and/or statistically binding. At the exception of using a DVPRG instead of a VPRG, the proof system is identical to the one of [DN00, Section 5.1] (actually, [DN00] provides a ZAP in the plain model where the first flow can be fixed non-uniformly, which immediately implies a NIZK in the CRS model. Our construction does not imply a ZAP in the plain model, as we need to setup a CRS containing, in particular, the public parameters of the DVPRG. These public parameters must be honestly sampled to maintain the hiding property, hence they cannot be picked by the verifier in the first round.)

While the scheme is almost identical to the scheme of [DN00], the proof of soundness is more involved, as it must cope with the weaker binding property of our PRGs. To prove soundness, we proceed as follows: we identify a "bad event", which occurs whenever the adversary outputs pvk and a proof π for some position i of correct opening to 1 -x i , where x = Ext(pvk) (Ext being the possibly inefficient extractor guaranteed by the unbounded binding security notion of the DVPRG). We show that when this bad even does not happen, then there is a string (essentially x ⊕ ρ, where ρ is a long random string which is part of the CRS) which is a bad string, in the sense that if this string is used as the hidden bit string of the HB proof system, there exists accepting proofs of incorrect statement with respect to this hidden string. Then, we rely on the statistical soundness of the HB proof system to argue that only a tiny fraction of all possible strings (of a given length) are bad strings. Since ρ is random and x is uniquely defined given pvk, we can rely on the fact that pvk is short to argue, with a counting argument, that there is a negligible probability (over the random choice of ρ) that there exists a short pvk such that ρ ⊕ Ext(pvk) is a bad string. Hence, this situation is statistically unlikely, and we must be in the case where the bad event happens; then, we conclude the proof by observing that an occurrence of this bad event directly contradicts the unbounded binding property of the DVPRG. In contrast, the argument of [DN00] uses a counting argument over all possible seeds of the VPRG, which crucially relies on their stronger binding property which states that any possible pvk is in the stretch of the PRG, and is bound to a seed (while this seed need not be unique, all seeds associated to a given pvk must lead to the same pseudorandom string).

Theorem 16. Let G be a hiding unbounded binding DVPRG, and let (Π.Setup, Π.Prove, Π.Verify) be the DVNIZK proof system given on Figure 2. Then Π satisfies computational witness-indistinguishability and unbounded adaptive soundness. Furthermore, if G is equivocable, Π satisfies (adaptive, singletheorem) zero-knowledge.

The completeness of Π follows immediately from the completeness of HB and G. In the remainder of this section, we prove Theorem 16. The proof of witness-indistinguishability is similar to the one given in [DN00], but the proof of soundness is more involved (see the previous discussion).

DVNIZK Proof System Π

Let L be a language and let y ∈ L be a word with witness w. Let λ ← |y|. The DVNIZK relies on an HB proof system HB for the statement y ∈ L which uses = (λ) hidden bits, and achieves 2 -λ -statistical soundness. Let G = (G.Setup, G.Stretch, G.Prove, G.Verify) be a DVPRG, with public verification key size s(λ) and output size m(λ), satisfying m > (1 + s/λ) + 2 /λ. In the following, we consider the HB proof system HB obtain by executing HB m/ times in parallel (with independent hidden bits) and accepting only if all executions are accepted. Note that HB uses m hidden bits and achieves 2 -λm/ -statistical soundness. Recall that HB consists of m/ parallel repetitions of HB (with independent hidden bits hb j ). We consider a sequence of intermediate hybrids H 0.j for j = 0 to m/ , in which we use the witness w 1 for the j first repetitions (computing (S j , M j ) as HB.Prove(hb j , y, w 0 )) and the witness w 0 for the repetitions j + 1 to m/ . By a standard pigeonhole argument, there exists a j such that the advantage of A in distinguishing H 0.j from H 0.j+1 is at least ε /m. We further divide H 0.j in the following sub-hybrids:

-H 0.j.0 . In this hybrid, we modify the generation of (hb j+1 , S j+1 , M j+1 ). Namely, we compute (pvk, x, aux) $ ← G.Stretch(pp) (let x j+1 , ρ j+1 denote the (j + 1)-th block of bits of x, ρ), generate

(hb j+1 [S j+1 ], S j+1 , M j+1 ) $ ← Sim zk (y), hb j+1 $ ← Sim zk (hb j+1 [S j+1
], S j+1 , M j+1 , y, w 1 ), and set θ ← x j+1 ⊕ ρ j+1 ⊕ hb j+1 . The other repetitions of HB are executed as before; note that it holds that hb i = x i ⊕ ρ i ⊕ θ (i-1) mod for every i ≤ m. By the (perfect) single-theorem zero-knowledge property of HB, the distribution of (crs, π) in H 0.j.1 is identical to its distribution in H 0.j , hence the advantage of A in distinguishing H 0.j.1 from H 0.j+1 is at least ε /m. -H 0.j.k . We denote by -r the size of S j+1 (r is the size of the "unopened" subsequence of hb j+1 ). For k = 0 to r, we modify the generation of hb j+1 as follows: we generate as before (hb j+1 [S j+1 ], S j+1 , M j+1 ) $ ← Sim zk (y), denote R j+1 the set [ ] \ S j+1 of unopened positions of hb j+1 , and compute

• hb j+1.0 [R j+1 ] $ ← Sim zk (hb j+1 [S j+1 ], S j+1 , M j+1 , y, w 0 ), • hb j+1.1 [R j+1 ] $ ← Sim zk (hb j+1 [S j+1
], S j+1 , M j+1 , y, w 1 ). Then, we define hb j+1 [R j+1 ] to be the string that agrees with hb j+1.1 [R j+1 ] for positions 1 to k, and with hb j+1.0 [R j+1 ] for positions k + 1 to r. By a standard pingeonhole argument, there exists a k such that A distinguishes H 0.j.k from H 0.j.k+1 with probability at least ε /(mr) ≥ ε/m. Note that the string hb j+1 differs by a single bit between H 0.j.k and H 0.j.k+1 . From there, we immediately reach a contradiction to the hiding property of G: denoting i ← (j + 1) + k + 1, we receive (pp, pvk, i, (x t , π t ) t =i , compute (hb j+1 [S j+1 ], S j+1 , M j+1 ) $ ← Sim zk (y), guess the value x i at random (completing the string x), and set θ ← x j+1 ⊕ ρ j+1 ⊕ hb j+1 . Depending on our guess of x i , the distribution of (crs, π) is either identical to its distribution in H 0.j.k or in H 0.j.k+1 , hence we distinguish between x i = 0 and x i = 1 with probability at least ε/m. This concludes the proof.

Adaptive Single-Theorem Zero-Knowledge of Π

A witness-indistinguishable NIZK proof system for NP implies an adaptive zero-knowledge proof system for NP, by the transformation of [FLS90]. However, if G is equivocable, there is a more direct construction: we prove that in this case, the DVNIZK Π is adaptive single-theorem zero knowledge (and can be made adaptive multi-theorem zero-knowledge using [FLS90]); the argument is simpler than for witness indistinguishability, does only use Sim zk (the simulator Sim zk is not needed), and does not require θ (which can be removed from the construction -we keep it in the proof below for simplicity). Let A be a PPT adversary against the (adaptive) single-theorem zero-knowledge of Π. Let Sim = (Sim 0 , Sim 1 ) be the following simulator:

-On input 1 λ , Sim 0 computes (pp, T ) $ ← G.SimSetup(1 λ , m), and ρ $ ← {0, 1} m . He outputs crs ← (pp, ρ) and T .

-On input (crs, T , y), Sim parses crs as (pp, ρ) and computes (pvk, x , aux)

$ ← G.Stretch(pp). Then, Sim 1 runs (hb[S], S, M ) $ ← Sim zk (y)
, where Sim zk is the simulator of the zero-knowledge property of HB . Sim 1 picks θ $ ← {0, 1} . For every i ∈ S, he sets x i ← hb i ⊕ρ i ⊕θ (i-1 mod )+1 and computes π i $ ← G.Equivocate(pp, pvk, i, x i , T ). Sim 1 outputs (pvk, θ, S, hb[S], M, (π i ) i∈S ).

We prove that

Pr

   (crs, T ) $ ← Setup(1 λ ), (y, w) $ ← A(crs, T ), : (R L (y, w) = 1) ∧ (A(π) = 1) π $ ← Π.Prove(crs, y, w)    - Pr    (crs, T ) $ ← Sim 0 (1 λ ), (y, w) $ ← A(crs, T ), : (R L (y, w) = 1) ∧ (A(π) = 1) π $ ← Sim 1 (crs, T , y)    ≈ 0,
through a sequence of hybrids.

-Game H 0 . This is the real game, where we generate (crs, T )

$ ← Setup(1 λ ), run (y, w) $ ← A(crs, T ), π $ ← Π.Prove(crs, y, w), and b $ ← A(π).
-Game H 1 . In this game, we generate instead (crs, T ) as Sim 0 (1 λ ) (that is, we compute (pp, T )

$ ← G.SimSetup(1 λ , m) and ρ $ ← {0, 1} m
). Furthermore, we modify Π.Prove(crs, y, w) as follow: after computing (pvk, x , aux)

$ ← G.Stretch(pp), we pick x $ ← {0, 1} m and set hb i ← x i ⊕ ρ i ⊕ θ (i-1 mod )+1
. We compute the HB proof (S, M ) honestly using (y, w) and the hidden string hb. Finally, we compute the π i as G.Equivocate(pp, pvk, T , i, x i ). By the equivocability of G, the distribution of (pp, pvk, T , x, (π i ) i∈S ) in H 1 is computationally indistinguishable from its distribution in H 0 , and the rest of the proof is computed from (pp, pvk, T , x) identically in both games, hence there is a direct reduction from breaking the equivocability of G to distinguishing H 0 and H 1 .

-Game H 2 . In this game, instead of picking x $ ← {0, 1} m and setting hb i ← x i ⊕ρ i ⊕θ (i-1 mod )+1 , we first pick hb $ ← {0, 1} and set x i ← hb i ⊕ ρ i ⊕ θ (i-1 mod )+1 for every i ≤ m. Note that this is a purely syntactic change, since hb and x are just a uniformly random sharing of (ρ i ⊕ θ (i-1 mod )+1 ) i≤m , hence this game is perfectly indistinguishable from the previous one.

-Game H 3 . In this game, we play as in Game H 2 except that we compute (hb[S], S, M ) $ ← Sim zk (y) instead (note that the remaining hidden bits of hb are never used). By the single-theorem zeroknowledge property of HB, this game is perfectly indistinguishable from the previous one. Note that Game H 3 does exactly correspond to the simulation with (Sim 0 , Sim 1 ). This concludes the proof.

Unbounded Adaptive Soundness of Π

Let A be a PPT adversary against the soundness of Π, which is given oracle access to a verification oracle O(crs, •, •, T ). Let (crs, T ) $ ← Π.Setup(1 λ ), and parse crs as (pp, ρ). Run (y, π) $ ← A(crs). Let ε denote the probability (over the coins of Π.Setup) that Π.Verify(crs, y, π, T ) = 1 and y / ∈ L :

Pr (crs, T ) $ ← Setup(1 λ ), (y, π) $ ← A O(crs,•,•,T ) (crs) : Π.Verify(crs, y, π, T ) = 1 ∧ y / ∈ L = ε.
In the following, we assume for the sake of contradiction that ε is non-negligible. We will construct from A an adversary B which contradicts the unbounded binding of G. B interacts with A in the unbounded soundness security experiment of Π. The challenger of the unbounded binding property of G samples (pp, T ) $ ← Setup(1 λ , m). B receives pp and is given oracle access to G.Verify(pp, •, T , •, •, •). It picks ρ $ ← {0, 1} m , sets crs ← (pp, ρ), and runs A(crs). Let q be the number of queries that A asks to O(crs, •, •, T ) in the unbounded soundness security experiment of Π. B simulates the answers of O(crs, •, •, T ) as follows: on input π = (pvk, θ, S, hb[S], M, (π i ) i∈S ) it sets for every i ∈ S x i ← hb i ⊕ ρ i ⊕ θ (i-1 mod )+1 and calls G.Verify(pp, •, T , •, •, •) on input (pvk, i, x i , π i ). Then, it verifies the HB proof (S, hb[S], M ) for the statement y ∈ L and outputs 1 iff all checks succeeded. Then, A outputs a pair (y, π). Since B perfectly simulates crs and the answers of O(crs, •, •, T ), it holds that Π.Verify(crs, y, π, T ) = 1∧y / ∈ L with probability ε over the coins of the challenger and A, B. Finally, B parses π as (pvk * , θ, S, hb[S], M, (π i ) i∈S ), picks i * $ ← S, and outputs (pvk * , i * , π i * ). To simplify the analysis in the following, we assume that B also outputs (crs, y, π) in addition to (pvk * , i * , π i * ) (it is only a syntactic modification that will make it more convenient to describe the probability experiments).

We analyze the probability that G.Verify(pp, pvk * , T , i * , 1 -x i * , π i * ) = 1. Let us call 'bad' a string hb for which there exists y / ∈ L and an accepting proof of y ∈ L under the HB proof system HB . Under the 2 -λm/ -statistical soundness of HB , the ratio of bad strings must be at most 2 -λm/ < 2 λ+s+ . Let us say that a string hb is "close to a bad string w.r.t. pp" hb if there exists θ ∈ {0, 1} and a public verification key pvk ∈ {0, 1} s(λ) such that hb = (x i ⊕ hb i ⊕ θ (i-1 mod )+1 ) i is a bad string, where x = Ext(pp, pvk). As there are at most 2 +s possible choices of (θ, pvk), for any choice of public parameters pp, the ratio of strings which are close to a bad string w.r.t. pp must be at most 2 -λ-s-• 2 +s = 2 -λ . Therefore, with overwhelming probability 1 -2 -λ over the distribution of ρ, ρ is not close to a bad string w.r.t. pp, hence there does not exist a string (y, pvk, θ) with y / ∈ L such that

(hb i ) i = (x i ⊕ ρ i ⊕ θ (i-1 mod )+1 ) i is a bad string.
We consider two complementary cases, one of which must necessarily occur:

Case 1. With probability at least ε/2, the output (y, π) of A satisfies Π.Verify(crs, y, π, T ) = 1 ∧ y / ∈ L , and for every i ∈ S, it holds that G.Verify(pp, pvk * , T , i * , 1 -

x i , π i ) = 1. That is, Pr   (pp, T ) $ ← Setup(1 λ , m), (pvk * , i * , π i * , crs, y, π) $ ← B(pp), x ← Ext(pp, pvk * ) : Π.Verify(crs, y, π, T ) = 1 ∧ y / ∈ L ∧ ∀i ∈ S, G.Verify(pp, pvk * , T , i, 1 -x i , π i ) = 1   ≥ ε 2 ,
where B is given oracle access to G.Verify(pp, •, T , •, •, •). Now, parse π as (pvk * , θ, S, hb[S], M, (π i ) i∈S ). Let x denote Ext(pp, pvk * ), and let

(hb i ) i = (x i ⊕ ρ i ⊕ θ (i-1 mod )+1 ) i .
Since a random ρ has probability at most 1/2 λ to be close to a bad string w.r.t. pp, (hb i ) i has probability at most 1/2 λ of being a bad string. Therefore, if case 1 happens, we necessarily have (denoting µ = ε/2 -1/2 λ ):

Pr    (pp, T ) $ ← Setup(1 λ , m), (pvk * , i * , π i * , crs, y, π) $ ← B(pp), x ← Ext(pp, pvk * ) : Π.Verify(crs, y, π, T ) = 1 ∧ y / ∈ L ∧ ∀i ∈ S, G.Verify(pp, pvk * , T , i, 1 -x i , π i ) = 1 ∧ hb is not a bad string    ≥ µ.
Note that the condition Π.Verify(crs, y, π, T ) = 1 implies that for all i ∈ S, denoting x i ← hb i ⊕ ρ i ⊕ θ (i-1 mod )+1 , G.Verify(pp, pvk * , T , i, x i , π i ) = 1. Denoting x = Ext(pp, pvk * ), it holds by assumption that G.Verify(pp, pvk * , T , i, 1 -x i , π i ) = 1 for every i ∈ S, hence G.Verify(pp, pvk * , T , i, 1 -x i , π i ) = 0. This implies that for any i ∈ S, x i = 1 -x i , hence that (x i ) i∈S = (x i ) i∈S , which in turns implies that hb[S] = hb [S]. Therefore, if case 1 happens, with probability at least ε/2 -1/2 λ we have the following:

-y / ∈ L , -Π.Verify(crs, y, π, T ) = 1, -hb[S] = hb [S] is not a bad string.
However, by the soundness of the HB proof system HB , there cannot exist any accepting proof (S, hb[S], M ) for a statement y / ∈ L unless hb[S] is a bad string. Since Π.Verify does also check the HB proof, this event can never happen and we get:

ε 2 - 1 2 λ = 0,
contradicting our assumption that ε is non-negligible. Hence, case 1 never happens and the following case necessarily happens:

Case 2. There exists i ∈ S such that G.Verify(pp, pvk * , T , i, 1 -x i , π i ) = 1 with probability at least ε/2. That is,

Pr   (pp, T ) $ ← Setup(1 λ , m), (pvk * , i * , π i * , crs, y, π) $ ← B(pp) : Π.Verify(crs, y, π, T ) = 1 ∧ y / ∈ L ∧ ∃i ∈ S, G.Verify(pp, pvk * , T , i, 1 -x i , π i ) = 1   ≥ ε 2 .
Since B picks i * at random in a set S of size at most m, this gives us in particular

Pr (pp, T ) $ ← Setup(1 λ , m), (pvk * , i * , π i * , crs, y, π) $ ← B(pp) : G.Verify(pp, pvk * , T , i * , 1 -x i , π * ) = 1 ≥ ε 2m ,
which immediately gives a contradiction to the unbounded binding of G, concluding the proof.

Impact on our LWE-Based Instantiation. Note that our alternative proof strategy, which does not use any assumed structure for pvk except a bound on its length, is the key to our LWE-based instantiation. Indeed, if we had to assume some structure of pvk (such as "pvk was honestly generated"), we would have to include a NIZK proof of validity of pvk in our instantiation (which is similar to the NIZK proof of validity for the public key used in [RSS19]). Since there might not exist more than a single witness for the validity of pvk, it seems unlikely that we could use a NIWI instead of a NIZK here. By removing entirely the need for proving validity of pvk in our LWE-based instantiation, we enable the construction of a NIZK for NP from LWE using only a NIWI for a simple language (bounded distance decoding), improving over the result of [RSS19].

5 Constructions of Designated-Verifier Pseudorandom Generators

A DVPRG from the CDH Assumption

Assumptions. Let DHGen denote a PPT algorithm which, on input 1 λ , outputs an integer n, the description of a group G of order n, and a generator g of G. The computational Diffie-Hellman assumption (CDH), with respect to g over G, states that it is computationally infeasible, for any PPT algorithm which is given (n, g, G) and a random pair (g a , g b ) from G 2 , to compute g ab . The decisional Diffie-Hellman assumption (DDH), with respect to g over G, states that it is computationally infeasible for any PPT algorithm to distinguish the distribution {(g a , g b , g ab ) | (a, b)

$ ← Z 3 n } of random DDH tuples from the uniform distribution over G 3 .
The twin (computational or decisional) Diffie-Hellman assumption (twin-CDH and twin-DDH), defined in [CKS08], are variants of the CDH and DDH assumptions. The twin-CDH problem with respect to g over G states that it is computationally infeasible, for any PPT algorithm which is given (n, g, G) and a random triple (g a , g b , g c ) from G 3 , to compute (g ab , g ac ); twin-DDH is its natural decisional variant. Twin-CDH (resp. twin-DDH) is equivalent to the standard CDH (resp. DDH) assumption. However, there is a natural trapdoor test that allows to check the correctness of twin-DDH tuples: let (α, β) be a random pair of exponents satisfying g c = g α (g b ) -β (note that many such pairs exist). Then given an input (g a , g b , g c ), the probability for an arbitrary (possibly unbounded) adversary A to output a pair (h 1 , h 2 ) such that the truth value of h β 1 h 2 = (g a ) α does not agree with the truth value of (h 1 = g ab ) ∧ (h 2 = g ac ) is at most 1/n (see [CKS08]). Therefore, a verifier which is given the trapdoor (α, β) can check the correctness of a twin Diffie-Hellman tuple, with negligible error probability. This trapdoor test implies that the gap twin Diffie-Hellman problem, which states that solving the twin-CDH problem is hard even given an oracle that solves the twin-DDH problem, is at least as hard as the standard CDH problem.

Our Construction. Our construction will rely on the conjectured hardness of the computational Diffie-Hellman (CDH) assumption. Let B : G 3 → {0, 1} be a predicate satisfying the following property: given (g a , g b , g c ), computing B(g a , g ab , g ac ) should be as hard (up to polynomial factors) as computing (g a , g ab , g ac ). Note that this implies that distinguishing B(g a , g ab , g ac ) from a random bit given a random triple (g a , g b , g c ) is as hard as solving CDH. There are standard method to build this predicate using e.g. the Goldreich-Levin construction [GL89], see e.g. [CKS08] for an illustration in the specific case of CDH. Our construction proceeds as follows:

-Setup(1 λ , m) : sample (n, G, g) $ ← DHGen(1 λ ). For i = 1 to m, pick (a i , b i ) $ ← Z 2 n and set (u i , v i ) ← (g ai , g bi ). Set pp = (u i , v i ) i≤m . For i = 1 to m, pick β i $ ← Z n and set α i ← b i + a i β i (observe that (α i , β i ) are uniformly distributed exponents subject to v i = g αi u -βi i ).
Output pp and T ← (α i , β i ) i≤m . We also define SimSetup(1 λ , m) to be identical to Setup(1 λ , m) and define

T s = T . -Stretch(pp) : pick r $ ← Z n , set pvk ← g r , and for i = 1 to m, set x i $ ← B(pvk, u r i , v r i ). Output (pvk, x, aux = r). -Prove(pp, aux, i) : output π ← (u r i , v r i ). -Equivocate(pp, pvk, T s , i, σ) : pick u $ ← G, set v = pvk αi (u ) -βi
, and check whether B(pvk, u , v ) = σ; if it does not hold, start again. Output π ← (u , v ).

-Verify(pp, pvk, T , i, σ, π) : parse π as (u , v ), check whether B(pvk, u , v ) = σ and check whether (u ) βi v = pvk αi . If both checks pass, output 1; otherwise, output 0.

This construction follows the twin Diffie-Hellman paradigm of Cash, Kiltz, and Shoup [CKS08], which relies on the fact that computing the twin Diffie-Hellman function, which on input (g x , g y1 , g y2 ) outputs (g xy1 , g xy2 ), is at least as hard as solving the CDH problem, even given an oracle for twin-DDH.

Theorem 17. If the CDH assumption holds over G, then the above construction is a computationally hiding unbounded statistically binding DVPRG. Furthermore, if the DDH assumption holds over G, the above construction is also equivocable.

Proof. Completeness follows easily by inspection. We now look at the unbounded binding property; by Theorem 14, it suffices to show that the scheme is binding, consistent, and that we can efficiently sample trapdoors consistent with pp (a proof of Theorem 14 is given in Appendix A). From the analysis of [CKS08, Section 2], as (g x , g y1 , g y2 ) uniquely define the pair (h 1 , h 2 ) such that (h 1 = g xy1 ) ∧ (h 2 = g xy2 ) and any adversary has negligible probability 1/n of outputting a non-twin-DH pair (h 1 , h 2 ) that fools the test, it follows that the scheme is statistically binding (the inefficient extractor Ext simply extracts r from pvk = g r and computes the string x as x i $ ← B(pvk, u r i , v r i ) for i = 1 to m). Second, observe that we can efficiently sample trapdoors consistent with pp, by storing the random values (a i , b i ) i and sampling each trapdoor T = (α i , β i ) as β i $ ← Z n and α i ← b i + a i β i . Therefore, this defines an efficiently sampleable distribution Dist((a i , b i ) i ).

We now show that our construction satisfies consistency. Let ε ← 2/n5 and let A be an adversary that, on input pp = (u i , v i ) i = (g ai , g bi ) i , outputs a 4-tuple (pvk, i, π = (u , v ), σ) such that

Pr[β i $ ← Z n : Verify(pp, pvk, (α i , b i + a i β i ), i, σ, (u , v )) = 1] ≥ ε.
The above implies that A outputs (pvk, u , v ) such that (u ) βi v = pvk αi holds with probability at least 2/n. Suppose now that (pvk, u i , v i , u , v ) is not a twin-DH tuple; let us denote pvk = g r and (u , v ) = (g s , g t ) with s = a i r or t = b i r. Then the previous equation becomes g sβi+t = g rαi , which gives β i (s -a i r) = rb i -t.

However, if s -a i r = 0 or rb i -t = 0, then this equation holds with probability at most 1/n over the random choice of β i , hence since we assumed that this equation is satisfied with probability at least 2/n, it must be that s -a i r = rb i -t = 0, hence (pvk, u i , v i , u , v ) is a twin-DH tuple. But then, it immediately follows that the above equation is always satisfied, independently of the choice of β i :

Pr[β i $ ← Z n : Verify(pp, pvk, (α i , b i + a i β i ), i, σ, (u , v )) = 1] = 1,
which concludes the proof of consistency. Since the DVPRG is also statistically binding (in a bounded sense), we use Theorem 14 to conclude that the above construction satisfies (statistical) unbounded binding.

We now discuss the hiding property. We show that a PPT adversary against the hiding property of the above scheme implies the existence of a PPT adversary that solves the computational twin Diffie-Hellman problem. The result follows from the proof of [CKS08] that the computational twin Diffie-Hellman problem is at least as hard as the CDH problem. The reduction is relatively straightforward: given a position i ≤ m, we pick (a j , b j ) j =i , receive a computational twin-DH challenge (c 0 , c 1 , c 2 ), and set pvk ← c 0 , (u j , v j ) ← (g aj , g bj ) for every j = i, and (u i , v i ) ← (c 1 , c 2 ). We output pp ← (u j , v j ) j≤m , pvk, and (x j , π j ) $ ← (B(pvk, c ai 0 , c bj 0 ), (c ai 0 , c bj 0 )) for every j = i. Note that pp, pvk and the x j , π j are distributed exactly as in an honest execution of the experiment. Then, we run A(pp, pvk, (x j , π j ) j =i ) and get a bit b. If A guesses the value of x i = B(pvk, c 1 , c 2 ), where (c 1 , c 2 ) = (c r 1 , c r 2 ) for the value r such that c 0 = pvk = g r , then we efficiently find a hardcore bit for the twin-DH problem with non-negligible probability. As guessing a hardcore bit for twin-DH is at least as hard as solving the computational twin-DH problem, the proof follows.

Regarding equivocability, the reduction gets a DDH challenge (c 0 , c 1 , c 2 ). It sets pvk ← g r , samples

(α i , β i ) i $ ← Z 2m n and pp = (u i , v i ) i as (c ai 1 , g αi u -βi i ) i with random a i 's. It computes each proof π i as (u , v ) ← (c ai 2 , pvk αi (u ) -βi ).
Observe that the distribution of (pp, T , pvk, (π i ) i ) is identical to the distribution obtained with an honest run of the DVPRG when (c 0 , c 1 , c 2 ) is a DDH tuple, and identical to a run of the DVPRG with the algorithm Equivocate when (c 0 , c 1 , c 2 ). Hence, distinguishing honest proofs from equivocated proofs is equivalent to breaking the DDH assumption.

Corollary 18. Assuming the computational Diffie-Hellman assumption, there exists an unbounded designated-verifier non-interactive (adaptive, multi-theorem) zero-knowledge proof system for NP.

Note that the above construction also implies that the existence of a (publicly verifiable) NIZK proof system for the DDH language (together with the CDH assumption) would imply a NIZK proof system for NP.

A DVPRG from the LWE Assumption

We also give a construction of a DVPRG in the LWE setting. Our construction already assumes a designated-verifier NIWI proof system Π for the LWE language. We stress, however, that Π does not have to enjoy zero-knowledge; witness-indistinguishability is sufficient. We also note that Π can be publicly verifiable, in which case the DVPRG becomes publicly verifiable.

Algebraic setting. We largely follow the presentation of [GVW15] and abstract the setting as far as possible. In the following, let n, m = poly(λ) and q, β = 2 poly(λ) with m > n and q > β be suitable integers. We also assume an error distribution χ that outputs integers e with |e| < β.

The Learning With Errors (LWE) problem (relative to n, m, q, β) is to distinguish access to an oracle O lwe real,s (with hardwired uniform s ∈ Z n q ) from access to another oracle O lwe rand . Here, O lwe real,s (parameterized over s ∈ Z n q ) outputs samples (a, s a + e) for fresh a $ ← Z n q and e ← χ, and O lwe real,s outputs (a, r) with fresh a $ ← Z n q and r $ ← Z q . The LWE assumption is that for every PPT adversary A,

Pr A O lwe real,s (1 λ ) = 1 -Pr A O lwe rand (1 λ ) = 1 ≈ 0,
where the probability is over s $ ← Z n q and the random coins of A and the oracles. In the following, let A ∈ Z n×m q , and consider the language

L A := Au | u ∈ Z m q with ||u|| ∞ < β .
Depending on A, L A may be trivial. However, if A can be written as A = A s A + e with ||e|| ∞ < β, then L A consists of all zero-encryptions under Regev's encryption scheme [Reg05]. In that case, L A is hard to decide under the LWE assumption.

Homomorphic commitments. In the setting above, Gorbunov, Vaikuntanathan, and Wichs [GVW15] construct homomorphic trapdoor functions (HTDFs). As they point out, HTDFs can also be viewed as homomorphic commitments. Formally, an HTDF HF consists of the following PPT algorithms: Key generation. HF.Setup(1 λ ) outputs a keypair (pk, sk). We require that pk defines input, output, and index sets U, V, and X . These sets must be efficiently decidable, and we assume are efficiently samplable distributions D U and D V over U and V. Function evaluation. f pk,x evaluates a deterministic function from U to V. We can view f pk,x (u)

as a commitment under pk to x with random coins u. Function inversion. Inv sk,x probabilistically samples a preimage of f pk,x . We require that for every (pk, sk) in the range of HF.Setup, every x ∈ X , and every v in the range of f pk,x , the value Inv sk,x (v) is distributed statistically close to a random preimage of v under f pk,x sampled from D U . Homomorphic evaluation. Eval in and Eval out allow homomorphic computations on inputs and outputs, in the following sense. For all pk in the range of HF.Setup, all ∈ N, all functions g (represented as circuits), all

(x i , u i , v i ) ∈ X × U × V (1 ≤ i ≤ ) with v i = f pk,xi (u i ), and for u * := Eval in pk (g, (x i , u i ) i=1 ) and v * := Eval out pk (g, (v i ) i=1 ), we have f pk,g(x1,...,x ) (u * ) = v * .
Dual-mode homomorphic commitments. For security, [GVW15] require that it is computationally hard to find (x, u, x , u ) with x = x and f pk,x (u) = f pk,x (u ). When viewing HTDFs as commitment schemes, this corresponds to a computational binding property. For our purposes, however, we require a stronger property that [GVW15] mention but do not formally define or use. Namely, in analogy to dual-mode commitment schemes [GS08], we require that there are two computationally indistinguishable ways to sample public keys: one way leads to a statistically hiding commitment scheme, and the other to a statistically binding scheme. In the HTDF setting, this translates to the following requirements: Statistically hiding. For any fixed pk in the range of HF.Setup, and any x, x ∈ X , the random variables f pk,x (u) and f pk,x (u) (for random u ← D U ) are statistically close. Perfectly binding under alternate key generation. There exists a PPT algorithm HF.Setup bind that outputs public keys pk bind with the following properties:

pk bind c ≈ pk for public keys pk output by HF.Setup, the "function evaluation" and "homomorphic evaluation" properties above also hold (perfectly) for public keys pk bind , for all pk bind in the range of HF.Setup bind , and all x, x ∈ X with x = x , the sets {f pk bind ,x (u) | u ∈ U} and {f pk bind ,x (u) | u ∈ U} are disjoint. In other words, there are no (x, u, x , u ) with x = x and f pk bind ,x (u) = f pk bind ,x (u ).

The instantiation of Gorbunov, Vaikuntanathan, and Wichs.

[GVW15] offer a leveled instantiation of dual-mode homomorphic commitments. That is, their construction only allows for an arbitrary, but a-priori bounded number of homomorphic base operations on commitments. If this number of operations is exceeded, correctness will cease to hold. For our purposes, this leveled construction is sufficient, since the number and type of homomorphic operations is known in advance.

We further note that their HTDF application does not require any dual-mode features. However, in [GVW15, App. B], they explicitly describe and analyze what we call HF.Setup bind above. They show that their construction is secure (in the sense above) under the LWE assumption.

We will not need to consider any specifics of their construction, except for one. Namely, in their scheme, {0, 1} ⊂ X ⊂ Z, and commitments to x are of the form f pk,x (u) = AU + xG for fixed A, G ∈ Z n×m q defined in pk, and a short U ∈ Z m×m q with ||U|| ∞ < β. In other words, commitments to x = 0 are composed of m elements of the language L A defined above. Furthermore, a preimage u is the corresponding witness U. Hence, given an argument system for L A , we can prove that a given commitment v commits to a given x by proving that v -xG ∈ L m A .

Our construction. We can now give our construction of a DVPRG. We assume dual-mode homomorphic commitments HF as described above, and any family of PRGs G m : {0, 1} λ → {0, 1} m . In the following, let G m,i denote the circuit that computes the i-th output bit of G m . Furthermore, we assume a NIWI proof system Π = (Π.Gen, Π.Prove, Π.Verify) for the language L A . Slightly abusing notation, we will use NIWI as an argument system for the language (L A ) m .

-Setup(1 λ , m) runs pk bind $ ← HF.Setup bind (1 λ ) and (crs, T ) $ ← Π.Gen(1 λ ) (for the language L A given by the matrix A defined in pk bind ), and outputs public parameters pp = (pk bind , crs) and a trapdoor T .

-Stretch(pp) samples s = (s 1 , . . . , s λ ) $ ← {0, 1} λ and u 1 , . . . , u λ $ ← D U , then computes v i = f pk bind ,si (u i ), and finally outputs pvk = (v i ) λ i=1 , x = G m (s), and aux = (s, (u i ) λ i=1 ). Observe that the size of pvk does not depend on m.6 -Prove(pp, aux, i) (for aux = (s, (u j ) λ j=1 )) computes v i = f pk bind ,si (u i ) exactly as Stretch, and derives a witness

u * = Eval in pk bind (G m,i , (s j , u j ) λ j=1 ) that explains v * = Eval out pk bind (G m,i , (v j ) λ j=1 ) as v * = f pk bind ,b (u * ). By our discussion above, we have that hence v * -b i G ∈ L m
A with witness u * . Hence, Prove next computes and outputs a proof π

$ ← Π.Prove(crs, v * -bG, u * ). -Verify(pp, pvk, T , i, b, π) parses pvk = (v i ) λ i=1 , then computes v * = Eval out pk bind G m,i , (v j ) λ j=1 ,
and finally returns Π.Verify(crs, v * -b i G, π, T ).

Theorem 19. Assume that LWE holds for the parameters from [GVW15], that G m is pseudorandom, and that Π is perfectly complete, computationally witness-indistinguishable and satisfies unbounded adaptive soundness. Then the above DVPRG is perfectly complete, equivocable, and has the unbounded binding property.

We provide a proof of Theorem 19 in Appendix B.

Let x be such a string. Observe that

Pr[r $ ← R, (pp, T ) ← Setup(1 λ , m; r), T $ ← Dist(r) : Verify(pp, pvk, T , i, x i , π)] = Pr[r $ ← R, (pp, T ) ← Setup(1 λ , m; r) : Verify(pp, pvk, T , i, x i , π)]
by definition of Dist(r). Let us denote p this probability. We can consider two cases:

-Either x i = 1-x i , in which case p ≈ 0 by the binding property of the DVPRG, hence Verify(pp, pvk, T , i, x i , π) = Verify(pp, pvk, T , i, x i , π) = 0 except with negligible probability over the choice of (r, T ).

-Either x i = x i . Assume toward contradiction that Pr     r $ ← R, (pp, T ) ← Setup(1 λ , m; r), T $ ← Dist(r), (pvk, i, x i , π) $ ← A(pp) : Verify(pp, pvk, T , i, x i , π) = Verify(pp, pvk, T , i, x i , π)     ≥ µ,
where we define µ(λ) to be 2ε

← Setup(1 λ , m) : Verify(pp, pvk, T , i, x i , π)] ≥ ε.
As the DVPRG is consistent, this further implies that Pr[(pp, T )

$ ← Setup(1 λ , m) : Verify(pp, pvk, T , i, x i , π)] = 1 -negl(λ). Therefore, Pr     r $ ← R, (pp, T ) ← Setup(1 λ , m; r), T $ ← Dist(pp), (pvk, i, x i , π) $ ← A(pp) : Verify(pp, pvk, T , i, x i , π) = Verify(pp, pvk, T , i, x i , π)     ≈ 0,
contradicting our assumption.

Given Lemma 21, we obtain the following sufficient conditions for a DVPRG to be unbounded binding (repeated from Section 3):

Theorem 22. Let G = (Setup, Stretch, Prove, Verify) be a binding and consistent DVPRG, such that for any r, the distribution Dist(r) is efficiently sampleable. Then G is unbounded binding.

Proof. Let A be a PPT adversary against the unbounded binding of G. We must show that In the real game H 0 , the challenger samples (pp, T ) $ ← Setup(1 λ , m). Let q be the number of calls to Verify(pp, •, T , •, •, •); that is, A interacts (adaptively) with Verify(pp, •, T , •, •, •) for q queries, and outputs a triple (pvk * , i * , π * ). We prove theorem 14 through a sequence of q + 2 hybrids, starting with j = 0.

Hybrid H j . In this game, upon receiving the kth query (pvk, i, b, π) from A, the oracle O j pp,T answers as follows: if k ≤ j, it samples a new trapdoor T k $ ← Dist(pp) and outputs G.Verify(pp, pvk, T k , i, b, π). Otherwise, it outputs Verify(pp, pvk, T , i, b, π).

Claim. For all j ≤ q, games H j and H j+1 are indistinguishable. Assume now that there is a PPT adversary A that can distinguish between the games H j and H j+1 with non-negligible probability. Since the only difference between these hybrids is the answer of the oracle to the (j + 1)th query, it must necessarily hold that the answer of the oracle to the (j +1)th query is different in H j and H j+1 with non-negligible probability. Consider now the following adversary B against the consistency of G: upon receiving pp from the challenger, it runs A on pp. For kth query (pvk, i, b, π) of A from k = 1 to j, it perfectly simulates the behavior of the oracle O j pp,T by sampling a fresh new trapdoor T j and returning G.Verify(pp, pvk, T , i, b, π) (note that by assumption, this sampling procedure is efficient). then, upon receiving the (j + 1)th query (pvk, i, b, π) of A, it outputs (pvk, i, b, π) and aborts the simulation. Note that the simulation never used the actual value of T ; by our assumption, if we now sample T and T j+1 from Dist(r), it must be that G.Verify(pp, pvk, T , i, x i , π) = G.Verify(pp, pvk, T j+1 , i, x i , π) holds with non-negligible probability, contradicting the result of Lemma 21 Hybrid H q+1 . Note that in game H q , the oracle O q pp,T does not use T anymore; rather, it samples new trapdoors consistent with pp to answer every query. In game H q+1 , the challenger will exactly play the game of the (bounded) binding of G. Furthermore, it perfectly simulates all q answers of the oracle O q pp,T by sampling a new trapdoor T k $ ← Dist(r) for each query k (which can be done efficiently by assumption), and answering Verify(pp, pvk, T k , i, b, π). Note that H q and H q+1 are perfectly indistinguishable. By the (bounded) binding property of G, A has negligible probability to win game H q+1 , which concludes the proof.

B Proof of Security for the LWE-Based Construction

We provide a proof of Theorem 19 below: Proof. Completeness. Completeness follows from the correctness of HF and the completeness of Π. Binding. To prove that our scheme satisfies the unbounded binding property from Definition 10, observe that any given pp = pk bind , pvk = (v j ) λ j=1 , and i determine a unique HTDF image v * = Eval out pk bind (G m,i , (v j ) λ j=1 ). By the binding property of HF (when using alternate keys generated by HF.Setup bind ), this means that v * -x i G ∈ L A for at most one value of x i . Consider the extractor Ext that, on input pp, pvk, outputs x = (x 1 , . . . , x m ). Observe that now, any successful forgery (pvk, i, π) in the sense of Definition 10 for a bit 1 -x i directly corresponds to a valid proof Π for a false statement. Hence, unbounded soundness follows from the unbounded adaptive soundness of NIWI. Equivocability. We first describe the SimSetup and Equivocate algorithms. The algorithm SimSetup(1 λ , m) proceeds like Setup(1 λ , m), except that it chooses a non-binding pk through (pk, sk) $ ← HF.Setup(1 λ ), and additionally outputs an equivocation trapdoor T eq = sk.

Equivocate(pp, pvk, i, b, T eq ), first parses its input as pp = (pk, crs), pvk = (v i ) λ i=1 , and T eq = sk, and then samples a preimage u * $ ← Inv sk,b (v * ) of v * = Eval out pk (G m,i , (v j ) λ j=1 ). We note that because of the statistical hiding property of HF, such a preimage exists even when G m,i (s) = b. Since this preimage satisfies f pk,b (u * ) = v * , u * is a witness for a true instance of L A . Equivocate thus computes and outputs a proof π By the dual-mode property of HF, this changes A's success probability only negligibly. We will use the now-available trapdoor T eq = sk generated additionally by SimSetup shortly. D 0.2 uses Equivocate to compute proofs π i $ ← Equivocate(pp, pvk, i, x i , T eq ). Note that we still use the bits x i generated by Stretch. By construction of Equivocate, this change only modifies the witness used to compute the corresponding NIWI proofs π i . Hence, by the witness-indistinguishability of Π, this only changes the distribution of proofs π i in an indistinguishable way. D 0.3 changes the initial commitment pvk = (v i ) i such that each v i is computed as v i = f pk,s i (u i ) (instead of v i = f pk,si (u i )). Observe that the values u i are independently random and are now used only to generate the v i . Hence, the statistical hiding property of HF implies that this change is only statistical. D 1 We now change the values x i that determine what bits are opened from x i = G m,i (s) to independently random bits. Since the seed bits s i are at this point used nowhere else in the game, this change can be justified with the pseudorandomness of G m . The resulting distribution is exactly the distribution from the right-hand side of Definition 11.

←←

  , S, M ) : hb $ ← {0, 1} t , (S, M ) $ ← HB.Prove(hb, x, w)} and {Sim zk (x)} are perfectly indistinguishable; • the distributions {(hb, S, M ) : hb $ ← {0, 1} t , (S, M ) $ ← HB.Prove(hb, x, w)} and {(hb, S, M ) : (hb[S], S, M ) $ Sim zk (x), hb $ Sim zk (hb[S], S, M, x, w)} are perfectly indistinguishable. That is, the simulator can generate (hb[S]

-

  Π.Setup(1 λ ) : on input the security parameter in unary, compute (pp, T ) $ ← G.Setup(1 λ , m(λ)), and ρ $ ← {0, 1} m . Output crs ← (pp, ρ) and T .-Π.Prove(crs, y, w) : parse crs as (pp, ρ). Compute (pvk, x, aux)$ ← G.Stretch(pp). Pick θ $ ← {0, 1} . For i = 1 to m, set hbi ← xi ⊕ ρi ⊕ θ (i-1 mod )+1. Define hb = (hbi)i to be the hidden string of HB . Compute an HB proof (S, M ) $ ← HB .Prove(hb, y, w). For every i ∈ S, compute πi $ ← G.Prove(pp, aux, i). Output (pvk, θ, S, hb[S], M, (πi)i∈S).-Π.Verify(crs, G, π, T ) : parse crs as (pp, ρ) and π as (pvk, θ, S, hb[S], M, (πi)i∈S). For every i ∈ S, set xi ← hbi ⊕ ρi ⊕ θ (i-1 mod )+1 and check that G.Verify(pp, pvk, T , i, xi, πi). Check that HB .Verify(y, hb[S], M ) returns 1. Output 1 if all checks succeeded, and 0 otherwise.

Fig. 2 .

 2 Fig.2. Designated-verifier non-interactive zero-knowledge proof system Π for a language L using a DVPRG G and an HB proof system HB

←

  Setup(1 λ , m), (pvk * , i * , π * ) $ ← A Verify(pp,•,T ,•,•,•) (pp), : Verify(pp, pvk * , T , i * , 1 -x i , π * ) x ← Ext(pvk * )   ≈ 0.

←←

  (pp, T ) ← Setup(1 λ , m; r), T $ ← Dist(r), (pvk, i, x i , π) $ ← A(pp) : Verify(pp, pvk, T , i, x i , π) = Verify(pp, pvk, T , i, x i , π) T ) ← Setup(1 λ , m; r), (T 0 , T 1 ) $ Dist 2 (r), (pvk, i, x i , π) $ ← A(pp) :Verify(pp, pvk, T 0 , i, x i , π) = Verify(pp, pvk, T 1 , i, x i , π) Setup(1 λ , m)} and {(pp, T ) : r $ ← R, (pp, T ) ← Setup(1 λ , m; r), T $ ← Dist(r)} are identical.

$←

  Π.Prove(crs, v * -bG, u * ). We now show indistinguishability of the two distributions from Definition 11. We proceed with a number of intermediate distributions: D 0 is the distribution from the left-hand side of Definition 11:D 0 =    (pp, T ) $ ← Setup(1 λ , m), (pvk, x, aux) $ ← Stretch(pp) π $ ← (Prove(pp, aux, i)) i : (pp, pvk, T , x, π)    D 0.1 uses parameters pp = (pk, crs) generated through SimSetup (instead of through Setup).

  • (1 -ε), with ε being the negligible function guaranteed by the consistency definition (note that since ε is a negligible function, so is µ).

	Then we immediately
	have that
	Pr[(pp, T )

$

A formal argument requires a little care in choosing parameters, and in randomizing hb with an additional component in the NIZK common reference string.

One might wonder why we do not follow another route to obtain VPRGs from NIWI proofs for BDD. Specifically, [Bit17, GHKW17] construct even verifiable random functions from a NIWI for a (complex) LWE-related language. However, these constructions inherently use disjunctions, and it seems unlikely that the corresponding NIWIs can be reduced to the BDD language.

The actual construction of [RSS19] relies on a new notion of public-key encryption with prover-assisted oblivious ciphertext sampling, but the high level idea is comparable to the VPRG-based approach. A side contribution of our construction is that it is conceptually much simpler and straightforward than the construction of [RSS19].

Since n is the order of G and G is a group in which CDH is assumed to hold, 2/n is negligible in the security parameter.

Strictly speaking, this may not be true, depending on Gm: the LWE parameters may depend on the size of the Gm,i, which in turn may depend on m. However, here we implicitly assume that m ≤ 2 λ and a suitable Gm (e.g., one in which Gm,i(s) is of the form Fs(i) for a PRF F : {0, 1} λ → {0, 1}).

Supported by ERC grant "PREP-CRYPTO" (724307). Supported by ERC grant "PREP-CRYPTO" (724307) and DFG project GZ HO 4304/4-2.

1 In the HBM, there exist unconditionally secure NIZK proofs [FLS90].

Supplementary Material

A Sufficient Condition for Unbounded Binding DVPRGs

To simplify the construction of unbounded binding DVPRGs, we introduce a new security notion, the consistency, which provides a simple sufficient condition for satisfying unbounded binding. Informally, the consistency property states that if A can produce a proof which is accepted with non-negligible probability over a random choice of trapdoor (conditioned on being consistent with the public parameters), then this proof must be accepted with overwhelming probability over the choice of T . We prove afterwards that if a DVPRG is binding and consistent, it also satisfies the unbounded binding property. The proof of this implication proceeds by showing that we can replace the verification oracle with T hardcoded by a verification oracle which samples a fresh trapdoor T to answer each query, and that this change will not be noticeable by A since, by the binding property and the consistency of the DVPRG, A has negligible probability to produce a proof that would have been accepted (resp. refused) by the verification with T , but refused (resp. accepted) by the verification with T . Intuitively, the consistency capture the following idea: a DVPRG will satisfy unbounded binding if the verification of a proof does not leak a significant amount of information about the trapdoor, in the sense that a verification with a different trapdoor consistent with the public parameters will return the same result with overwhelming probability.

Definition 20 (Consistency of a DVPRG). Given a DVPRG (Setup, Stretch, Prove, Verify) and a pair (pp, T ) = Setup(1 λ , m; r) for some r, we define for any ε the set ε-Good(r) to be the set of 4-tuple (pvk, i, π, x i ) satisfying

where Dist(r) samples random pairs (pp , T ) with Setup(1 λ , m) subject to the constraint pp = pp, and outputs T . Note that for any ε ≥ ε, it holds that ε -Good(r) ⊂ ε-Good(r). Then, we say that a DVPRG is consistent if there exists a negligible function ε such that for any PPT adversary A,

The following lemma will prove useful in the analysis:

Lemma 21. Let (Setup, Stretch, Prove, Verify) be a binding and consistent DVPRG scheme, with random space R for Setup. Then, it holds that

Proof. By the binding property of the DVPRG, we have for any PPT A

By the binding property of the DVPRG, it must be (except with negligible probability) that Verify(pp, pvk, T , i, 1-x i , π) = 0. But then, since A is only given pp, it must hold that Verify(pp, pvk, T , i, 1-x i , π) = 1 happens with non-negligible probability for any trapdoor T consistent with pp; that is, there exists a string x = x 1 • • • x m such that Pr T $ ← Dist(r) : Verify(pp, pvk, T , i, 1 -x i , π) = 1 ≈ 0.