Benoît Libert
email: benoit.libert@ens-lyon.fr.

Alain Passelègue
email: alain.passelegue@inria.fr.

Hoeteck Wee
email: wee@di.ens.fr.

David J Wu

New Constructions of Statistical NIZKs: Dual-Mode DV-NIZKs and More

Non-interactive zero-knowledge proofs (NIZKs) are important primitives in cryptography. A major challenge since the early works on NIZKs has been to construct NIZKs with a statistical zero-knowledge guarantee against unbounded verifiers. In the common reference string (CRS) model, such "statistical NIZK arguments" are currently known from k-Lin in a pairing-group and from LWE. In the (reusable) designated-verifier model (DV-NIZK), where a trusted setup algorithm generates a reusable verification key for checking proofs, we also have a construction from DCR. If we relax our requirements to computational zero-knowledge, we additionally have NIZKs from factoring and CDH in a pairing group in the CRS model, and from nearly all assumptions that imply public-key encryption (e.g., CDH, LPN, LWE) in the designated-verifier model. Thus, there still remains a gap in our understanding of statistical NIZKs in both the CRS and the designated-verifier models.

In this work, we develop new techniques for constructing statistical NIZK arguments. First, we construct statistical DV-NIZK arguments from the k-Lin assumption in pairing-free groups, the QR assumption, and the DCR assumption. These are the first constructions in pairing-free groups and from QR that satisfy statistical zero-knowledge. All of our constructions are secure even if the verification key is chosen maliciously (i.e., they are "malicious-designated-verifier" NIZKs), and moreover, they satisfy a "dual-mode" property where the CRS can be sampled from two computationally indistinguishable distributions: one distribution yields statistical DV-NIZK arguments while the other yields computational DV-NIZK proofs. We then show how to adapt our k-Lin construction in a pairing group to obtain new publicly-verifiable statistical NIZK arguments from pairings with a qualitatively weaker assumption than existing constructions of pairing-based statistical NIZKs.

Our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS). While the FLS framework has traditionally been used to construct computational (DV)-NIZK proofs, we newly show that the same framework can be leveraged to construct dual-mode (DV)-NIZKs.

Introduction

Non-interactive zero-knowledge (NIZK) proofs [START_REF] Blum | Non-interactive zero-knowledge and its applications[END_REF][START_REF] Goldwasser | The knowledge complexity of interactive proof systems[END_REF] allow a prover to send a single message to convince a verifier that a statement is true without revealing anything beyond this fact. Although such NIZKs cannot exist in the plain model, they can be realized in the common reference string (CRS) model, where a trusted party generates and publishes a common reference string accessible to the prover and the verifier. Shortly after the introduction of NIZKs, numerous constructions have been developed in the CRS model from many classes of cryptographic assumptions such as factoring [BFM88, DMP87, FLS90, BY92, FLS99, DDO + 01, Gro10, Gol11, GR13, CL18], pairing-based assumptions [START_REF] Canetti | A forward-secure public-key encryption scheme[END_REF][START_REF] Groth | Perfect non-interactive zero knowledge for NP[END_REF], and lattice-based assumptions [CCH + 19, PS19]. We can also construct NIZKs in the random oracle model [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF].

A major open problem since the early works on non-interactive zero-knowledge has been to construct NIZKs with a statistical zero-knowledge guarantee against computationally-unbounded verifiers (i.e., "statistical NIZK arguments"). Here, we only have constructions from the k-Lin family of assumptions over pairing groups [START_REF] Groth | Perfect non-interactive zero knowledge for NP[END_REF][START_REF] Groth | New techniques for noninteractive zero-knowledge[END_REF] and LWE [START_REF] Peikert | Noninteractive zero knowledge for NP from (plain) learning with errors[END_REF] (or circular-secure FHE [CCH + 19]). If we relax the model and consider (reusable) designated-verifier NIZKs (DV-NIZKs), where the trusted party that generates the CRS also generates a secret verification key that is used to verify proofs, then the recent work of Chase et al. [CDI + 19] provides an instantiation of a statistical DV-NIZK from the DCR assumption. In contrast, if we are satisfied with computational zero-knowledge, then we can additionally construct publicly-verifiable NIZKs in the CRS model from QR [START_REF] Blum | Non-interactive zero-knowledge and its applications[END_REF], factoring [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF], and the CDH assumption over a pairing group [START_REF] Canetti | A forward-secure public-key encryption scheme[END_REF]. In the designated-verifier model, a recent line of works [QRW19, CH19, KNYY19a, KNYY19b, LQR + 19] has provided constructions of computational DV-NIZKs from essentially all cryptographic assumptions known to imply public-key encryption. These include assumptions like CDH in a pairing-free group and LPN. Thus, there is still a gap in our understanding of statistical NIZKs in the CRS model, and especially in the designated-verifier model. In this work, we develop new techniques for constructing statistical NIZKs in both the standard CRS model as well as the (reusable) designated-verifier model, which we review below.

Reusable designated-verifier NIZKs. A key focus in this work is the designated-verifier model [START_REF] Pass | Construction of a non-malleable encryption scheme from any semantically secure one[END_REF][START_REF] Damgård | Non-interactive zero-knowledge from homomorphic encryption[END_REF], where a trusted party generates the CRS together with a secret verification key that is used to verify proofs. In this work, we focus exclusively on reusable (i.e., multitheorem) security where soundness holds even against a prover who has oracle access to the verification algorithm. We also consider the stronger malicious-designated-verifier model (MDV-NIZKs) introduced by Quach et al. [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF], where a trusted party only samples a common reference string,1 and the verifier is allowed to choose its public and secret key-pair, which is used to generate and verify proofs, respectively. Here, we require that zero-knowledge should hold even if the verifier samples its public key maliciously. As discussed in [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF], MDV-NIZKs are equivalent to 2-round zero-knowledge protocols in the CRS model where the verifier's initial message is reusable. A recent line of works have shown how to construct (M)DV-NIZKs with computational zero-knowledge from nearly all assumptions known to imply public-key encryption (e.g., CDH, LWE, LPN) [QRW19, CH19, KNYY19a, KNYY19b, LQR + 19].

Several recent works have also explored other relaxations of the standard notion of publiclyverifiable NIZKs such as the reusable designated-prover model (where there is a secret proving key and a public verification key) [START_REF] Kim | Multi-theorem preprocessing NIZKs from lattices[END_REF][START_REF] Katsumata | Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions[END_REF] or the reusable preprocessing model (where both the proving and verifications keys are secret) [BCGI18, BCG + 19]. In this work, our focus is on reusable designated-verifier NIZKs and publicly-verifiable NIZKs.

Dual-mode NIZKs. An appealing feature of several existing NIZK constructions [GOS06, [START_REF] Groth | New techniques for noninteractive zero-knowledge[END_REF][START_REF] Peikert | Noninteractive zero knowledge for NP from (plain) learning with errors[END_REF] is they satisfy a "dual-mode" property. Namely, the CRS in these schemes can be sampled from one of two computationally indistinguishable distributions. One distribution yields computational NIZK proofs while the other yields statistical NIZK arguments. Dual-mode NIZKs are powerful primitives and a recent work has also studied generic constructions from obfuscation [START_REF] Hofheinz | Dual-mode NIZKs from obfuscation[END_REF]. Most of the constructions we develop in this work naturally satisfy this dual-mode property.

Our Results

In this work, we develop new techniques for constructing statistical NIZKs for general NP languages that yield new constructions in both the reusable designated-verifier model and the standard CRS model. Our techniques enable the following new constructions:

• Under the k-Lin assumption in a pairing-free group (for any k ≥ 1; recall that 1-Lin ≡ DDH),

we obtain a statistical MDV-NIZK argument in the common random string model and a computational MDV-NIZK proof in the common reference string model.2 This is the first construction of a statistical DV-NIZK argument (even ignoring malicious security) in a pairing-free group, and the first construction of a computational MDV-NIZK proof from a static assumption. Previously, computational MDV-NIZK proofs were only known from the interactive "one-more CDH" assumption [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF].

• Under the k-Lin assumption in G 1 and the k-KerLin assumption in G 2 of a pairing group (for any k ≥ 1), we obtain a publicly-verifiable statistical NIZK argument in the common reference string model. Notably, the k-KerLin assumption is a search assumption that is implied by the standard k-Lin assumption [START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF][START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF]. This is a qualitatively weaker assumption than existing pairing-based constructions of statistical NIZK arguments which rely on a decisional assumption (k-Lin) in both G 1 and G 2 [START_REF] Groth | Perfect non-interactive zero knowledge for NP[END_REF][START_REF] Groth | New techniques for noninteractive zero-knowledge[END_REF].

• Under the QR assumption, we obtain a dual-mode MDV-NIZK in the common reference string model. Previously, we could only construct (publicly-verifiable) computational NIZKs from the QR assumption [START_REF] Blum | Non-interactive zero-knowledge and its applications[END_REF] (or more generally, from factoring [START_REF] Feige | Multiple non-interactive zero knowledge proofs based on a single random string[END_REF][START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF]), but nothing was known for statistical NIZKs or DV-NIZKs from these assumptions.

• Under the DCR assumption, we obtain a dual-mode MDV-NIZK in the common reference string model. This matches the recent construction described in [CDI + 19], which realizes the result through a different approach (via reusable non-interactive secure computation).

We provide a detailed comparison of our constructions with existing NIZK constructions (in both the designated-verifier and the publicly-verifiable models) in Table 1. We describe the formal instantiations in Section 6. 1: Comparison of our construction to existing multi-theorem NIZKs. We write "public" to denote the standard CRS model (with public proving and public verification), "DV" to denote the designated-verifier model, and "MDV" to denote the malicious-designated-verifier model. For soundness and zero-knowledge, we write "comp." to denote the computational variant of the property, "stat." to denote the statistical variant, and "perf." to denote the perfect variant. When a scheme supports a dual-mode CRS, we indicate the two modes by writing "stat./comp." For the pairing-based constructions, we list the necessary assumptions needed within each of the base groups G 1 and G 2 (assuming an asymmetric pairing).

From FLS to statistical NIZKs. All of our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS) [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] who provide a general compiler from a NIZK in an idealized model (i.e., the "hidden-bits" model) to a computational NIZK proof in the CRS model. To date, all existing instantiations of the [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] paradigm have yielded computational NIZK proofs in either the CRS model [FLS90, BY92, FLS99, CHK03, Gro10, Gol11, GR13, CL18] or the designated-verifier model [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF][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]. In this work, we show how to adapt the general FLS paradigm to obtain new constructions of statistical NIZK arguments and more generally, dual-mode NIZKs.

We provide a general overview of our techniques in Section 1.2. We further note that previous statistical NIZK arguments from pairings, LWE, and DCR follow very different approaches. Our work can also be viewed as providing a unified approach to realizing these existing results-both computational and statistical, with the sole exception of the LWE-based scheme-via the FLS paradigm, while also improving upon some of these prior results, and obtaining new ones.

Technical Overview

We begin with a brief overview of the Feige-Lapidot-Shamir (FLS) framework [START_REF] Feige | Multiple non-interactive zero knowledge proofs based on a single random string[END_REF][START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] for constructing NIZK proofs for NP. We then describe how to adapt the main ideas from the FLS framework to obtain new constructions of (malicious) designated-verifier dual-mode NIZKs as well as publicly-verifiable statistical NIZK arguments.

The FLS framework. The starting point of the FLS construction is a NIZK in an idealized model called the "hidden-bits model." In this model, a trusted party generates a string of uniformly random bits r 1 , . . . , r ρ ∈ {0, 1} and gives them to the prover. The prover then outputs a proof π along with a set of indices I ⊆ [ρ]. The verifier receives (π, {r i } i∈I ) from the trusted party. The model guarantees that the prover cannot influence the value of any of the r i 's and the verifier does not learn anything about r i for indices i / ∈ I. Feige et al. [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] showed how to construct a NIZK with statistical soundness and perfect zero-knowledge in the hidden-bits model by adapting Blum's Σ-protocol for graph Hamiltonicity [START_REF] Blum | How to prove a theorem so no one else can claim it[END_REF]. Next, the FLS construction compiles a NIZK in the hidden-bits model into one in the CRS model by using the CRS to define the sequence of hidden bits. We recall the FLS compiler based on trapdoor permutations:

• The CRS contains the description of a family of trapdoor permutations over {0, 1} λ together with ρ random strings w 1 , . . . , w ρ ∈ {0, 1} λ that are used to define a string of ρ hidden bits.

• A hidden-bits string is defined by sampling a permutation σ from the family of trapdoor permutations specified by the CRS, along with a trapdoor for computing σ -1 . In conjunction with w i in the CRS, the permutation σ defines a hidden bit r i := hc(σ -1 (w i )), where hc(•) is a hard-core bit of σ. We refer to σ as a "commitment" to the hidden-bits string r ∈ {0, 1} ρ .

•

The prover can open a commitment σ to a bit r i by sending (i, r i , u i ) where u i := σ -1 (w i ).

The verifier checks that σ(u i ) = w i and that hc(u i ) = r i .

The security argument proceeds roughly as follows:

• Since hc is a hard-core bit, the value of any unopened bit r i is computationally hidden given σ and w i . The resulting NIZK satisfies computational zero-knowledge.

• The permutation σ and the string w i statistically determine r i , and the prover cannot open r i to any value other than hc(σ -1 (w i )). The resulting NIZK satisfies statistical soundness. Note that a cheating prover can bias the bit r i due to the adaptive choice of σ. The FLS construction works around this by leveraging the fact that if the commitment σ has length , then a malicious prover can bias at most of the ρ bits, and soundness holds as long as ρ.

Our approach. In this work, we start by showing how to realize a dual-mode variant of the hidden-bits model in the designated-verifier setting where the underlying commitment to the random bits is either statistically binding or statistically hiding. This "dual-mode" property yields either a computational DV-NIZK proof or a statistical DV-NIZK argument depending on how the CRS is sampled (similar to previous dual-mode NIZKs [GOS06, GOS12, PS19]). We then show how to extend one of our constructions to the publicly-verifiable setting.

An instantiation from DDH. We first sketch our construction from the DDH assumption. Here, we will work with a (multiplicative) group G of prime order p and generator g. For a vector v = (v 1 , . . . , v n ) ∈ Z n p , we write g v to denote a vector of group elements (g v 1 , . . . , g vn ). Analogous to the FLS construction from trapdoor permutations, the CRS contains

• the description g v of a function, where v r ← Z ρ+1 p and g v plays a role similar to the family of trapdoor permutations in the FLS construction;

• g w 1 , . . . , g wρ where each w i ∈ Z ρ+1 p plays a role similar to w i ∈ {0, 1} λ .

In our construction, we will vary the distribution of w i (but not v) as follows:

• If we want statistically-binding "hidden bits," then we sample w i ← s i v, where s i r ← Z p .

• If we want statistically-hiding "hidden bits," then we sample w i r ← Z ρ+1 p .

Thanks to the DDH assumption, (g v , g s i v ) is pseudorandom, and therefore, these two CRS distributions are computationally indistinguishable. 3 As with the construction from trapdoor permutations, the hidden bit r i is a function of the CRS components g v , g w i together with an additional message σ from the prover. Concretely, the prover samples a random y r ← Z ρ+1 p and sends σ = g y T v ∈ G. In conjunction with g w i in the CRS, the vector y defines a hidden bit r i := H(g y T w i ), where H : G → {0, 1} is a universal hash function. Importantly, while the description g v , g w 1 , . . . , g wρ in the CRS grows with ρ, the prover's message σ does not. Now, observe that:

• In binding mode where w i = s i v, we have y T w i = s i y T v. Then, r i = H(g y T w i ) = H(g s i y T v ) = H(σ s i ) is fully determined by the commitment σ = g y T v together with g v , g w i in the CRS.

• In hiding mode where w i r ← Z ρ+1 p , the quantity g y T w i is completely hidden given g y T v along with g v , g w i in the CRS, provided that v and w i are linearly independent. More generally, perfect hiding holds as long as the vectors v, w 1 , . . . , w ρ are linearly independent over Z ρ+1 p .

Next, to open the bit r i , the prover will send along g y T w i . To ensure that a cheating prover computes this quantity correctly in the designated-verifier model, we rely on techniques using the Cramer-Shoup hash-proof system [CS98, CS02, CKS08] (and also used to construct computational DV-NIZK proofs from CDH [QRW19, CH19, KNYY19a]):

• The verifier's public key consists of components g z i := g aw i +b i v where a, b i r ← Z p are secret coefficients chosen by the verifier. The secret verification key is the scalars (a, b 1 , . . . , b ρ ).

• The prover sends

g u i := g y T z i ∈ G in addition to σ = g c := g y T v ∈ G and g t i := g y T w i ∈ G.
• The verifier checks that

g u i = (g t i ) a (g c ) b i using (a, b i ).
In the statistically-binding mode where w i = s i v, we have z i = (as i + b i )v, so (a, b i ) has (statistical) entropy given v, w i , z i . Roughly speaking, reusable soundness then follows from the analysis of the Cramer-Shoup CCA-secure encryption scheme [CS98, CS02, CKS08] to enforce the consistency check t i = s i c. In conjunction with a NIZK in the hidden-bits model, we thus obtain a dual-mode DV-NIZK from the DDH assumption. This construction generalizes very naturally to the k-Lin family of assumptions [BBS04, HK07, Sha07, EHK + 13] for any k ≥ 1 (where in particular, 1-Lin is the DDH assumption). Concretely, we make the following substitutions to the above construction:

v ∈ Z ρ+1 p → V ∈ Z (ρ+1)×k p s i , b i ∈ Z p → s i , b i ∈ Z k p t i , u i , c ∈ Z p → t i , u i , c ∈ Z k p
We provide the full details and security analysis in Section 4.1.

Extending to QR/DCR. Our DDH construction readily generalizes to the subgroup indistinguishability family of assumptions [START_REF] Brakerski | Circular and leakage resilient public-key encryption under subgroup indistinguishability -(or: Quadratic residuosity strikes back)[END_REF] (which generalize the QR [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF] and DCR [Pai99] assumptions). While there are some technical differences in our concrete instantiations from QR (Section 5) and DCR (Appendix E), all of the main ideas can be described via the conceptually-simpler language of subgroup indistinguishability. This is the approach we take in this overview, and we refer to the technical sections for the full details. First, the subgroup indistinguishability assumption says that the distributions (g, h, g r 1 ) and (g, h, g r 1 h r 2 ) are computationally indistinguishable, where g, h generate subgroups of co-prime order m g , m h , respectively, and r 1 r ← Z mg , r 2 r ← Z m h . Similar to the DDH instantiation, the CRS contains a function g v (where v r ← Z ρ mgm h ) together with additional components g s 1 v h ŵ1 , . . . , g sρv h ŵρ , where ŵi = 0 in binding mode and ŵi = e i in hiding mode. Here e i is the basis vector whose i th index is 1. Under the subgroup indistinguishability assumption, these two distributions are computationally indistinguishable.

Next, the hidden bit r i is a function of the CRS components g v and g s i v h ŵi together with an additional commitment σ from the prover. Specifically, the prover samples a vector y = (y 1 , . . . , y ρ ) r ← Z ρ mgm h and computes σ := g y T v and t i := g s i y T v h y T ŵi and r

i := H(t i ), (1.1)
where H is a hash function. Now, observe that:

• In binding mode where ŵi = 0, then t i = g s i y T v = σ s i . Thus, t i (and correspondingly, r i ) is fully determined by the commitment σ and the components g v , g s i v h ŵi = g s i v in the CRS.

• In hiding mode where ŵi = e i , then t i = g s i w T y h y i . Since g and h generate subgroups of co-prime order m g and m h , respectively, we can appeal to the Chinese remainder theorem to argue that the commitment σ = g y T v perfectly hides the value of y mod m h . Since y is uniform over Z mgm h , this means that t 1 , . . . , t i have at least log m h bits of statistical entropy given σ (and the components of the CRS).

In the DCR construction, m h = N is a product of two large primes, so we can use a standard universal hash function to extract a uniformly random bit [START_REF] Håstad | A pseudorandom generator from any one-way function[END_REF].

In the QR construction, m h = 2, so each component t i contains just one bit of entropy, and we cannot appeal to the leftover hash lemma. In this case, we adapt an idea from [DGI + 19] (for constructing trapdoor hash functions from QR) and use a deterministic function to extract the bit from t i . We provide the full details in Section 5.

Finally, to open a bit r i , the prover provides σ, t i , along with a proof that t i and σ are consistent (i.e., there exists some y such that Eq. (1.1) hold). Here, we use the same techniques as in the DDH setting (i.e., using the Cramer-Shoup hash-proof system) to implement this. In the QR setting, we encounter some challenges because the order of the subgroup generated by h is polynomial-sized, which allows the adversary to break soundness with noticeable probability. To amplify soundness, we essentially embed multiple copies of the Cramer-Shoup hash-proof system and ensure that the proof verifies only if all copies verify (while retaining reusable soundness). We refer to Section 5 and Appendix E for the full analysis of the QR and DCR constructions, respectively.

Handling malicious verifiers. All of the constructions described thus far are zero-knowledge only if the verifier samples its public verification key honestly. However, if the verifier can choose its key arbitrarily, then it can break zero-knowledge. To see this, consider again the DDH construction (in hiding mode). There, the CRS contains elements g v , g w 1 , . . . , g wρ , and a verifier's public key is (g z 1 , . . . , g zρ ) where

z i = aw i + b i v.
To generate a hidden-bits string r, the prover samples y r ← Z ρ+1 p and sets r i = H(g y T w i ). To open a bit r i , the prover computes g t i = g y T w i and g u i = g y T z i . In order to appeal to security of the underlying NIZK in the hidden-bits model, we require that the commitment σ = g y T v , the value of r i , and the opening (g t i , g u i ) do not leak information about any other (unopened) bit r j . This is the case when all of the verification key components z i are generated honestly. In this case, v, w 1 , . . . , w ρ are linearly independent, and z i is a function of only v and w i . However, a malicious verifier can choose z i = w j for some j = i. Then, if the honest prover computes an opening to r i , it will also compute g u i = g y T z i = g y T w j , which completely leaks the value of r j . As such, the basic scheme is insecure against a malicious verifier. This problem where an opening to r i can leak information about the value r j for j = i is the same problem encountered in the basic DV-NIZK from [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF]. In this work, we adopt the same general strategy as them to defend against malicious verifiers. At a high-level, the approach of [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] for achieving security against malicious verifiers is to use the basic scheme above to generate a hidden-bits string r 1 , . . . , r of length ρ. Each of the ρ hidden bits r 1 , . . . , r ρ is then derived as a sparse pseudorandom combination of the bits r 1 , . . . , r . More specifically, the prover chooses a mapping ϕ that maps each index i ∈ [ρ] onto a set ϕ(i) ⊆ [ ]. Each bit r i is a deterministic function of r j for j ∈ ϕ(i). To open a bit r i , the prover instead opens up all bits r j for j ∈ ϕ(i). The length and the size |ϕ(i)| of the sets are chosen so as to ensure that for all unopened bits j ∈ [ρ], there is at least one index k ∈ ϕ(j) such that r k is hidden from the verifier, which ideally, is sufficient to mask the value of r j . Quach et al. show how to implement this idea by relying on a one-more CDH assumption (in conjunction with somewhere equivocal PRFs [HJO + 16]), and a complex rewinding argument in the security proof. In our setting, the algebraic structure of our construction enables us to make a conceptually-simpler information-theoretic argument (and only needing to assume a PRG). As such, we are able to obtain a dual-mode MDV-NIZK from the DDH (and more generally, k-Lin)as well as the QR and DCR assumptions.

We give a brief overview of how we extend the basic DDH construction sketched above to achieve security against malicious verifiers. The same idea extends to the QR and DCR constructions. Specifically, we use our basic construction to generate a hidden-bits string of length ρ as follows:

• The CRS (in hiding mode) consists of group elements g v , g w 1 , . . . , g w , where v, w 1 , . . . , w r ← Z +1

p . With overwhelming probability, these vectors are linearly independent.

• The honest verifier's public key is (g z 1 , . . . , g z ), constructed in the usual manner.

• The prover's commitment is a vector y ∈ Z +1 p as well as a seed s for a PRG. 4 The PRG outputs a collection of ρ blocks, where each block consists of a set S i ⊆ [ ] and a vector α ∈ Z p . The hidden bit r i is determined by first computing g t j = g y T w j for all j ∈ S i and defining r i := H( j∈S i g α j t j ).

• The opening for r i consists of g t j = g y T w j and g u j = g y T z j for all j ∈ S i .

Our goal is to show that even for an adversarially-chosen verification key, the commitment σ and the opening ({g t j , g u j } j∈S i ) to a bit r i does not leak any information about r j whenever j = i. 5 By construction, the opening to r i is determined by y T v, y T w j , and y T z j for j ∈ S i (where the set S i is pseudorandom). Take any index i * = i. Then, if there exists j * ∈ ϕ(i * ) such that w j * is linearly independent of {v, w j , z j } j∈S i , then the value of y T w j * is independent and uniformly random given the view of the adversary (since the honest prover samples y r ← Z +1 p ). In this case, the value g t j * = g y T w j * remains uniformly random and statistically hides r i * . Thus, it suffices to set and |S i | so that there will always exist j * ∈ ϕ(i * ) where w j * is linearly independent of {v, w j , z j } j∈S i with overwhelming probability. In the case of our DDH construction, we can set |S i | = λ, where λ is a security parameter, and = 3ρ 2 λ to satisfy this property. We provide the full analysis of our DDH (more generally, its generalization to the k-Lin assumption) in Section 4.3, our QR construction in Section 5.2 and our DCR construction in Appendix E.2.

Public verifiability via pairings. All of the constructions we have described so far operate in the designated-verifier model because our constructions rely on a Cramer-Shoup-style hash proof system to argue consistency between a commitment and the opening. If we can instead publicly check consistency between a commitment and its opening, then the resulting scheme becomes publicly verifiable. For the DDH construction, we can implement the consistency check using a pairing (this is the approach taken in [START_REF] Canetti | A forward-secure public-key encryption scheme[END_REF] to obtain a computational NIZK proof). In this work, we develop a similar approach to obtain a statistical NIZK argument from pairings.

In particular, let e : G 1 ×G 2 → G T be an (asymmetric) pairing. Let g 1 , g 2 be generators of G 1 and G 2 , respectively. At a high level, we implement the DDH scheme in G 1 and use G 2 for verification. More specifically, the CRS is g v 1 , g w 1 1 , . . . , g wρ 1 , and the verification key is g

(aw 1 +b 1 v) 1 , . . . , g (awρ+bρv) 1
. The commitment, hidden-bits sequence, and openings are defined as before:

σ = g c 1 = g y T v 1 , r i = H(g y T w i 1 ) , g t i 1 = g y T w i 1 and g u i 1 = g y T (aw i +b i v) 1 .
In the designated-verifier setting, the verifier checks g u i 1 ?

= (g t i 1 ) a (g c 1 ) b i . A direct approach for public verification is to include g a 2 , g b 1 2 , . . . , g bρ 2 as part of the verification key, and check the following:

e(g u i 1 , g 2 ) ? = e(g t i 1 , g a 2 ) • e(g c 1 , g b i 2
). While this approach is correct, it is unclear to argue soundness (even against computationallybounded adversaries). In the designated-verifier setting, the soundness analysis critically relies on the verification coefficients a, b i being hidden from the adversary, and it is unclear how to make such an argument when the adversary is given g a 2 , g b i 2 . To base hardness on a concrete cryptographic assumption, we leverage a technique from [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF], who describe a general method to "securely publish" the verification key in the exponent (as we hoped to do in our initial attempt above) with a concrete security reduction to a search assumption in G 2 . This yields a general compiler from a designated-verifier scheme with unconditional soundness to a publicly-verifiable scheme with computational soundness, at the expense of requiring a pairing and a search assumption in G 2 . The compiler preserves zero-knowledge of the underlying scheme.

Concretely, instead of scalar verification coefficients a, b i , we instead sample vectors a, b i r ← Z 2 p , and publish g

w i a T +vb T i 1 for each i ∈ [ρ] in the CRS. The public verification components will consist of g d 2 , g a T d 2 , g b T 1 d 2 , . . . , g b T ρ d 2 , where d ∈ Z 2 p .
The key observation is that a, b 1 , . . . , b ρ have statistical entropy even given the public components

g d 2 , g a T d 2 , g b T 1 d 2 , . . . , g b T ρ d 2
. The commitment, hidden-bits sequence, and openings are still computed as before, except the verification component g u i 1 is replaced with g

u T i 1 = g y T (w i a T +vb T i ) 1
. The verification relation now checks e(g

u T i 1 , g d 2 ) ? = e(g t i 1 , g a T d 2 ) • e(g c 1 , g b T i d 2 ).
Since the verification coefficients a, b 1 , . . . , b ρ have statistical entropy given the public key, we can appeal to DDH in G 1 and the 1-KerLin assumption (a search assumption that is weaker than DDH) over G 2 to argue soundness of the resulting construction. This yields a publicly-verifiable statistical NIZK argument in the common reference string model. We provide the full description and analysis (generalized to the k-Lin and k-KerLin family of assumptions for any k ≥ 1) in Section 4.2.

Our pairing-based construction does not appear to have a dual mode and it is unclear how to modify this construction to obtain computational NIZK proofs. We do note that computational NIZK proofs can be built directly from pairings (under the CDH assumption in G 1 ) also by following the FLS paradigm [START_REF] Canetti | A forward-secure public-key encryption scheme[END_REF]. At the same time, it is also unclear how to adapt the [START_REF] Canetti | A forward-secure public-key encryption scheme[END_REF] construction to obtain statistical NIZK arguments.

A unifying abstraction: dual-mode hidden-bits generators. We unify the different algebraic constructions through the abstraction of a "dual-mode hidden-bits generator." Previously, Quach et al. [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] introduced the notion of a hidden-bits generator (HBG) and showed how to use an HBG to implement the classic FLS paradigm in both the designated-verifier and the publicly-verifiable settings. Very briefly, an HBG with output size ρ consists of four main algorithms (Setup, KeyGen, GenBits, Verify):

• The Setup algorithm outputs a common reference string crs, and KeyGen generates a public key pk along with a (possibly secret) verification key sk.

• The GenBits algorithm outputs a short commitment σ together with a sequence of hidden bits r ∈ {0, 1} ρ as well as openings {π i } i∈[ρ] .

• The Verify algorithm takes an index i ∈ [ρ], a bit r i ∈ {0, 1}, and an opening π i and either accepts or rejects the proof.

The main security requirements are statistical binding (i.e., no adversary can produce a commitment σ and valid openings π i , π i that open to 0 and 1 for the same index) and computational hiding (i.e., an honestly-generated commitment σ and set of openings {r i , π i } i∈I should hide all unopened bits r j for j / ∈ I from any computationally-bounded adversary). Quach et al. show that an HBG with these properties can be combined directly with a NIZK in the hidden-bits model to obtain a computational NIZK proof in the CRS model. If the HBG is in the (malicious) designated-verifier model, then so is the resulting NIZK.

In this work, we extend this framework by introducing the notion of a dual-mode HBG where the CRS can be generated in one of two modes: a binding mode where the HBG satisfies statistical binding (as in [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF]) and a hiding mode where the HBG satisfies a stronger notion of statistical hiding (i.e., the unopened bits are statistically hidden given the CRS, the commitment σ and any subset of opened bits {(r i , π i )} i∈I ). In our case, we impose an even stronger equivocation property in the hiding mode: namely, given any any set of indices I ⊆ [ρ] and any assignment r I ∈ {0, 1} |I| to that set, it is possible to simulate a commitment σ and a set of openings {π i } i∈I that is statistically indistinguishable from the output of the honest generator. This allows us to directly argue adaptive and multi-theorem6 statistical zero-knowledge for the resulting NIZK construction. We give our formal definition in Section 3, and describe our construction of dual-mode (designated-verifier) NIZKs from dual-mode (designated-verifier) HBGs in Section 3.1. In Section 4 and Section 5 and Appendix E, we show how to construct dual-mode HBGs from the k-Lin, QR, and DCR assumptions.

Preliminaries

Throughout this work, we write λ (oftentimes implicitly) to denote the security parameter. For a positive integer n ∈ N, we write [n] to denote the set {1, . . . , n}. We will typically use bold lowercase letters (e.g., v, w) to denote vectors and bold uppercase letters (e.g., A, B) to denote matrices. For a vector v ∈ Z n p , we will use non-boldface letters to refer to its components; namely, we write v = (v 1 , . . . , v n ). For a (sorted) set of indices I = {i 1 , . . . , i m } ⊆ [n], we write v I to denote the sub-vector (v i 1 , . . . , v im ). For a matrix A, we write span(A) to denote the vector space spanned by the columns of A.

We say that a function f is negligible in λ, denoted negl(λ), if f (λ) = o(1/λ c ) for all c ∈ N. We write poly(λ) to denote a function bounded by a fixed polynomial in λ. We say an event happens with negligible probability if the probability of the event happening is negligible, and that it happens with overwhelming probability if its complement occurs with negligible probability. We say that an algorithm is efficient if it runs in probabilistic polynomial-time in the length of its inputs. We say that two families of distributions D 1 = {D 1,λ } λ∈N and D 2 = {D 2,λ } λ∈N are computationally indistinguishable if no efficient adversary can distinguish samples from D 1 and D 2 except with negligible probability, and we denote this by writing D 1 c ≈ D 2 . For two distributions D 1 , D 2 , we write ∆(D 1 , D 2 ) to denote the statistical distance between D 1 and D 2 . We write D 1 s ≈ D 2 to denote that D 1 and D 2 are statistically indistinguishable: namely, that ∆(D 1 , D 2 ) = negl(λ). For a finite set S, we write x r ← S to denote that x is sampled uniformly at random from S. For a distribution D, we write x ← D to denote that x is sampled from D. We now recall the definition of a pseudorandom generator (PRG).

Definition 2.1 (Pseudorandom Generator). A pseudorandom generator (PRG) with seed length κ = κ(λ) and output length = (λ) is an efficiently-computable function G : {0, 1} κ → {0, 1} with the property that for all efficient adversaries A,

Pr[s r ← {0, 1} κ : A(G(s)) = 1] -Pr[t r ← {0, 1} : A(t) = 1] = negl(λ).

Hash Functions and Randomness Extraction

We now recall the leftover hash lemma [START_REF] Håstad | A pseudorandom generator from any one-way function[END_REF] and some properties of hash functions.

Definition 2.2 (Uniformity of Hash Functions). A family of hash functions

H = {H : X → Y} satisfies statistical uniformity if {H r ← H, x r ← X : (H, H(x))} s ≈ {H r ← H, y r ← Y : (H, y)}.
When the two distributions above are identically distributed, then H satisfies perfect uniformity.

Definition 2.3 (Universal Hash Function). A family of hash functions

H = {H : X → {0, 1} } is universal if for any x 1 = x 2 ∈ X , we have that Pr[H r ← H : H(x 1 ) = H(x 2 )] ≤ 1/2 .
Lemma 2.4 (Leftover Hash Lemma [START_REF] Håstad | A pseudorandom generator from any one-way function[END_REF]). Let H = {H : X → {0, 1} } be a universal family of hash functions. Take any ε > 0 and let D be a distribution over X with min-entropy H ∞ (D) ≥ + 2 log(1/ε). Then, ∆((H, H(x)), (H, U )) = ε, where H We also need a variant of the leftover hash lemma that allows extracting randomness from sources that may be correlated with the seed. We use the following lemma from [YYHK16]: Lemma 2.6 (Randomness Extraction from Seed-Dependent Sources [START_REF] Yamakawa | Adversary-dependent lossy trapdoor function from hardness of factoring semi-smooth RSA subgroup moduli[END_REF]). Let H = {H : X → {0, 1} } be a family of pairwise-independent hash functions. Take any ε > 0 and let D = {D i :

H ∞ (D i ) ≥ + 2 log(1/ε)} i∈[M ]
be a collection of distributions D i over X where each D i has minentropy at least + 2 log(1/ε). Then, for all algorithms A that takes as input a hash function H ∈ H and outputs an index i ∈

[M ], ∆((H, H(x)), (H, U )) ≤ |D| ε = M ε, where H r ← H, i r ← A(H), x ← D i , and U r ← {0, 1} .

NIZKs in the Hidden-Bits Model

In this section, we recall the notion of a NIZK in the hidden-bits model [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF]. Our presentation is adapted from the description from [QRW19, CH19, KNYY19a].

Definition 2.7 (NIZKs in the Hidden-Bits Model). Let L ⊆ {0, 1} n be an NP language associated with an NP relation R with n = n(λ). A non-interactive zero-knowledge proof in the hidden-bits model for L consists of a tuple Π HBM = (Prove, Verify) and a parameter ρ = ρ(λ, n) with the following properties:

• Prove(1 λ , r, x, w) → (I, π): On input the security parameter λ, a string r ∈ {0, 1} ρ , a statement

x ∈ {0, 1} n and a witness w, this algorithm outputs a set of indices I ⊆ [ρ] and a proof π.

• Verify(1 λ , I, r I , x, π) → {0, 1}: On input the security parameter λ, a subset I ⊆ [ρ], a string r I ∈ {0, 1} |I| , a statement x ∈ {0, 1} n and a proof π, the verification algorithm outputs a bit b ∈ {0, 1}.

Moreover, Π HBM satisfies the following properties:

• Completeness: For all (x, w) ∈ R and r ∈ {0, 1} ρ , Pr[(I, π) ← Prove(1 λ , r, x, w) : Verify(1 λ , I, r I , x, π) = 1] = 1.

• Statistical soundness: For all unbounded provers P * , we have that for r r ← {0, 1} ρ and (x, π, I) ← P * (1 λ , r),

Pr[x / ∈ L ∧ Verify(1 λ , I, r I , x, π) = 1] = negl(λ).
We will oftentimes refer to the above probability as the soundness error.

• Perfect zero-knowledge: There exists an efficient simulator S such that for all unbounded verifiers V * , if we take (x, w) ← V * (1 λ ), r r ← {0, 1} ρ , (I, π) ← Prove(1 λ , r, x, w), and ( I, r I , π) ← S(1 λ , x), and moreover if R(x, w) = 1, then the following two distributions are identically distributed:

(I, r I , π) ≡ ( I, r I , π).

Remark 2.8 (Soundness Amplification). Take any polynomial = (λ, n). Then, given any NIZK in the hidden-bits model with soundness error ε, we can construct another NIZK in the hidden-bits model with ε soundness error by running copies of the NIZK in parallel (and accepting a proof only if all of the copies are valid). The simulator would simulate each of the individual instances independently. Parallel repetition increases the length of the hidden-bits string by a factor of .

Theorem 2.9 (NIZKs in the Hidden-Bits Model [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF]). For any ε > 0, every language L ∈ NP has a NIZK in the hidden-bits model with soundness error ε and relying on a hidden-bits string of length ρ = poly(n, log(1/ε)).

Designated-Verifier NIZKs and Dual-Mode NIZKs

We now review the notion of a reusable designated-verifier NIZK (DV-NIZK). Namely, we require that the same common reference string and verification state can be reused to prove and verify many statements without compromising either soundness or zero-knowledge. As in [LQR + 19], we use the fine-grained notion with separate setup and key-generation algorithms. The setup algorithm samples the common reference string (CRS) while the key-generation algorithm generates a public key (used to generate proofs) along with a secret key (used to verify proofs). We allow the same CRS to be reusable by many verifiers, who each generate their own public/secret key-pairs. In the traditional notion of DV-NIZKs, the setup and key-generation algorithms would be combined into a single algorithm that outputs the CRS (which would include the public proving key) along with a secret verification key.

Definition 2.10 (Designated-Verifier NIZK). Let L ⊆ {0, 1} n be an NP language associated with an NP relation R with n = n(λ). A reusable designated-verifier non-interactive zero-knowledge (DV-NIZK) proof for L consists of a tuple of efficient algorithms Π dvNIZK = (Setup, KeyGen, Prove, Verify) with the following properties:

• Setup(1 λ ) → crs: On input the security parameter λ, this algorithm outputs a common reference string crs. If Setup outputs a uniformly random string, we say that the scheme is in the common random string model.

• KeyGen(crs) → (pk, sk): On input the common reference string crs, the key-generation algorithm outputs a public key pk and a secret key sk.

• Prove(crs, pk, x, w) → π: On input the common reference string crs, a public key pk, a statement x ∈ {0, 1} n , and a witness w, this algorithm outputs a proof π.

• Verify(crs, sk, x, π) → {0, 1}: On input the common reference string crs, a secret verification key sk, a statement x, and a proof π, the verification algorithm outputs a bit b ∈ {0, 1}.

Moreover, Π dvNIZK should satisfy the following properties:

• Completeness: For all (x, w) ∈ R, and taking crs ← Setup(1 λ ), (pk, sk) ← KeyGen(crs),

Pr π ← Prove(crs, pk, x, w) : Verify(crs, sk, x, π) = 1 = 1.

• (Statistical) soundness: We consider two variants of soundness:

-Non-adaptive soundness: For all x / ∈ L and all polynomials q = q(λ), and all unbounded adversaries A making at most q verification queries, and sampling crs ← Setup(1 λ ), (pk, sk) ← KeyGen(crs), we have that Pr π ← A Verify(crs,sk,•,•) (1 λ , crs, pk, x) : Verify(crs, sk, x, π) = 1 = negl(λ).

-Adaptive soundness: For all polynomials q = q(λ) and all unbounded adversaries A making at most q verification queries, and sampling crs ← Setup(1 λ ), (pk, sk) ← KeyGen(crs), we have that Pr (x, π) ← A Verify(crs,sk,•,•) (1 λ , crs, pk) : x / ∈ L ∧ Verify(crs, sk, x, π) = 1 = negl(λ).

We also define the corresponding notions of computational soundness where the above properties only need to hold against efficient adversaries A.

• (Statistical) zero-knowledge: For all polynomials q = q(λ) and all unbounded adversaries A making at most q oracle queries, there exists an efficient simulator S = (S 1 , S 2 ) such that

Pr[A O 0 (crs,pk,•,•) (crs, pk, sk) = 1] -Pr[A O 1 (st S ,•,•) ( crs, pk, sk) = 1] = negl(λ),
where crs ← Setup(1 λ ), (pk, sk) ← KeyGen(crs) and (st S , crs, pk, sk) ← S 1 (1 λ ), the oracle O 0 (crs, pk, x, w) outputs Prove(crs, pk, x, w) if R(x, w) = 1 and ⊥ otherwise, and the oracle O 1 (st S , x, w) outputs S 2 (st S , x) if R(x, w) = 1 and ⊥ otherwise. Similar to soundness, we also consider computational zero-knowledge where the above property only needs to hold against efficient adversaries A.

Definition 2.11 (Publicly-Verifiable NIZKs). A NIZK Π NIZK is publicly-verifiable if the secret key output by KeyGen is empty. In this case, we can combine the Setup and KeyGen algorithms into a single algorithm that just outputs the CRS, and there is no notion of separate public/secret keys pk and sk. Both the Prove and Verify algorithms just take crs as input. We can define all of the properties analogously. In the publicly-verifiable setting, we do not need to provide the prover a separate verification oracle in the soundness game.

Remark 2.12 (Single-Theorem vs. Multi-Theorem Zero-Knowledge). The zero-knowledge property in Definition 2.10 is multi-theorem in the sense that the adversary can see proofs of multiple statements. We can consider a weaker notion of single-theorem zero-knowledge where the adversary can only see a proof on a single (adaptively-chosen) statement. Previously, Feige et al. [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] showed how to generically compile a single-theorem NIZK into a multi-theorem NIZK using a PRG. This transformation also applies in the designated-verifier setting [QRW19, CH19, KNYY19a]. One limitation of the [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] transformation is that it requires making non-black-box use of a PRG. The constructions we present in this work directly achieve multi-theorem zero-knowledge without needing to go through the [START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] transformation. As such, our constructions do not require making non-black-box use of any cryptographic primitives.

Malicious DV-NIZKs. We also consider the notion of a malicious designated-verifier NIZK (MDV-NIZK) from [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] where zero-knowledge holds even when the public key pk is chosen maliciously. In this case, the only trusted setup that we require is generating the common reference string (or, in some cases, a common random string), which can be reused by many verifiers.

Definition 2.13 (Malicious Designated-Verifier NIZKs [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF]). Let Π dvNIZK = (Setup, KeyGen, Prove, Verify) be a DV-NIZK for a language L. We say that Π dvNIZK satisfies statistical zero-knowledge against malicious verifiers if for all polynomials q = q(λ) and all unbounded adversaries A making at most q verification queries, there exists an efficient simulator S = (S 1 , S 2 ) such that

Pr[ExptReal[A, S](1 λ )] -Pr[ExptSim[A, S](1 λ )] = negl(λ),
where the two experiments ExptReal[A, S](1 λ ) and ExptSim[A, S](1 λ ) proceed as follows:

• Setup phase: In ExptReal, the challenger samples crs ← Setup(1 λ ) and gives crs to A. In ExptSim, the challenger samples (st S , crs) ← S 1 (1 λ ) and gives crs to A. The adversary replies with a public key pk.

• Query phase: Algorithm A is then given access to a verification oracle, and is allowed to make up to q queries to the oracle. On an input (x, w), the challenger replies with ⊥ if R(x, w) = 1. Otherwise, in ExptReal, the challenger replies with π ← Prove(crs, pk, x, w) while in ExptSim, the challenger replies with π ← S 2 (st S , pk, x).

• Output phase: At the end of the experiment, the adversary outputs a bit b ∈ {0, 1}, which is the output of the experiment.

Correspondingly, we can define the analogous notion of computational zero-knowledge against malicious verifiers by only requiring the above property to hold against computationally-bounded adversaries. If Π dvNIZK provides zero-knowledge against malicious verifiers, we say it is a maliciousdesignated-verifier NIZK (MDV-NIZK).

Dual-mode DV-NIZKs. Next, we recall the formal definition of a dual-mode (DV)-NIZK [START_REF] Groth | Perfect non-interactive zero knowledge for NP[END_REF][START_REF] Groth | New techniques for noninteractive zero-knowledge[END_REF].

Definition 2.14 (Dual-Mode Designated-Verifier NIZK). A dual-mode DV-NIZK Π dvNIZK = (Setup, KeyGen, Prove, Verify) is a DV-NIZK with the following additional properties:

• Dual-mode: The Setup algorithm takes an additional argument mode ∈ {binding, hiding}, and outputs a common reference string crs.

• CRS indistinguishability: The common reference string output by the two modes are computationally indistinguishable:

Setup(1 λ , binding) c ≈ Setup(1 λ , hiding).
• Statistical soundness in binding mode: If crs ← Setup(1 λ , binding), the designated-verifier NIZK satisfies statistical soundness.

• Statistical zero-knowledge in hiding mode: If crs ← Setup(1 λ , hiding), the designatedverifier NIZK satisfies statistical zero-knowledge.

We define a dual mode MDV-NIZK analogously by requiring the stronger property of statistical zero-knowledge against malicious verifiers in hiding mode.

Remark 2.15 (Dual-Mode Designated-Verifier NIZKs). Let Π dvNIZK = (Setup, KeyGen, Prove, Verify) be a dual-mode DV-NIZK for a language L ⊆ {0, 1} n . Then, the following properties hold:

• When the CRS is generated in binding mode, Π dvNIZK satisfies statistical soundness and computational zero-knowledge (i.e., Π dvNIZK is a "computational DV-NIZK proof").

• When the CRS is generated in hiding mode, Π dvNIZK satisfies non-adaptive computational soundness and statistical zero-knowledge (i.e., Π dvNIZK is a "statistical DV-NIZK argument").

• If Π dvNIZK is a dual-mode MDV-NIZK, then the zero-knowledge properties in each of the above instantiations also hold against malicious verifiers.

The first two properties follow from CRS indistinguishability and the corresponding statistical properties of Π dvNIZK in the two modes. Note though that even if Π dvNIZK satisfies adaptive soundness in binding mode, we do not know how to argue adaptive soundness for Π dvNIZK in hiding mode. At a high-level, this is because in the definition of adaptive soundness, checking whether the adversary succeeded or not requires deciding whether the statement x output by the adversary is contained in the language L or not. Unless NP ⊆ P/poly, this is not an efficiently-checkable property in general, and as such, we are not able to directly argue adaptive soundness of the construction. We refer to [START_REF] Abe | Perfect NIZK with adaptive soundness[END_REF] for more discussion on the challenges of using black-box reductions to argue adaptive soundness for statistical NIZK arguments.

Remark 2.16 (Adaptive Soundness via Complexity Leveraging). Using complexity leveraging [START_REF] Boneh | Efficient selective-ID secure identity-based encryption without random oracles[END_REF] and relying on a sub-exponential hardness assumption (as in [GOS06, GOS12]), we can show that non-adaptive soundness implies adaptive soundness. A direct application of complexity leveraging to a dual-mode NIZK yields an adaptively-sound statistical NIZK argument for proving statements of a priori bounded length n = n(λ). Using the method from [QRW19, §7] (see also Remark 6.5), we can also obtain adaptive soundness for statements with arbitrary polynomial length, but still at the expense of a subexponential hardness assumption.

3 Dual-Mode Hidden-Bits Generators and Dual-Mode DV-NIZKs

In this section, we formally define a dual-mode hidden-bits generator. Our definition extends the notion of a hidden-bits generator from [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] (and the similar notion of a designated-verifier PRG from [START_REF] Couteau | Designated-verifier pseudorandom generators, and their applications[END_REF]). Our definition differs from that in [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] in the following respects:

• Dual mode: We require that the common reference string for the hidden-bits generator can be generated in two computationally indistinguishable modes: a binding mode where the commitment statistically binds to a sequence of hidden bits, and a hiding mode where the commitment (and the openings to any subset of the bits) statistically hide the remaining bits.

• Statistical simulation in hiding mode. Minimally, our hiding property requires that the commitment and openings to any subset of the bits output by the HBG statistically hide the unopened bits. Here, we require an even stronger simulation property where there is an efficient simulator that can simulate the commitment and openings to any (random) string, given only the values of the opened bits. Moreover, we allow the adversary to adaptively choose the subset of bits for which it wants to see openings, and we also allow multiple interactions with the simulator. This strong simulation property enables us to directly argue adaptive and multi-theorem statistical zero-knowledge for our NIZK constructions (Section 3.1).7

Definition 3.1 (Dual-Mode Hidden-Bits Generator). Let λ be a security parameter and ρ be the output length. Let = (λ, ρ) be a polynomial. A dual-mode (designated-verifier) hiddenbits generator (HBG) with commitments of length consists of a tuple of efficient algorithms Π HBG = (Setup, KeyGen, GenBits, Verify) with the following properties:

• Setup(1 λ , 1 ρ , mode) → crs: On input the security parameter λ, a length ρ, and a mode mode ∈ {binding, hiding}, the setup algorithm outputs a common reference string crs.

• KeyGen(crs) → (pk, sk): On input a common reference string crs, the key-generation algorithm outputs a public key pk and a secret key sk.

• GenBits(crs, pk) → (σ, r, {π i } i∈[ρ] ): On input a common reference string crs and a public key pk, the bit-generation algorithm outputs a commitment σ ∈ {0, 1} , a string r ∈ {0, 1} ρ , and a collection of proofs π i for i ∈ [ρ].

• Verify(crs, sk, σ, i, r i , π i ) → {0, 1}: On input a common reference string crs, a secret key sk, a commitment σ ∈ {0, 1} , an index i ∈ [ρ], a bit r i ∈ {0, 1}, and a proof π i , the verification algorithm outputs a bit b ∈ {0, 1}.

In addition, we require that Π HBG satisfy the following properties:

• Correctness: For all integers λ ∈ N, and all polynomials ρ = ρ(λ), all indices i ∈ [ρ] and both modes mode ∈ {binding, hiding}, and sampling crs ← Setup(1 λ , 1 ρ , mode), (pk, sk) ← KeyGen(crs), and (σ, r,

{π i } i∈[ρ] ) ← GenBits(crs, pk), we have Pr[Verify(crs, sk, σ, i, r i , π i ) = 1] = 1.
• Succinctness: The length of the commitment depends only on the security parameter and not the length of the output: namely, = poly(λ).8

• CRS indistinguishability: For all polynomials ρ = ρ(λ), we have that

Setup(1 λ , 1 ρ , binding) c ≈ Setup(1 λ , 1 ρ , hiding).
• Statistically binding in binding mode: There exists a (possibly inefficient) deterministic algorithm Open(crs, σ) such that for all polynomials ρ = ρ(λ) and q = q(λ) and all unbounded adversaries A making up to q oracle queries, and sampling crs ← Setup(1 λ , 1 ρ , binding), (pk, sk) ← KeyGen(crs), (σ

* , i * , r * , π * ) ← A Verify(crs,sk,•,•,•,•) (1 λ , 1 ρ , crs, pk), r ← Open(crs, σ * ), we have that Pr[r i * = r * ∧ Verify(crs, sk, σ * , i * , r * , π * ) = 1] = negl(λ).
• Statistical simulation in hiding mode: For all polynomials ρ = ρ(λ), q = q(λ), and all unbounded adversaries A making up to q queries, there exists an efficient simulator S = (S 1 , S 2 ) such that

Pr[ExptHide[A, S, 0](1 λ , 1 ρ ) = 1] -Pr[ExptHide[A, S, 1](1 λ , 1 ρ ) = 1] = negl(λ), (3.1)
where for a bit b ∈ {0, 1}, the hiding experiment ExptHide[A, S, b](1 λ , 1 ρ ) is defined as follows:

-Setup phase: If b = 0, the challenger samples crs ← Setup(1 λ , 1 ρ , hiding) and (pk, sk) ← KeyGen(crs), and gives (crs, pk, sk

) to A. If b = 1, it samples (st S , crs, pk, sk) ← S 1 (1 λ , 1 ρ )
and gives ( crs, pk, sk) to A.

-Query phase: The adversary A can now make up to q challenge queries. On each query, the challenger responds as follows: * If b = 0, the challenger computes (σ, r, -Output phase: At the end of the experiment, the adversary outputs a bit b ∈ {0, 1}, which is the output of the experiment.

{π i } i∈[ρ] ) ← GenBits(crs,
When the difference in Eq. (3.1) is identically zero, we say that Π HBG satisfies perfect simulation in hiding mode.

Definition 3.2 (Publicly-Verifiable Dual-Mode HBG). A dual-mode HBG Π HBG is publicly-verifiable if the secret key sk output by KeyGen is empty. In this case, we can combine the Setup algorithm and the KeyGen algorithm into a single algorithm that just outputs the crs, and there is no notion of separate public/secret keys pk and sk. The GenBits and Verify algorithms just take crs as input.

We define all of the other properties analogously. In the publicly-verifiable setting, we do not need to provide the verification oracle to the adversary in the statistical binding security definition.

Definition 3.3 (Statistical Simulation for Malicious Keys). Let Π HBG = (Setup, KeyGen, GenBits, Verify) be a hidden-bits generator. We say that Π HBG satisfies statistical simulation for malicious keys if Π HBG satisfies the following stronger simulation property (where the adversary chooses the public key pk) in hiding mode:

• Statistical simulation for malicious keys: For all polynomials ρ = ρ(λ), q = q(λ), and all unbounded adversaries A making up to q queries, there exists an efficient simulator S = (S 1 , S 2 ) such that

Pr[ExptHide * [A, S, 0](1 λ , 1 ρ ) = 1] -Pr[ExptHide * [A, S, 1](1 λ , 1 ρ ) = 1] = negl(λ),
where for a bit b ∈ {0, 1}, the hiding experiment

ExptHide * [A, S, b](1 λ , 1 ρ ) is defined to be ExptHide[A, S, b](1 λ , 1 ρ
) with the following differences:

-Setup phase: If b = 0, the challenger samples crs ← Setup(1 λ , 1 ρ , hiding) and gives crs to A. If b = 1, the challenger samples (st S , crs) ← S 1 (1 λ , 1 ρ ) and gives crs to A. The adversary then chooses a public key pk.

-Query phase: Same as in ExptHide[A, S, b], except when b = 1, the challenger also provides the (adversarially-chosen) public key pk to the simulator. In other words, when b = 1, the challenger's reply to A is computed as ( σ, { π i } i∈I ) ← S 2 (st S , pk, I, r I ).

-Output phase: Same as in ExptHide[A, S, b].

Dual-Mode DV-NIZK from Dual-Mode HBG

In this section, we give our construction of a dual-mode designated-verifier NIZK from a dual-mode designated-verifier HBG and a NIZK in the hidden-bits model. Our generic construction is essentially the same as the corresponding construction from [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF]. We do rely on a different argument to show adaptive, multi-theorem statistical zero-knowledge, and in particular, we appeal to the statistical simulation property of our dual-mode HBG that we introduced in Definition 3.1.

Construction 3.4 (Dual-Mode DV-NIZK from Dual-Mode HBG). Let L ⊆ {0, 1} n be an NP language with associated NP relation R. We rely on the following building blocks:

• Let Π HBM = (HBM.Prove, HBM.Verify) be a NIZK in the hidden-bits model for L, and let ρ = ρ(λ) be the length of the hidden-bits string for Π HBM .

• Let Π HBG = (HBG.Setup, HBG.KeyGen, HBG.GenBits, HBG.Verify) be a hidden-bits generator with commitments of length = (λ, ρ), where λ is the security parameter and ρ is the output length of the generator.

We construct a dual-mode DV-NIZK Π dvNIZK = (Setup, KeyGen, Prove, Verify) for L as follows:

• Setup(1 λ , mode) → crs: On input λ and mode ∈ {binding, hiding}, sample s r ← {0, 1} ρ . Then, run crs HBG ← HBG.Setup(1 λ , 1 ρ , mode), and output crs = (λ, s, crs HBG ).

• KeyGen(crs) → (pk, sk): On input crs = (λ, s, crs HBG ), the key-generation algorithm runs (pk HBG , sk HBG ) ← HBG.KeyGen(crs HBG ) and outputs pk = pk HBG and sk = sk HBG .

• Prove(crs, pk, x, w) → π: On input crs = (λ, s, crs HBG ), pk = pk HBG , x ∈ {0, 1} n , and w, compute a hidden-bits string (σ, r, {π HBG,i } i∈[ρ] ) ← HBG.GenBits(crs HBG , pk HBG ), and an HBM proof (I, π HBM ) ← HBM.Prove(1 λ , r ⊕ s, x, w). Output π = (σ, I, r I , {π HBG,i } i∈I , π HBM ).

• Verify(crs, sk, x, π): On input crs = (λ, s, crs HBG ), sk = sk HBG , x ∈ {0, 1} n , and the proof π = (σ, I, r I , {π HBG,i } i∈I , π HBM ), output 1 if HBM.Verify(1 λ , I, r I ⊕ s I , x, π HBM ) = 1 and HBG.Verify(crs HBG , sk HBG , σ, i, r i , π HBG,i ) = 1 for all i ∈ I. Otherwise, output 0.

Theorem 3.5 (Completeness). If Π HBM is complete and Π HBG is correct, then Π dvNIZK from Construction 3.4 is complete.

Proof. Take any mode ∈ {binding, hiding}, and sample crs ← Setup(1 λ , mode), (pk, sk) ← KeyGen(crs).

Here, crs = (λ, s, crs HBG ), pk = pk HBG , and sk = sk HBG . Take any statement (x, w) ∈ R, and let π ← Prove(crs, pk, x, w). Then π = (σ, I, r I , {π HBG,i } i∈I , π HBM ). Consider the behavior of Verify(crs, sk, x, π). By correctness of Π HBG , HBG.Verify(crs HBG , sk HBG , σ, i, r i , π HBG,i ) = 1 for all i ∈ I. By completeness of Π HBM , HBM.Verify(1 λ , I, r I ⊕ s I , x, w) = 1, and the verifier accepts.

Theorem 3.6 (CRS Indistinguishability). If Π HBG satisfies CRS indistinguishability, then Π dvNIZK from Construction 3.4 satisfies CRS indistinguishability.

Proof. The CRS in Construction 3.4 consists of a tuple (λ, s, crs HBG ). In both modes, the first two components are identically distributed, and crs HBG is computationally indistinguishable by CRS indistinguishability of Π HBG .

Theorem 3.7 (Statistical Soundness in Binding Mode). If Π HBM is statistically sound with soundness error ε(λ), Π HBG is statistically binding in binding mode, and 2 • ε = negl(λ) then Π dvNIZK from Construction 3.4 satisfies adaptive statistical soundness.

The proof of Theorem 3.7 is very similar to the corresponding proof of adaptive statistical soundness from [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF]. We include it in Appendix A.

Theorem 3.8 (Statistical Zero-Knowledge in Hiding Mode). If Π HBM satisfies statistical (resp., perfect) zero-knowledge and Π HBG provides statistical (resp., perfect) simulation in hiding mode, then Π dvNIZK from Construction 3.4 satisfies statistical (resp., perfect) zero-knowledge in hiding mode.

Proof. Let S HBM denote the zero-knowledge simulator for Π HBM and S HBG = (S HBG,1 , S HBG,2 ) be the simulator for Π HBG in hiding mode. We construct a simulator S = (S 1 , S 2 ) as follows:

• S 1 (1 λ ) → (st S , crs, pk, sk): Run (st HBG , crs HBG , pk HBG , sk HBG ) ← S HBG,1 (1 λ , 1 ρ ). Choose s r ← {0, 1} ρ and set st S = st HBG , crs = (λ, s, crs HBG ), pk = pk HBG , and sk = sk HBG . Output (st S , crs, pk, sk).

• S 2 (st S , x) → π: On input st S = st HBG and x ∈ {0, 1} n , run ( I, r I , π HBM ) ← S HBM (1 λ , x) and ( σ, { π HBG,i } i∈ I ) ← S HBG,2 (st HBG , I, r I ⊕ s I ). Output the simulated proof π = ( σ, I, r I ⊕ s I , { π HBG,i } i∈ I , π HBM ).

To complete the proof, we proceed via a hybrid argument:

• Hyb 0 : This is the real distribution. Namely, the challenger begins by sampling crs ← Setup(1 λ ) and (pk, sk) ← KeyGen(crs), and gives (crs, pk, sk) to the adversary. The challenger responds to oracle queries on inputs (x, w) with π ← Prove(crs, pk, x, w) if R(x, w) = 1 and with ⊥ otherwise.

In more detail, the challenger samples s r ← {0, 1} ρ and runs crs HBG ← HBG.Setup(1 λ , 1 ρ , hiding), and (pk HBG , sk HBG ) ← HBG.KeyGen(crs HBG ). It sets crs = (λ, s, crs HBG ), pk = pk HBG , and sk = sk HBG . When the adversary makes an oracle query on (x, w) where R(x, w) = 1, the challenger computes (σ, r, {π HBG,i } i∈[ρ] ) ← HBG.GenBits(crs HBG , pk HBG ) and (I, π HBM ) ← HBM.Prove(1 λ , r ⊕ s, x, w). It outputs π = (σ, I, r I , {π HBG,i } i∈I , π HBM ).

• Hyb 1 : Same as Hyb 0 , except the challenger uses S HBG,1 to generate the common reference string and public/secret keys. It uses S HBG,2 to simulate the openings to the hidden-bits generator when responding to oracle queries. Specifically, the challenger works as follows:

1. At the start of the game, the challenger runs (st HBG , crs HBG , pk HBG , sk HBG ) ← S HBG,1 (1 λ , 1 ρ ). It samples s r ← {0, 1} ρ and gives crs = (λ, s, crs HBG ), pk = pk HBG , and sk = sk HBG to the adversary.

2. Whenever the adversary makes an oracle query (x, w) where R(x, w) = 0, the challenger replies with ⊥. Otherwise, it samples r r ← {0, 1} ρ and runs (I, π HBM ) ← HBM.Prove(1 λ , r ⊕ s, x, w). Then, it samples ( σ, { π HBG,i } i∈I ) ← S HBG,2 (st HBG , I, r I ), and finally outputs the proof π = ( σ, I, r I , { π HBG,i } i∈I , π HBM ).

• Hyb 2 : Same as Hyb 1 , except when responding to oracle queries, the challenger uses the simulator for the hidden-bits model NIZK to simulate the proofs. More precisely, on input (x, w) where R(x, w) = 1, the challenger computes ( I, r For an adversary A, we write Hyb i (A) to denote the output distribution of Hyb i with adversary A. We now show that the output distributions of each adjacent pair of hybrid experiments are statistically indistinguishable.

Lemma 3.9. If Π HBG satisfies statistical (resp., perfect) simulation in hiding mode, then the output distributions of Hyb 0 and Hyb 1 are statistically (resp., perfectly) indistinguishable.

Proof. Suppose there exists an adversary A such that |Pr[Hyb

0 (A) = 1] -Pr[Hyb 1 (A) = 1]| = ε for some non-negligible ε.
We use A to construct an adversary B such that ExptHide[B, S HBG , 0] and ExptHide[B, S HBG , 1] are distinguishable (with the same advantage ε). Algorithm B works as follows:

• First, algorithm B receives a tuple (crs HBG , pk HBG , sk HBG ) from the challenger. It samples s r ← {0, 1} ρ , and gives crs = (λ, s, crs HBG ), pk = pk HBG , and sk = sk HBG to A.

• When A makes a query on (x, w), if R(x, w) = 0, algorithm B responds with ⊥. Otherwise, B makes a challenge query to its challenger to obtain a string r ∈ {0, 1} ρ . Algorithm B computes (I, π HBM ) ← HBM.Prove(1 λ , r ⊕ s, x, w) and gives I ⊆ [ρ] to the challenger.

The challenger replies with a pair (σ, {π HBG,i } i∈I ). Finally, B replies to A with the proof π = (σ, I, r I , {π HBG,i } i∈I , π HBM ).

• At the end of the game, B outputs whatever A outputs.

By construction, if the challenger generates the parameters and answers the queries according to ExptHide[B, S HBG , 0], then B perfectly simulates Hyb 0 for A. Alternatively, if the challenger implements the logic according to ExptHide[B, S HBG , 1], then B perfectly simulates Hyb 1 for A.

Lemma 3.10. If Π HBM satisfies statistical (resp., perfect) zero-knowledge, then the output distributions of Hyb 1 and Hyb 2 are statistically (resp., perfectly) indistinguishable.

Proof. We define a sequence of q + 1 intermediate hybrid experiments Hyb 1,0 , . . . , Hyb 1,q , where q = poly(λ) is a bound on the number of queries the adversary makes. Hybrid Hyb 1,i is the experiment where the first i oracle queries are handled according to the procedure in Hyb 2 and the remaining queries are handled according to the procedure in Hyb 1 . By construction Hyb 1,0 ≡ Hyb 1 and Hyb 1,q ≡ Hyb 2 . Moreover, each adjacent pair of hybrid experiments Hyb 1,i-1 and Hyb 1,i only differ in how the i th oracle query (x, w) is handled. In Hyb 1,i-1 , the challenger samples a random r r ← {0, 1} ρ and computes (I, π HBM ) ← HBM.Prove(1 λ , r ⊕ s, x, w) while in Hyb 1,i , the challenger invokes the simulator ( I, r I , π HBM ) ← S HBM (1 λ , x). By statistical zero-knowledge of Π HBM , we have that (I, r I ⊕ s I , π HBM ) s ≈ ( I, r I , π HBM ). If Π HBM satisfies perfect zero-knowledge, then these two distributions are identically distributed. Correspondingly, hybrids Hyb 1,i-1 and Hyb 1,i are statistically indistinguishable (or identically distributed if Π HBM satisfies perfect zeroknowledge). Since q = poly(λ), we conclude by a hybrid argument that the outputs of Hyb 2 and Hyb 3 are statistically indistinguishable (or identically distributed if Π HBM satisfies perfect zero-knowledge).

Since each consecutive pair of hybrid experiments is statistically indistinguishable (or identically distributed), the claim follows.

Theorem 3.11 (Statistical Zero-Knowledge against Malicious Verifiers). If Π HBM satisfies statistical zero-knowledge and Π HBG provides statistical simulation for malicious keys, then Construction 3.4 is a MDV-NIZK. Namely, Construction 3.4 satisfies statistical zero-knowledge against malicious verifiers in hiding mode.

The proof of Theorem 3.11 follows from a similar argument as Theorem 3.8 and is included in Appendix A.

Dual-Mode Hidden-Bits Generator from k-Lin

In this section, we show how to construct a dual-mode hidden-bits generator from the k-linear (k-Lin) assumption [BBS04, HK07, Sha07, EHK + 13] over pairing-free groups for any k ≥ 1. We note that the 1-Lin assumption is precisely the decisional Diffie-Hellman (DDH) assumption. We begin by recalling some basic notation as well as the k-Lin assumption.

Notation. Throughout this section, we will work with cyclic groups G of prime order p. We will use multiplicative notation to denote the group operation. For x ∈ Z p , we often refer to g x as an "encoding" of x. For a matrix A ∈ Z n×m p , we write g A ∈ G n×m to denote the matrix of group elements formed by taking the element-wise encoding of each component of A.

Definition 4.1 (Prime-Order Group Generator). A prime-order group generator algorithm GroupGen is an efficient algorithm that on input the security parameter 1 λ outputs a description G = (G, p, g) of a prime-order group G with order p and generator g. Throughout this work, we will assume that 1/p = negl(λ). Definition 4.2 (k-Linear Assumption [BBS04, HK07, Sha07, EHK + 13]). Fix a constant k ≥ 1. We say that a prime-order group generator GroupGen satisfies the k-Lin assumption if for all efficient adversaries A and sampling

G = (G, p, g) ← GroupGen(1 λ ), a r ← Z k p , w r ← Z k+1 p , and u r ← Z k p , we have that Pr[A(G, g A , g Aw ) = 1] -Pr[A(G, g A , g u ) = 1] = negl(λ),
where

A = diag(a) 1 T ∈ Z (k+1)×k p , (4.1)
and diag(a) ∈ Z k×k p denotes the diagonal matrix whose entries are a 1 , . . . , a k , and 1 ∈ Z k+1 p is the all-ones vector.

Construction 4.3 (Dual-Mode Hidden-Bits Generator from k-Lin). Let GroupGen be a prime-order group generator algorithm. We construct a dual-mode hidden-bits generator (HBG) as follows:

• Setup(1 λ , 1 ρ , mode) → crs: First, the setup algorithm samples G = (G, p, g) ← GroupGen(1 λ ) and a hash function H -

If mode = hiding, sample w i r ← Z ρ+k p for all i ∈ [ρ]. -If mode = binding, sample s i r ← Z k p and set w i ← Vs i for all i ∈ [ρ].
Output crs = (G, H, g V , g w 1 , . . . , g wρ ).

• KeyGen(crs) → (pk, sk): On input crs = (G, H, g V , g w 1 , . . . , g wρ ), the key-generation algorithm samples a

r ← Z p and b 1 , . . . , b ρ r ← Z k p . For each i ∈ [ρ], it sets z i ← w i a + Vb i ∈ Z ρ+k p . It outputs pk = (g z 1 , . . . , g zρ ) and sk = (a, b 1 , . . . , b ρ ).
• GenBits(crs, pk) → (σ, r, {π i } i∈[ρ] ): On input crs = (G, H, g V , g w 1 , . . . , g wρ ) and public key pk = (g z 1 , . . . , g zρ ), sample y r ← Z ρ+k p and compute for each i ∈ [ρ],

g t i ← g y T w i and g u i ← g y T z i .
Next, let σ = g y T V . For each i ∈ [ρ], set r i ← H(g t i ) and π i ← (g t i , g u i ), and output σ, r, and

{π i } i∈[ρ] .
• Verify(crs, sk, σ, i, r i , π i ): On input crs = (G, H, g V , g w 1 , . . . , g wρ ), secret key sk

= (a, b 1 , . . . , b ρ ), σ = g c T , i ∈ [ρ], r i ∈ {0, 1}, and π i = (g t i , g u i ), output 1 if g u i = (g t i a )(g c T b i ) and r i = H(g t i ).
Otherwise, output 0.

Correctness and security analysis.

Publicly-Verifiable Hidden-Bit Generators from Pairings

In this section, we describe a variant of our dual-mode hidden-bits generator from Section 4.1 to obtain a publicly-verifiable hidden-bits generator from pairings. Our resulting construction does not give a dual-mode hidden-bits generator. Instead, we obtain a standard HBG (where there is a single mode) that satisfies statistical simulation and computational binding. Using an analog of Construction 3.4, this suffices to construct a publicly-verifiable statistical NIZK argument. We refer to Appendix B for the details. Below, we define the computational binding property we use:

Definition 4.10 (Computational Binding). A publicly-verifiable hidden bits generator Π HBG = (Setup, GenBits, Verify) is computationally binding if the following property holds:

• Computational binding: There exists an efficient extractor E = (E 1 , E 2 ), where E 2 is deterministic, and for all polynomials ρ = ρ(λ), the following two properties hold:

-CRS indistinguishability: The following distributions are computationally indistinguishable:

{Setup(1 λ , 1 ρ )} c ≈ {(st E , crs) ← E 1 (1 λ , 1 ρ ) : crs}.
-Binding: For all efficient adversaries A, and sampling (st

E , crs) ← E 1 (1 λ , 1 ρ ) followed by (σ * , i * , r * , π * ) ← A(1 λ , 1 ρ , crs) and r ← E 2 (st E , σ * ), we have that Pr[r i * = r * ∧ Verify( crs, σ * , i * , r * , π * ) = 1] = negl(λ).
Pairing groups. In this section, we work in (asymmetric) pairing groups. We review the notion of a pairing below, as well as the kernel k-linear (k-KerLin) assumption [MRV15, KW15], which can be viewed as a search version of the k-linear assumption. As shown in [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF], the k-KerLin assumption is weaker than the k-Lin assumption (in particular, k-Lin implies k-KerLin), but stronger than the CDH assumption.

Definition 4.11 (Prime-Order Pairing-Group Generator). A prime-order (asymmetric) pairing group generator algorithm PairingGroupGen is an efficient algorithm that on input the security parameter 1 λ outputs a description G = (G 1 , G 2 , G T , p, g 1 , g 2 , e) of two base groups G 1 (generated by g 1 ), G 2 (generated by g 2 ), and a target group G T , all of prime order p, together with an efficiently-computable mapping e : G 1 × G 2 → G T (called the "pairing"). Finally, the mapping e is bilinear: for all x, y ∈ Z p , e(g x 1 , g y 2 ) = e(g 1 , g 2 ) xy .

Definition 4.12 (Kernel k-Linear Assumption [START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF][START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF]). The kernel k-linear (k-KerLin) assumption holds in G 2 relative to a pairing-group generator PairingGroupGen if for all efficient adversaries A, and sampling

G = (G 1 , G 2 , G T , p, g 1 , g 2 , e) ← PairingGroupGen(1 λ ), a r ← Z k p ,
Pr[g c T 1 ← A(G, g A 2 ) : c T A = 0 ∧ c = 0] = negl(λ).
We can define an analogous assumption over G 1 (by interchanging the roles of G 1 and G 2 above).

Notation. For a matrix A, we continue to write g A 1 and g A 2 to denote matrices of group elements (over G 1 and G 2 , respectively). In addition, if we have two matrices A ∈ Z m× and B ∈ Z ×n , we write e(g A 1 , g B 2 ) to denote the operation that outputs e(g 1 , g 2 ) AB ∈ G m×n T . In particular, the (i, j) th entry of e(g A 1 , g B 2 ) is computed as

e(g A 1 , g B 2 ) i,j = k∈[ ] e(g a i,k 1 , g b k,j 2 ).
Construction 4.13 (Publicly-Verifiable Hidden-Bits Generator from Pairings). Let PairingGroupGen be a prime-order bilinear group generator algorithm. We construct a publicly-verifiable hidden-bits generator (HBG) as follow:

• Setup(1 λ , 1 ρ ) → crs: The setup algorithm starts by sampling G = (G 1 , G 2 , G T , p,
D = diag(d) 1 T ∈ Z (k+1)×k p . (4.2) It computes âT ← a T D ∈ Z k p , and for each i ∈ [ρ], it computes Z i ← w i a T + VB i ∈ Z (ρ+k)×(k+1) p and Bi ← B i D ∈ Z k×k p . It outputs crs = G, H, g V 1 , g âT 2 , g D 2 , g w i 1 , g Z i 1 , g Bi 2 i∈[ρ] .
• GenBits(crs) → (σ, r,

{π i } i∈[k] ): On input crs = G, H, g V 1 , g âT 2 , g D 2 , g w i 1 , g Z i 1 , g Bi 2 i∈[ρ]
, sample y r ← Z ρ+k p , and compute for each i ∈ [ρ],

g t i 1 ← g y T w i 1 and g u T i 1 ← g y T Z i 1 . Next, let σ = g y T V 1
, and for each i ∈ [ρ], set r i ← H(g t i 1 ) and π i = (g t i 1 , g

u T i 1
). Output σ, r, and

{π i } i∈[ρ] . • Verify(crs, σ, i, r i , π i ): On input crs = G, H, g V 1 , g âT 2 , g D 2 , g w i 1 , g Z i 1 , g Bi 2 i∈[ρ] , σ = g c T 1 , i ∈ [ρ], r i ∈ {0, 1}, and π i = (g t i 1 , g u T i 1 ), output 1 if e(g t i 1 , g âT 2 ) • e(g c T 1 , g Bi 2 ) = e(g u T i 1 , g D 2 ) (4.3)
and r i = H(g t i 1 ). If either check fails, output 0.

Correctness and security analysis. We now state the correctness and security theorems for Construction 4.13 and provide the proofs in Appendix C.2.

Theorem 4.14 (Correctness). Construction 4.13 is correct.

Theorem 4.15 (Succinctness). Construction 4.13 is succinct.

Theorem 4.16 (Computational Binding). Suppose PairingGroupGen outputs groups (G 1 , G 2 , G T ) such that the k-Lin assumption holds in G 1 and the k-KerLin assumption holds in G 2 . Then, Construction 4.13 satisfies computational binding in binding mode.

Theorem 4.17 (Statistical Simulation). If H satisfies statistical uniformity, then Construction 4.13 satisfies statistical simulation.

Dual-Mode Hidden-Bits Generator with Malicious Security from k-Lin

We now show how to modify the k-Lin construction from Section 4.1 (Construction 4.3) to obtain a hidden-bits generator with security against malicious verifiers. Combined with Construction 3.4, this yields a dual-mode MDV-NIZK (Theorem 3.11). We refer to Section 1.2 for a high-level description of our approach.

Construction 4.18 (Dual-Mode HBG with Malicious Security from k-Lin). Let ρ be the output length of the hidden-bits generator. We require the following primitives:

• Let GroupGen be a prime-order group generator algorithm.

• Let = 3ρλ and define T λ, := {S ⊆ [ ] : |S| = λ} to be the set of all subsets of [ ] that contains exactly λ elements. Let G : {0, 1} κ → T ρ λ, × Z ρ p be a PRG with seed length κ = κ(λ). Here, p is the order of the group G output by GroupGen (on input 1 λ ).

Constructing the PRG G. It is straightforward to construct a PRG with outputs in T ρ λ, × Z ρ p from a PRG with outputs in {0, 1} ρλ (1+ log p ) . To see this, it suffices to give an efficient algorithm that maps from the uniform distribution on {0, 1} λ (1+ log p ) to a distribution that is statistically close to uniform over T λ, × Z p . Take a string γ ∈ {0, 1} λ (1+ log p ) .

-The first λ bits of γ are interpreted as blocks of λ-bit indices i 1 , . . . , i ∈ {0, 1} λ . These indices specify the set S ⊆ T λ, as follows. First, take S 0 ← [ ]. For each j ∈ [λ], take s j to be the (i j mod |S j-1 |) th element of S j-1 and define S j ← S j-1 \ {s j }. Define S ← {s 1 , . . . , s } ∈ T λ, .

-The remaining λ log p bits of γ are taken to be the binary representation of an -dimensionalvector α ∈ Z , where each component is a λ log p -bit integer.

The string γ ∈ {0, 1} λ (1+ log p ) is mapped onto (S, α mod p) ∈ T λ, × Z p . By construction, this procedure maps from the uniform distribution over {0, 1} λ (1+ log p to a distribution that is statistically uniform over T λ, × Z p .

We construct the dual-mode designated-verifier hidden-bits generator with malicious security as follows:

• Output crs = (G, H, g V , g w 1 , . . . , g w ).

• KeyGen(crs) → (pk, sk): • GenBits(crs, pk) → (σ, r, {π i } i∈[ρ] ): On input crs = (G, H, g V , g w 1 , . . . , g w ) and the public key pk = (g z 1 , . . . , g z ), sample y r ← Z +k p and compute for each i ∈ [ ]

On input crs = (G, H, g V , g w 1 , . . . , g w ), sample a r ← Z p and b 1 , . . . , b r ← Z k p . For each i ∈ [ ], compute z i ← w i a + Vb i ∈ Z +k
g t i ← g y T w i and g u i ← g y T z i .
Next, sample a PRG seed s r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s) where Ŝi ∈ T λ, for all i ∈ [ρ] and α ∈ Z ρ p . Compute the shifted sets

S i ← {j + • (i -1) | j ∈ Ŝi } for each i ∈ [ρ]. Finally, compute r i ← H   j∈S i g α j t j   and π i ← {(j, g t j , g u j )} j∈S i .
Output σ = (s, g y T V ), r, and

{π i } i∈[ρ] .
• Verify(crs, sk, σ, i, r i , π i ): On input crs = (G, H, g V , g w 1 , . . . , g w ), sk = (a, b 1 , . . . , b ), σ = (s, g c T ), i ∈ [ρ], r i ∈ {0, 1}, and π i = {(j, g t j , g u j )} j∈S for an implicitly-defined set S ⊆ [ρ ], the verification algorithm performs the following checks:

-Compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s) and the shifted set

S i ← {j + • (i -1) | j ∈ Ŝi }.
It checks that S = S i and outputs 0 if not. -It checks that g u j = (g t j a )(g c T b j ) for all j ∈ S, and outputs 0 if not. -It checks that r i = H j∈S g α j t j and outputs 0 if not. If all checks pass, the verification algorithm outputs 1.

Correctness and security analysis. We now state the correctness and security theorems for Construction 4.18 and provide the proofs in Appendix C.3. 5 Dual-Mode Hidden-Bits Generators from QR In this section, we show how to similarly construct dual-mode hidden-bits generators from subgroupindistinguishability-type assumptions [START_REF] Brakerski | Circular and leakage resilient public-key encryption under subgroup indistinguishability -(or: Quadratic residuosity strikes back)[END_REF], and specifically, from the QR and DCR assumptions. We begin in Section 5.1 with a basic construction from QR (the analog of Construction 4.3), and then show in Section 5.2 how we can use similar techniques from Section 4.3 to obtain a dual-mode hidden-bits generator with malicious security also from the QR assumption. While the construction with malicious security (Construction 5.9) subsumes the basic construction (Construction 5.3), we begin with the basic construction because it is both simpler to understand and contains all of the essential ingredients for realizing HBGs from a subgroup-indistinguishability-type assumption. Finally, in Appendix E, we show how to adapt our techniques to also obtain dual-mode HBGs from the DCR assumption.

Dual-Mode Hidden-Bits Generator from QR

In this section, we describe our construction of a dual-mode hidden-bits generator from the quadratic residuosity (QR) assumption [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF]. We first recall some basic notation and the QR assumption.

Notation. Our construction works with a modulus N = pq that is a product of safe primes p, q: namely, p = 2p + 1 and q = 2q + 1 for primes p and q . We write J N to denote the multiplicative subgroup of Z * N with Jacobi symbol +1 (which has order 2p q ) and QR N to denote the multiplicative subgroup of quadratic residues modulo N (which has order p q ). In the following description, we use the fact that J N splits into two subgroups of coprime order: namely, J N = QR N × H, where H is the multiplicative subgroup {±1} of order 2 generated by -1. When N is a product of safe primes, QR N is also cyclic. As such, we will write g to denote a generator of QR N and h = -1 to denote the generator of H. We will typically write elements of J N with a bar (e.g., c, t). In the analysis, it will be more conducive to analyze the components in their respective subgroups. In this case, we will often express elements of J N as c = g c h ĉ ∈ J N , for exponents c ∈ Z p q and ĉ ∈ Z 2 .

Definition 5.1 (Sampling Safe Prime Product Modulus). A safe prime product modulus sampler SampleModulus is an efficient algorithm that on input the security parameter λ, outputs a tuple (N, p, q) where N = pq, p = 2p + 1, q = 2q + 1, for distinct primes p , q where 1/p , 1/q = negl(λ).

Definition 5.2 (Quadratic Residuosity Assumption [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF]). A safe prime product sampler SampleModulus satisfies the quadratic residuosity (QR) assumption if, for any efficient adversary A, and any sampling (N, p, q) ← SampleModulus(1 λ ), x r ← QR N , where p = 2p + 1 and q = 2q + 1,

|Pr[A(N, x) = 1] -Pr[A(N, (-1) • x) = 1]| = negl(λ).
Our QR-based construction is conceptually similar to the QR-based trapdoor hash function of [DGI + 19, Section 4.3]. Like [DGI + 19], it uses the predicate LEQ : J N × J N → {0, 1} that outputs 1 if the bit representation of its first argument is no larger than that of its second argument in some lexicographical ordering. In particular, for all x 1 , x 2 ∈ J N , it will be the case that LEQ(x 1 , x 2 ) = 1 -LEQ(x 2 , x 1 ). Construction 5.3 (Dual-Mode Hidden-Bits Generator from QR). Let ρ be the output length of the hidden-bits generator. Our QR-based dual-mode hidden-bits generator (HBG) works as follows:

• Setup(1 λ , 1 ρ , mode) → crs: Sample (N, p, q) ← SampleModulus(1 λ ), and let g be a generator of QR N . Let h = -1 be the generator of H = {±1}. The setup algorithm then samples a vector v

r ← Z ρ N/2 , scalars s 1 , . . . , s ρ r ← Z N/2
, and sets ŵi ∈ Z ρ 2 for i ∈ [ρ] as follows:

-If mode = hiding, set ŵi ← e i where e i ∈ Z ρ 2 is the i th basis vector.

-If mode = binding, set ŵi ← 0.
Finally, it sample a hash function H r ← H, where H is a family of hash functions with domain Z N and range {0, 1} λ . Output crs = (N, g, h, H, g v , g s 1 v h ŵ1 , . . . , g sρv h ŵρ ). For each i ∈ [ρ], let u i ← H(u 1,i , . . . , u T,i ) and r i ← LEQ(t i , t i h). Output σ = c, r, and

π = {(t i , u i )} i∈[ρ] .
• Verify(crs, sk, σ, i, r i , π i ): On input crs = (N, g, h, H, v, w 1 , . . . , w ρ ), the verification key

sk = {a τ , b τ,i } τ ∈[T ],i∈[ρ] , σ = c, i ∈ [ρ], r i ∈ {0, 1}
, and π i = (t i , u i ), output 1 if

u i = H t a 1 i c b 1,i , . . . , t a T i c b T,i , (5.1)
and r i = LEQ(t i , t i h). Otherwise, output 0.

The group elements that are input to algorithms KeyGen, GenBits, and Verify are assumed to be elements of the subgroup J N of Z * N . Note that since membership in J N can be efficiently tested given the modulus N (by computing the Jacobi symbol), each of the algorithms will first check this condition, and proceed only if all of the inputs are from the correct domains. We omit this explicit check in the above description for ease of exposition.

Correctness and security analysis. We now state the correctness and security theorems for Construction 5.3 and give the proofs in Appendix D.1.

Dual-Mode Hidden-Bits Generator with Malicious Security from QR

In this section, we show how to extend Construction 5.3 to obtain a dual-mode hidden-bits generator with malicious security from the QR assumption. Our construction is conceptually similar to Construction 4.18 from k-Lin.

Construction 5.9 (Dual-Mode HBG with Malicious Security from QR). Let ρ be the output length of the hidden-bits generator. We rely on a similar set of building blocks as Construction 4.18:

• Let SampleModulus be a safe prime modulus sampler. Let T = 2(λ + log N ), where log N is a bound on the bit-length of the modulus output by SampleModulus (on input 1 λ ).

• Let = 36ρλ 2 T and define T λ, := {S ⊆ [ ] : |S| = λ} to be the set of all subsets of [ ] that contains exactly λ elements. Let G : {0, 1} κ → T ρ λ, × Z ρ 2 be a PRG with seed length κ = κ(λ). Here, N is the modulus output by SampleModulus. We refer to Construction 4.18 for a description of how to construct such a PRG.

We construct the dual-mode designated-verifier HBG with malicious security as follows:

• Setup(1 λ , 1 ρ , mode) → crs: Let = ρ . Sample (N, p, q) ← SampleModulus(1 λ ). Let g be a generator of QR N and h = -1 be the generator of H = {±1}. The setup algorithm samples a vector v r ← Z N/2 , scalars s 1 , . . . , s r ← Z N/2 , and sets ŵi ∈ Z 2 for i ∈ [ ] as follows:

-If mode = hiding, set ŵi ← e i where e i ∈ Z 2 is the i th basis vector.

-If mode = binding, set ŵi ← 0.

Finally, it sample a hash function H r ← H, where H is a family of hash functions with domain Z N and range {0, 1} λ . Output crs = (N, g, h, H, g v , g s 1 v h ŵ1 , . . . , g s v h ŵ ).

• KeyGen(crs) → (pk, sk):

On input crs = (N, g, h, H, v, w 1 , . . . , w ), sample a τ , b τ,i r ← Z N/2 for all τ ∈ [T ] and i ∈ [ ]. It computes and outputs the public key pk = {v b τ,i w aτ i } τ ∈[T ],i∈[ ] and sk = {a τ , b τ,i } τ ∈[T ],i∈[ ] . • GenBits(crs, pk) → (σ, r, {π i } i∈[ρ] ): On input crs = (N, g, h, H, v, w 1 , . . . , w ) and pk = {z τ,i } τ ∈[T ],i∈[ ] , sample y r ← Z N/2 and compute for all τ ∈ [T ] and i ∈ [ ] c ← j∈[ ] v y i j and t i ← j∈[ ] w y j i,j and u τ,i ← j∈[ ] z y j τ,i,j .
In addition, for each i ∈ [ ], compute u i ← H(u 1,i , . . . , u T,i ). Next, sample a PRG seed s r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s) where Ŝi ∈ T λ, for all i ∈ [ρ] and α ∈ Z ρ 2 . For each i ∈ [ρ], compute the shifted sets S i ← {j + • (i -1) | j ∈ Ŝi } and set

t i ← j∈S i t α j j
and r i ← LEQ(t i , t i h) and π i ← {(j, t j , u j )} j∈S i .

Output σ = (s, c), r, and

π = {π i } i∈[ρ] . • Verify(crs, sk, σ, i, r i , π i ): On input crs = (N, g, h, H, v, w 1 , . . . , w ), sk = {a τ , b τ,i } τ ∈[T ],i∈[ ] , σ = (s, c), i ∈ [ρ], r i ∈ {0, 1}
, and π i = {(h, t j , u j )} j∈S for an implicitly-defined set S ⊆ [ ], the verification algorithm performs the following checks:

-Compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s) and the shifted set

S i ← {j + • (i -1) | j ∈ Ŝi }.
It checks that S = S i and outputs 0 if not.

-It checks that

u j = H t a 1 j c b 1,j , . . . , t a T j c b T,j , (5.2)
for all j ∈ S, and outputs 0 if not.

-It computes t i ← j∈S t α j j and checks that r i = LEQ(t i , t i h).

The group elements that are input to algorithms KeyGen, GenBits, and Verify are assumed to be elements of the subgroup J N of Z * N . Note that since membership in J N can be efficiently tested given the modulus N (by computing the Jacobi symbol), each of the algorithms will first check this condition, and proceed only if all of the inputs are from the correct domains. We omit this explicit check in the above description for ease of exposition.

Correctness and security analysis. We now state the correctness and security theorems for Construction 5.9 and give the proofs in Appendix D.2.

Theorem 5.10 (Correctness). Construction 5.9 is correct.

Theorem 5.11 (Succinctness). Construction 5.9 is succinct.

Theorem 5.12 (CRS Indistinguishability). Suppose the QR assumption holds with respect to SampleModulus. Then, Construction 5.9 satisfies CRS indistinguishability.

Theorem 5.13 (Statistical Binding in Binding Mode). If H is pairwise independent, Construction 5.9 satisfies statistical binding in binding mode.

Theorem 5.14 (Statistical Simulation in Hiding Mode). Construction 5.9 satisfies statistical simulation in hiding mode.

Instantiations and Extensions

In this section, we provide the main implications of our framework for constructing statistical (and more generally, dual-mode) NIZKs. We conclude by describing two simple extensions to augment our NIZKs with additional properties.

Dual-mode MDV-NIZKs. By instantiating Construction 3.4 with a dual-mode MDV hiddenbits generator (e.g., Constructions 4.18, 5.9 and E.16), we obtain a dual-mode MDV-NIZK (Theorems 3.5, 3.7 and 3.11). We summarize our instantiations with the following corollaries: Corollary 6.1 (Dual-Mode MDV-NIZK from k-Lin). Under the k-Lin assumption over pairingfree groups (for any k ≥ 1), there exists a statistical MDV-NIZK argument (with non-adaptive soundness) in the common random string model, and a computational MDV-NIZK proof (with adaptive soundness) for NP in the common reference string model. Corollary 6.2 (Dual-Mode MDV-NIZK from QR or DCR). Under the QR or DCR assumptions, there exists a statistical MDV-NIZK argument (with non-adaptive soundness) and a computational MDV-NIZK proof (with adaptive soundness) for NP in the common reference string model. Remark 6.3 (Perfect Zero-Knowledge DV-NIZK from k-Lin). As discussed in Remark C.8, Construction 4.3 satisfies perfect statistical simulation if the hash function H : G \ {g 0 } → {0, 1} is perfectly uniform and there is an efficient algorithm to exactly sample t r ← Z p such that H(g t ) = r for any r ∈ {0, 1}. Here we describe a straightforward candidate for H when G = E(F p ) is an ellipticcurve group of prime-order. We can write E(F p ) = {y 2 = x 3 + Ax + B | (x, y) ∈ F 2 p } ∪ {O}, where O is the identity element. For a point (x, y) ∈ G \ {O}, we define the hash function H(x, y) := sign(y), where sign(y) outputs 0 if y ∈ F p is lexicographically smaller than -y ∈ F p , and 1 otherwise. Since (x, y) ∈ G implies that (x, -y) ∈ G, H perfectly partitions G \ {O} into two equal-size sets, and correspondingly, H is perfectly uniform. Next, it is straightforward to sample t i r ← G \ {O} such that H(t) = r. Simply sample (x, y) r ← G \ {O}, and output either (x, y) or (x, -y), depending on r. Thus, H satisfies the required properties and combined with Construction 4.3, gives a hidden-bits generator with perfect simulation in hiding mode. Combined with Construction 3.4, we obtain a perfect DV-NIZK argument from the k-Lin assumption in pairing-free groups. Note that our MDV-NIZK construction from the k-Lin assumption (Construction 4.18) does not satisfy perfect simulation in hiding mode, so we do not obtain a perfect MDV-NIZK argument.

Publicly-verifiable statistical NIZK arguments. By instantiating Construction B.1 with a publicly-verifiable hidden-bits generator satisfying statistical simulation (e.g., Construction 4.13), we obtain a publicly-verifiable statistical NIZK argument in the common reference string model: Corollary 6.4 (Publicly-Verifiable Statistical NIZK Argument from Pairings). Suppose that the k-Lin assumption holds in G 1 and the k-KerLin assumption holds in G 2 (for any k ≥ 1) over a pairing group. Then, there exists a publicly-verifiable statistical NIZK argument for NP (with non-adaptive soundness) in the common reference string model.

Extensions. We conclude by describing two simple extensions to our framework to support languages where statements can have an arbitrary a priori unbounded polynomial length as well as how to obtain a proof of knowledge. Remark 6.5 (Unbounded Statement Size). All of our NIZK constructions in this paper assumed an a priori bound on the length n of the statements in the language (which determines the length of the hidden-bits string we require), and the length of the CRS scales with n. Using the same idea from [QRW19, §7], it is straightforward to adapt the construction to have a fixed-size CRS (independent of n) that supports proving statements of arbitrary poly(λ) size. We require a noninteractive commitment in the CRS model, and we will use 3-SAT as our underlying NP-complete language. To prove that a specific 3-CNF formula is satisfiable, the prover would commit to the satisfying assignment (one variable at a time), and then use the NIZK to prove that the committed values indeed satisfy each clause. Observe that we now only require a NIZK that supports a fixed-size language to implement this transformation. Moreover, if we instantiate the commitment with a "dual-mode" commitment, where in one mode, the commitment is statistically binding, and in the other, is statistically hiding, then we retain the dual-mode properties of the underlying NIZK. We can build dual-mode commitments from any lossy public-key encryption scheme [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] (implied by standard intractability assumptions like DDH, QR, and DCR). Specifically, the CRS would contain a public key for the encryption scheme, and a commitment to a bit b ∈ {0, 1} would be an encryption of b with fresh randomness r. The randomness r then serves as the commitment opening. When the lossy encryption scheme is injective, then the commitment is statistically binding and if the encryption scheme is lossy, then the commitment scheme is statistically hiding. Remark 6.6 (Proofs of Knowledge). It is also straightforward to update our NIZK constructions to obtain a proof of knowledge via the classic transformation where the prover encrypts the witness (using a public-key encryption scheme) and gives a proof that the encrypted witness satisfies the relation [START_REF] De | Zero-knowledge proofs of knowledge without interaction[END_REF]. To preserve the dual-mode properties of the NIZK, we again require a lossy public-key encryption scheme [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] (similar to Remark 6.5).

A Analysis of Construction 3.4 (Dual-Mode DV-NIZK)

In this section, we provide complete proofs for statements in Section 3.1.

Proof of Theorem 3.7 (Statistical Soundness). The argument proceeds very similarly to the corresponding proof of adaptive statistical soundness from [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF]. We use a simple hybrid argument:

• Hyb 0 : This is the real soundness experiment where the challenger begins by sampling crs ← Setup(1 λ ) and (pk, sk) ← KeyGen(crs), where crs = (λ, s, crs HBG ), pk = pk HBG , and sk = sk HBG . The challenger gives crs and pk to A. Adversary A can then make verification queries on pairs (x, π) and the challenger responds with Verify(crs, sk, x, π). At the end of the experiment, the adversary outputs (x * , π * ) and the output of the experiment is 1 if x * / ∈ L and Verify(crs, sk, x * , π * ) = 1.

• Hyb 1 : Same as Hyb 0 except that, at the end of the experiment, after the adversary outputs its statement x * ∈ {0, 1} n and proof π * = σ * , I * , r * I * , {π * HBG,i } i∈I * , π * HBM , the challenger performs the following additional check:

-Compute r ← Open(crs HBG , σ * ). If HBG.Verify(crs HBG , sk HBG , σ * , i, r * i , π * HBG,i ) = 1 for all i ∈ I * and r I * = r * I * , then the challenger aborts the experiments and outputs ⊥.

For an adversary A, we write Hyb i (A) to denote the output distribution of an execution of experiment Hyb i with adversary A. We now show that Hyb 0 (A) s ≈ Hyb 1 (A) and that Pr[Hyb 1 (A) = 1] = negl(λ).

Lemma A.1. If Π HBG is statistically binding in binding mode, then for all adversaries A, Hyb 0 (A)

s ≈ Hyb 1 (A).
Proof. The only difference between Hyb 0 and Hyb 1 is the additional check the challenger performs when computing Verify(crs, sk, x * , π * ) which precisely coincides with the binding property of the hidden-bits generator. An adversary that causes Hyb 1 to output ⊥ with noticeable probability can break the binding property with the same probability (formally, the reduction algorithm can simulate the Verify(crs, sk, •, •) queries via oracle access to HBG.Verify(crs HBG , sk HBG , •, •, •, •) in the binding game).

Lemma A.2. For all adversaries A, Pr[Hyb 1 (A) = 1] = negl(λ).

Proof. Let x * ∈ {0, 1} n and π * = (σ * , I * , r * I * , {π * HBG,i } i∈I * , π * HBM ) be the adversary's output in Hyb 1 . For Hyb 1 (A) to output 1, the following conditions must hold:

• r I * = r * I * where r ← Open(crs HBG , σ * );

• HBM.Verify(1 λ , I * , r I * ⊕ s I * , x * , π * HBM ) = 1. Fix any commitment string σ ∈ {0, 1} and let r ← Open(crs HBG , σ) be the associated sequence of bits. For a randomly and independently sampled s r ← {0, 1} ρ , r I * ⊕ s I * is also uniformly random. By soundness of Π HBM , Pr[HBM.Verify(1 λ , I * , r

I * ⊕ s I * , x * , π * HBM )] = ε(λ).
Taking a union bound over all possible commitments σ ∈ {0, 1} , we have that

Pr[∃ σ ∈ {0, 1} : HBM.Verify(1 λ , I * , r I * ⊕ s I * , x * , π * HBM )] ≤ 2 • ε(λ) = negl(λ),
where in the above expression, r ← Open(crs HBG , σ * ). Thus, Hyb 1 (A) outputs 1 with negligible probability.

Since the distributions Hyb 0 (A) and Hyb 1 (A) are statistically indistinguishable, the probability that Hyb 0 (A) outputs 1 (i.e., A breaks soundness) is negligible.

Proof of Theorem 3.11 (Statistical Zero-Knowledge). The proof follows by essentially the same argument as the proof of Theorem 3.8. Specifically, let S HBM be the zero-knowledge simulator for Π HBM and S HBG = (S HBG,1 , S HBG,2 ) be the simulator for Π HBG in hiding mode. We construct the the zero-knowledge simulator S = (S 1 , S 2 ) for Π dvNIZK as follows:

• S 1 (1 λ ) → (st S , crs): Run (st HBG , crs HBG ) ← S HBG (1 λ , 1 ρ ) and sample s r ← {0, 1} ρ . Output st S = st HBG and crs = (λ, s, crs HBG ).

• S 2 (st S , pk, x) → π: On input st S = st HBG , pk and x ∈ {0, 1} n , run ( I, r I , π HBM ) ← S HBM (1 λ , x) and ( σ, { π HBG,i } i∈ I ) ← S HBG,2 (st HBG , pk, I, r I ⊕ s I ). Output the simulated proof π = ( σ, I, r I ⊕ s I , { π HBG,i } i∈ I , π HBM ).

To complete the proof, we use the same hybrid structure as in the proof of Theorem 3.8:

• Hyb 0 : This is the real distribution.

• Hyb 1 : Same as Hyb 0 , except the challenger uses S HBG,1 to generate the common reference string. It uses S HBG,2 to simulate the openings to the hidden-bits generator when responding to oracle queries.

• Hyb 2 : Same as Hyb 1 , except when responding to oracle queries, the challenger uses the simulator for the hidden-bits model NIZK to simulate the proofs. This is the simulated distribution.

By essentially the same argument as in the proof of Lemma 3.9, Hyb 0 and Hyb 1 are statistically indistinguishable if Π HBG satisfies statistical simulation for malicious keys. Similarly, Hyb 1 and Hyb 2 are statistically indistinguishable if Π HBM provides statistical zero-knowledge. This follows by an identical argument as in the proof of Lemma 3.10.

B Publicly-Verifiable Statistical NIZK Arguments from HBG

In this section, we show that a (publicly-verifiable) hidden-bits generator that satisfies computational binding (Definition 4.10) yields a (publicly-verifiable NIZK) that satisfies non-adaptive computational soundness. The analysis is very similar to the proof of statistical soundness (Theorem 3.7). Here, we consider a variant of Construction 3.4 that is publicly-verifiable but has just a single mode. This is essentially the construction from [START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF]. For completeness, we recall the specific construction:

Construction B.1 (NIZK from Publicly-Verifiable HBG). Let L ⊆ {0, 1} n be an NP language with associated NP relation R. We rely on the following building blocks:

• Let Π HBG = (HBG.Setup, HBG.GenBits, HBG.Verify) be a publicly-verifiable hidden-bits generator with commitments of length = (λ, ρ), where λ is the security parameter and ρ is the output length of the generator.

• Let Π HBM = (HBM.Prove, HBM.Verify) be a NIZK in the hidden-bits model for L, and let ρ = ρ(λ) be the length of the hidden-bits string for Π HBM .

We construct a publicly-verifiable NIZK Π NIZK = (Setup, Prove, Verify) for L as follows:

• Setup(1 λ ) → crs: On input λ ∈ N, sample s r ← {0, 1} ρ . Run crs HBG ← HBG.Setup(1 λ , 1 ρ , mode) and output crs = (λ, s, crs HBG ).

• Prove(crs, x, w) → π: On input crs = (λ, s, crs HBG ), x ∈ {0, 1} n , and w, compute a hidden-bits string (σ, r, {π HBG,i } i∈{1,...,ρ} ) ← HBG.GenBits(crs HBG , pk HBG ), and an HBM proof (I, π HBM ) ← HBM.Prove(1 λ , r ⊕ s, x, w). Output π = (σ, I, r I , {π HBG,i } i∈I , π HBM ).

• Verify(crs, x, π): On input crs = (λ, s, crs HBG ), x ∈ {0, 1} n , and π = (σ, I, r I , {π HBG,i } i∈I , π HBM ), output 1 if HBM.Verify(1 λ , I, r I ⊕ s I , x, π HBM ) = 1 and HBG.Verify(crs HBG , σ, i, r i , π HBG,i ) = 1 for all i ∈ I. Otherwise, output 0.

Theorem B.2 (Completeness).

If Π HBM is complete and Π HBG is correct, then Π NIZK from Construction B.1 is complete.

Proof. Follows by a similar argument as the proof of Theorem 3.5.

Theorem B.3 (Computational Soundness).

If Π HBM is statistically sound with soundness error ε(λ), Π HBG is is computationally binding (Definition 4.10), and 2 • ε = negl(λ), then Π NIZK from Construction B.1 satisfies non-adaptive computational soundness.

Proof. The proof uses a similar hybrid structure as in the proof of Theorem 3.7, except we are in the non-adaptive setting. In particular, fix a statement x / ∈ L, and let E be the extractor associated with Π HBG (from Definition 4.10). Consider the following sequence of hybrid experiments:

• Hyb 0 : This is the real soundness experiment, where the challenger begins by sampling crs ← Setup(1 λ ) and gives crs = (λ, s, crs HBG ) to A. At the end of the experiment, A outputs a proof π * and the output of the experiment is 1 if Verify(crs, x, π * ) = 1.

• Hyb 1 : Same as Hyb 0 , except the challenger samples (st E , crs HBG ) ← E 1 (1 λ , 1 ρ ) and uses crs = (λ, s, crs HBG ) in place of crs.

• Hyb 2 : Same as Hyb 1 , except at the end of the experiment, after the adversary outputs π * = σ * , I * , r * I * , {π * HBG,i } i∈I * , π * HBM , the challenger performs the following check:

-Compute r ← E 2 (st E , σ * ). If HBG.Verify( crs HBG , σ * , i, r * i , π * HBG,i ) = 1 for all i ∈ I * and r I * = r * I * , then the challenger aborts the experiments and outputs ⊥.

For an adversary A, we write Hyb i (A) to denote the output distribution of an execution of experiment Hyb i with adversary A. We now show that each adjacent pair of hybrids are computationally indistinguishable, and moreover, that Pr[Hyb 2 (A) = 1] = negl(λ).

Lemma B.4. If Π HBG satisfies computational binding, then for all efficient A, Hyb 0 (A)

c ≈ Hyb 1 (A).
Proof. Follows immediately by the CRS indistinguishability property of E.

Lemma B.5. If Π HBG satisfies computational binding, then for all efficient A, Hyb

1 (A) c ≈ Hyb 2 (A).
Proof. The only difference between Hyb 1 and Hyb 2 is the additional check the challenger performs when computing Verify(crs, x, π * ). But if A manages to output a commitment σ * and an index i ∈ [ρ] such that HBG.Verify( crs HBG , σ * , i, r * i , π * HBG,i ) = 1 and r i = r * i where r r ← E 2 (st E , σ * ), then (σ * , i, r * i , π HBG,i ) breaks the binding property of Π HBG . Hence, if Π HBG is computationally binding, then the probability that the additional check fails and the challenger aborts is negligible.

Lemma B.6. For all adversaries A, Pr[Hyb 2 (A) = 1] = negl(λ).

Proof. Follows by a similar argument as the proof of Lemma A.2.

Thus, for all efficient adversaries A, Hyb 0 (A) c ≈ Hyb 2 (A) and Pr[Hyb 2 (A) = 1] = negl(λ). Thus, the probability that Hyb 0 (A) outputs 1 (meaning that A breaks non-adaptive soundness) is also negligible.

Theorem B.7 (Statistical Zero-Knowledge). If Π HBM satisfies statistical zero-knowledge and Π HBG provides statistical simulation, then Π NIZK from Construction B.1 is statistical zero-knowledge.

Proof. Follows by a similar argument as the proof of Theorem 3.8.

C Analysis of Constructions from k-Lin (Section 4)

In this section, we provide the analysis of the dual-mode hidden-bits generators from Section 4.

C.1 Analysis of Construction 4.3 (Dual-Mode HBG from k-Lin)

In this section, we give the proofs for the correctness and security theorems (Theorems 4.4 to 4.8) for the dual-mode hidden-bits generator from the k-Lin assumption (Construction 4.3).

where z i = V(s i a + b i ). The adversary can then make queries to the verification oracle. On each query (σ, i, r i , π i ), the challenger replies with Verify(crs, sk, σ, i, r i , π i ). At the end of the game, the adversary outputs a tuple (σ * , i * , r * , π * ). The output of the experiment is 1 if r * = r i where r ← Open(crs, σ * ) and Verify(crs, sk, σ * , i * , r * , π * ) = 1.

• Hyb 1 : Same as Hyb 0 , except the challenger samples x 1 , . . . , x ρ r ← Z k p and computes z i ← Vx i . It then samples a r ← Z p and sets b i ← x i -s i a.

• Hyb 2 : Same as Hyb 1 , except the challenger implements Verify(crs, sk, σ, i, r i , π i ) by computing Verify * (σ, r i , π i , s i , x i ), where on input σ = g c T , r i ∈ {0, 1},

π i = (g t i , g u i ), s i ∈ Z k p , x i ∈ Z k p , Verify * (σ, π i , r i , s i , x i ) outputs 1 if and only if r i = H(g t i ) and t i = c T s i and u i = c T x i .
For an adversary A, we write Hyb i (A) to denote the output of Hyb i with adversary A. We show that the output distributions of each adjacent pair of hybrid experiments are statistically indistinguishable, and moreover, Hyb 2 (A) output 0 with overwhelming probability for all adversaries A. Lemma C.2. For all adversaries A, Hyb 0 (A) ≡ Hyb 1 (A).

Proof. Follows by construction.

Lemma C.3. For all adversaries A, Hyb

1 (A) s ≈ Hyb 2 (A).
Proof. We use a hybrid argument. The challenger evaluates Verify at most Q + 1 times, where Q = poly(λ) is the bound on the number of queries the adversary makes (the challenger evaluates Verify also at the end to determine the output of the experiment). We define a sequence of intermediate hybrids Hyb 1,j for j ∈ {0, . . . Q + 1}, where in hybrid Hyb 1,j , the first j queries are handled according to the specification in Hyb 2 while the remaining queries are handled according to the specification in Hyb 1 . By construction, Hyb 1 ≡ Hyb 1,0 and Hyb 2 ≡ Hyb 1,Q+1 . Consider Hyb 1,j-1 and Hyb 1,j for j ∈ [Q + 1]. These two experiments only differ in how the challenger computes the output for the j th Verify call. Let (crs, sk, σ, i, r i , π i ) be the arguments to the j th Verify call, where σ = g c T and π i = (g t i , g u i ). Consider the behavior in Hyb 1,j-1 . Here, the verifier accepts only if

r i = H(g t i ) and u i = t i a + c T b i = c T (s i a + b i ) + (t i -c T s i )a = c T x i + (t i -c T s i )a.
We consider two possibilities:

• If t i = c T s i ,
then Verify in Hyb 1,j-1 outputs 1 if and only if r i = H(g t i ) and u i = c T x i . This is identical to the behavior of Verify * in Hyb 1,j .

• If t i = c T s i , then the output in Hyb 1,j-1 is 1 only if a = (u i -c T x i )(t i -c T s i ) -1 .
In Hyb 1,j-1 , neither the public parameters (crs and pk) nor the responses to the first j -1 queries depend on the value of a (in particular, Verify * is independent of a, and thus, leaks no information about a). Thus, the challenger can sample a r ← Z p after the adversary has chosen c, t i , and u i . In this case, Verify outputs 1 with probability 1/p = negl(λ). Thus, with overwhelming probability, the output in Hyb 1,j-1 is 0. This is the output of Verify * in Hyb 1,j .

Since the outputs of Verify in Hyb 1 and Verify * in Hyb 2 are statistically indistinguishable for each query, the claim now follows by a hybrid argument. To conclude the proof, it suffices to show that the output in Hyb 2 is always 0. Let (σ * , i * , r * , π * ) be the adversary's output in Hyb 2 . The output in Hyb 2 is 1 only if Verify(crs, sk, σ * , i * , r * , π * ) = 1 and r i * = r * where r ← Open(crs, σ * ). Write σ * = g (c * ) T and π * = (g t * i , g u * i ). By definition of Open, r i * = H(g (c * ) T s i ). In Hyb 3 , the Verify function outputs 1 only if t * i = (c * ) T s i and

r * = H(g t * i ) = H(g (c * ) T s i ) = r i * .
But then, the output of Hyb 2 is 0. Since the output of Hyb 0 and Hyb 2 are statistically indistinguishable, this means that the output in Hyb 0 is also 0 with overwhelming probability.

Theorem 4.7 now follows by a hybrid argument.

Proof of Theorem 4.8 (Statistical Simulation). We construct a simulator S = (S 1 , S 2 ) as follows:

• S 1 (1 λ , 1 ρ ) → (st S , crs, pk, sk): Sample G = (G, p, g) ← GroupGen(1 λ ), H r ← H, V r ← Z (ρ+k)×k p , w 1 , . . . , w ρ r ← Z ρ+k p , a r ← Z p , and b 1 , . . . , b ρ r ← Z k p . For each i ∈ [ρ], let z i ← w i a + Vb i .
In the following, we will write

W = [ w 1 | • • • | w ρ | V ] ∈ Z (ρ+k)×(ρ+k) p . (C.1)
Output crs = (G, H, g V , g w 1 , . . . , g wρ ), pk = (g z 1 , . . . , g zρ ), sk = (a, b 1 , . . . , b ρ ), and st S = ( crs, pk, W)

• S 2 (st S , I, r I ) → ( σ, { π i } i∈I ): On input st S = ( crs, pk, W) where crs = (G, H, g V , g w 1 , . . . , g wρ ) and pk = (g z 1 , . . . , g zρ ), a set of indices I ⊆ [ρ], and a bitstring r I ∈ {0, 1} |I| , the simulator samples a vector t ∈ Z ρ p as follows:

-For each i ∈ I, sample t i r ← Z p conditioned on H(g t i ) = r i . Specifically, the simulator repeatedly samples t i r ← Z p until finding one that satisfies H(g t i ) = r i . If no such t i is found after λ iterations, then the simulator aborts and outputs ⊥.

-For the remaining indices i ∈ [ρ] \ I, sample t i r ← Z p . Next, it samples c r ← Z k p and sets y T ← [ t T | c T ] • W -1 (outputting ⊥ if W is not invertible). It computes σ = g c T and g u i ← g y T z i for each i ∈ I. It output σ and { π i } i∈I where π i = (g t i , g u i ).
To show that ExptHide[A, 0] and ExptHide[A, 1] are statistically indistinguishable, we use a hybrid argument:

• Hyb 0 : This is the distribution in ExptHide[A, S, 0]. Namely, the challenger begins by sampling crs ← Setup(1 λ , 1 ρ , hiding) and (pk, sk) ← KeyGen(crs). For each challenge query, the challenger first samples (σ, r, {π i } i∈[ρ] ) ← GenBits(crs, pk) and gives r to A to receive a set I ⊆ [ρ]. It then replies with σ and {π i } i∈I .

• Hyb 1 : Same as Hyb 0 , except the challenger computes (st S , crs, pk, sk) ← S 1 (1 λ , 1 ρ ) and uses crs, pk, and sk in place of crs, pk, and sk, respectively.

Specifically, the challenger samples

V r ← Z (ρ+k)×k p , w 1 , . . . , w ρ r ← Z ρ+k p , a r ← Z p , and b 1 , . . . , b ρ r ← Z k p . For each i ∈ [ρ]
, it sets z i ← w i a+Vb i . It sets crs = (G, H, g V , g w 1 , . . . , g wρ ), pk = (g z 1 , . . . , g zρ ), and sk = (a, b 1 , . . . , b ρ ). On each challenge query, the challenger samples y r ← Z ρ+k p and computes [ t T | c T ] ← y T W, r i ← H(g t i ), and

g u i ← g y T z i for each i ∈ [ρ],
where W is defined in Eq. (C.1). The challenger sends r to the adversary and receives a set I ⊆ [t]. The challenger replies with σ = g c T and {π i } i∈I = {(g t i , g u i )} i∈I .

• Hyb 2 : Same as Hyb 1 , except when responding to the challenge queries, instead of sampling y r ← Z ρ+k p , the challenger samples t

r ← Z ρ p and c r ← Z k p . It sets y T ← [ t T | c T ] • W -1 (and outputs ⊥ if W is not invertible).
All remaining components are constructed as in Hyb 1 .

• Hyb 3 : Same as Hyb 2 except when responding to the challenge queries, the challenger first samples r

r ← {0, 1} k . For each i ∈ [ρ], it samples t i r ← Z p conditioned on H(g t i ) = r i .
The challenger uses the same rejection procedure for this step as in S 2 to implement this. It samples c r ← Z k p and the remaining components as in Hyb 2 .

• Hyb 4 : Same as Hyb 3 except when responding to the challenge queries, the challenger samples t after it receives the challenge set. In particular, on each query, after the challenger receives the set

I ⊆ [ρ], it samples t i r ← Z p conditioned on H(g t i ) = r i if i ∈ I and t i r ← Z p otherwise.
All remaining components are constructed as in Hyb 3 . This is the distribution in ExptHide[A, S, 1].

For an adversary A, we write Hyb i (A) to denote the output distribution of experiment Hyb i with adversary A. We now show that for all adversaries A, the output distributions of each consecutive pair of hybrids are either statistically indistinguishable or identically distributed.

Lemma C.4. For all adversaries A, Hyb 0 (A) ≡ Hyb 1 (A).

Proof. Since S 1 (1 λ , 1 ρ ) samples crs, pk, and sk using the same procedure as Setup and KeyGen, the output distributions of hybrids Hyb 0 and Hyb 1 are identically distributed.

Lemma C.5. For all adversaries A, Hyb 1 (A) s ≈ Hyb 2 (A).

Proof. With overwhelming probability, W is full-rank and thus invertible. In this case, the distributions of y in Hyb 1 and Hyb 2 are identical. Thus, the output distributions of Hyb 1 and Hyb 2 are statistically indistinguishable.

Lemma C.6. If H is statistically uniform, then for all adversaries A, Hyb 2 (A)

s ≈ Hyb 3 (A).
Proof. Since H is sampled from a hash family that satisfies statistical uniformity, the distribution of H(g t i ) when t i r ← Z p is statistically close to uniform over {0, 1}. Thus, in Hyb 2 , each bit r i is statistically close to uniform. It suffices to argue that the sampling algorithm in Hyb 3 does not abort. In this is the case, then the two distributions are statistically close. Again, using the fact that H is statistically uniform, for a random t i r ← Z p , Pr[H(g t i ) = r i ] ≥ 1/2 -negl(λ) for any r i ∈ {0, 1}. Thus, with overwhelming probability, the challenger successfully finds a t i after λ independent attempts. Since ρ = poly(λ) and the adversary makes at most q = poly(λ) queries, the claim now follows by a union bound.

Lemma C.7. For all adversaries A, Hyb 3 (A) ≡ Hyb 4 (A).

Proof. First, the challenger's first message to the adversary in both experiments is ( crs, pk, sk) where crs = (G, H, g V , g w 1 , . . . , g wρ ), pk = (g z 1 , . . . , g zρ ), and sk = (a, b 1 , . . . , b ρ ). These components are identically distributed in the two experiments. We consider the challenge queries. On each challenge query, in both Hyb 3 and Hyb 4 , the challenger sends the adversary a random string r r ← {0, 1} k . To conclude the proof, we argue that the challenger's response to each challenge query is identically distributed in the two experiments. In particular, after the adversary outputs a set I ⊆ [ρ], the challenger replies with a commitment σ = g c T and a collection of proofs {π i } i∈I = {(g t i , g u i )} i∈I . We show that c, t i , u i for i ∈ I in Hyb 3 and Hyb 4 are identically distributed:

• In Hyb 3 and Hyb 4 , for all i ∈ I, the challenger samples t i r ← Z p subject to H(g t i ) = r i . Thus, the distribution of t i for each i ∈ I is identically distributed in the two experiments.

• In Hyb 3 and Hyb 4 , c ∈ Z k p is independent and uniformly distributed.

• In Hyb 3 and Hyb 4 ,

u i = y T z i = y T (w i a + Vb i ) = t i a + c T b i . Since a, b i , t i , c
are all identically distributed in the two experiments for i ∈ I, we conclude that u i is identically distributed in Hyb 3 and Hyb 4 for all i ∈ I.

Theorem 4.8 now follows by a hybrid argument.

Remark C.8 (Perfect Simulation in Hiding Mode). A modified version of Construction 4.3 can be

shown to satisfy perfect simulation in hiding mode. Specifically, we make the following adjustments:

• Modify Setup(1 λ , 1 ρ , hiding) so that it always outputs V, w 1 , . . . , w ρ such that the matrix W in Eq. (C.1) is full-rank. This property already holds with overwhelming probability, so this only introduces a negligible loss to the CRS indistinguishability property. With this change, Hyb 1 and Hyb 2 in the proof of Theorem 4.8 are identically distributed.

• Replace the hash family H with one that is perfectly uniform and one where there is a procedure to exactly sample t

i r ← Z p such that H(g t i ) = r i .
Currently, H is a hash family from a prime-order group G to {0, 1}, so perfect uniformity is impossible. However, we can modify the construction to use a hash function with domain G \ {g 0 }, where g 0 ∈ G denotes the identity element. To enforce this, we modify the GenBits algorithm to sample y r ← Z ρ+k p subject to the restriction that t i = (y T W) i = 0 for all i ∈ [ρ]. A randomly-sampled y, will satisfy this property with overwhelming probability (since 1/p = negl(λ)), and thus, this can only change the distribution of GenBits by a negligible amount. With this modification and assuming that H is a perfectly uniform family of hash functions from G \ {[0]} to {0, 1}, and that there is an efficient algorithm to sample t i r ← Z p such that H(g t i ) = r i , then hybrids Hyb 2 and Hyb 3 in the proof of Theorem 4.8 are identically distributed. As we show in Section 6, it is straightforward to construct a hash function with these properties when G is an elliptic curve group over a finite field (see Remark 6.3).

With these modifications, each pair of adjacent hybrids in the proof of Theorem 4.8 is identically distributed, and we conclude that Π HBG satisfies perfect simulation in hiding mode. Combined with Construction 3.4, this gives a dual-mode NIZK with perfect zero-knowledge in hiding mode.

Binding. We use a hybrid argument:

• Hyb 0 : This is the real binding experiment. Namely, the challenger starts by sampling

(st E , crs) ← Setup(1 λ , 1 ρ ) and gives crs = G, H, g V 1 , g âT 2 , g D 2 , g w i 1 , g Z i 1 , g Bi 2 i∈[ρ]
to the adversary. Here, w i = Vs i , âT = a T D, Z i = w i a T + VB i , and Bi = B i D. The adversary then outputs a tuple (σ * , i * , r * , π * ). The output of the experiment is 1 if r * = r i where r ← E 2 (st E , σ * ) and Verify( crs, σ * , i * , r * , π * ) = 1. Otherwise, the output is 0.

• Hyb 1 : Same as Hyb 0 except after the adversary outputs its tuple (σ * , i * , r * , π * ), the challenger performs the following additional check. First, write σ * = g

(c * ) T 1 and π * = (g t * 1 , g (u * ) T 1
). The output of Hyb 1 is 0 if Verify( crs, σ * , i * , r * , π * ) = 1 and t * a T + (c * ) T B i * = (u * ) T . Otherwise, the output of Hyb 1 is computed as in Hyb 0 .

We write Hyb i (A) to denote the output of experiment Hyb i with adversary A. To complete the proof, we show that for all efficient adversaries A, the output distributions of Hyb 0 (A) and Hyb 1 (A) are computationally indistinguishable, and moreover, that Hyb 1 (A) outputs 1 with negligible probability. This means that the output in Hyb 0 (the real binding experiment) is 1 with negligible probability, which proves the claim.

Lemma C.9. Suppose the k-KerLin assumption holds in G 2 with respect to PairingGroupGen. Then, for all efficient adversaries A, Hyb 0 (A)

c ≈ Hyb 1 (A).
Proof. The only difference between Hyb 0 (A) and Hyb 1 (A) is the additional check the challenger performs at the end of the experiment. Suppose there exists an efficient adversary A such that Pr[Hyb 0 (A) = 1] > Pr[Hyb 1 (A) = 1] + ε for some non-negligible ε. We use A to construct an adversary B that breaks the k-KerLin assumption:

1. Algorithm B receives the k-KerLin challenge G = (G 1 , G 2 , G T , p, g 1 , g 2 ,
crs = G, H, g V 1 , g a T D 2 , g D 2 , g Vs i 1 , g Vs i a T +VB i 1 , g B i D 2 i∈[ρ] .
Note that B can efficiently compute the components g a T D 2 and g B i D 2 from the challenge component g D 2 since it knows a and B i . The challenger gives crs to A.

Algorithm

A outputs σ * = g (c * ) T 1 , i * ∈ [ρ], r * ∈ {0, 1}, and π * = g t * 1 , g (u * ) T 1 . 3. Algorithm B outputs the group element g t * a T +(c * ) T B i * -(u * ) T 1
. This can be computed efficiently

given g t * 1 , g (c * ) T 1 , g (u * ) T 1
, a, and B i * , all of which are known to B.

By construction, B perfectly simulates crs according to the specification in Hyb 0 . Thus, with probability ε, algorithm A will output g

(c * ) T 1 , g t * 1
, and g

(u * ) T 1
such that Verify( crs, σ * , i * , r * , π * ) = 1 and t * a T + (c * ) T B i * = (u * ) T . If the output of Verify is 1, then it must be the case that

e g t * 1 , g a T D 2 • e g (c * ) T 1 , g B i * D 2 = e g (u * ) T 1 , g D 2 ,
or equivalently,

t * a T D + (c * ) T B i * D = (t * a T + (c * ) T B i * )D = (u * ) T D, This means that t * a T + (c * ) T B i * -(u * ) T D = 0. Since t * a T + (c * ) T B i * = (u * ) T , this means that g t * a T +(c * ) T B i * -(u * ) T 1
is a valid solution to the k-KerLin challenge. Thus, B breaks k-KerLin with the same advantage ε.

To complete the proof, it suffices to show that in Hyb 1 , the output is 0 with overwhelming probability. We show that this is the case for all (possibly unbounded) adversaries A. Our analysis will rely on the following claim from [KW15, Lemma 2]: . Then, for all (possibly unbounded) adversaries A, if we sample

K r ← Z n×(k+1) p and (z, y) ← A(M T K, KD), Pr[y / ∈ span(M) ∧ z T = y T K] ≤ 1/p. To complete the proof, let crs = G, H, g V 1 , g â 2 , g D 2 , g w i 1 , g Z i 1 , g Bi 2 i∈[ρ]
be the simulated CRS in Hyb 1 , and let (σ * , i * , r * , π * ) be the adversary's output, where σ * = g

(c * ) T 1 and π * = (g t * 1 , g (u * )T 1
). The state st E is st E = (H, s 1 , . . . , s k ). In this case, w i = Vs i , âT = a T D, Z i = w i a T + VB i , and Bi = B i D. We now show that with overwhelming probability, the output of Hyb 1 is 0:

• If Verify( crs, σ * , i * , r * , π * ) = 0, then the output in Hyb 1 is 0 by definition.

• Suppose t * = (c * ) T s i * . Then, if Verify( crs, σ * , i * , r * , π * ) = 1, it must be the case that r * = H(g t * 1 ) = H(g (c * ) T s i * 1
). Let r ← E 2 (st E , σ * ). By definition r i = H(g

(c * ) T s i * 1
). But in this case, r * = r i , and the output in Hyb 1 is 0.

• Suppose that t * = (c * ) T s i * . Here, we will rely on Lemma C.10. Let w ∈ Z ρ(ρ+k) p be the vector formed by stacking w 1 , . . . , w ρ , and define matrices K and M as follows:

K =      a T B 1 . . . B ρ      ∈ Z (ρk+1)×(k+1) p and M T = [ w | I ρ ⊗ V ] ∈ Z ρ(ρ+k)×(ρk+1) p .
By construction, observe that all of the group elements in crs are a function of the components of M (i.e., the components V, w i ), D, M T K (i.e., Z i ), and KD (i.e., â, Bi ). Thus, by Lemma C.10, over a uniform choice of K (correspondingly, over a random choice of the verification parameters a, B i ), no adversary A (given M, D, M T K, and KD) can output y and u * such that y / ∈ span(M) and (u * ) T = y T K, except with negligible probability.

Consider y T = [ t * | e T i * ⊗ (c * ) T ] ∈ Z ρ+1 p
, where e i * ∈ Z ρ p denotes the (i * ) th basis vector. Since t * = (c * ) T s i * , y / ∈ span(M), so by Lemma C.10, Pr[y T K = (u * ) T ] = negl(λ). Since y T K = t * a T + (c * ) T B i * , this means that with overwhelming probability,

t * a T + (c * ) T B i * = (u * ) T .
In this case, if Verify( crs, σ * , i * , r * , π * ) = 1, then the output in Hyb 1 is 0 by definition. (And if the output of Verify is 0, the output in Hyb 1 is also 0). With overwhelming probability, the output of Hyb 1 in this case is 0.

If there is some j ∈ S i where t j = c T s j , then we can argue (as in the proof of Lemma C.3) that with overwhelming probability over the choice of a, the verifier in Hyb 1 outputs 0. Conversely, if t j = c T s j for all j ∈ S i , then Verify and Verify * behave identically, and the claim follows. Finally, by a similar argument as in the proof of Theorem 4.7, the output of Hyb 2 is always 0.

Proof of Theorem 4.23 (Statistical Simulation). We construct a simulator S = (S 1 , S 2 ) as follows:

• S 1 (1 λ , 1 ρ ) → (st S , crs): Sample G = (G, p, g) ← GroupGen(1 λ ), H r ← H, V r ← Z ( +k)×k p , w 1 , . . . , w r ← Z +k p
exactly as in Setup(1 λ , 1 ρ , hiding). In the following, we will write

W = [ w 1 | • • • | w | V ] ∈ Z ( +k)×( +k) p .
Output crs = (G, H, g V , g w 1 , . . . , g w ), and st S = ( crs, W)

• S 2 (st S , pk, I, r I ) → ( σ, { π i } i∈I ): On input the simulation state st S = ( crs, W) where crs = (G, H, g V , g w 1 , . . . , g w ), a public key pk = (g z 1 , . . . , g z ), a set of indices I ⊆ {0, 1} k , and a bitstring r I ∈ {0, 1} |I| , the simulator samples a seed s r ← {0, 1} κ and computes ( Ŝ1 , . . . , Ŝρ , α) ← G(s). For each i ∈ I, it computes the shifted sets

S i ← {j + •(i-1) | j ∈ Ŝi }.
Then, it samples a vector t ∈ Z p as follows:

-For each i ∈ I, first sample t i r ← Z p subject to H(g t i ) = r i . Specifically, the simulator repeatedly samples t i r ← Z p until finding one that satisfies H(g t i ) = r i . If no such t i is found after λ iterations, then the simulator aborts and outputs ⊥. Then for j ∈ S i , sample t j r ← Z p subject to the constraint that j∈S i α j t j = t i .

-For all of the remaining indices j

∈ [ ] \ i∈I S i , sample t j r ← Z p . Next, it samples c r ← Z k p and computes y T ← [ t T | c T ] • W -1 (outputting ⊥ if W is not invertible).
It computes g u j ← g y T z j for each j ∈ S i and i ∈ I. Finally, for each i ∈ I, it sets π i = {(j, g t j , g u j )} j∈S i . Finally, it outputs σ = (s, g c T ) and { π i } i∈I .

To show that ExptHide[A, 0] and ExptHide[A, 1] are statistically indistinguishable, we use a hybrid argument:

• Hyb 0 : This is the distribution in ExptHide[A, S, 0]. Namely, the challenger begins by sampling crs ← Setup(1 λ , 1 ρ , hiding). It gives crs to A to receive a public key pk. For each challenge query, the challenger samples (σ, r, {π i } i∈[ρ] ) ← GenBits(crs, pk) and gives r to A to receive a set I ⊆ [ρ]. It then replies with σ and {π i } i∈I .

• Hyb 1 : Same as Hyb 0 except the challenger computes (st S , crs) ← S 1 (1 λ , 1 ρ ) and uses crs in place of crs. Everything else proceeds identically to Hyb 0 . Specifically, in this experiment, the challenger samples G, H, and V, w 1 , . . . , w as specified by S 1 and sets crs = (G, H, g V , g w 1 , . . . , g w ). It gives crs to the adversary and receives a public key pk = (g z 1 , . . . , g z ). Let Z ∈ Z ( +k)× p be the matrix whose columns are z 1 , . . . , z . On a challenge query, the challenger proceeds as follows:

1. Sample s r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s). For each i ∈ [ρ], compute S i ← {j + • (i -1) | j ∈ Ŝi }. 2. Sample y r ← Z +k p and compute [ t T | c T ] ← y T W, u T ← y T Z. 3. For each i ∈ [ρ], compute t i ← j∈S i g α j t j , r i ← H(t i ) and π i ← {(j, g t j , g u j )} j∈S i .
4. The challenger gives r ∈ {0, 1} ρ to A and receives a set I ⊆ [ρ].

5. The challenger replies with σ = (s, g t +1 ) = (s, g c T ) and the set {π i } i∈I .

• Hyb 2 : Same as Hyb 1 , except when responding to the challenge queries, instead of sampling y

r ← Z +k p , the challenger instead samples t r ← Z p and c r ← Z k p . It sets y T ← [ t T | c T ] • W -1 (and outputs ⊥ if W is not invertible).
All remaining components are constructed as in Hyb 1 .

• Hyb 3 : Same as Hyb 2 , except when responding to the challenge queries, the challenger first samples t

r ← Z ρ p . Next, for each i ∈ [ρ] and j ∈ S i , it samples t j r ← Z p subject to the constraint that j∈S i α j t j = t i . For indices j ∈ [ ] \ i∈[ρ] S i , sample t j r ← Z p .
• Hyb 4 : Same as Hyb 3 , except when responding to the challenge queries, the challenger first samples r r ← {0, 1} ρ . Then, for each i ∈ [ρ], it samples t i r ← Z p conditioned on H(t i ) = r i . All remaining components are constructed as in Hyb 3 .

• Hyb 5 : Same as Hyb 4 except when responding to the challenge queries, the challenger samples t ∈ Z p after it receives the challenge set. In particular, on each query, after the challenger receives the set I ⊆ [ρ], it samples t as follows:

-

For each i ∈ I, first sample t i r ← Z p subject to H(g t i ) = r i . Then, for j ∈ S i , sample t j r ← Z p subject to the constraint that j∈S i α j t j = t i .
-For all of the remaining indices j

∈ [ + 1] \ i∈I S i , sample t j r ← Z p .
After sampling t using the above procedure, the simulator constructs the remaining components as in Hyb 4 . This is the distribution in ExptHide[A, S, 1].

For an adversary A, we write Hyb i (A) to denote the output of hybrid Hyb i with adversary A. In the following, we will show that the output distribution of each pair of adjacent experiments is statistically indistinguishable (or identically distributed). Our analysis will rely on the following statistical property on the output of a secure PRG: Claim C.11. Suppose G is a secure PRG, and take s r ← {0, 1} κ . Let ( Ŝ1 , . . . , Ŝρ , α) ← G(s). Then, with overwhelming probability over the choice of s, the following properties hold:

• For any i ∈ [ρ ], Pr[α i = 0] = negl(λ).
• Let A ∈ Z × p be any fixed matrix and let I ⊆ [ρ] be any fixed set of indices. For each i ∈ I, let S i ← {j + • (i -1) | j ∈ Ŝi } be the shifted set of indices, and define

J = {j ∈ S i for some i ∈ I | j ∈ [ ]} ⊆ [ ].
Let  ∈ Z ×λ|I| p be the submatrix of A formed by taking only the columns of A indexed by J. For i ∈ [ρ], define α (i) ∈ Z p as follows:

α (i) j = α j+ •(i-1) if j ∈ Ŝi 0 otherwise.
By construction, α (i) contains exactly λ non-zero entries (as specified by the set Ŝi ). Then, for any i ∈ [ρ] \ I,

Pr[α (i) ∈ span( Â)] = Pr[∃v ∈ Z λ|I| p : α (i) = Âv] = negl(λ).
Proof. Both properties above are efficiently-checkable given ( Ŝ1 , . . . , Ŝρ , α), the matrix A, and the set of indices I. It suffices to show that both hold with overwhelming probability when ( Ŝ1 , . . . , Ŝρ , α)

r ← T ρ λ, × Z ρ p .
The claim then follows by PRG security. We show each property below:

• Since α r ← Z ρ
p , α i = 0 with probability 1/p = negl(λ).

• Let  be the matrix defined above, and let âT j ∈ Z λ|I| p denote the j th row of Â. Let n = rank( Â) ≤ λ |I| ≤ λρ = /3. This means that there exists a collection of indices j 1 , . . . , j n ∈ [ ] such that the collection {â T j 1 , . . . , âT jn } is linearly independent and span( ÂT ) = span({â T j 1 , . . . , âT jn }). By construction,  only depends on A and the sets Ŝi where i ∈ I. This means that we can sample the sets Ŝi where i / ∈ I after fixing  and the set of indices {j 1 , . . . , j n }. In this case, since Ŝi

r ← T λ, , Pr[ Ŝi r ← T λ, : Ŝi ⊆ {j 1 , . . . , j n }] ≤ n λ λ ≤ ne λ = negl(λ),
since n ≤ /3. Thus, for any i ∈ [ρ]\I, there exists an index j * ∈ Ŝi where j * / ∈ {j 1 , . . . , j n } with overwhelming probability. In addition, since âT j ∈ span( ÂT ), there exist scalars β 1 , . . . , β n ∈ Z p such that âT j * = τ ∈[n] β τ âT jτ . This means that if there exists v ∈ Z λ|I| p such that α (i) = Âv, then α (i)

j * = âT j * v = τ ∈[n] β τ âT jτ v = τ ∈[n] β τ α (i)
jτ .

Since j * ∈ Ŝi , by construction, α

j * = α j * + •(i-1) , which is uniform over Z p and independent of β τ and α

(i) = Âv] = Pr   α (i) j * = τ ∈[n] β τ α (i) jτ   = 1 p = negl(λ).
We will also use the following simple fact on linear independence.

Claim C.12. Take any matrix A ∈ Z m×n p and any vector v ∈ Z m p where v / ∈ span(A). Then, for any γ ∈ Z p , the following distributions are identical:

{t r ← Z m p : (A, v, γ, t T A)} ≡ {t r ← {t ∈ Z m p | t T v = γ} : (A, v, γ, t T A)}
Proof. Follows immediately from the fact that v is not in the span of A.

Lemma C.13. For all adversaries A, Hyb 0 (A) ≡ Hyb 1 (A).

• The commitment vector c is independently and uniformly sampled from Z k p in both experiments.

• For i ∈ I, t i is sampled identically in the two experiments (namely, t i r ← Z p subject to H(g t i ) = r i ). Correspondingly, the vectors t (i) for all i ∈ I are identically distributed.

It suffices to show that in Hyb 4 and Hyb 5 , the components {u j } j∈S i for all i ∈ I are statistically indistinguishable (given all of the other components in the adversary's view). In both experiments,

u T = y T Z = [ t T | c T ] • W -1 Z. Let A = W -1 Z =      A (1)
. . .

A (ρ) A      ∈ Z ( +k)× , p
where

A (i) ∈ Z × p and A ∈ Z k× p
. This is a fixed matrix (determined by the CRS and the adversary's choice of public key). Moreover, the adversary's choice of indices i ∈ I is fixed before the challenger samples the commitment and the openings. Let

J = {j ∈ S i for some i ∈ I | j ∈ [ ]}
be the set of indices that appear in some set S i for i ∈ I. Let  ∈ Z . With this, we can write

[ t T | c T ] • Â = i∈[ρ] (t (i) ) T Â(i) + c T Â ∈ Z λ|I| p (C.2)
Since c and all of the t (i) are sampled independently, we can consider each summand individually:

• If i ∈ I, then as argued above, t (i) is identically distributed in Hyb 4 and Hyb 5 . Since  is a fixed matrix (independent of t), the products (t (i) ) T Â(i) are also identically distributed.

• If i / ∈ I, then the t (i) in the two experiments are sampled from different distributions. In Hyb 4 ,

t (i) is uniform over Z p subject to j∈[ ] α (i) j t (i) j = t i while, in Hyb 5 , t (i) is uniform over Z p . Since i / ∈ I and A (i) ∈ Z ×
p is a fixed matrix, we can appeal to Claim C.11 to conclude that the probability that α (i) ∈ span Â(i) is negligible. By Claim C.12, this means that with overwhelming probability, the distribution of t (i) T Â(i) is statistically indistinguishable in Hyb 4 (where t (i) is uniform subject to a linear constraint α (i) / ∈ span( Â(i) )) and Hyb 5 (where t (i) is uniform).

• As argued above, c is identically distributed in the two experiments (and independent of Â).

Thus, c T Â is identically distributed in the two experiments.

Since every term in Eq. (C.2) is either statistically indistinguishable or identically distributed in the two experiments, we conclude that [ t T | c T ] • Â is also statistically indistinguishable. Based on the above analysis, the adversary's view in each challenge query is statistically indistinguishable in Hyb 4 and Hyb 5 . Since the adversary makes at most a polynomial number of challenge queries, the claim follows by a hybrid argument.

Since each consecutive pair of hybrid experiments is statistically indistinguishable (or identically distributed), the claim follows.

D Analysis of Constructions from QR (Section 5)

In this section, we provide the analysis of the dual-mode hidden-bits generators from Section 5.

D.1 Analysis of Construction 5.3 (Dual-Mode HBG from QR)

In this section, we give the proofs for the correctness and security theorems (Theorems 5.4 to 5.8) for the dual-mode hidden-bits generator from QR (Construction 5.3).

Proof of Theorem 5.4 (Correctness). Fix λ ∈ N, a polynomial ρ = ρ(λ), an index i ∈ [ρ], and a mode mode ∈ {binding, hiding}. Let crs ← Setup(1 λ , 1 ρ , mode), (pk, sk) ← KeyGen(crs), and (σ, r, {π i } i∈[ρ] ) ← GenBits(crs, pk). By construction, crs = (N, g, h, H, g v , g s 1 v h ŵ1 , . . . , g sρv h ŵρ ), for some vectors v ∈ Z ρ p q and ŵ1 , . . . ,

ŵρ ∈ Z ρ 2 . Then sk = {a τ , b τ,i } τ ∈[T ],i∈[ρ] and pk = {z τ,i } τ ∈[T ],i∈[ρ] = {(g s i v h ŵi ) aτ (g v ) b τ,i } τ ∈[T ],i∈[ρ] = {g (aτ s i +b τ,i )v h aτ ŵi } τ ∈[T ],i∈[ρ] .
Next, we have that σ = c = j∈[ρ] g v j y j = g y T v , r i = LEQ(t i , t i h) and π i = (t i , u i ), where

t i = j∈[ρ]
(g s i v j h ŵi,j ) y j = g s i y T v h y T ŵi , and u i = H(u 1,i , . . . , u T,i ) where

u τ,i = j∈[ρ]
g (aτ s i +b τ,i v j ) h aτ ŵi,j y j = g (aτ s i +b τ,i )y T v h aτ y T ŵi for all τ ∈ [T ]. Consider now the behavior of Verify(crs, sk, σ, i, r i , π i ). By construction, r i = LEQ(t i , t i h), so it suffices to check that Eq. (5.1) holds. By construction, for each τ ∈ [T ] t aτ τ c b τ,i = (g aτ s i y T v h aτ y T ŵi )(g b τ,i y T v ) = g (aτ s i +b τ,i )y T v h aτ y T ŵi = u τ,i .

Thus, Eq. (5.1) is equivalent to checking whether u i = H(u 1,i , . . . , u T,i ), which holds by construction, and Verify outputs 1.

Proof of Theorem 5.5 (Succinctness). The size of the commitment in Construction 5.3 consists of a single element in Z * N , which has length log N = poly(λ).

• Hyb 0 : This is the real soundness experiment. The challenger samples crs ← Setup(1 λ , 1 ρ , binding) and (pk, sk) ← KeyGen(crs) and gives (crs, pk) to A. Here, crs = (N, g, h, H, g v , g s 1 v , . . . , g sρv ) and pk = {g (aτ

s i +b τ,i )v } τ ∈[T ],i∈[ρ] .
The adversary can make queries to the verification oracle, and on each query (σ, i, r i , π i ), the challenger replies with Verify(crs, sk, σ, i, r i , π i ). At the end of the game, the adversary outputs a tuple (σ * , i * , r * , π * ) and the output of the experiment is 1 if r * = r i where r ← Open(crs, σ * ) and Verify(crs, sk, σ * , i * , r * , π * ) = 1.

• Hyb 1 : Same as Hyb 0 except the challenger samples the scalars s 1 , . . . , s ρ and the secret key components a τ , b τ,i uniformly at random from Z 2p q (instead of Z N/2 ) for all τ ∈ [T ] and i ∈ [ρ].

• Hyb 2 : Same as Hyb 1 except the challenger computes Verify(crs, sk, σ, i, r i , π i ) using the following modified procedure. First, parse σ = g c h ĉ and π i = (g t i h ti , u i ), for some c, t i ∈ Z p q , ĉ, ti ∈ Z 2 , and u i ∈ {0, 1} λ . Then, the challenger does the following:

-If r i = LEQ(g t i h ti , g t i h ti +1 ), output 0.

-If ĉ = 0 or ti = 0, then output 0.

-If t i = s i c, then output 0.

-Otherwise, take any y ∈ Z ρ p q such that y T v = c. Write the public key as pk = {g z τ,i } τ ∈[T ],i∈[ρ] and output 1 if u i = H g y T z 1,i , . . . , g y T z T,i . Otherwise (or if no such y exists), output 0.

Importantly, the challenger's responses to the verification queries in Hyb 2 depend only on the public components (i.e., crs and pk).

For an adversary A, we write Hyb i (A) to denote the output distribution of an execution of experiment Hyb i with adversary A. We now show that the output distribution of each adjacent pair of hybrid experiments is statistically indistinguishable. Lemma D.2. For all adversaries A, Hyb 0 (A) s ≈ Hyb 1 (A).

Proof. The statistical distance between Uniform(Z N/2 ) and Uniform(Z 2p q ) satisfies ∆(Uniform(Z N/2 ), Uniform(Z 2p q )) = 1 -2p q N/2 = 1 -2p q 2p q + p + q = negl(λ), (D.1) since 1/p , 1/q = negl(λ). Since ρ, T = poly(λ), the claim follows by a union bound.

Lemma D.3. If H is pairwise independent, then for all adversaries A, Hyb 1 (A) s ≈ Hyb 2 (A).

Proof. In Hyb 1 and Hyb 2 , the challenger evaluates Verify at most Q + 1 times where Q = poly(λ) is the bound on the number of queries the adversary makes. For j ∈ {0, . . . , Q + 1}, let Hyb 1,j denote the experiment where the first j queries are handling according to the specification in Hyb 2 while the remaining queries are handling according to the specification in Hyb 1 . By construction, Hyb 1 ≡ Hyb 1,0 and Hyb 2 ≡ Hyb 1,Q+1 . Consider Hyb 1,j-1 and Hyb 1,j for j ∈ [Q + 1]. These two experiments only differ in how the challenger computes the output for the j th Verify call. Moreover, by construction of Hyb 1,j-1 and Hyb 1,j , all of the adversary's queries prior to the j th query are handled according to the specification in Hyb 2 , which depend only on the public components crs and pk. Let (σ, i, r i , π i ) be the arguments to the j th Verify call. Write σ = g c h ĉ and π i = (g t i h ti , u i ) for c, t i ∈ Z p q , ĉ, ti ∈ Z 2 , and u i ∈ {0, 1} λ . We consider each case individually:

• Suppose r i = LEQ(g t i h ti , g t i h ti +1 ). Then, the output in both experiments is 0.

• Suppose ĉ = 0 or ti = 0. We argue that with overwhelming probability, the output in Hyb 1,j-1 is 0. For the output to be 1 in Hyb 1,j-1 , it must be the case that u i = H(ω i ) where

ω i = (g t i h ti ) a 1 (g c h ĉ) b 1,i , . . . , (g t i h ti ) a T (g c h ĉ) b T,i ∈ J T N . (D.2)
In both Hyb 1 and Hyb 2 , the public parameters are independent of the values of a τ mod 2 and b τ,i mod 2 for all τ ∈ [T ]. This follows from the fact that a τ , b τ,i ∈ Z 2p q , and the adversary only sees elements g (aτ s i +b τ,i )v , where g generates a group of order p q (and gcd(p q , 2) = 1). Next, since a τ and b τ,i are uniform over Z 2p q , the values a τ mod 2 and b τ,i mod 2 are distributed uniformly and independently of the rest of the public parameters. Since the responses to all of the adversary's queries prior to its j th query only depend on the public parameters, the conditional distribution of a τ mod 2 and b τ,i mod 2 given the adversary's view up to the time of its j th query is uniform and independently random. Since at least one of ĉ and ti is non-zero, this means that the value of a τ ti + b τ,i ĉ mod 2 is independently and uniformly random over Z 2 , and correspondingly, the conditional min-entropy of the vector ω i from Eq. (D.2) is at least T = 2(λ + log N ). We now appeal to Lemma 2.6 to argue that the output distribution of H(ω i ) is (3p q ε)-close to uniform over {0, 1} λ where

ε = 2 -(T -λ)/2 = 2 -λ/2-log N ,
since the adversary can choose the values of c, t i ∈ Z p q and (ĉ, ti ) ∈ Z 2 2 \ {0} after seeing the hash function H. Since 3p q < N , 3p q ε < 2 -λ/2 = negl(λ), so we conclude that conditioned on the adversary's view, the distribution of H(ω i ) in Hyb 1,j-1 is statistically close to uniform over {0, 1} λ . The probability that u i = H(ω i ) is then negligibly close to 1/2 λ , and the challenger outputs 0 with overwhelming probability.

• Suppose that t i = s i c ∈ Z p q . We only need to consider the case where ĉ = 0 and ti = 0. We show that in this case, the output in Hyb 1,j-1 is 0 with overwhelming probability. For the output to be 1 in Hyb 1,j-1 in this case, we require that u i = H(ω i ) where

ω i = g a 1 t i +b 1,i c , . . . , g a T t i +b T,i c ∈ QR T N . (D.
3)

The only components in crs and pk that depend on a τ and b τ,i for τ ∈ [T ] are the public-key components g aτ s i v+b τ,i v . Let b τ ∈ Z ρ 2p q be the vector whose components are b τ,1 , . . . , b τ,ρ , and let s ∈ Z ρ 2p q be the vector whose components are s 1 , . . . , s ρ . The public parameters pk can then be expressed as a function of

Z τ = [ s | I ρ ] • a τ b τ • v T ∈ Z ρ×ρ 2p q ,
where I ρ ∈ Z ρ×ρ 2p q is the identity matrix. Namely, the components of pk consist of g Zτ for all τ ∈ [T ]. Since t i = s i c ∈ Z p q , by the Chinese remainder theorem, it must be the case that t i = s i c (mod p ) or t i = s i c (mod q ). Without loss of generality, suppose that t i = s i c (mod p ). In this case the vector [ t i | c • e i ] is linearly independent of the rows of the matrix [ s (mod p ) | I ρ ]. Since a τ , b τ are uniform over Z 2p q , the components a τ mod p and b τ mod p are uniform over Z p . By linear independence over Z p , the value of a τ t i + b τ,i c (mod p ) is uniformly random over Z p even given Z τ for all τ ∈ [T ]. As such, the conditional min-entropy of the vector ω i from Eq. (D.3) is at least T log p > T . By an analogous argument as in the previous case, we can now appeal to Lemma 2.6 and conclude that the output distribution of H(ω i ) is statistically close to uniform over {0, 1} λ , in which case the probability that u i = H(ω i ) is negligible.

• The only remaining case is when ĉ = 0 = ti , t i = s i c, and r i = LEQ(g t i , g t i h). In this case, (g

t i ) aτ (g c ) b τ,i = g (aτ s i +b τ,i )c for all τ ∈ [T ]. Since v r ← Z N/2
, with overwhelming probability, there will be some component that is invertible modulo p q . If so, there always exists y ∈ Z p q such that y T v = c. Then, in Hyb 1,j-1 , the challenger outputs 1 if and only if

u i = H g (a 1 s i +b 1,i )c , . . . , g (a T s i +b T,i )c = H g (a 1 s i +b 1,i )y T v , . . . , g (a T s i +b T,i )y T v = H g y T z 1 , . . . , g y T z T ),
where z τ,i = (a τ s i + b τ,i )v are the components in the public key. This is precisely the verification relation in Hyb 1,j .

In each case, we see that the j th call to Verify is implemented correctly with overwhelming probability in Hyb 1,j-1 and Hyb 1,j .

To complete the proof, it suffices to show that for all adversaries A, the output of Hyb 2 (A) is 0 with overwhelming probability. Let (σ * , i * , r * , π * ) be the adversary's output in Hyb 2 . The output of Hyb 2 is 1 only if Verify(crs, sk, σ * , i * , r * , π * ) = 1 and r i * = r * where r ← Open(crs, σ * ). Write σ * = g c h ĉ and π * = (g t i * h ti * , u i * ) In Hyb 2 , if Verify(crs, sk, σ * , i * , r * , π * ) = 1, it must be the case that ĉ = 0, ti * = 0, t i * = s i * c, and

r * = LEQ g t i * h ti * , g t i * h ti * +1 = LEQ g s i * c , g s i * c h .
Moreover, since ĉ = 0, r i * = LEQ(g cs i * , g cs i * h) = r * . In this case, the output in Hyb 2 is 0, and the theorem follows.

Proof of Theorem 5.8 (Statistical Simulation). We construct a simulator S = (S 1 , S 2 ) as follows:

• S 1 (1 λ , 1 ρ ) → (st S , crs, pk, sk): Sample (N, p, q) ← SampleModulus(1 λ ), where p = 2p + 1 and q = 2q + 1. Let g be a generator of QR N and h = -1. Sample a vector v r ← Z ρ N/2 , scalars s 1 , . . . , s ρ r ← Z N/2 , and a hash function H r ← H. Set crs = (N, g, h, H, g v , g s 1 v h e 1 , . . . , g sρv h eρ ).

Sample a

τ , b τ,i r ← Z N/2 for all τ ∈ [T ] and i ∈ [ρ]. Output crs, pk = {g (aτ s i +b τ,i )v h aτ e i } τ ∈[T ],i∈[ρ] , sk = {a τ , b τ,i } τ ∈[T ],i∈[ρ]
, and st S = ( crs, pk, p , q , s 1 , . . . , s ρ ).

• S 2 (st S , I, r I ) → ( σ, { π i } i∈I ): On input st S = ( crs, pk, p , q , s 1 , . . . , s ρ ) where crs = N, g, h, H, g v , g s 1 v h e 1 , . . . , g sρv h eρ and pk

= {g z τ,i h ẑτ,i } τ ∈[T ],i∈[ρ] ,
a set of indices I ⊆ [ρ], and a bitstring r I ∈ {0, 1} |I| , the simulator samples y r ← Z ρ p q . Then, for each i ∈ [ρ], it samples ŷ i ∈ Z 2 as follows:

-If i / ∈ I, sample ŷ i r ← Z 2 .
-If i ∈ I, set ŷi ∈ Z 2 to be the unique value where r i = LEQ(g s i (y ) T v h ŷi , g s i (y ) T v h ŷi +1 ).

Define y ∈ Z ρ 2p q to be the vector where y = y (mod p q ) and y = ŷ (mod 2). The simulator then sets g t i g ti = g s i y T v h ŷi and u i = H g y T z 1,i h y T ẑ1,i , . . . , g y T z T,i h y T ẑT,i .

Output σ = g y T v and { π i } i∈I where π i = (g t i h ti , u i ).

To show that ExptHide[A, S, 0] and ExptHide[A, S, 1] are statistically indistinguishable, we use a hybrid argument:

• Hyb 0 : This is the experiment ExptHide[A, S, 0]. Namely, the challenger begins by sampling crs ← Setup(1 λ , 1 ρ , hiding) and (pk, sk) ← KeyGen(crs). For each challenge query, the challenger first samples (σ, r, {π i } i∈[ρ] ) ← GenBits(crs) and gives r to A before receiving a set I ⊆ [ρ] chosen by A. It then replies with σ and {π i } i∈I .

More precisely, in this experiment, crs = N, g, h, H, g v , g s 1 v h e 1 , . . . , g sρv h eρ and pk

= {g z τ,i h ẑτ,i } τ ∈[T ],i∈[ρ] ,
where z τ,i = (a τ s i + b τ,i )v and ẑτ,i = a τ e i . On each challenge query, the challenger samples y r ← Z N/2 and computes σ = g y T v and g t i h ti = g s i y T v h y T e i and g u τ,i h ûτ,i = g y T z τ,i h y T ẑτ,i , for all τ ∈ [T ] and i ∈ [ρ]. The random bits r i satisfy r i = LEQ(g t i h ti , g t i h ti +1 ). Finally, the proofs π i are given by π i = (g t i h ti , u i ), where u i = H(g u 1,i h û1,i , . . . , g u T,i h ûT,i ).

• Hyb 1 : Same as Hyb 0 , except that the challenger computes (st S , crs, pk, sk) ← S 1 (1 λ , 1 ρ ) and uses crs, pk, and sk instead of crs, pk, and sk, respectively.

• Hyb 2 : Same as Hyb 1 , except when responding to the challenge queries, the challenger samples y

r ← Z ρ 2p q instead of y r ← Z ρ N/2 .
• Hyb 3 : Same as Hyb 2 , except when responding to the challenge queries, the challenger first samples y r ← Z ρ p q and ŷ r ← Z ρ 2 . It defines y ∈ Z ρ 2p q to be the vector where y = y (mod p q ) and y = ŷ (mod 2).

-For all of the remaining indices j ∈ [ ] \ i∈I S i , sample ŷ j r ← Z 2 . Define y ∈ Z 2p q to be the vector where y = y (mod p q ) and y = ŷ (mod 2). 4. Next, the simulator computes σ = (s, g y T v ) and t j = g s j y T v h y T e j for each j ∈ S i . Next, for each j ∈ S i and τ ∈ [T ], compute u τ,j ← k∈[ ] z y k τ,j,k , and set u j ← H(u 1,j , . . . , u T,j ). It sets π i = {(j, t j , u j )} j∈S i . 5. Output σ and { π i } i∈I .

We now use a hybrid argument to show that ExptHide[A, 0] and ExptHide[A, 1] are statistically indistinguishable:

• Hyb 0 : This is the experiment ExptHide[A, S, 0]. Namely, the challenger begins by sampling crs ← Setup(1 λ , 1 ρ , hiding), and gives crs to A. The adversary A replies with a public key pk.

For each challenge query, the challenger samples (σ, r, {π i } i∈[ρ] ) ← GenBits(crs, pk) and gives r to A before receiving a set I ⊆ [ρ] chosen by A. It then replies with σ and {π i } i∈I .

• Hyb 1 : This experiment is identical to Hyb 0 , except that the challenger computes (st S , crs) ← S 1 (1 λ , 1 ρ ) and uses crs in place of crs. Everything else proceeds identically to Hyb 0 .

Specifically, in this experiment, the challenger samples (N, p, q), H, v, s 1 , . . . , s as specified by S 1 and sets crs = (N, g, h, H, g v , g s 1 v h e 1 , . . . , g s v h e ). It gives crs to A to receive a public key pk = {z τ,i } τ ∈[T ],i∈[ ] . On a challenge query, the challenger proceeds as follows:

1. Check that z τ,i ∈ J N for all τ ∈ [T ] and i ∈ [ ], and output ⊥ otherwise. c ← g y T v and t j ← g s j y T v h y T e j and u τ,j ← k∈[ ] (z τ,j,k ) y k .

Sample s

r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s). For each i ∈ [ρ], let S i ← {j + • (i -1) | j ∈ Ŝi }.
Then, for each j ∈ [ ], compute u j ← H(u 1,j , . . . , u T,j ). 4. For each i ∈ [ρ], compute t i ← j∈S i t α j j and r i ← LEQ(t i , t i h) and π i ← {(j, t j , u j )} j∈S i . 5. The challenger gives r to A and receives a set I ⊆ [ρ].

6. The challenger replies with σ = (s, c) and the set {π i } i∈I .

• Hyb 2 : Same as Hyb 1 , except when responding to challenge queries, the challenger samples y

r ← Z 2p q instead of y r ← Z N/2 .
• Hyb 3 : Same as Hyb 2 , except when responding to the challenge queries, the challenger first samples y r ← Z p q and ŷ r ← Z 2 . It defines y ∈ Z 2p q to be the vector where y = y (mod p q ) and y = ŷ (mod 2).

• Hyb 4 : Same as Hyb 3 , except when responding to challenge queries, the challenger samples s and y as in Hyb 3 . Next, for each i ∈ [ρ], it samples ωi r ← Z 2 , and for j ∈ S i , it samples ŷ j r ← Z 2 subject to the constraint that j∈S i α j ŷ j = ωi . For all of the remaining indices

j ∈ [ ] \ i∈I S i , sample ŷ j r ← Z 2 . • Since α r ← Z ρ 2 , for all j ∈ [ρ ], Pr[α j = 0] = 1/2. Since | Ŝi | = λ,
we have that Pr[∀j ∈ Ŝi : α j = 0] = 1/2 λ = negl(λ), and the claim holds.

• Let  be the matrix defined above and let âT j ∈ Z λ|I|T 2 denote the j th row of Â. Let n = rank( Â) ≤ λ |I| T ≤ λρT = /(36λ). This means that there exists a collection of indices j 1 , . . . , j n ∈ [ ] such that the collection {â T j 1 , . . . , âT jn } is linearly independent and span( ÂT ) = span({â T j 1 , . . . , âT jn }). By construction  only depends on A and the sets Ŝi where i ∈ I. This means that we can sample the sets Ŝi where i / ∈ I after fixing  and the set of indices {j 1 , . . . , j n }. In this case, we will show that if we sample Ŝi r ← T λ, , then with negligible probability, | Ŝi ∩ {j 1 , . . . , j n }| ≥ λ/2. Let K = | Ŝi ∩ {j 1 , . . . , j n }|. In the proof of Claim C.11, it was sufficient to show that K < λ with overwhelming probability because we were working over a super-polynomial-size field. Here, we require a stronger property that K < λ/2 with overwhelming probability because we are working over the binary field. Take any λ ≥ k ≥ λ/2.

Pr[K = k] = n k -n λ-k λ ≤ en k k (e ) λ-k λ λ ,
where we have used the fact that

n k k ≤ n k ≤ en k k . Since n ≤ /(36λ) and λ ≥ k ≥ λ/2, we have that Pr[K = k] ≤ (eλ) λ k n k k ≤ (eλ) λ k 2 36λ 2 k = (eλ) λ 2 k (36λ 2 ) k ≤ (2e) λ 36 λ/2 = (2e) λ 6 λ = negl(λ).
Then, by a union bound Pr[λ ≥ K ≥ λ/2] = negl(λ). Thus, with overwhelming probability, K = | Ŝi ∩ {j 1 , . . . , j n }| < λ/2. This means that there exist at least λ/2 indices j * k ∈ Ŝi where j * k / ∈ {j 1 , . . . , j n }. Now as in the proof of Claim C.11, since âj * k ∈ span( ÂT ), there exists scalars β 1 , . . . , β n ∈ Z 2 such that âT

j * k = γ∈[n] β γ âT jγ . This means that if there exists v ∈ Z λ|I|T 2 such that α (i) = Âv, then α (i) j * k = âT j * k v = γ∈[n] β γ âT jγ v = γ∈[n] β γ α (i) jγ . (D.5) Since j * k ∈ Ŝi , by construction, α (i) j * k = α j * k + •(i-1)
, which is uniform over Z 2 and independent of β γ and α

2 : α (i) = Âv] ≤ 1 2 λ/2 = negl(λ).
Lemma D.10. For all adversaries A, Hyb 0 (A) ≡ Hyb 1 (A).

Proof. Since S 1 (1 λ , 1 ρ ) samples crs using the same procedure as Setup(1 λ , 1 ρ ), the output distributions of Hyb 0 and Hyb 1 are identical. Proof. Follows by the same argument as the proof of Lemma D.5. Lemma D.12. For all adversaries A, Hyb 2 (A) ≡ Hyb 3 (A).

Proof. Follows by the Chinese remainder theorem (as in the proof of Lemma D.6).

Lemma D.13. If G is a secure PRG, then for all adversaries A, Hyb 3 (A) s ≈ Hyb 4 (A).

Proof. In Hyb 3 , the challenger samples ŷ r ← Z 2 while in Hyb 4 , the challenger samples ŷ j r ← Z 2 subject to the constraint that j∈S i α j ŷ j = ωi where ωi r ← Z 2 for j ∈ S i and i ∈ [ρ]. For the indices j ∈ [ ] \ i∈I S i , ŷ j r ← Z 2 . These distributions are identical as long as there exists some j ∈ S i where α j = 0 for each i ∈ [ρ]. Since G is a secure PRG, this follows by Claim D.9.

Lemma D.14. For all adversaries A, Hyb 4 (A) ≡ Hyb 5 (A).

Proof. First, y is sampled identically in the two distributions. It suffices to show that once we fix the PRG seed s and the vector y ∈ Z p q , there is a one-to-one correspondence between the value of ωi and the value of r i . In Hyb 4 , r i = LEQ(t i , t i h) where

t i = j∈S i t α j j = j∈S i (g s j y T v h y T e j ) α j .
Since g generates a subgroup of order p q , and y = y (mod p q ), we have that in Hyb 3 , g α j s j y T v = g α j s j (y ) T v . Similarly, since h has order 2, h y T e j = h y j = h ŷ j . This means that t i = j∈S i (g s j y T v h y T e j ) α j = j∈S i g α j s j (y ) T v h α j ŷ j = g ω i (y ) T v h ωi , where ω i = j∈S i α j s j and ωi = j∈S i α j ŷ j . Since r i = LEQ(t i , t i h), we conclude that once we fix the seed s (which together with the CRS determines the value of ω i ) and the vector ŷ , then the value of r i is entirely dependent on the value of ωi (mod 2). By the same argument as in the proof of Lemma D.7, there is a one-to-one correspondence between the value of ωi and r i , and both distributions enforce this correspondence. As such, these two distributions are identical. Proof. The challenger samples crs identically in the two experiments, so N , g, h, v, s 1 , . . . , s are identically distributed in the two experiments. so it suffices to consider its responses to the challenge queries. In both experiments, on each query, the challenger starts by sending the adversary a random string r r ← {0, 1} ρ , and the adversary replies with a set I ⊆ [ρ]. The challenger then replies with a commitment σ = (s, c) and a set of proofs {π i } i∈I , where π i = {(j, t j , u j )} j∈S i . We show that the challenger's responses are statistically indistinguishable in the two experiments. To this end, we define the following variables:

• For i ∈ [ρ], let ŷ(i) ∈ Z 2 be the vector where ŷ(i)

j = ŷ j+ •(i-1) ∈ Z N . In other words, (ŷ ) T = [ (ŷ (1) ) T | • • • | (ŷ (ρ) ) T ] ∈ Z 2 . • For i ∈ [ρ], define α (i) = (α (i) 1 , . . . , α (i) ) ∈ Z N as follows: α (i) j = α j+ •(i-1) if j ∈ Ŝi 0 otherwise.
We now consider the different components in the two experiments:

• The string r is independently and uniformly sampled from {0, 1} ρ in both experiments.

• The seed s is independently and uniformly sampled from {0, 1} κ in both experiments, so the seed s, the sets S 1 , . . . , S ρ , and the vector α are identically distributed as well.

• The vector y is sampled uniformly from Z p q in both experiments. Since g generates a group of order p q , the commitment c = g y T v = g (y ) T v is identically distributed in Hyb 5 and Hyb 6 .

• For all i ∈ I, both experiments set ω i ← j∈S i α j s j (mod p q ) and sample ωi

r ← Z 2 subject to r i = LEQ(g ω i (y ) T v h ωi , g ω i (y ) T v h ωi +1
). This means that the vectors ŷ(i) for i ∈ I are identically distributed in the two experiments. Then, for j ∈ S i , we have that t j = g s i (y ) T v h ŷ j , so the components t j for j ∈ S i and i ∈ I are identically distributed.

It suffices to show that the remaining components {u j } j∈S i for i ∈ I are drawn from statistically indistinguishable distributions (from the view of the adversary). Since u j = H(u 1,j , . . . , u T,j ), it suffices to show that the elements {u τ,j } τ ∈[T ],j∈S i are statistically indistinguishable in the two experiments. First, let

J = {j ∈ S i for some i ∈ I | j ∈ [ ]}
be the set of indices that appear in some set S i for i ∈ I. Next, let z τ,j = g z τ,j h ẑτ,j be the subgroup decomposition of the public-key components. Then, in both experiments, the challenger computes u τ,j as u τ,j =

k∈[ ] z y k τ,j,k = g (y ) T z τ,j h (ŷ ) T ẑτ,j .

Since y is identically distributed in Hyb 5 and Hyb 6 , it suffices to consider the distribution of u τ,j in the H subgroup, or equivalently, the distribution of (ŷ ) T ẑτ,j over Z 2 . Let Ẑi ∈ Z ×T 2 be the matrix whose columns are ẑ1,i , . . . , ẑT,i , and let Ẑ ∈ Z × T 2 be the matrix

Ẑ = [ Ẑ1 | • • • | Ẑ ]. Let Ẑ ∈ Z ×λ|I|T 2
be the submatrix of Ẑ formed by taking only the blocks of Ẑ indexed by the set J (namely, the blocks Ẑj for j ∈ J). In particular, the values of h (ŷ ) T Ẑ ∈ H λ|I|T precisely coincide with the components in the H-subgroup of u τ,j for all τ ∈ [T ], j ∈ S i and i ∈ I. Thus, it suffices to show that the distributions of (ŷ ) T Ẑ ∈ Z By definition, Ẑ is a fixed matrix (determined by the CRS and the adversary's public key) and independent of ŷ . Since each ŷ(i) is sampled independently, we can consider each term individually in this summation:

• If i ∈ I, then as argued above, ŷ(i) is identically distributed in Hyb 5 and Hyb 6 , and correspondingly, so is the product (ŷ (i) ) T Ẑ(i) .

• If i / ∈ I, then the ŷ(i) in the two experiments are sampled from distinct distributions. In Hyb 5 , ŷ(i) is uniform over Z 2 subject to ωi = j∈[ ] α (i) j ŷ(i) j , while in Hyb 6 , ŷ(i) is uniform over Z 2 .

Since i / ∈ I and Ẑ is a fixed matrix, we can appeal to Claim D.9 (for the i th block of Ẑ) and conclude that with overwhelming probability, α (i) / ∈ span( Ẑ(i) ). By Claim C.12, this means that the distribution of (ŷ (i) ) T Ẑ(i) in Hyb 5 (where ŷ(i) is uniform subject to a linear constraint α (i) / ∈ span( Ẑ(i) )) is statistically indistinguishable from its distribution in Hyb 6 (where ŷ(i) is uniform).

Since every term in Eq. (D.6) is either statistically indistinguishable or identically distributed in the two experiments, we conclude that (ŷ ) T Ẑ is also statistically indistinguishable in the two experiments. Correspondingly, this means that the components u τ,j for τ ∈ [T ], j ∈ S i , and i ∈ I are also statistically indistinguishable in the two experiments.

Since each consecutive pair of hybrid experiments is statistically indistinguishable (or identically distributed), the theorem follows.

E Dual-Mode Hidden-Bits Generators from DCR

In this section, we show how to construct dual-mode hidden-bits generators from the DCR assumption. As in Section 5, we begin with a basic construction (Construction E.2) and then show how to extend it to obtain one with security against malicious verifiers (Construction E.16). Both constructions are structurally similar to the corresponding constructions from QR (Constructions 5.3 and 5.9, respectively). One difference between the two construction is that we now use a universal hash function to extract the hidden bit rather than the LEQ predicate. In addition, we rely on a slightly different verification check. This is because in the QR constructions, the public key, commitment, and proofs are all elements in J N and membership in J N is efficiently-decidable. The analog of J N in the DCR setting is the subgroup of quadratic residues in Z * N 2 , which is not an efficiently-decidable language. Thus, a malicious prover or verifier could publish public-keys, commitments, or proofs that are quadratic non-residues over Z * N 2 to try and break soundness or zero-knowledge. We handle this case by adjusting the verification relation.

E.1 Dual-Mode Hidden-Bits Generator from DCR

In this section, we construct a standard dual-mode hidden-bits generator from the DCR assumption (without malicious security). This is an analog of Construction 5.3 from the QR assumption. Our construction is inspired by the trapdoor hash function of [DGI + 19, Appendix A]. We begin by recalling some basic notation as well as the DCR assumption.

Notation. Let N = pq be a product of safe primes p, q. Our construction works over the group Z * N 2 , which splits into two subgroups H := {(1 + N ) i | i ∈ [N ]} and NR N := {x N | x ∈ Z * N 2 } of coprime orders N and ϕ(N ), respectively. In our analysis, we will use the fact that if x ∈ Z * N 2 = NR N × H, then x 2 ∈ NR 2N × H. When N is a product of safe primes p = 2p + 1, q = 2q + 1, the subgroup NR 2N of 2N th residues is cyclic (and has order p q ). In the following, we write g to denote a generator of NR 2N and h = (1 + N ) to denote a generator of H. We will typically denote elements of NR 2N × H with a bar (e.g., c, t). In the analysis, we often analyze elements of NR 2N × H by examining their components in their respective subgroups: we write c = g c h ĉ ∈ NR 2N × H where c ∈ Z p q and ĉ ∈ Z N .

Definition E.1 (Decisional Composite Residuosity Assumption [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]). A safe prime modulus sampler SampleModulus satisfies the decisional composite residuosity (DCR) assumption if for all efficient adversaries A, and sampling (N, p, q) ← SampleModulus(1 λ ), x Construction E.2 (Dual-Mode Hidden-Bits Generator from DCR). Our DCR-based dual-mode hidden-bits generator (HBG) goes as follows:

• Setup(1 λ , 1 ρ , mode) → (crs, sk): Sample (N, p, q) ← SampleModulus(1 λ ). Let g be a generator of NR 2N and h = 1 + N be the generator of H. The setup algorithm samples a vector v -If mode = hiding, set ŵi ← e i , where e i ∈ Z ρ N is the i th basis vector.

-If mode = binding, set ŵi ← 0.

Finally, it sample a hash function H r ← H where H is a family of hash functions with domain Z N 2 and range {0, 1}. Output crs = (N, g, h, H, g v , g s 1 v h ŵ1 , . . . , g sρv h ŵρ ).

• KeyGen(crs) → (pk, sk): On input crs = (N, g, h, H, v, w 1 , . . . (z 2 i,j ) y j .

For each i ∈ [ρ], let r i ← H(t • Verify(crs, sk, σ, i, r i , π i ): On input crs = (N, g, h, H, v, w 1 , . . . , w ρ ), sk = (a, b 1 , . . . , b ρ ), σ = c, i ∈ [ρ], r i ∈ {0, 1}, and π i = (t i , u i ), output 1 if u i = (t a i c b i ) 2 and r i = H(t 2 i ). Otherwise, output 0.

• Hyb 2 : Same as Hyb 1 except the challenger computes Verify(crs, sk, σ, i, r i , π i ) using the following modified procedure. Let σ = c ∈ Z * N 2 , and write c 2 = g c h ĉ for some c ∈ Z p q and ĉ ∈ Z N . Similarly, parse π i = (t i , u i ) ∈ (Z * N 2 ) 2 and write t 2 i as g t i h ti for t i ∈ Z p q and ti ∈ Z N . Next, the challenger outputs 0 if u i / ∈ NR 2N × H. Otherwise, it writes u i as g u i h ûi for u i ∈ Z p q and ûi ∈ Z N . Then the challenger does the following:

-If r i = H(t 2 i ), output 0.

-If ĉ = 0 or ti = 0, then output 0.

-If t i = s i c, then output 0.

-Otherwise, take any y ∈ Z ρ p q such that y T v = c. Output 1 if u i = (as i + b i )y T v and ûi = 0. Otherwise (or if no such y exists), output 0.

Importantly, the challenger's responses to the verification queries in Hyb 2 depend only on the public components (i.e., crs and pk).

For an adversary A, we write Hyb i (A) to denote the output distribution of an execution of experiment Hyb i with adversary A. We now show that the output distribution of each adjacent pair of hybrid experiments is statistically indistinguishable. Lemma E.9. For all adversaries A, Hyb 0 (A) s ≈ Hyb 1 (A).

Proof. The statistical distance between Uniform(Z N 2 /4 ) and Uniform(Z N p q ) satisfies ∆(Uniform(Z N 2 /4 ), Uniform(Z N p q )) = 1 -N p q N 2 /4 = negl(λ), (E.1) since 1/p , 1/q = negl(λ). Since ρ = poly(λ), the claim follows by a union bound.

Lemma E.10. For all adversaries A, Hyb 1 (A) s ≈ Hyb 2 (A).

Proof. In Hyb 1 and Hyb 2 , the challenger evaluates Verify at most Q + 1 times where Q = poly(λ) is the bound on the number of queries the adversary makes. For j ∈ {0, . . . , Q + 1}, let Hyb 1,j denote the experiment where the first j queries are handling according to the specification in Hyb 2 while the remaining queries are handling according to the specification in Hyb 1 . By construction, Hyb 1 ≡ Hyb 1,0 and Hyb 2 ≡ Hyb 1,Q+1 . Consider Hyb 1,j-1 and Hyb 1,j for j ∈ [Q + 1]. These two experiments only differ in how the challenger computes the output for the j th Verify call. Moreover, by construction of Hyb 1,j-1 and Hyb 1,j , all of the adversary's queries prior to the j th query are handled according to the specification in Hyb 2 , which depend only on the public components crs and pk. Let (σ, i, r i , π i ) be the arguments to the j th Verify call. As in the specification of Hyb 2 , parse σ = c ∈ Z * N 2 and π i = (t i , u i ) ∈ Z * N 2 . First, if u i is not a quadratic residue (i.e., u i / ∈ NR 2N × H), then the challenger in Hyb 1,j always outputs 0. We argue that this is the case in Hyb 1,j-1 as well. By construction of Verify, the output is 1 only if u i = (t a i c b i ) 2 . But if u i is not a quadratic residue, this relation is never satisfied, and so the output in Hyb 1,j is also 0. Thus, it suffices to only consider the case where u i is a quadratic residue. Then, define c, t i , u i ∈ Z p q and ĉ, ti , ûi ∈ Z N such that c 2 = g c h ĉ, t 2 i = g t i h ti , and u i = g u i h ûi . We consider the different cases:

• Suppose r i = H(t 2 i ). Then, the output in both experiments is 0.

• Suppose ĉ = 0 or ti = 0. We argue that with overwhelming probability, the output in Hyb 1,j-1 is 0. For the output to be 1 in Hyb 1,j-1 , it must be the case that u i = (t a i c b i ) 2 , or equivalently, u i = at i + b i c ∈ Z p q and ûi = a ti + b i ĉ ∈ Z N .

In both Hyb 1 and Hyb 2 , the public parameters are independent of the values of a mod N and b i mod N . This follows from the fact that a, b i ∈ Z N p q , and the adversary only sees elements g (as i +b i )v , where g generates a group of order p q (and gcd(p q , N ) = 1). Next, since a and b i are uniform over Z N p q , the values a mod N and b i mod N are distributed uniformly and independently of the rest of the public parameters. Since the responses to all of the adversary's queries prior to its j th query only depend on the public parameters, the conditional distribution of a mod N and b i mod N given the adversary's view up to the time of its j th query is uniform and independently random. Since at least one of ĉ and ti is non-zero, this means that the value of a ti + b i ĉ mod N is independently and uniformly random over Z N . Therefore, ûi = a ti + b i ĉ with probability at most 1/N = negl(λ). This means that the output in Hyb 1,j-1 is 0 with overwhelming probability.

• Suppose that t i = s i c ∈ Z p q . We only need to consider the case where ĉ = 0 and ti = 0. We show that in this case, the output in Hyb 1,j-1 is 0 with overwhelming probability. For the output to be 1 in Hyb 1,j-1 , it must be the case that u i = (t a i c b i ) 2 , or equivalently,

u i = at i + b i c ∈ Z p q and ûi = a ti + b i ĉ = 0 ∈ Z N .
The only components in crs and pk that depend on a and b i are the public-key components g (as i +b i )v . Let b ∈ Z ρ N p q be the vector whose components are b 1 , . . . , b ρ , and let s ∈ Z ρ N p q be the vector whose components are s 1 , . . . , s ρ . The public parameters pk can then be expressed as a function of

Z = [ s | I ρ ] • a b • v T ∈ Z ρ×ρ N p q ,
where I ρ ∈ Z ρ×ρ N p q is the identity matrix. Namely, the components of pk consist of g Z . Since t i = s i c ∈ Z p q , by the Chinese remainder theorem, it must be the case that t i = s i c (mod p ) or t i = s i c (mod q ). Without loss of generality, suppose that t i = s i c (mod p ). In this case the vector [ t i | c • e i ] is linearly independent of the rows of the matrix [ s (mod p ) | I ρ ]. Since a, b are uniform over Z N p q , the components a mod p and b mod p are uniform over Z p . By linear independence over Z p , the value of at i + b i c (mod p ) is uniformly random over Z p even given Z. This means that at i + b i c = u i (mod p) with probability at most 1/p = negl(λ). Thus, the challenger in Hyb 1,j-1 outputs 0 with overwhelming probability.

• The only remaining case is when ĉ = 0 = ti , t i = s i c, and r i = H(t 2 i ). In this case, (g t i ) a (g c ) b i = g (as i +b i )c . Since v r ← Z N 2 /4 , with overwhelming probability, there will be some component that is invertible modulo p q . If so, there always exists y ∈ Z p q such that y T v = c. Then, in Hyb 1,j-1 , the challenger outputs 1 if and only if u i = (t a i c b i ) 2 = g at i +b i c = g (as i +b i )c = g (as i +b i )y T v .

Since u i = g u i h ûi , this is equivalent to checking that u i = (as i + b i )y T v and ûi = 0. This is precisely the check in Hyb 1,j .

In each case, we see that the j th call to Verify is implemented correctly with overwhelming probability in Hyb 1,j-1 and Hyb 1,j .

To complete the proof, it suffices to show that for all adversaries A, the output of Hyb 2 (A) is 0 with overwhelming probability. Let (σ * , i * , r * , π * ) be the adversary's output in Hyb 2 . The output of Hyb 2 is 1 only if Verify(crs, sk, σ * , i * , r * , π * ) = 1 and r i * = r * where r ← Open(crs, σ * ). Write σ * = c, c 2 = g c h ĉ, π * = (t, u), t 2 = g t h t, and u = g u h û (if u is not a quadratic residue in Z N 2 , then the output in Hyb 2 is 0). In Hyb 2 , if Verify(crs, sk, σ * , i * , r * , π * ) = 1, it must be the case that r * = H(t 2 ) and ĉ = 0 and t = 0 and t = s i * c.

Consider now the value of r i * and r * :

• From the above, t 2 = g t h t = g t = g cs i * . Thus r * = H(t 2 ) = H(g cs i * ).

• By definition of Open, r i * = H((c s i * ) 2 ) = H((c 2 ) s i * ) = H((g c ) s i * ) = r * .

Since r * = r i * , the output in Hyb 2 (A) is 0.

Proof of Theorem E.7 (Statistical Simulation). We construct a simulator S = (S 1 , S 2 ) as follows:

• S 1 (1 λ , 1 ρ ) → (st S , crs, pk, sk): Sample (N, p, q) ← SampleModulus(1 λ ), where p = 2p + 1 and q = 2q + 1. Let g be a generator of NR 2N and h = 1 + N be the generator of H. Sample a vector v Output crs, pk, sk and st S = ( crs, pk, p , q , s 1 , . . . , s ρ ).

• S 2 (st S , I, r I ) → ( σ, { π i } i∈I ): On input st S = ( crs, pk, p , q , s 1 , . . . , s ρ ) where crs = N, g, h, H, g v , g s 1 v h e 1 , . . . , g sρv h eρ and pk = g z 1 h ẑ1 , . . . , g zρ h ẑρ , where z i = (as i + b i )v and ẑi = ae i for all i ∈ [ρ], a set of indices I ⊆ [ρ], and a bitstring r I ∈ {0, 1} |I| , the simulator samples y r ← Z ρ p q . Then, it samples a vector ŷ ∈ Z ρ N componentby-component: specifically, for each i ∈ [ρ], it does the following:

-If i / ∈ I, sample ŷ i r ← Z N .
-If i ∈ I, sample ŷ i r ← Z N conditioned on r i = H (g s i (y ) T v h ŷ i ) 2 . Specifically, repeatedly sample ŷ i r ← Z N until finding one that satisfies the relation. If no candidate is found after λ attempts, then abort and output ⊥.

r

  ← H, x ← D, and U r ← {0, 1} .

  Corollary 2.5 (Universal Hash Functions are Statistically Uniform). Let H = {H : X → {0, 1} } be a universal family of hash functions. If |X | ≥ + ω(log λ), then H satisfies statistical uniformity.

  pk) and gives r to the adversary. If b = 1, the challenger responds with r r ← {0, 1} ρ . * The adversary specifies a subset I ⊆ [ρ]. * If b = 0, then the challenger replies with the pair (σ, {π i } i∈[I] ) it sampled above. If b = 1, the challenger replies to A with ( σ, { π i } i∈I ) ← S 2 (st S , I, r I ).

I

  , π HBM ) ← S HBM (1 λ , x). It sets r I = r I ⊕ s I , and computes ( σ, { π HBG,i } i∈I ) ← S HBG,2 (st HBG , I, r I ) and outputs the proof π = ( σ, I, r I , { π HBG,i } i∈ I , π HBM ). This is the simulated distribution (up to interchanging the labels r I and r I ).

  r ← H, where H is a family of hash functions with domain G and range {0, 1}. Next, it samples V r ← Z (ρ+k)×k p and vectors w 1 , . . . , w ρ ∈ Z ρ+k p as follows:

  and defining A ∈ Z (k+1)×k p as in Eq. (4.1), the following holds:

  Setup(1 λ , 1 ρ , mode) → crs: Let = ρ . Sample G = (G, p, g) ← GroupGen(1 λ ) and H r ← H, where H is a family of hash functions with domain G and range {0, 1}. Next, it samples V r ← Z ( +k)×k p and vectors w 1 , . . . , w ∈ Z +k p as follows: -If mode = hiding, sample w i r ← Z +k p for all i ∈ [ ]. -If mode = binding, sample s i r ← Z k p and set w i ← Vs i for all i ∈ [ ].

  g z 1 , . . . , g z ) and sk = (a, b 1 , . . . , b ).

  Theorem 4.19 (Correctness). Construction 4.18 is correct.

  Theorem 4.20 (Succinctness). Construction 4.18 is succinct.

  Theorem 4.21 (CRS Indistinguishability). Suppose the k-Lin assumption holds for GroupGen. Then, Construction 4.18 satisfies CRS indistinguishability. Theorem 4.22 (Statistical Binding in Binding Mode). Construction 4.18 satisfies statistical binding in binding mode.Theorem 4.23 (Statistical Simulation in Hiding Mode). If G is a secure PRG and H satisfies statistical uniformity, then Construction 4.18 satisfies statistical simulation in hiding mode against malicious verifiers.

•

  KeyGen(crs) → (pk, sk): On input crs = (N, g, h, H, v, w 1 , . . . , w ρ ), sample a τ , b τ,i r ← Z N/2 for all τ ∈ [T ] and i ∈ [ρ], where T = 2(λ + log N ). It computes and outputs the public key pk = {v b τ,i w aτ i } τ ∈[T ],i∈[ρ] and sk = {a τ , b τ,i } τ ∈[T ],i∈[ρ] . • GenBits(crs, pk) → (σ, r, {π i } i∈[ρ] ): On input crs = (N, g, h, H, v, w 1 , . . . , w ρ ) and pk = {z τ,i } τ ∈[T ],i∈[ρ] , sample y r ← Z ρ N/2 and compute for all τ ∈ [T ] and i ∈ [ρ]

  Theorem 5.4 (Correctness). Construction 5.3 is correct.Theorem 5.5 (Succinctness). Construction 5.3 is succinct.Theorem 5.6 (CRS Indistinguishability). Suppose the QR assumption holds with respect to SampleModulus. Then, Construction 5.3 satisfies CRS indistinguishability.Theorem 5.7 (Statistical Binding in Binding Mode). If H is pairwise independent, Construction 5.3 satisfies statistical binding in binding mode.Theorem 5.8 (Statistical Simulation in Hiding Mode). Construction 5.3 satisfies statistical simulation in hiding mode.

  e) and a matrix g D 2 from the challenger (where D ∈ Z (k+1)×k p has the form in Eq. (4.2)). It uses the challenge to simulate a CRS as follows. First, it samples H r ← H and V r ← Z (ρ+k)×k p , and vectors s 1 , . . . , s k r ← Z k p . It also samples verification components a r ← Z k+1 p , B 1 , . . . , B ρ r

  Lemma C.10 ([KW15, Lemma 2]). Let n, t, k be integers. Fix any matrix M ∈ Z n×t p and D ∈ Z (k+1)×k p

  jτ for all τ ∈ [n]. Thus, over the randomness of α, for any i ∈ [ρ] \ I Pr[∃v ∈ Z λ|I| p : α

(

  +k)×λ|I| p be the submatrix of A formed by taking only the columns of A indexed by the set J. In particular, the elements of [ t T | c T ] •  precisely coincide with i∈I {u j } j∈S i , which are the elements in the adversary's view. Now, write  as follows:

3. Sample y r ←

 r Z N/2 and compute for each j ∈ [ ] and τ ∈ [T ],

  jγ for all γ ∈ [n]. Thus, over the randomness of α, Eq. (D.5) holds with probability 1/2 for each index j * k . Thus, for any i ∈ [ρ] \ I, with overwhelming probability over the choice of Ŝi , there are at least λ/2 such indices j * k ∈ Ŝi , and since each α(i) j * kis sampled independently and uniformly over Z 2 , we have that Pr[∃v ∈ Z

  λ|I|T

Lemma D. 11 .≈

 11 For all adversaries A, Hyb 1 (A) s Hyb 2 (A).

Lemma D. 15 .≈

 15 If G is a secure PRG, then for all adversaries A, Hyb 5 (A) s Hyb 6 (A).

  in the two experiments. First, for i ∈ [ρ], let Ẑ(i) ∈ Z

  r ← Z * N 2 , Pr[A(N, x) = 1] -Pr[A(N, x N )] = negl(λ).

r ← Z ρ N 2

 2 /4 , scalars s 1 , . . . , s ρ r ← Z N 2 /4 and sets ŵi ∈ Z ρ N for i ∈ [ρ] as follows:

  , w ρ ), sample a, b 1 , . . . , b ρ r ← Z N 2 /4 . Output pk = (v b 1 w a 1 , . . . , v bρ w a ρ ) and sk = (a, b 1 , . . . , b ρ ). • GenBits(crs, pk) → (σ, r, {π i } i∈[ρ] ): On input crs = (N, g, h, H, v, w 1 , . . . , w ρ ) and pk = (z 1 , . . . , z ρ ), sample y r ← Z ρ N 2 /4 and compute for all i ∈ [ρ]: c ← j∈[ρ]

2i)

  ∈ {0, 1}. Output σ = c, r, and π = {(t i , u i )} i∈[ρ] .

r ← Z ρ N 2

 2 /4 , scalars s 1 , . . . , s ρ r ← Z N 2 /4 , and a hash functionH r ← H. Sample a, b 1 , . . . , b ρ r ← Z N 2 /4, and set crs = N, g, h, H, g v , g s 1 v h e 1 , . . . , g sρv h eρ pk = g (as 1 +b 1 )v h ae 1 , . . . , g (asρ+bρ)v h aeρ sk = a, b 1 , . . . , b ρ .

  We now state the correctness and security theorems for Construction 4.3 and give the proofs in Appendix C.1.

Theorem 4.4 (Correctness). Construction 4.3 is correct.

Theorem 4.5 (Succinctness). Construction 4.3 is succinct. Theorem 4.6 (CRS Indistinguishability). Suppose the k-Lin assumption holds for GroupGen. Then, Construction 3.4 satisfies CRS indistinguishability.

Theorem 4.7 (Statistical Binding in Binding Mode). Construction 4.3 satisfies statistical binding in binding mode.

Theorem 4.8 (Statistical Simulation in Hiding Mode). If H satisfies statistical uniformity, then Construction 4.3 satisfies statistical simulation in hiding mode.

Remark 4.9 (Common Random String in Hiding Mode). Construction 4.3 has the property that in hiding mode, the CRS is a collection of uniformly random group elements; in other words, the CRS in hiding mode can be sampled as a common random string. In conjunction with Construction 3.4, we obtain a statistical NIZK argument in the common random string model (and a computational NIZK proof in the common reference string model).

In[START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF], they require the stronger notion where the CRS is a uniformly random string. In some of our constructions in this work, the CRS will be a structured string. We believe that this model is still meaningful as the CRS just needs to be sampled once and can be reused by arbitrarily many verifiers, and zero-knowledge holds as long as the CRS is properly sampled.

This is in fact a dual-mode NIZK, where one of the CRS distributions corresponds to the uniform distribution.

This idea of encoding either a full-rank matrix in the exponent or a rank-1 matrix in the exponent also featured in the construction of lossy public-key encryption from the Matrix Diffie-Hellman assumptions[START_REF] Hofheinz | Public-key encryption with simulationbased selective-opening security and compact ciphertexts[END_REF].

We require a PRG because the prover's message needs to be succinct in order to argue soundness of the resulting NIZK in the FLS paradigm. Thus, we rely on a PRG for compression. Note that even though we rely on a computational assumption, we can still show statistical zero-knowledge. The security proof only requires that there are no efficient statistical tests that can distinguish the output of the PRG from a random string (which is implied by PRG security).

To show adaptive, multi-theorem zero-knowledge, we in fact show an even stronger simulation property. We refer to Section 3 for more details.

We can also use the transformation from[START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF] to generically go from single-theorem zero-knowledge to multitheorem zero-knowledge, but at the expense of making non-black-box use of a PRG. Our approach yields a direct construction of multi-theorem zero-knowledge without needing to make non-black-box use of cryptography. We discuss this in greater detail in Remark 2.12.

The previous notion from[START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF] was only sufficient for single-theorem non-adaptive computational zero-knowledge. Extending to adaptive multi-theorem computational zero-knowledge required imposing additional properties on the underlying NIZK in the hidden-bits model as well as making non-black-box use of cryptographic primitives[START_REF] Feige | Multiple non-interactive zero knowledge proofs under general assumptions[END_REF].

We remark that this is a stronger requirement than the corresponding requirement in[START_REF] Quach | Reusable designated-verifier NIZKs for all NP from CDH[END_REF], which also allows to scale sublinearly with ρ. We use this definition because it is conceptually simpler and all of our constructions satisfy this stronger property.

Acknowledgments

We thanks the anonymous Eurocrypt reviewers for helpful feedback on this work.

Part of this research was supported by the French ANR ALAMBIC project (ANR-16-CE39-0006). Supported in part by ERC Project aSCEND (H2020 639554). Part of this work was done while visiting ENS de Lyon. Supported by NSF CNS-1917414 and a University of Virginia SEAS Research Innovation Award. based construction. setting).

Dual-Mode HBGs from the k-Lin Assumption

In this section, we show how to construct dual-mode hidden-bits generators from the k-Lin assumption. We begin with a basic construction from the k-Lin assumption (Section 4.1) and then show how to extend it to achieve public verifiability in a pairing group (Section 4.2) as well as how to achieve security against malicious verifiers in a pairing-free group (Section 4.3).

Proof of Theorem 4.4 (Correctness). Fix λ ∈ N, a polynomial ρ = ρ(λ), an index i ∈ [ρ], and a mode mode ∈ {binding, hiding}. Let crs ← Setup(1 λ , 1 ρ , mode), (pk, sk) ← KeyGen(crs), and (σ, r, {π i } i∈[ρ] ) ← GenBits(crs, pk). By construction, crs = (G, H, g V , g w 1 , . . . , g wρ ), pk = (g z 1 , . . . , g zρ ), and sk = (a, b 1 , . . . , b ρ ). Moreover, z i = w i a + Vb i . In addition, σ = g c T = g y T V , r i = H(g t i ), and π i = (g t i , g u i ), where t i = y T w i and u i = y T z i for some y ∈ Z ρ+k p . This means that u i = y T z i = y T (w i a + Vb i ) = t i a + c T b i , and the verification algorithm accepts.

Proof of Theorem 4.5 (Succinctness). The length of a commitment in Construction 4.3 consists of k = O(1) group elements, each of which can be represented by a string of length poly(λ).

Thus, |σ| = k • poly(λ) = poly(λ).

Proof of Theorem 4.6 (CRS Indistinguishability). Our analysis relies on the following corollary of the k-Lin assumption, which roughly says that an encoding of a random rank-k matrix is computationally indistinguishable for an encoding of a uniformly random matrix.

Lemma C.1 ([EHK + 13]). Suppose GroupGen is a prime-order group generator where k-Lin holds.

Then for all polynomials n = n(λ) where k ≤ n, the following two distributions are computationally indistinguishable:

To complete the proof observe that the output of Setup(1 λ , 1 ρ , mode) for mode ∈ {binding, hiding} differ only in how the vectors w 1 , . . . , w ρ are sampled. In both cases, Setup starts by sampling V r ← Z (ρ+k)×k p

. Then, if mode = binding, w i ← Vs i for s i r ← Z k p , while if mode = hiding, w i r ← Z ρ+k p . By Lemma C.1, these two distributions are computationally indistinguishable, and the claim now follows by a standard hybrid argument.

Proof of Theorem 4.7 (Statistical Binding). We first define the (inefficient) Open algorithm as follows:

• Open(crs, σ) → r: On input a crs = (G, H, g V , g w 1 , . . . , g wρ ) and a commitment σ = g c T , the open algorithm first recovers V, w 1 , . . . , w ρ by solving the discrete logarithm problem over G.

For each i ∈ [ρ], it checks that w i = Vs i for some s i ∈ Z k p , and outputs ⊥ if not. If all checks pass, it computes r i ← H(g c T s i ) for each i ∈ [ρ] and outputs r.

To complete the proof, we use a hybrid argument:

• Hyb 0 : This is the real binding experiment. Namely, the challenger starts by sampling crs ← Setup(1 λ , 1 ρ , binding) and (pk, sk) ← KeyGen(crs), and gives (crs, pk) to the adversary. By construction, crs = (G, H, g V , g Vs 1 , . . . , g Vsρ ) and pk = (g z 1 , . . . , g zρ ),

C.2 Analysis of Construction 4.13 (Publicly-Verifiable HBG from Pairings)

In this section, we give the proofs for the correctness and security theorems (Theorems 4.14 to 4.17) for the publicly-verifiable hidden-bits generator from pairings (Construction 4.13).

Proof of Theorem 4.14 (Correctness). Fix λ ∈ N, a polynomial ρ = ρ(λ), and an index i ∈ [ρ]. Let crs ← Setup(1 λ , 1 ρ ) and (σ, r, {π i } i∈[ρ] ) ← GenBits(crs). Consider the value of Verify(crs, σ, i, r i , π i ). First, by construction,

âT = a T D, Z i = w i a T + VB i , and Bi = B T i D. In addition, σ = g c T 1 = g y T V 1 , r i = H(g t i 1 ), and π i = (g t i 1 , g

, where

.

It suffices to check Eq. (4.3) holds. By construction, e(g t i 1 , g âT 2 ) • e(g c T 1 , g Bi 2 ) = e(g 1 , g 2 ) (y T w i )(a T D)+(y T V)(B i D) = e(g 1 , g 2 ) y T (w i a T +VB i )D = e(g

and Verify accepts.

Proof of Theorem 4.15 (Succinctness). The length of a commitment in Construction 4.13 consists of k = O(1) elements in G 1 , each of which can be represented by a string of length poly(λ). Thus, |σ| = k • poly(λ) = poly(λ).

Proof of Theorem 4.16 (Computational Binding). We begin by constructing an efficient extractor E = (E 1 , E 2 ) as follows:

and set D as in Eq. (4.2). Then, set âT ← a T D and for each i

Output r. This is a deterministic algorithm by construction.

We now show that E satisfies the two required properties.

CRS indistinguishability.

The only difference in the CRS output by Setup and that output by E 1 is in how the w i are sampled (from

). This is precisely the distinction between the CRS in the hiding mode and the CRS in the binding mode in Construction 4.3. As such, the proof follows via the same argument as in the proof of Theorem 4.6 (by appealing to k-Lin in G 1 ).

Proof of Theorem 4.17 (Statistical Simulation). Follows by the same argument as in the proof of Theorem 4.8.

C.3 Analysis of Construction 4.18 (Dual-Mode (Malicious) HBG from k-Lin)

In this section, we give the proofs for the correctness and security theorems (Theorems 4.19 to 4.23) for the hidden-bits generator with malicious security from the k-Lin assumption (Construction 4.18).

Proof of Theorem 4.19 (Correctness). Follows by an analogous argument as in the proof of Theorem 4.4.

Proof of Theorem 4.20 (Succinctness). The commitment σ in Construction 4.18 consists of a PRG seed s ∈ {0, 1} κ where κ = poly(λ) and k = O(1) group elements g c T ∈ G k . Thus, |σ| = poly(λ).

Proof of Theorem 4.21 (CRS Indistinguishability). Same as the proof of Theorem 4.6.

Proof of Theorem 4.22 (Statistical Binding). This follows by an analogous argument as the proof of Theorem 4.7. In particular, we first define the following (inefficient) Open algorithm:

the open algorithm first recovers V, w 1 , . . . , w by solving the discrete logarithm problem over G. For each i ∈ [ ], it checks that w i = Vs i for some s i ∈ Z k p , and outputs ⊥ if not. If all checks pass, it computes ( Ŝ1 , . . . , Ŝρ , α) ← G(s) and the shifted sets

, and outputs r. As in the proof of Theorem 4.7, we use a hybrid argument to complete the proof:

• Hyb 0 : This is the real binding experiment.

• Hyb 1 : Same as Hyb 0 , except when generating the public key pk = (g z 1 , . . . , g z ), the challenger samples x 1 , . . . , x r ← Z k p and sets z i ← Vx i . Afterwards, it samples a r ← Z p and sets b i ← x i -s i a for use as the (secret) verification coefficients.

• Hyb 2 : Same as Hyb 1 except the challenger implements Verify(crs, sk, σ, i, r i , π i ) by computing Verify * (σ, r i , π i , (s 1 , . . . , s ), (x 1 , . . . , x )), which does the following. On input σ = (s, g c T ), r i ∈ {0, 1}, π i = {(j, g t j , g u j )} j∈S for some implicitly-defined set S ⊆ [ ], and vectors s 1 , . . . , s ∈ Z k p , x 1 , . . . , x ∈ Z k p , compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s), and the shifted set

It then checks the following conditions and outputs 1 only of them are satisfied (and outputs 0 otherwise): S = S i and r i = H j∈S i g α j t j and ∀j ∈ S i : t j = c T s j and u j = c T x j

As usual, we write Hyb i (A) to denote the output of Hyb i with adversary A. Hybrids Hyb 0 (A) and Hyb 1 (A) are identical by construction. Hybrids Hyb 1 (A) and Hyb 2 (A) are statistically indistinguishable by a similar argument as that in the proof of Lemma C.3. Namely, the Verify algorithm in Hyb 1 outputs 1 only if for all j ∈ S i :

Proof. Since S 1 (1 λ , 1 ρ ) samples crs using the same procedure as Setup(1 λ , 1 ρ , hiding), the output distributions of Hyb 0 and Hyb 1 are identically distributed.

Lemma C.14. For all adversaries A, Hyb 1 (A) s ≈ Hyb 2 (A).

Proof. With overwhelming probability, W is full-rank and invertible. In this case, the distribution of y in Hyb 1 and Hyb 2 is identical.

Lemma C.15. If G is a secure PRG, then for all adversaries A, Hyb 2 (A)

Proof. These two distributions are identical provided that for each i ∈ [ρ], there is at least one index j ∈ S i where α j = 0. In this case, both t and t are uniformly random over Z p and Z ρ p , respectively, subject to the condition that t i = j∈S i α j t j for all i ∈ [ρ]. By Claim C.11, with overwhelming probability, α j = 0 for any j ∈ [ ]. Since ρ = poly(λ), the claim follows by a union bound.

Lemma C.16. If H is statistically uniform, then for all adversaries A, Hyb 3 (A) s ≈ Hyb 4 (A).

Proof. In Hyb 3 , the challenger samples t i r ← Z p and sets r i ← H(t i ) while, in Hyb 4 , the challenger samples r i r ← {0, 1} and sets t i r ← Z p subject to H(t i ) = r i . These two distributions are statistically indistinguishable by the argument from the proof of Lemma C.6.

Lemma C.17. If G is a secure PRG, then for all adversaries A, Hyb 4 (A) s ≈ Hyb 5 (A).

Proof. The challenger samples crs identically in the two experiments, so it suffices to consider its responses to the challenge queries. Let W ∈ Z ( +k)×( +k) p be the matrix of components in the CRS and let pk = (g z 1 , . . . , g z ) be the adversary's chosen public key. As above, let Z ∈ Z ( +k)× p be the matrix whose columns are z 1 , . . . , z . Now, on each challenge query, in both Hyb 4 and Hyb 5 , the challenger starts by sending the adversary a random string r r ← {0, 1} ρ , and the adversary replies with a set I ⊆ [ρ]. The challenger then replies with a commitment σ = (s, g c T ) and a set of proofs {π i } i∈I , where π i = {(j, g t j , g u j )} j∈S i . To complete the proof, it suffices to show that the challenger's response is statistically indistinguishable in the two experiments. To facilitate the analysis, we first define the following variables:

• For i ∈ [ρ], let t (i) ∈ Z p be the vector where t

By construction, in both experiments,

j . We now consider the different components in the two experiments:

• The string r is independently and uniformly sampled from {0, 1} ρ in both experiments.

• The seed s is independently and uniformly sampled from {0, 1} κ in both experiments, so the seed s, the sets S 1 , . . . , S ρ , and the vector α are identically distributed in the two experiments.

Proof of Theorem 5.6 (CRS Indistinguishability). The proof of Theorem 5.6 follows via the following claim from [START_REF] Brakerski | Circular and leakage resilient public-key encryption under subgroup indistinguishability -(or: Quadratic residuosity strikes back)[END_REF]:

). Suppose a safe prime product modulus sampler SampleModulus satisfies the QR assumption. Let h = -1. Then, for all polynomials ρ = ρ(λ), all fixed vectors ŵ ∈ {0, 1} ρ , and all efficient adversaries A, if we sample (N, p, q) ← SampleModulus(1 λ ), v r ← Z ρ p q , s r ← Z p q , where p = 2p + 1 and q = 2q + 1, we have that

where g is a generator of QR N .

First, Claim D.1 also holds if we instead sample v r ← Z ρ N/2 and s r ← Z N/2 since the statistical distance between {r r ← Z N/2 : r mod p q } and Uniform(Z p q ) is ∆({r r ← Z N/2 : r mod p q }, Uniform(Z p q )) = (N -1)/2 mod p q (N -1)/2 = p + q 2p q + p + q = negl(λ), since 1/p , 1/q = negl(λ). To complete the proof, we use a hybrid argument, where for j ∈ {0, . . . , ρ}, Hyb j is defined as follows:

, and let g be a generator of QR N . Output crs = (N, g, h, H, g v , g s 1 v , . . . , g s i v , g s i+1 v h e i+1 , . . . , g sρv h eρ ).

By construction, Hyb 0 implements Setup(1 λ , 1 ρ , hiding) and Hyb ρ implements Setup(1 λ , 1 ρ , binding). We can appeal to Claim D.1 (where v and s are sampled from Z ρ N/2 and Z N/2 , respectively) to argue that each pair of adjacent hybrids Hyb j-1 and Hyb j for j ∈ [ρ] are computationally indistinguishable. To see this, set ŵ = e j in Claim D.1, and let (N, g, g v , g sv h ŵ ) be the challenge. We simulate a CRS by sampling s 1 , . . . , s j-1 , s j+1 , . . . , s ρ r ← Z N/2 , H r ← H and outputting (N, g, h, H, g v , g s 1 v , . . . , g s j-1 v , g sv h ŵ , g s j+1 v h e j+1 , . . . , g sρv h eρ ).

If ŵ = 0, then this is precisely the distribution Hyb j and if ŵ = e j , then this is the distribution Hyb j-1 . Thus, by Claim D.1, the outputs of Hyb j-1 and Hyb j are computationally indistinguishable for all j ∈ [ρ]. Since ρ = poly(λ), Theorem 5.6 follows by a hybrid argument.

Proof of Theorem 5.7 (Statistical Binding). Recall that in binding mode, the common reference string is given by crs = (N, g, h, H, g v , g s 1 v , . . . , g sρv ).

We define the (inefficient) Open algorithm as follows:

• Open(crs, σ) → r: On input a crs = (N, g, h, H, g v , g s 1 v , . . . , g sρv ) and a commitment σ = g c (outputting ⊥ if the components do not have this form), the open algorithm recovers v, s 1 , . . . , s ρ , and c. Then, it computes r i ← LEQ(g cs i , g cs i h) for each i ∈ [ρ], and outputs r.

To complete the proof, we use a hybrid argument:

• Hyb 4 : Same as Hyb 3 , except when responding to the challenge queries, the challenger first samples r r ← {0, 1} ρ . Then it samples y r ← Z ρ p q . For each i ∈ [ρ], it sets ŷ i ∈ Z 2 to be the unique value where r i = LEQ(g s i (y ) T v h ŷ i , g s i (y ) T v h ŷ i +1 ). Finally it sets y ∈ Z ρ 2p q to be the vector where y = y (mod p q ) and y = ŷ (mod 2). The remaining components are constructed as before.

• Hyb 5 : Same as Hyb 4 , except when responding to the challenge queries, the challenger samples ŷ ∈ Z ρ 2 after it receives the challenge set. In particular, on each query, after the challenger receives the set I ⊆ [ρ], it sets ŷ i ∈ Z 2 to the unique value where For an adversary A, we write Hyb i (A) to denote the output distribution of an execution of experiment Hyb i with adversary A. We now show that the output distribution of each adjacent pair of hybrid experiments is statistically indistinguishable.

Lemma D.4. For all adversaries A, Hyb 0 (A) ≡ Hyb 1 (A).

Proof. Since S 1 (1 λ , 1 ρ ) samples crs, pk, and sk using the same procedure as Setup and KeyGen, the output distributions of hybrids Hyb 0 and Hyb 1 are identically distributed.

Lemma D.5. For all adversaries A, Hyb

Proof. The only difference between Hyb 1 and Hyb 2 is that the challenger samples y uniformly at random from Z ρ 2p q instead of Z ρ N/2 when answering challenge queries. Since the distributions Uniform(Z N/2 ) and Uniform(Z 2p q ) are statistically indistinguishable (see Eq. (D.1)), the claim follows by a union bound (since ρ = poly(λ) and A makes a polynomial number of queries).

Lemma D.6. For all adversaries A, Hyb 2 (A) ≡ Hyb 3 (A).

Proof. The two distribution only differ in how y is sampled. In Hyb 2 , y is uniform over Z ρ 2p q while in Hyb 3 , we sample y r ← Z p q and ŷ r ← Z ρ 2 and define y so that y = y (mod p q ) and y = ŷ (mod 2). These distributions are identical by the Chinese remainder theorem (since gcd(p q , 2) = 1).

Lemma D.7. For all adversaries A, Hyb 3 (A) ≡ Hyb 4 (A).

Proof. First, y is sampled identically in the two distributions. It suffices to show that once we fix y , there is a one-to-one correspondence between the value of ŷ ∈ Z ρ 2 and the value of r. Since g generates a subgroup of order p q , and y = y (mod p q ), we have that in Hyb 3 , g s i y T v = g s i (y ) T v . Similarly, since h has order 2, h y T e i = h y i = h ŷ i . This means that the bit r i satisfies

By construction of LEQ and the fact that h generates a subgroup of order 2, this means that

and so we see that there is a one-to-one correspondence between ŷ ∈ Z ρ 2 and the bitstring r ∈ {0, 1} ρ . Both Hyb 3 and Hyb 4 enforce this correspondence, and thus, are identically distributed.

Lemma D.8. For all adversaries A, Hyb 4 (A) ≡ Hyb 5 (A).

Proof. First, the challenger generates the common reference string crs and the public key pk identically in the two experiments. It suffices to argue that the challenger's response to the adversary's challenge query is identically distributed in Hyb 4 and Hyb 5 . In particular, on each challenge query, after the adversary outputs a set I ⊆ [ρ], the challenger replies with a commitment σ = g y T v and a collection of proofs {π i } i∈I where π i = (g t i h ti , u i ). We show that the commitment σ and the components t i , ti , and u i are identically distributed in the two experiments:

• In Hyb 4 and Hyb 5 , the challenger samples y r ← Z ρ p q . Since g generates a subgroup of order p q and y = y (mod p q ), it follows that σ = g y T v = g (y ) T v , and so σ is identically distributed in the two experiments.

• In Hyb 4 and Hyb 5 , for all i ∈ I, the challenger samples ŷ i r ← Z 2 conditioned on r i = LEQ(g s i (y ) T v h ŷi , g s i (y ) T v h ŷi +1 ). Thus, the variables ŷ i for i ∈ I in the two experiments are identically distributed. In both experiments, it then defines

and so all of the g t i h ti terms for i ∈ I are identically distributed.

• In Hyb 4 and Hyb 5 , u i = H(g u 1,i h û1,i , . . . , g u T,i h ûT,i ) where

using the fact that g generates a group of order p q , h generates a group of order 2 and ẑτ,i = a τ e i . Since all of the components in Eq. (D.4) are identically distributed for all i ∈ I and τ ∈ [T ], we conclude that the components u i for i ∈ I are also identically distributed.

Theorem 5.8 now follows by a hybrid argument.

D.2 Analysis of Construction 5.9 (Dual-Mode (Malicious) HBG from QR)

In this section, we give the proofs for the correctness and security theorems (Theorems 5.10 to 5.14) for the dual-mode hidden-bits generator with malicious security from QR (Construction 5.9). The analysis proceeds very similarly to that of the basic QR scheme (Construction 5.3) in Appendix D.1.

Proof of Theorem 5.10 (Correctness). Follows by an analogous argument as the proof of Theorem 5.4.

Proof of Theorem 5.11 (Succinctness). The commitment σ in Construction 5.9 consists of a PRG seed s ∈ {0, 1} κ where κ = poly(λ) and an element of Z N , which has size 2 log N = poly(λ). Thus, |σ| = poly(λ).

Proof of Theorem 5.12 (CRS Indistinguishability). Same as the proof of Theorem 5.6.

Proof of Theorem 5.13 (Statistical Binding). Follows by a similar argument as in the proof of Theorem 5.7. Specifically, we first show that we can substitute the real verification algorithm Verify with the following algorithm. On input (σ, i, r i , π i ), the challenger does the following:

• Write σ = (s, c) and π i = {(j, t j , u j )} j∈S for an implicitly defined set S. Let ( Ŝ1 , . . . , Ŝρ , α) ← G(s), and define the shifted set

• If c = g c for some c ∈ Z p q , output 0.

• If t j = g cs j for any j ∈ S i , output 0. Here, s j ∈ Z p q is sampled by Setup and used to construct crs = (N, g, h, g v , g s 1 v , . . . , g s v )

• Take any y ∈ Z p q such that y T v = c, and write the public key as pk

. . , g y T z T,j ) for some j ∈ S i , or if no such y exists, then output 0. If all checks pass, output 1.

Using the same argument as the proof of Theorem 5.7 (applied to each individual component σ, t j , and u j ), and appealing to a union bound, we can conclude that the output of the real verification algorithm and this modified verification algorithm are identical with overwhelming probability. Similarly, as in the proof of Theorem 5.7, no adversary is able to win the binding game with respect to the modified verification algorithm, and the claim follows.

Proof of Theorem 5.14 (Statistical Hiding). We construct a simulator S = (S 1 , S 2 ) as follows:

• S 1 (1 λ , 1 ρ ) → (st S , crs): Sample (N, p, q) ← SampleModulus(1 λ ), where p = 2p + 1 and q = 2q + 1. Let g be a generator of QR N and h = -1 be the generator of and st S = ( crs, p , q , s 1 , . . . , s ).

• S 2 (st S , pk, I, r I ) → ( σ, { π i } i∈I ): On input st S = ( crs, p , q , s 1 , . . . , s ) where

, and a bitstring r I ∈ {0, 1} |I| , the simulator does the following:

2. Sample a seed s r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s), where α ∈ Z ρ 2 . For each i ∈ I, it computes the shifted sets

3. Sample y r ← Z p q . Then, it samples a vector ŷ ∈ Z 2 as follows:

-For each i ∈ I, let ω i ← j∈S i α j s j (mod p q ). Then, set ωi ∈ Z 2 to be the unique value where r i = LEQ(g ω i (y ) T v h ωi , g ω i (y ) T v h ωi +1 ) Them, for each j ∈ S i sample ŷ j r ← Z 2 subject to the constraint that j∈S i α j ŷ j = ωi .

• Hyb 5 : Same as Hyb 4 , except when responding to the challenge queries, the challenger first samples r r ← {0, 1} ρ . Then, after sampling s and y , it computes for each i ∈ [ρ], ω i ← j∈S i α j s j (mod p q ). Then, it sets ωi ∈ Z 2 to be the unique value where r i = LEQ(g ω i (y ) T v h ωi , g ω i (y ) T v h ωi +1 ).

• Hyb 6 : Same as Hyb 5 , except when responding to the challenge queries, the challenger samples ŷ ∈ Z 2 after it receives the challenge set. On each query, after the challenger receives the set I ⊆ [ρ], for each i ∈ I, it samples ŷ as follows:

-For each i ∈ I, let ω i ← j∈S i α j s j (mod p q ). Then, set ωi ∈ Z 2 to be the unique value where r i = LEQ(g ω i (y ) T v h ωi , g ω i (y ) T v h ωi +1 ) Finally, sample ŷ j r ← Z 2 for each j ∈ S i subject to the constraint that j∈S i α j ŷ j = ωi .

-For all of the remaining indices j

The remaining components are constructed as in Hyb 5 . This is exactly the distribution in ExptHide[A, S, 1].

For an adversary A, we write Hyb i (A) to denote the output of Hyb i (A) with adversary A. In the following, we show that the output distribution on each pair of adjacent experiments is statistically indistinguishable (or identically distributed). Because H = {±1} is small, our analysis will rely on a stronger version of Claim C.11: Claim D.9. Suppose G is a secure PRG and take s r ← {0, 1} κ . Let ( Ŝ1 , . . . , Ŝρ , α) ← G(s). Then, with overwhelming probability over the choice of s, the following properties hold:

• Let A ∈ Z × T 2 be any fixed matrix and let I ⊆ [ρ] be any fixed set of indices. For each i ∈ I, let S i ← {j + • (i -1) | j ∈ Ŝi } be the shifted set of indices, and define

be the submatrix of A formed by taking only the blocks of A indexed by the set J (namely, the blocks A j for j ∈ J). Next, for i ∈ [ρ], define α (i) ∈ Z 2 as follows:

By construction, α (i) contains exactly λ non-zero entries (as specified by the set Ŝi ). Then, for any i ∈ [ρ] \ I,

Proof. As in the proof of Claim C.11, it suffices to check that these properties hold for truly random ( Ŝ1 , . . . , Ŝρ , α) In this section, we give the proofs for the correctness and security theorems (Theorems E.3 to E.7) for the dual-mode hidden-bits generator from the DCR assumption (Construction E.2).

Proof of Theorem E.3 (Correctness

and a mode mode ∈ {binding, hiding}. Let crs ← Setup(1 λ , 1 ρ , mode), (pk, sk) ← KeyGen(crs), and (σ, r, {π i } i∈[ρ] ) ← GenBits(crs, pk). By construction, crs = (N, g, h, H, g v , g s 1 v h ŵ1 , . . . , g sρv h ŵρ ) for some v ∈ Z ρ N 2 /4 and ŵ1 , . . . , ŵρ ∈ Z ρ N . Then, sk = (a, b 1 , . . . , b ρ ) and pk = g b 1 v+as 1 v h a ŵ1 , . . . , g bρv+asρv h a ŵρ = g (as 1 +b 1 )v h a ŵ1 , . . . , g (asρ+bρ)v h a ŵρ .)

Similarly, we have σ = c = j∈[ρ] g v j y j = g y T v , r i = H(t 2 i ) and π i = (t i , u i ) where

g s i v j h ŵi,j y j = g s i y T v h y T ŵi

g (as i +b i )v j h a ŵi,j 2y j = (g (as i +b i )y T v h ay T ŵi ) 2 .

Consider now the behavior of Verify(crs, sk, σ, i, r i , π i ). By construction,

and the verification algorithm outputs 1.

Proof of Theorem E.4 (Succinctness). The size of the commitment in Construction E.2 is a single element in Z N 2 , which has length 2 log N = poly(λ).

Proof of Theorem E.5 (CRS Indistinguishability). First, under the DCR assumption, for N ← SampleModulus(1 λ ), the following two distributions are computationally indistinguishable:

This means that the following two distributions are also computationally indistinguishable:

This means that the uniform distribution over NR 2N × H is computationally indistinguishable from the uniform distribution over NR 2N . We can now appeal to the following theorem from [START_REF] Brakerski | Circular and leakage resilient public-key encryption under subgroup indistinguishability -(or: Quadratic residuosity strikes back)[END_REF]:

). Suppose a safe prime product modulus sampler SampleModulus satisfies the DCR assumption. Then, for all polynomials ρ = ρ(λ), all fixed vectors ŵ ∈ {0, 1} ρ , and all efficient adversaries A, if we sample (N, p, q) ← SampleModulus(1 λ ), v r ← Z ρ p q , s r ← Z p q , where p = 2p + 1 and q = 2q + 1, we have that

where g is a generator of NR 2N and h = (1 + N ) is a generator of H. ← Z N 2 /4 : r mod p q } and Uniform(Z p q ) is negligible. The theorem now follows by an analogous hybrid argument as in the proof of Theorem 5.6.

Proof of Theorem E.6 (Statistical Binding). Recall that in binding mode, the common reference string is given by crs = (N, g, h, H, g v , g s 1 w , . . . , g sρw ).

We define the (inefficient) Open algorithm as follows:

• Open(crs, σ) → r: On input a crs = (N, g, h, g v , g s 1 v , . . . , g sρv ) and a commitment σ = c ∈ Z * N 2 (outputting ⊥ if the components do not have this form), the open algorithm recovers s 1 , . . . , s ρ . It computes r i ← H((c s i ) 2 ) for each i ∈ [ρ] and outputs r.

To complete the proof, we use a hybrid argument:

• Hyb 0 : This is the real soundness experiment. The challenger samples crs ← Setup(1 λ , 1 ρ , binding) and (pk, sk) ← KeyGen(crs) and gives (crs, pk) to A. Here, crs = N, g, h, H, g v , g s 1 v , . . . , g sρv and pk = g (as 1 +b 1 )v , . . . , g (asρ+bρ)v .

The adversary can make queries to the verification oracle, and on each query (σ, i, r i , π i ), the challenger replies with Verify(crs, sk, σ, i, r i , π i ). At the end of the game, the adversary outputs a tuple (σ * , i * , r * , π * ) and the output of the experiment is 1 if r * = r i where r ← Open(crs, σ * ) and Verify(crs, sk, σ * , i * , r * , π * ) = 1.

• Hyb 1 : Same as Hyb 0 except the challenger samples the scalars s 1 , . . . , s ρ and the secret key components a, b 1 , . . . , b ρ uniformly at random from Z N p q (instead of Z N 2 /4 ).

Define y ∈ Z ρ N p q to be the vector where y = y (mod p q ) and y = ŷ (mod N ). The simulator then sets t i = g s i y T v h y T e i and u i = (g y T z i h y T ẑi ) 2 . Output σ = g y T v and { π i } i∈I where π i = (t i , u i ).

To show that ExptHide[A, S, 0] and ExptHide[A, S, 1] are statistically indistinguishable, we use a hybrid argument:

• Hyb 0 : This is the experiment ExptHide[A, S, 0]. Namely, the challenger begins by sampling crs ← Setup(1 λ , 1 ρ , hiding) and (pk, sk) ← KeyGen(crs). For each challenge query, the challenger first samples (σ, r, {π i } i∈[ρ] ) ← GenBits(crs) and gives r to A before receiving a set I ⊆ [ρ] chosen by A. It then replies with σ and {π i } i∈I .

More precisely, in this experiment, crs = N, g, h, H, g v , g s 1 v h e 1 , . . . , g sρv h eρ and pk = g z 1 h ẑ1 , . . . , g zρ h ẑρ , where z i = (as i + b i )v and ẑi = ae i for all i ∈ [ρ]. On each challenge query, the challenger samples y r ← Z N 2 /4 and computes σ = g y T v and t i = g s i y T v h y T e i and u i = (g y T z i h y T ẑi ) 2 , for all i ∈ [ρ]. The random bits r i satisfy r i = H(t 2 i ), and the proofs π i satisfy π i = (t i , u i ).

• Hyb 1 : Same as Hyb 0 , except that the challenger computes (st S , crs, pk, sk) ← S 1 (1 λ , 1 ρ ) and uses crs, pk, and sk instead of crs, pk, and sk, respectively.

• Hyb 2 : Same as Hyb 1 , except when responding to the challenge queries, the challenger samples y r ← Z ρ N p q instead of y r ← Z ρ N 2 /4 .

• Hyb 3 : Same as Hyb 2 , except when responding to the challenge queries, the challenger first samples y r ← Z ρ p q and ŷ r ← Z ρ N . It defines y ∈ Z ρ N p q to be the vector where y = y (mod p q ) and y = ŷ (mod N ).

• Hyb 4 : Same as Hyb 3 , except when responding to the challenge queries, the challenger first samples r r ← {0, 1} ρ . Then it samples y r ← Z ρ p q . Next, for each i ∈ [ρ], it samples ŷ i r ← Z N such that r i = H (g s i (y ) T v h ŷ i ) 2 . It uses the same rejection sampling procedure as in S 2 : namely, repeated sample ŷ i r ← Z N until finding one that satisfies the relation, and abort with output ⊥ if no such ŷ i is found after λ attempts. Finally it sets y ∈ Z ρ N p q to be the vector where y = y (mod p q ) and y = ŷ (mod N ). The remaining components are constructed as before.

• Hyb 5 : Same as Hyb 4 , except when responding to the challenge queries, the challenger samples ŷ ∈ Z ρ N after it receives the challenge set. In particular, on each query, after the challenger receives the set I ⊆ [ρ], for each i ∈ I, it applies the same rejection sampling procedure as S 2 to sample ŷ i ∈ Z N such that r i = H (g s i (y ) T v h ŷ i ) 2 . If i / ∈ I, then it samples r i r ← Z N . All remaining components are constructed as in Hyb 4 . This is the distribution in ExptHide[A, S, 1].

Lemma E.11. For all adversaries A, Hyb 0 (A) ≡ Hyb 1 (A).

Proof. Since S 1 (1 λ , 1 ρ ) samples crs, pk, and sk using the same procedure as Setup and KeyGen, the output distributions of hybrids Hyb 0 and Hyb 1 are identically distributed.

Lemma E.12. For all adversaries A, Hyb 1 (A) s ≈ Hyb 2 (A).

Proof. The only difference between Hyb 1 and Hyb 2 is that the challenger samples y uniformly at random from Z ρ N p q instead of Z ρ N 2 /4 when answering challenge queries. Since the distributions Uniform(Z N 2 /4 ) and Uniform(Z N p q ) are statistically indistinguishable (see Eq. (E.1)), the claim follows by a union bound (since ρ = poly(λ) and A makes a polynomial number of queries).

Lemma E.13. For all adversaries A, Hyb 2 (A) ≡ Hyb 3 (A).

Proof. The two distributions only differ in how y is sampled. In Hyb 2 , y is uniform over Z ρ N p q while in Hyb 3 , we sample y r ← Z ρ p q and ŷ r ← Z ρ N and define y so that y = y (mod p q ) and y = ŷ (mod N ). These distributions are identical by the Chinese remainder theorem (since gcd(p q , N ) = 1).

Lemma E.14. If H is a universal hash, then for all adversaries A, Hyb 3 (A) s ≈ Hyb 4 (A).

Proof. In Hyb 3 and Hyb 4 , the challenger first samples y r ← Z ρ p q . In Hyb 3 , the challenger then samples ŷ i r ← Z N , and sets

In Hyb 4 , the challenger first samples r i r ← {0, 1} and then samples ŷ i r ← Z ρ N such that Eq. (E.2) holds for each i ∈ [ρ]. First, all of the other components in Eq. (E.2) (i.e., s i , v, and y ) are identically distributed in Hyb 3 and Hyb 4 ). Thus, it suffices to show the following:

• The distribution of r i in Hyb 3 is statistically close to uniform over {0, 1}. This follows from the fact that ŷ i is uniform over Z N . This means that ŷ i is sampled from a distribution with at least log N bits of min-entropy. Since gcd(N, 2) = 1, the distribution of (g s i (y ) T v h ŷ i ) 2 also has at least log N bits of min-entropy over Z N 2 (even after fixing s i , v, y ). Since H is universal, 1/N = negl(λ), we appeal to the the leftover hash lemma to conclude that r i is statistically close to uniform over {0, 1}. Since each ŷ i is sampled independently, each r i is correspondingly independent and statistically close to uniform. By a union bound, we conclude that r ∈ {0, 1} λ is statistically close to uniform in Hyb 3 . Thus, the distribution of r in the two experiments are statistically indistinguishable.

• With overwhelming probability, the sampling algorithm in Hyb 4 does not abort. If this is the case, then in Hyb 4 , the distribution of ŷ i is uniform over Z N subject to Eq. (E.2) holding, which coincides with the distribution in Hyb 3 . From the above analysis, we have that for

) is statistically close to uniform over {0, 1}, and thus, will equal r i with probability at least 1/2 -negl(λ). The probability that the challenger fails to sample a ŷ i such that Eq. (E.2) holds is then 1/2 λnegl(λ) = negl(λ). Thus, the challenger in Hyb 4 succeeds with overwhelming probability, and the claim follows.

Lemma E.15. For all adversaries A, Hyb 4 (A) ≡ Hyb 5 (A).

Proof. First, the challenger generates the common reference string crs and the public key pk identically in the two experiments. It suffices to argue that the challenger's response to the adversary's challenge query is identically distributed in Hyb 4 and Hyb 5 . In particular, on each challenge query, after the adversary outputs a set I ⊆ [ρ], the challenger replies with a commitment σ = g y T v and a collection of proofs {π i } i∈I where π i = (t i , u i ). We show that the commitment σ and the group elements t i , u i ∈ Z * N are identically distributed in the two experiments:

• In Hyb 4 and Hyb 5 , the challenger samples y r ← Z ρ p q . Since g generates a subgroup of order p q and y = y (mod p q ), it follows that σ = g y T v = g (y ) T v , and so σ is identically distributed in the two experiments.

• In Hyb 4 and Hyb 5 , for all i ∈ I, the challenger samples ŷ i ∈ Z 2 conditioned on r i = H (g s i (y ) T v h ŷ i ) 2 . Thus, the variables ŷ i for i ∈ I in the two experiments are identically distributed. In both experiments, the value t i satisfies t i = g s i (y ) T v h ŷ i , and since y and ŷ i are identically distributed in the two experiments (along with the remaining components s i , and v), the value t i is also identically distributed in the two experiments.

• In Hyb 4 and Hyb 5 , u i = (g y T z i h y T ẑi ) 2 , where z i = (as i + b i )v and ẑi = ae i . In particular, this means that u i = (g (as i +b i )(y ) T v h aŷ i ) 2 . By construction, for all i ∈ I, all of the terms in the exponents are identically distributed in the two experiments.

The theorem now follows by a hybrid argument.

E.2 Dual-Mode Hidden-Bits Generator with Malicious Security from DCR

In this section, we describe our construction of a dual-mode hidden-bits generator with malicious security from the decisional composite residuosity (DCR) assumption from [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. This is an analog of Construction 5.9 from the QR assumption.

Construction E.16 (Dual-Mode HBG with Malicious Security from DCR). Let ρ be the output length of the hidden-bits generator. Our construction relies on a similar set of building blocks as Construction 4.18:

• Let SampleModulus be a safe prime modulus sampler.

• Let = 3ρλ and define T λ, := {S ⊆ [ ] : |S| = λ} to be the set of all subsets of [ ] that contains exactly λ elements. Let G : {0, 1} κ → T ρ λ, × Z ρ N be a PRG with seed length κ = κ(λ). Here, N is the modulus output by SampleModulus. We refer to Construction 4.18 for a description of how to construct such a PRG.

We construct the dual-mode designated-verifier HBG with malicious security as follows:

• Setup(1 λ , 1 ρ , mode) → crs: Let = ρ . Sample (N, p, q) ← SampleModulus(1 λ ). Let g be a generator of NR 2N and h = 1 + N be the generator of H. The setup algorithm samples a vector v r ← Z N 2 /4 , scalars s 1 , . . . , s r ← Z N 2 /4 and sets ŵi ∈ Z N for i ∈ [ ] as follows:

if mode = hiding, set ŵi ← e i , where e i ∈ Z N is the i th basis vector.

-If mode = binding, set ŵi ← 0.

Finally, it samples a hash function H r ← H where H is a family of hash functions with domain Z N 2 and range {0, 1}. Output crs = (N, g, h, H, g v , g s 1 v h ŵ1 , . . . , g s v h ŵ ).

• KeyGen(crs) → (pk, sk):

• GenBits(crs, pk) → (σ, r, {π i } i∈[ρ] ): On input crs = N, g, h, H, v, w 1 , . . . , w and pk = (z 1 , . . . , z ), first check that z i ∈ (Z * N 2 ) for all i ∈ [ ] (and output ⊥ otherwise). Then, sample y r ← Z N 2 /4 and compute for each i ∈ [ ]:

Next, sample a PRG seed s r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s) where Ŝi ∈ T λ, for all i ∈ [ρ] and α ∈ Z ρ N . Compute the shifted sets

Output σ = (s, c), r, and

, and π i = {(j, t j , u j )} j∈S for an implicitly-defined set S ⊆ [ ], the verification algorithm performs the following checks:

-Compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s) and the shifted set S i ← {j + • (i -1) | j ∈ Ŝi }. It checks that S = S i and outputs 0 if not.

-It checks that u j = (t a j c b j ) 2 for all j ∈ S, and outputs 0 if not. -It checks that r i = H j∈S t 2α j j and outputs 0 if not.

If all checks pass, the verification algorithm outputs 1.

Correctness and security analysis. We state the correctness and security theorems for Construction 5.3 here, but defer the proofs to Appendix E.2.1.

Theorem E.17 (Correctness). Construction E.16 is correct. In this section, we give the proofs for the correctness and security theorems (Theorems E.17 to E.21) for the dual-mode hidden-bits generator with security against malicious verifiers from the DCR assumption (Construction E.16). The analysis is very similar to that of the basic scheme from DCR (Construction E.2).

Proof of Theorem E.17 (Correctness). Follows by an analogous argument as the proof of Theorem E.3.

Proof of Theorem E.18 (Succinctness). The commitment σ in Construction E.16 consists of a PRG seed s ∈ {0, 1} κ where κ = poly(λ) and an element of Z N 2 , which has size 2 log N = poly(λ).

Proof of Theorem E.19 (CRS Indistinguishability). Same as the proof of Theorem E.5.

Proof of Theorem E.20 (Statistical Binding). Follows by a similar argument as the proof of Theorem E.6.

Proof of Theorem E.21 (Statistical Hiding). We construct a simulator S = (S 1 , S 2 ) as follows:

• S 1 (1 λ , 1 ρ ) → (st S , crs): Sample (N, p, q) ← SampleModulus(1 λ ), where p = 2p + 1 and q = 2q + 1. Let g be a generator of NR 2N and h = 1 + N be the generator of H. and st S = ( crs, p , q , s 1 , . . . , s ).

• S 2 (st S , pk, I, r I ) → ( σ, { π i } i∈I ): On input st S = ( crs, p , q , s 1 , . . . , s ) where crs = N, g, h, H, g v , g s 1 v h e 1 , . . . , g s v h e , a public key pk = (z 1 , . . . , z ), a set of indices I ⊆ [ρ], and a bitstring r I ∈ {0, 1} |I| , the simulator does the following:

Output ⊥ if this is not the case. 2. Sample a seed s r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s), where α ∈ Z ρ N . For each i ∈ I, it computes the shifted sets

3. Sample y r ← Z p q . Then, it samples a vector ŷ ∈ Z N as follows:

-For each i ∈ I, let ω i ← j∈S i α j s j (mod p q ). Then, sample ωi r ← Z N conditioned on r i = H (g ω i (y ) T v h ωi ) 2 . Specifically, repeatedly sample ωi r ← Z N until finding one that satisfies the relation. If no candidate is found after λ attempts, then abort and output ⊥. After sampling ωi , sample ŷ j r ← Z N for each j ∈ S i subject to the constraint that j∈S i α j ŷ j = ωi .

-For all of the remaining indices j ∈ [ ] \ i∈I S i , sample ŷ j r ← Z N . Define y ∈ Z N p q to be the vector where y = y (mod p q ) and y = ŷ (mod N ). 4. Next, the simulator computes σ = (s, g y T v ), t j = g s j y T v h y T e j , and u j ← k∈[ ] (z 2 j,k ) y k for all j ∈ S i and i ∈ I. It sets π i = {(j, t j , u j )} j∈S i . 5. Output σ and { π i } i∈I .

We now use a hybrid argument to show that ExptHide[A, 0] and ExptHide[A, 1] are statistically indistinguishable:

• Hyb 0 : This is the experiment ExptHide[A, S, 0]. Namely, the challenger begins by sampling crs ← Setup(1 λ , 1 ρ , hiding), and gives crs to A. The adversary A replies with a public key pk.

For each challenge query, the challenger samples (σ, r, {π i } i∈[ρ] ) ← GenBits(crs, pk) and gives r to A before receiving a set I ⊆ [ρ] chosen by A. It then replies with σ and {π i } i∈I .

• Hyb 1 : This experiment is identical to Hyb 0 , except that the challenger computes (st S , crs) ← S 1 (1 λ , 1 ρ ) and uses crs in place of crs. Everything else proceeds identically to Hyb 0 .

Specifically, in this experiment, the challenger samples (N, p, q), H, v, s 1 , . . . , s as specified by S 1 and sets crs = (N, g, h, H, g v , g s 1 v h e 1 , . . . , g s v h e ). It gives crs to A to receive a public key pk = (z 1 , . . . , z ). On a challenge query, the challenger proceeds as follows:

1. Check that z i ∈ (Z * N 2 ) for all i ∈ [ ], and output ⊥ otherwise. 2. Sample s r ← {0, 1} κ and compute ( Ŝ1 , . . . , Ŝρ , α) ← G(s). c ← g y T v and t j ← g s j y T v h y T e j and u j ←

and π i ← {(j, t j , u j )} j∈S i .

5. The challenger gives r to A and receives a set I ⊆ [ρ].

6. The challenger replies with σ = (s, c) and the set {π i } i∈I .

• Hyb 2 : Same as Hyb 1 , except when responding to challenge queries, the challenger samples y r ← Z N p q instead of y r ← Z N 2 /4 .

• Hyb 3 : Same as Hyb 2 , except when responding to the challenge queries, the challenger first samples y r ← Z p q and ŷ r ← Z N . It defines y ∈ Z N p q to be the vector where y = y (mod p q ) and y = ŷ (mod N ).

• Hyb 4 : Same as Hyb 3 , except when responding to challenge queries, the challenger samples s and y as in Hyb 3 . Next, for each i ∈ [ρ], it samples ωi r ← Z N , and for j ∈ S i , it samples ŷ j r ← Z N subject to the constraint that j∈S i α j ŷ j = ωi . For all of the remaining indices

• Hyb 5 : Same as Hyb 4 , except when responding to the challenge queries, the challenger first samples r r ← {0, 1} ρ . Then, after sampling s and y , it computes for each i ∈ [ρ], ω i ← j∈S i α j s j (mod p q ). Then, it samples ωi r ← Z N conditioned on r i = H (g ω i (y ) T v h ωi ) 2 . It uses the same rejection sampling procedure as in S 2 to sample ωi .

• Hyb 6 : Same as Hyb 5 , except when responding to the challenge queries, the challenger samples ŷ ∈ Z N after it receives the challenge set. On each query, after the challenger receives the set I ⊆ [ρ], for each i ∈ I, it samples ŷ as follows:

-For each i ∈ I, let ω i ← j∈S i α j s j (mod p q ). Then, sample ωi r ← Z N conditioned on r i = H (g ω i (y ) T v h ωi ) 2 using the same rejection sampling procedure as in Hyb 5 .

After sampling ωi , sample ŷ j r ← Z N for each j ∈ S i subject to the constraint that

The remaining components are constructed as in Hyb 5 . This is exactly the distribution in ExptHide[A, S, 1].

For an adversary A, we write Hyb i (A) to denote the output of Hyb i (A) with adversary A. In the following, we show that the output distribution on each pair of adjacent experiments is statistically indistinguishable (or identically distributed).

Lemma E.22. For all adversaries A, Hyb 0 (A) ≡ Hyb 1 (A).

Proof. Since S 1 (1 λ , 1 ρ ) samples crs using the same procedure as Setup(1 λ , 1 ρ ), the output distributions of Hyb 0 and Hyb 1 are identical.

Lemma E.23. For all adversaries A, Hyb 1 (A) s ≈ Hyb 2 (A).

Proof. Follows by the same argument as the proof of Lemma E.12. Lemma E.24. For all adversaries A, Hyb 2 (A) ≡ Hyb 3 (A).

Proof. Follows by the Chinese remainder theorem (as in the proof of Lemma E.13).

Lemma E.25. If G is a secure PRG, then for all adversaries A, Hyb 3 (A) Proof. In Hyb 4 , except the challenger samples ŷ ∈ Z N first in Hyb 4 while it samples r ∈ {0, 1} ρ first in Hyb 5 . We show that these two distributions are statistically indistinguishable. In Hyb 4 , each challenge bit r i satisfies

where ω i = j∈S i α j s j (mod p q ) and ω i = j∈S i α j ŷ j (mod N ), since g generates a group of order p q and h generates a group of order N . Now, in Hyb 4 , each ωi is uniform over Z N , and r i is derived from Eq. (E.3), while in Hyb 5 , r i r ← {0, 1}, and ωi is sampled uniformly from Z N subject to Eq. (E.3). Using an analogous argument to Lemma E.14, these two distributions are statistically indistinguishable.

Lemma E.27. If G is a secure PRG, then for all adversaries A, Hyb 5 (A) s ≈ Hyb 6 (A).

Proof. The challenger samples crs identically in the two experiments, so N , g, h, v, s 1 , . . . , s are identically distributed in the two experiments. so it suffices to consider its responses to the challenge queries. In both experiments, on each query, the challenger starts by sending the adversary a random string r r ← {0, 1} ρ , and the adversary replies with a set I ⊆ [ρ]. The challenger then replies with a commitment σ = (s, c) and a set of proofs {π i } i∈I , where π i = {(j, t j , u j )} j∈S i . We show that the challenger's responses are statistically indistinguishable in the two experiments. To this end, we define the following variables: i) ) ∈ Z N as follows:

We now consider the different components in the two experiments:

• The string r is independently and uniformly sampled from {0, 1} ρ in both experiments.

• The seed s is independently and uniformly sampled from {0, 1} κ in both experiments, so the seed s, the sets S 1 , . . . , S ρ , and the vector α are identically distributed as well.

• The vector y is sampled uniformly from Z p q in both experiments. Since g generates a group of order p q , the commitment c = g y T v = g (y ) T v is identically distributed in Hyb 5 and Hyb 6 .

• For all i ∈ I, both experiments set ω i ← j∈S i α j s j (mod p q ) and sample ωi r ← Z N subject to r i = H (g ω i (y ) T v h ωi ) 2 . This means that the vectors ŷ(i) for i ∈ I are identically distributed in the two experiments. Then, for j ∈ S i , we have that t j = g s i (y ) T v h ŷ j , so the components t j for j ∈ S i and i ∈ I are identically distributed.

It suffices to show that the remaining components {u j } j∈S i for i ∈ I are drawn from statistically indistinguishable distributions (from the view of the adversary). First, let J = {j ∈ S i for some i ∈ I | j ∈ [ ]} be the set of indices that appear in some set S i for i ∈ I. Since |S i | = λ and the S i 's are pairwise disjoint, |J| = λ |I| ≤ λρ = /3. It suffices to consider the case where z j ∈ Z * N 2 for all j ∈ [ ]. Otherwise, both experiments output ⊥. This means z 2 j,k ∈ NR 2N × H, and correspondingly, we can write z 2 j,k = g z j,k h ẑj,k for some z j,k ∈ Z p q and ẑj,k ∈ Z N . Now, for all j ∈ S i and i ∈ I, the challenger (in both experiments) computes u j as u j =

k∈[ ] (z 2 j,k ) y k =

j∈[ ] g z j,k y k h ẑj,k y k = g (y ) T z j h (ŷ ) T ẑj .

Since y is identically distributed in Hyb 5 and Hyb 6 , it suffices to consider the distribution of u j in the H subgroup, or equivalently, the distribution of (ŷ ) T ẑj over Z N . Let Ẑ ∈ Z × N be the matrix whose columns are ẑ1 , . . . , ẑ . Let Ẑ ∈ Z ×λ|I| N be the submatrix of Ẑ formed by taking only the columns in Ẑ indexed by the set J. In particular, the values of h (ŷ ) T Ẑ ∈ H λ|I| precisely coincide with the components in the H-subgroup of u j for j ∈ S i and i ∈ I. Thus, it suffices to show that for these indices j ∈ S i and i ∈ I, the distributions of (ŷ ) T Ẑ ∈ Z By definition, Ẑ is a fixed matrix (determined by the CRS and the adversary's public key) and independent of ŷ . Since each ŷ(i) is sampled independently, we can consider each term individually in this summation:

• If i ∈ I, then as argued above, ŷ(i) is identically distributed in Hyb 5 and Hyb 6 , and correspondingly, so is the product (ŷ (i) ) T Ẑ(i) .

• If i / ∈ I, then the ŷ(i) in the two experiments are sampled from distinct distributions. In Hyb 5 , ŷ(i) is uniform over Z N subject to ωi = j∈[ ] α (i) j ŷ(i) j , while in Hyb 6 , ŷ(i) is uniform over Z N . By the Chinese remainder theorem, we can sample (and analyze) the Z p and Z q components of ŷ(i) independently.

Define

Ẑ(i) p , Ẑ(i) q , α (i) p , and α (i) q as follows:

Ẑ(i) p = Ẑ(i) (mod p) α (i) p = α (i) (mod p) Ẑ(i) q = Ẑ(i) (mod q) α (i) q = α (i) (mod q). By Claim C.11 (generalized to Z N via the Chinese remainder theorem), we have that with overwhelming probability, α

p / ∈ span( Ẑ(i) p ) and α (i) q / ∈ span( Ẑ(i) q ). By Claim C.12, this means that the distribution of (ŷ (i) ) T Ẑ(i) p (mod p) in Hyb 5 (where ŷ(i) (mod p) is uniform subject to a linear constraint α (i) p / ∈ span( Ẑ(i) p )) is statistically indistinguishable from its distribution in Hyb 6 (where ŷ(i) (mod p) is uniform). By the same argument, the distributions of (ŷ (i) ) T Ẑ(i) q (mod q) in Hyb 5 and Hyb 6 are also statistically indistinguishable. By the Chinese remainder theorem and a union bound, this means that the product (ŷ (i) ) T Ẑ(i) ∈ Z λ|I| N is statistically indistinguishable in the two experiments.

Since every term in Eq. (E.4) is either statistically indistinguishable or identically distributed in the two experiments, we conclude that Ẑ ŷ is also statistically indistinguishable in the two experiments. Correspondingly, this means that the components u j for j ∈ S i and i ∈ I are also statistically indistinguishable in the two experiments.

Since each consecutive pair of hybrid experiments is statistically indistinguishable (or identically distributed), the theorem follows.