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

Somindu C Ramanna
email: somindu.ramanna@ens-lyon.fr

Moti Yung

Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions

Keywords: Cryptography, commitment schemes, functional commitments, accumulators, provable security, pairing-based, simple assumptions

We formalize a cryptographic primitive called functional commitment (FC) which can be viewed as a generalization of vector commitments (VCs), polynomial commitments and many other special kinds of commitment schemes. A non-interactive functional commitment allows committing to a message in such a way that the committer has the flexibility of only revealing a function F (M ) of the committed message during the opening phase. We provide constructions for the functionality of linear functions, where messages consist of vectors of n elements over some domain D (e.g., ⃗ m = (m1, . . . , mn) ∈ D n ) and commitments can later be opened to a specific linear function ∑ n i=1 mixi = y ∈ R of the vector coordinates. An opening for a function F : D n → R thus generates a witness for the fact that F ( ⃗ m) indeed evaluates to y. One security requirement is called function binding and requires that it be infeasible open a commitment to two different evaluations y, y ′ for the same function F . We propose a construction of functional commitment (FC) for linear functions based on constant-size assumptions in composite order groups endowed with a bilinear map. The construction has commitments and openings of constant size (i.e., independent of n or function description) and is perfectly hiding -the underlying message is information theoretically hidden. Our security proofs build on the Déjà Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016) to encryption primitives, thus relying on constant-size subgroup decisional assumptions. We show that FCs for linear functions are sufficiently powerful to solve four open problems. They, first, imply polynomial commitments, and, then, give cryptographic accumulators (i.e., an algebraic hash function which makes it possible to efficiently prove that some input belongs to a hashed set). In particular, specializing our FC construction leads to the first pairing-based polynomial commitments and accumulators for large universes, known to achieve security under simple assumptions. We also substantially extend our pairing-based accumulator to handle subset queries which requires a non-trivial extension of the Déjà Q framework.

Introduction

Commitment schemes [START_REF] Blum | Coin Flipping by Telephone[END_REF] are fundamental primitives used as building blocks in a number of cryptographic protocols. A commitment scheme emulates a publicly observed safe; it allows a party to commit to a message m so that this message is not revealed until a later moment when the commitment is opened and the receiver gets convinced that the message was indeed m. Two important security properties of commitment schemes are called hiding and binding. The former requires that no information about the committed message is revealed to an observer. The latter property means that the committing party cannot change the message after committing to it.

Several works considered commitment schemes where the committer has the flexibility of only revealing some partial information about the message (rather than the entire message) during the opening phase. In vector commitments [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF][START_REF] Catalano | Vector Commitments and their Applications[END_REF], messages are vectors and commitments are only opened with respect to specific positions. Another example is polynomial commitments, where users commit to a polynomial and only reveal evaluations of this polynomial on certain inputs.

In this work, we consider functional commitments (FC) for linear functions. Namely, messages consist of vectors (m 1 , . . . , m n ) and commitments can be partially opened by having the sender verifiably reveal a linear combination ∑ n i=1 x i •m i , for public coefficients {x i } n i=1 . We show that this functionality implies many other natural functionalities, including vector commitments, polynomial commitments and cryptographic accumulators. We provide an efficient FC realization for linear functions based on well-studied assumptions in groups with a bilinear map. In turn, our scheme implies solutions to past natural questions. We give the first constructions under constant-size assumptions of two important primitives: polynomial commitments and cryptographic accumulators. In both cases, earlier solutions were based on non-standard assumptions where the number of input elements (and thus the strength of the assumption) depended on specific features of the schemes (like the maximal degree of committed polynomials). Our third result is a solution to an accumulator supporting subset queries, which is also based on constant size assumption.

Related Works and the Open Problems

Functional commitments. Functional commitments can be seen as the natural commitment analogue of functional encryption [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF][START_REF] Boneh | Functional Encryption: Definitions and Challenges[END_REF]. The latter primitive allows restricting what the receiver learns about encrypted data: when a decryption operation is conducted using a secret key SK F for the function F , the decryptor learns F (x) and nothing else. Likewise, FC schemes allow the committer to accurately control what the opening phase can reveal about the committed message.

In their most general form, functional commitments were implicitly suggested by Gorbunov, Vaikuntanathan and Wichs [START_REF] Gorbunov | Leveled Fully Homomorphic Signatures from Standard Lattices[END_REF] who described a statistically-hiding commitment scheme for which the sender is able to only reveal a circuit evaluation C(x) when x is the committed input. While their solution supports arbitrary circuits and relies on wellstudied lattice assumptions, its inputs x must be committed to in a bit-by-bit manner (or at least by splitting x into small blocks). We remark that, assuming a common reference string, non-interactive FC for general functionalities can be realized by combining ordinary statistically-hiding commitments with non-interactive zero-knowledge (NIZK) proofs [START_REF] Blum | Non-Interactive Zero-Knowledge and its Applications[END_REF]. Here, we focus on the problem of achieving a better efficiency for more restricted (yet, sufficiently powerful for many applications) functionalities. Assuming a common reference string (as in all non-interactive perfectly hiding commitments), we aim at efficient construction supporting short witnesses without resorting to the machinery of NIZK proofs. In particular, we aim at constant-size commitment strings (regardless of how long the committed message is) supporting constant-size witnesses.

In the literature, a number of earlier works consider settings where a sender is given the flexibility of revealing only a partial information about committed data. Verifiable random functions [START_REF] Micali | Verifiable Random Functions[END_REF], for example, can be seen as a perfectly binding commitment to a pseudo-random function key for which the committer can convince a verifier about the correct function evaluation for the committed key on a given input. Selective-opening security [START_REF] Dwork | Magic Functions[END_REF][START_REF] Bellare | Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening[END_REF] addresses the problem of proving the security of un-opened commitments when an adversary gets to see the opening of other commitments to possibly correlated messages.

Zero-knowledge sets, as introduced by Micali, Rabin and Kilian [START_REF] Micali | Zero-Knowledge Sets[END_REF], are another prominent example where users commit to a set S or an elementary database and subsequently prove the (non-)membership of some elements without revealing any further information (not even the cardinality of the committed set S). Ostrovsky, Rackoff and Smith [START_REF] Ostrovsky | Efficient Consistency Proofs for Generalized Queries on a Committed Database[END_REF] envisioned committed databases for which the sender can demonstrate more general statements than just membership of non-membership.

Vector commitments. Concise vector commitments were first suggested by Libert and Yung [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF] and further developed by Catalano and Fiore [START_REF] Catalano | Vector Commitments and their Applications[END_REF]. They basically consist of Pedersen-like [START_REF] Pedersen | Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[END_REF] commitments to vectors (m 1 , . . . , m n ) where a constant-size opening (where "constant" means independent of n) allows the sender to open the commitment for only one coordinate m i without revealing anything on other coordinates. The initial motivation of vector commitments was the design of zero-knowledge databases with short proofs [START_REF] Catalano | Zero-Knowledge Sets with Short Proofs[END_REF][START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF] via mercurial commitments [START_REF] Chase | Mercurial Commitments with Applications to Zero-Knowledge Sets[END_REF] supporting short coordinate-wise openings [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF]. Other applications in the context of verifiable databases [START_REF] Benabbas | Verifiable Delegation of Computation over Large Datasets[END_REF] were suggested in [START_REF] Catalano | Vector Commitments and their Applications[END_REF]. While concise vector commitments can be based on long-lived hardness assumptions like RSA or Computational Diffie-Hellman [START_REF] Catalano | Vector Commitments and their Applications[END_REF], they either require groups of hidden order (making them incompatible with zero-knowledge proofs in the standard model [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]) or public keys of size O(n 2 ) if n is the dimension of committed vectors. In contrast, solutions based on variable-size assumptions allow for public keys of size O(n), which leaves open the following problem.

Problem 1: Is there a concise vector commitment scheme achieving linear-size public keys under constant-size assumptions in groups with a bilinear map?

Polynomial commitments. As introduced by Kate, Zaverucha and Goldberg [START_REF] Kate | Constant-Size Commitments to Polynomials and their Applications[END_REF], polynomial commitments are a mechanism whereby a sender can generate a constant-size commitment to a polynomial P [Z] (where "constant" means independent of the degree) in such a way that a constant-size witness can convince a verifier that the committed P [Z] indeed evaluates to P (i) for a given i. Polynomial commitments find natural applications in the context of verifiable secret sharing [START_REF] Chor | Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults[END_REF][START_REF] Feldman | A Practical Scheme for Non-interactive Verifiable Secret Sharing[END_REF], anonymous credentials with attributes [START_REF] Camenisch | Composable & Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] or in optimized flavours of zero-knowledge databases which do not seek to hide the size of the committed set. They also imply vector commitments, as observed in [START_REF] Camenisch | Composable & Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF]. Camenisch et al. [START_REF] Camenisch | Composable & Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] used vector commitments in a modular design of anonymous credentials where users's credentials are associated with descriptive attributes. While the commitments in [START_REF] Kate | Constant-Size Commitments to Polynomials and their Applications[END_REF][START_REF] Camenisch | Composable & Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] were based on parameterized assumptions, the problem described below has been open.

Problem 2: Design a polynomial commitment based on constant-size assumptions.

Accumulators. Cryptographic accumulators can be interpreted as commitments, especially when the hashing algorithm is randomized. Accumulators [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Signatures[END_REF] are closely related to zero-knowledge sets in that they make it possible to hash a set S while efficiently generating witnesses guaranteeing the inclusion of certain elements in the hashed set. Unlike zero-knowledge sets, they do not hide the cardinality of the underlying set but usually achieve a better efficiency via short membership witnesses. The first family of accumulators based on number theoretic techniques relies on groups of hidden order [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Signatures[END_REF][START_REF] Baric | Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees[END_REF][START_REF] Lipmaa | Secure Accumulators from Euclidean Rings Without Trusted Setup[END_REF][START_REF] Boneh | Bivariate Polynomials Modulo Composites and Their Applications[END_REF] and includes proposals based on the Strong RSA assumption [START_REF] Baric | Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees[END_REF][START_REF] Li | Universal Accumulators with Efficient Nonmembership Proofs[END_REF]. The second family [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF][START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF], which was first explored by Nguyen [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF], appeals to bilinear maps (a.k.a. pairings) and assumptions, like the Strong Diffie-Hellman assumption [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF], whose hardness depends on a parameter q determined by features of the scheme or the number of adversarial queries. Solutions based on the Strong RSA assumption feature short public parameters and readily extend into universal accumulators [START_REF] Li | Universal Accumulators with Efficient Nonmembership Proofs[END_REF] (where non-membership witnesses can show that a given input was not accumulated) or dynamic accumulators [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF] (where witnesses can be autonomously updated when the hashed set is modified). On the other hand, they usually require expensive operations to injectively encode set elements as prime numbers. While pairing-based schemes [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF][START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF] do not need such a prime-number-encoding, they require linear-size public parameters in the maximal number of accumulated elements. On the positive side, they are useful in applications [START_REF] Au | Compact E-Cash from Bounded Accumulator[END_REF][START_REF] Canard | Multiple Denominations in E-cash with Compact Transaction Data[END_REF], like e-cash systems, where the number of hashed elements cannot exceed a pre-determined bound. Pairingbased accumulators also proved useful in the context of authenticated data structures. Papamanthou et al. [START_REF] Papamanthou | Optimal Verification of Operations on Dynamic Sets[END_REF] used them to authenticate set operations and notably prove (using a constant-size witness) the inclusion of a given set in the accumulated set. The same technique was extended [START_REF] Papamanthou | Optimal Verification of Operations on Dynamic Sets[END_REF] to provide evidence that two accumulated sets have a given intersection.

A third family of accumulators [START_REF] Papamanthou | Streaming Authenticated Data Structures[END_REF][START_REF] Boneh | Bivariate Polynomials Modulo Composites and Their Applications[END_REF] builds on Merkle trees [START_REF] Merkle | A Certified Digital Signature[END_REF] rather than number theoretic assumptions. Its main disadvantage is that the use of hash trees entails witnesses of size O(log N ) (where N denote the cardinality of hashed sets) whereas numbertheoretic solutions enable O(1)-size witnesses.

The security properties of accumulators were recently re-formalized by Derler et al. [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF] who showed connections with other primitives. It was notably showed that, when endowed with an indistinguishability property, accumulators imply non-interactive commitment schemes and are implied by zero-knowledge sets.

Despite their numerous applications, cryptographic accumulators still have relatively few assumptions to rely on. So far, known candidates based on standard assumption arise from a generic construction from vector commitments [START_REF] Catalano | Vector Commitments and their Applications[END_REF]. While implying solutions based on RSA or Diffie-Hellman, the generic construction of [START_REF] Catalano | Vector Commitments and their Applications[END_REF] only supports inputs living in a small domain: the public key size is indeed linear in the size of the input universe, which prevents from hashing elements consisting of arbitrary strings. This leaves open Problem 3.

Problem 3: Does there exist a pairing-based accumulator for large input universes secure under constant-size assumptions?

As mentioned earlier, accumulators are applicable in authenticating set operations ( [START_REF] Papamanthou | Optimal Verification of Operations on Dynamic Sets[END_REF]) and a useful extension would allow creating witnesses for set inclusion and intersection that are of constant size. Namely, a short witness can serve as evidence that some set X is a subset of the accumulated set or that two sets X 1 , X 2 have a particular intersection I. In this domain, the following problem still remains open.

Problem 4: Construct a pairing-based accumulator supporting set operations with constant-size witnesses achieving security under simple assumptions.

Our Contributions

We first generalize the notion of vector commitments (VCs) to what we call functional commitments (FCs) for linear functions. Similar to VCs, such a commitment scheme allows committing to vectors of messages which can later be opened to specific function evaluations. While possible [START_REF] Gorbunov | Leveled Fully Homomorphic Signatures from Standard Lattices[END_REF], the design of FCs for arbitrary functionalities seems unlikely to lead to truly efficient solutions. Instead, we aim at FCs for linear function families {F ⃗ x :

D n × D n → D} ⃗ x∈D n defined by F ⃗ x ( ⃗ m) = ⟨⃗ x, ⃗ m⟩ = ∑ n i=1 x i m i for ⃗ m ∈ D n that
suffice for many important applications. An FC scheme for a family of linear functions {F ⃗ x :

D n → D} ⃗ x∈D n produces commitments to messages of the form ⃗ m = (m 1 , . . . , m n ) ∈ D n over the domain D. Fixing a specific ⃗ x ∈ D n , such that F ⃗ x ( ⃗ m) = ∑ n i=1 x i m i = y ∈ D, an opening for F ⃗ x demonstrates that F ⃗ x ( ⃗ m)
indeed evaluates to y. The security notions of hiding and binding extend to our setting in a natural way. In addition, we require the commitments and witnesses to be concise i.e., their size should be independent of the length of messages or function description.

Our first contribution is a construction of functional commitment for linear functions based on well-studied assumptions in composite order bilinear groups. The scheme is perfectly hiding and computationally binding under subgroup decision assumptions. The construction can be seen as a variant of the vector commitment scheme of Izabachène et al. [START_REF] Izabachène | Blockwise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes[END_REF] which was only proved secure under a non-standard variable-size assumption. We show that the composite-order setting makes it possible to use the Déjà Q framework of [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions In Eurocrypt 2014[END_REF] so as to obtain security from constant size assumptions. As FC for linear functions implies vector commitments, our construction provides a positive answer to Problem 1.

As a second contribution, we show that our FC scheme implies polynomial commitments and large-universe accumulators supporting subset queries. The resulting schemes are secure under subgroup decision assumptions of constant-size thus settling Problem 2 and Problem 3. We finally extend our accumulator into a scheme supporting subset queries while retaining security from constant size assumptions, partially answering Problem 4 in the affirmative.

Overview of our Construction. We now present the top level idea of our construction. Let e : G × G → G T be a bilinear map with common group order N = p 1 p 2 p 3 and let G q denote the subgroup of G of order q (here q would be of the form p e1 1 p e2 2 p e3 3 for e 1 , e 2 , e 3 ∈ {0, 1}). The linear functions will be defined over Z N . The commitment key consists of elements {g α j } n j=1 , {U j = u α j } j∈ [1,2n]\{n+1} for some g, u ∈ G p1 . The trapdoor key is

U n+1 = u α n+1 . Commitment to a vector ⃗ m is defined as C = g γ • ∏ n j=1 g α j mj
. Witness for a linear function evaluation ⟨⃗ x, ⃗ m⟩ = y is defined as

W y = ∏ n i=1 W xi i with the G p1 component of W i being u α n-i+1 γ •
∏ n j=1,j̸ =i u α n+1+j-i mj for each i = 1, . . . , n. The absence of the trapdoor u α n+1 in the witness enables us to verify that y = ⟨⃗ x, ⃗ m⟩ by checking whether e(C,

∏ n i=1 u α n-i+1 xi ) = e(g α , u α n ) y • e(g, W y ) holds.
The u-components are additionally randomized with elements of G p3 . This modification does not affect verification since the G p3 components get cancelled upon pairing with G p1 elements. The scheme is a simple composite-order analogue of the vector commitment scheme proposed in [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF].

Proof Idea. We fix some notation first (similar to [START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF]). A (q 1 → q 2 ) subgroup decision assumption requires random elements of G q1 to be indistinguishable from random elements of G q2 . Using Wee's adaptation [START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF] of the Déjà Q framework, we prove security of our FC scheme based on (p 1 → p 1 p 2 ) and (p 1 p 3 → p 1 p 2 p 3 ) subgroup decision assumptions. An adversary breaking the binding property is successful if it can produce a commitment C and two conflicting witnesses W y and W y ′ for evaluation of a function ⃗ x. Given that both witnesses satisfy the associated verification equations, one can say that the adversary can essentially produce ∆W = ( W y ′ /W y ) 1/(y-y ′ ) which is of the form

u (α n+1 ) • g r2 2 • g r3
3 for some r 2 , r 3 ∈ Z N and generators g 2 ∈ G p2 and g 3 ∈ G p3 . The G p1 component of ∆W is identical to that of the trapdoor key. Define two types of keys (attacks) according to {U j } 2n j=1 (∆W ) containing a G p2 component or not. We argue that the attacker cannot mount an attack of a type different from that of the key based on the (p 1 → p 1 p 2 ) The distribution of G p2 components for the keys are changed gradually via the transition described below.

u α i R 3,i subgroup ------→ u α i g r1α i 2 R 3,i CRT ---→ u α i g r1α i 1 2 R 3,i ,
where α 1 is uniformly distributed over Z N . The first step of the transition uses the p 1 p 3 → p 1 p 2 p 3 subgroup decision assumptions and the second transition is based on the Chinese remainder theorem (CRT) that states that α mod p 1 and α mod p 2 are uncorrelated. We can thus replace α mod p 2 by α 1 mod p 2 as long as α mod p 2 is not revealed in any information provided to the attacker. By repeated application of the transition 2n times, we obtain the transformation:

u α i → u α i g ∑ 2n j=1 rj α i j 2 R ′ 3,i .
The exponent of g 2 is a pseudorandom function [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions In Eurocrypt 2014[END_REF][START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF] and hence can be replaced by a random exponent, RF (i) for U i in particular. After the final transition, creating ∆W consistent with these keys amounts to predicting the value of the random function evaluated at n + 1 (for the trapdoor U n+1 ), which is statistically infeasible.

Polynomial Commitments from Simple Assumptions. We wish to commit to a polynomial

P [Z] = a 0 + a 1 Z + • • • + a n-1 Z n-1 of
degree n over D and reveal an opening for P (x) for x ∈ D. Using the FC scheme for linear functions, we can commit to (a 0 , . . . , a n-1 ) ∈ D n so that an opening to P (x) is a witness for ⟨⃗ x, ⃗ m⟩ = P (x) where ⃗ x = (1, x, . . . , x n-1 ).

Accumulators for Large Universes. An accumulator allows hashing a set to a single element so that one can prove the membership of a value in the set. Vector commitments are known to imply accumulators [START_REF] Catalano | Vector Commitments and their Applications[END_REF], but via a construction that only supports a small universe of values. Our polynomial commitment naturally leads to an accumulator for large universes (i.e., the domain size can be exponential in the security parameter). To accumulate a set of values S = {y 1 , . . . , y n-1 }, use a polynomial commitment to

P [Z] = ∏ n-1 i=1 (Z -y i ). A witness for x ∈ S (or x / ∈ S) is generated based on the fact P [x] = 0 if and only if x ∈ S.
Tackling Subset Queries.As explained above, polynomial commitments and universal accumulators can be seen as direct consequences of the FC for linear functions. On the other hand, proving security for accumulators with concise subset witnesses requires a novel extension of the Déjà Q framework. We now provide a brief outline of the same.

Let n be the maximal number of values that can be accumulated and let d be the maximal size of "provable" subsets. In the commitment scheme, keys consisted of powers of α in the exponent over the interval [1, 2n] with a hole at position n + 1 (the n + 1st exponent being the trapdoor key). We extend this interval to [1, (d + 1)n] making n + 1, 2n + 1, . . . , dn + 1 part of the trapdoor. The witness component for a specific position i of the linear function was defined as

W i = u α n-i+1 γ • ∏ n j=1,j̸ =i u α n+1+j-i mj .
In order to combine witnesses for several (at most d) values into a constant size witness, we define the witness for the i-th position of the ℓ-th element as a "shift" of W i by a factor ℓ in the exponent. More precisely, W ℓ,i is defined to have

u α ℓn-i+1 γ • n ∏ j=1,j̸ =i u α ℓn+1+j-i mj as its G p1 component.
Security for accumulators is captured by the notion of collision-freeness which asserts that it is computationally infeasible for an attacker to produce a set S and a witness W X for a subset X = {x 1 , . . . , x k } ̸ ⊆ S that verifies correctly with an accumulated value for S (generated using randomness specified by the adversary). Given the randomness, the reduction can compute valid witnesses of membership and non-membership for individual values in X (as in the normal accumulator scheme). Combining appropriate "shifts" of these witnesses gives us W X∩S (combined membership witness) and W X\S (combined non-membership witness). We then observe that

W X /(W X∩S W X\S ) has a G p1 -component of the form u ∑ ℓ∈[1,k],x ℓ / ∈S w ℓ α ℓn+1
(w ℓ ̸ = 0) which means that the attacker essentially produces a linear combination of the discrete logarithms of trapdoor keys in the exponent. The rest of the reduction proceeds similar to the FC scheme with the pseudorandom function now extending to the larger interval. Using this pseudorandom function, the distribution of the keys is gradually modified until the G p2 components of all U i 's are truly random. We argue that generating such a witness requires the adversary to predict a linear combination of at most d specific evaluations of a random function which is clearly infeasible.

Background

Bilinear Maps and Complexity Assumptions

We use groups (G, G T ) of composite order N = p 1 p 2 p 3 endowed with an efficiently computable map (a.k.a. pairing) e :

G × G → G T such that: (1) e(g a , h b ) = e(g, h) ab for any (g, h) ∈ G × G and a, b ∈ Z; (2) if e(g, h) = 1 G T for each h ∈ G, then g = 1 G
. An important property of composite order groups is that pairing two elements of order p i and p j , with i ̸ = j, always gives the identity element 1 G T .

In the following, for each i ∈ {1, 2, 3}, we denote by G pi the subgroup of order p i . For all distinct i, j ∈ {1, 2, 3}, we call G pipj the subgroup of order p i p j . We rely on the following assumptions introduced in [START_REF] Lewko | New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts[END_REF], which are non-interactive, falsifiable [START_REF] Naor | On Cryptographic Assumptions and Challenges[END_REF]. In both of them, the number of input elements is constant (regardless of the number of adversarial queries).

Assumption 1 Given a description of (G, G T ) as well as

g R ← G p1 , X 3 R ← G p3 and T ∈ G, it is infeasible to efficiently decide if T ∈ G p1p2 or T ∈ G p1 . Assumption 2 Let g, X 1 R ← G p1 , X 2 , Y 2 R ← G p2 , Y 3 , Z 3 R ← G p3 . Given a description of (G, G T ), (g, X 1 X 2 , Z 3 , Y 2 Y 3 ) and T , it is hard to decide if T ∈ R G p1p3 or T ∈ R G.

Vector Commitment Schemes

In prime order groups, Libert and Yung [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF] introduced concise vector commitment schemes, which are commitments that can be opened with a short de-commitment string for each individual coordinate. Such commitments were described in [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF][START_REF] Catalano | Vector Commitments and their Applications[END_REF]. In [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF], the commitment key is CK = (g, g 1 , . . . , g n , g n+2 , . . . , g 2n ) ∈ G 2n , where

g i = g (α i ) for each i. The trapdoor is g n+1 . To commit to ⃗ m = (m 1 , . . . , m n ), one picks r R ← Z p and computes C = g r • ∏ n j=1 g mκ n+1-j . A single element W i = g r i • ∏ n j=1,j̸ =i g mj n+1-j+i provides evidence that m i is the i-th component of ⃗ m as it satisfies e(g i , C) = e(g, W i ) • e(g 1 , g n ) mi
. The infeasibility of opening C to two distinct messages for some i relies on a parametrized assumption [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF].

Functional Commitments for Linear Functions: Definitions

In [START_REF] Izabachène | Blockwise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes[END_REF], Izabachène et al. implicitly showed that the vector commitment scheme of [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF] can be generalized into a commitment scheme allowing to commit to a vector ⃗ m while proving -via a partial opening made of a short piece of information -that the committed vector ⃗ m satisfies ⃗ m • ⃗ x = y, for some public ⃗ m and y. We call such a primitive functional commitment for linear functions. In this section, we formally define this primitive and its security. The correctness condition for a functional commitment scheme requires that for every

Definition 1 (Functional Commitments). Let D be a domain and consider linear functions

⟨•, •⟩ : D n × D n → D defined by ⟨⃗ x, ⃗ m⟩ = ∑ n i=1 x i m i for ⃗ x, ⃗ m ∈ D n with ⃗ x = (x 1 , . . . , x n ), ⃗ m = (m 1 , . . . , m n ). A functional commitment scheme FC for (D, n, ⟨•, •⟩) is a
(CK, T K) ← Setup(λ, n), for all ⃗ m, ⃗ x ∈ D n , if (C, aux) ← Commit(CK, ⃗ m) and W y ← Open(CK, C, aux, ⃗ x), then Verify(CK, C, W y , ⃗ x, y) = 1 with probability 1.
In some applications (e.g., [START_REF] Krupp | Nearly Optimal Verifiable Data Streaming[END_REF]), it may be useful to extend the syntax with an equivocation algorithm which allows generating witnesses for arbitrary values y using the trapdoor T K. This equivocation algorithm Equivocate takes as input a pair (C, aux) produced as (C, aux) ← Commit(CK, ⃗ m), a vector ⃗ x ∈ D n , an arbitrary value y and the trapdoor T K. It outputs a witness W y such that Verify(CK, C, W y , ⃗ x, y) = 1. While our construction readily extends to support such a mechanism, we omit it from the syntax for simplicity.

The security requirements of functional commitments are formalized as follows.

Definition 2 (Perfectly Hiding). A commitment scheme is perfectly hiding if for a key CK generated by an honest setup, for all

⃗ m 1 , ⃗ m 2 ∈ D n with ⃗ m 1 ̸ = ⃗ m 2 ,
(i) y ̸ = y ′ ; (ii) Verify(CK, C, W y , ⃗ x, y) = Verify(CK, C, W y ′ , ⃗ x, y ′ ) = 1.

Cryptographic Accumulators

The basic functionality of an accumulator is to combine a set S of values into a single value V so that for any x ∈ S it is possible to prove that x is accumulated in V .

Definition 4 (Accumulator).

Let D be a domain. An accumulator scheme Acc for D is a tuple (Setup, Eval, WitCreate, Verify) of PPT algorithms defined as follows.

Setup(1 λ , 1 n ): takes as input a security parameter λ and an integer n ∈ N upper bounding the number of elements that can be accumulated; outputs a pair of keys (P K, SK). Eval(P K, S): inputs a key P K, a set S ⊂ D of elements (with |S| ≤ n) to be accumulated and outputs an accumulated value V along with some auxiliary information aux. WitCreate(P K, S, V, aux, x, type): inputs a public key P K, a set S, a pair of accumulated value and state information (V, aux) generated by Eval(P K, S), an element x ∈ D and a boolean value type ∈ {0, 1} indicating whether the output should be membership or non-membership witness according as its value is 1 or 0 respectively. Case type = 1: If x / ∈ S, it returns ⊥. Otherwise, a membership witness W is returned. Case type = 0: It returns ⊥ if x ∈ S and a non-membership witness W otherwise.

Verify(P K, V, W, x, type): takes as input the public key P K, an accumulator V for set S, a witness W , an element x ∈ D and a boolean value type. Returns 1 if and only if either -W is a valid witness for x ∈ S and type = 1 -W is a valid witness for x / ∈ S and type = 0.

The above definition consider static accumulators. In dynamic accumulators, the accumulated value as well as witnesses can be publicly updated whenever an element is added to or deleted from the set. In this work, we only consider static accumulators.

The correctness condition requires that for all honestly generated keys, all honestly competed accumulators and witnesses, the Verify algorithm always accepts. An accumulator scheme is deemed secure if it is at least collision-free. Collision-freeness ensures the computational infeasibility of producing either a membership witness for an nonaccumulated value or a non-membership witness for an accumulated value.

Accumulators Supporting Subset Queries

In accumulators supporting subset queries, witnesses can be generated for a subset of the accumulated set rather than individual elements. While accumulators have been defined in the universal setting, i.e., both membership and non-membership witnesses can be generated, here we only consider the non-universal setting.

Definition 5 (Accumulator with subset queries). Let D be a domain. An accumulator scheme Acc for D is defined by a tuple (Setup, Eval, WitCreate, Verify) of probabilistic polynomial time algorithms defined as follows.

Setup(1 λ , 1 n , 1 d ): takes as input a security parameter λ, an upper bound n ∈ N on the number of elements that can be accumulated and an integer d ∈ N denoting the maximum size of a set for which a witness can be created; outputs a pair of keys (P K, SK). Eval(P K, S): takes in a public key P K, a set S ⊂ D of elements (with |S| ≤ n) to be accumulated and outputs an accumulated value V with some auxiliary information aux. WitCreate(P K, S, V, aux, X): inputs a public key P K, a set S, a pair of accumulated value and state information (V, aux) generated by Eval(P K, S), a set X ⊆ S with |X| ≤ d and outputs a witness W X . Verify(P K, V, W X , X): takes as input the public key P K, an accumulator V for set S, a witness W X , a set X ⊆ S. Returns 1 if W X is a witness for X ⊆ S and ⊥ otherwise.

In the above syntax, we assume that the auxiliary information aux includes the randomness that was used to compute V when Eval is a probabilistic algorithm.

A Functional Commitment from Subgroup Decision Assumptions

We prove that the Déjà Q framework [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions In Eurocrypt 2014[END_REF] allows proving security of the functional commitment of [START_REF] Izabachène | Blockwise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes[END_REF] under constant size assumptions by switching to composite order groups.

Setup(1 λ , 1 n ): Choose bilinear groups (G, G T ) of composite order N = p 1 p 2 p 3 , where

p i > 2 l(λ) for each i ∈ {1, 2, 3}, for a suitable polynomial l : N → N. Choose g, u R ← G p1 , R 3 R ← G p3 and α R ← Z N at
random in order to define G j = g α j for each j ∈ [1, n] and

U 1 = u α • R 3,1 , . . . U n = u (α n ) • R 3,n U n+2 = u (α n+2 ) • R 3,n+2 , . . . U 2n = u (α 2n ) • R 3,2n , where R 3,j R ← G p3 for each j ∈ [1, 2n]\{n + 1}. Define the commitment key to consist of CK := ( g, {G j } n j=1 , {U j } j∈[1,2n]\{n+1} , R 3
) .

The trapdoor is

T K := U n+1 = u (α n+1 ) • R 3,n+1 , where R 3,n+1 R ← G p3 . Commit(CK, ⃗ m): Given ⃗ m = (m 1 , . . . , m n ) ∈ Z n N , compute C = g γ • ∏ n j=1 G mj j
for a randomly chosen γ R ← Z N and output the commitment C with the auxiliary information aux = (m 1 , . . . , m n , γ).

Open(CK, C, aux, ⃗ x): Given

⃗ x = (x 1 , . . . , x n ) ∈ Z n , the information aux = (m 1 , . . . , m n , γ)
allows generating a witness for the function ⃗ m

• ⃗ x = ∑ n i=1 m i • x i by computing W i = U γ n-i+1 • n ∏ j=1,j̸ =i U mj n+1+j-i ∀i ∈ {1, . . . , n}, (1)
and outputting

W y = ∏ n i=1 W xi i . Verify(CK, C, W y , ⃗ x, y): Given C ∈ G and ⃗ x = (x 1 , . . . , x n ) ∈ Z n N , accept W y ∈ G as evidence that C is a commitment to ⃗ m ∈ Z n N such that y = ⟨ ⃗ m, ⃗ x⟩ if and only if it holds that e(C, ∏ n i=1 U xi n-i+1 ) = e(G 1 , U n ) y • e(g, W y ). If so, output 1. Otherwise, return 0.
The correctness is verified by observing that, for each i ∈ {1, . . . , n}, [START_REF] Acar | Revocation for Delegatable Anonymous Credentials[END_REF] implies that

e(C, U n-i+1 ) = e(g, u) (α n+1 )•mi • e ( g, U γ n-i+1 • n ∏ j=1,j̸ =i U mj n+j-i+1 ) = e(G 1 , U n ) mi • e(g, W i )
By raising both members of the above equality to the power x i ∈ Z N and taking the product over all i ∈ [1, n], we find that W y satisfies e(C,

n ∏ i=1 U xi n-i+1 ) = e(G 1 , U n ) ⟨ ⃗ m,⃗ x⟩ • e(g, W y ).
It is clear that the commitment is perfectly hiding: since C lives in the cyclic subgroup G p1 , any vector (m 1 , . . . , m n ) ∈ Z n N has a corresponding opening γ ∈ Z N (and even p 2 p 3 openings since only γ mod p 1 is fixed by ⃗ m). We now prove it computationally binding under subgroup assumptions. While this property can be proved via a reduction from the one-wayness of Wee's broadcast encryption [47, Section 4], we found it interesting to give a direct proof based on the underlying assumptions for two reasons. First, this proof allows relying on a computational (rather than decisional) analogue of Assumption 1. Second, the proof provides insights allowing to prove the security of variants of this commitment or the other primitives it implies. For example, by adapting the proof of Theorem 1, we design an accumulator supporting subset queries in section 5. Since the latter scheme has a public key containing more elements than in [START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF], it can hardly be proved secure via a reduction from the security of Wee's broadcast encryption [START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF].

The proof involves two computationally indistinguishable distributions of parameters (CK, T K). The normal distribution is as in the real scheme whereas the semi-functional distribution allows CK and T K to have a G p2 component. As in [47, Theorem 2], we use the Déjà Q framework so as to gradually move to a game where the

{U i } 2n i=1 all contain a G p2 component g R(i) 2
which is determined by a random function R : [1, 2n] → Z p2 . As in [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF][START_REF] Izabachène | Blockwise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes[END_REF], we rely on the fact that any attack against the binding property publicly reveals a value U n+1 which contains u (α n+1 ) as its G p1 component. Depending on whether U n+1 contains a G p2 component or not, we speak of Type B or Type A attacks. The proof uses a subsequence of 2n games where, in the k-th game, the G p2 component of U i is of the form g

F k (i) 2
, where F k : [1, 2n] → Z p2 is a k-wise independent function. The strategy of the proof is to show that, unless either Assumption 1 or Assumption 2 can broken, the attack on the binding property also reveals a U n+1 of the form

U n+1 = u (α n+1 ) • g F k (n+1) 2 • R 3 ,
for some R 3 ∈ G p3 in the k-th game. Said otherwise, the attack reveals a trapdoor U n+1 which mimics the distribution of the commitment key CK. When we reach the 2n-th game, the G p2 component of each U i is determined by F 2n (i). Since F 2n (.) is a 2n-wise independent function, the G p2 of U n+1 is thus statistically independent of those of {U i } i∈ [1,2n]\{i} , which appear in the public key. The detailed proof of Theorem 1 is given in Appendix C. Theorem 1. The scheme is binding if Assumption 1 and Assumption 2 both hold.

Further Constructions

Polynomial Commitments from Constant-Size Assumptions

It is easy to see that any functional commitment for linear functions implies a polynomial commitment scheme. Indeed, in order to commit to a polynomial

P [Z] = a 0 + a 1 Z + • • • + a n-1 Z n-1 of degree n -1,
we can simply commit to the vector containing the coefficients ⃗ m = (a 0 , a 1 , . . . , a n-1 ) ∈ Z n N . When the sender wants to convince a verifier that P (x) = y, for some public x, y ∈ Z N , it is sufficient to generate a witness W y showing that ⟨ ⃗ m, ⃗ x⟩ = y, where ⃗ x = (1, x, x 2 , . . . , x n-1 ). Our construction of Section 3 thus implies the first polynomial commitment based on constant-size assumptions. Indeed, the schemes of [START_REF] Kate | Constant-Size Commitments to Polynomials and their Applications[END_REF][START_REF] Camenisch | Composable & Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] rely on q-type assumptions where q is proportional to the maximal degree of committed polynomials.

Large-Universe Pairing-Based (Universal) Accumulators from Constant-Size Assumptions

In [START_REF] Catalano | Vector Commitments and their Applications[END_REF], Catalano and Fiore showed how to construct cryptographic accumulators from vector commitments. While their construction notably yields an accumulator based on the Computational Diffie-Hellman assumption, it only supports small universes. Namely, accumulated values should be taken from a polynomial-size domain since the public key has linear size in the cardinality of this domain.

It is easy to see that polynomial commitments imply accumulators for exponential-size universes. While the size of the public key is linear in the maximal number of accumulated values (as in Nguyen's accumulator [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF]), it does not depend of the universe size. As a result, we can accumulate inputs consisting of arbitrary strings of polynomial length.

In order to accumulate a set S = {x 1 , . . . , x n-1 }, one can simply commit to the ndimensional vector (a 0 , a 1 , . . . , a n-2 , 1) that contains the coefficients of the polynomial

P [Z] = ∏ n-1 j=1 (Z -x j ) =
∑ n-2 j=0 a j Z j + Z n-1 and rely on the fact that x ∈ S if and only if P (x) = 0. A witness that x i ∈ S (resp. x i ̸ ∈ S) is obtained by generating a witness that the committed polynomial satisfies P (x i ) = 0 (resp. P (x i ) ̸ = 0)). A concrete construction based on Assumptions 1 and 2 is described in Appendix B.

Accumulators Supporting Subset Queries

We now generalize the accumulator of Section 4.2 so that a constant-size witness W ∈ G can provide evidence that a purported set X is contained in the hashed set S. Such a commitment was previously designed by Papamanthou et al. [START_REF] Papamanthou | Optimal Verification of Operations on Dynamic Sets[END_REF] under a non-standard q-type assumption. Our construction is thus the first realization based on fixed-size assumptions.

Gen(1 λ , 1 n ): Choose bilinear groups (G, G T ) of composite order N = p 1 p 2 p 3 , where p i > 2 l(λ) for each i ∈ {1, 2, 3}, for a suitable polynomial l :

N → N. Choose g, u R ← G p1 , R 3 R ← G p3 and α R ← Z N at random. Let d ≤
n be the bound placed on size of a subset (also polynomial in the security parameter). Define G i = g (α i ) for each i ∈ [1, n] and

U 1 = u α • R 3,1 , U 2 = u (α 2 ) • R 3,2 , . . . , U n = u (α n ) • R 3,n U n+2 = u (α n+2 ) • R 3,n+2 , . . . , U 2n = u (α 2n ) • R 3,2n , . . . U dn+2 = u (α dn+2 ) • R 3,dn+2 , . . . , U (d+1)n = u (α (d+1)n ) • R 3,(d+1)n , where R 3,j R ← G p3 for each j ∈ [1, (d + 1)n]. The secret key is SK := {U ℓn+1 } d ℓ=1 , where U ℓn+1 = u (α ℓn+1 ) • R 3,ℓn+1 with R 3,ℓn+1 R ← G p3 for all ℓ ∈ [1, d].
The public key is

P K := ( g, {G j } n j=1 , {U j } j∈[1,(d+1)n]\{n+1,2n+1,...,dn+1} , R 3
) .

Eval(P K, S):

To hash a set S = {y 1 , . . . , y n ′ } of cardinality n ′ ≤ n -1, expand the

polynomial P S [Z] = ∏ n ′ j=1 (Z -y j ) = ∑ n ′ j=0 m j • Z j . Choose γ R ← Z N to compute and output V = g γ • n ′ +1 ∏ j=1 G mj-1 j = g γ+α•PS (α) , aux = (S, γ) (2)
WitCreate(P K, V, S, aux, X): Given a set S = {y 1 , . . . , y n ′ }, a subset X = {x 1 , . . . , x k } ⊆ S of size k ≤ d (we assume w.l.o.g. that x 1 , . . . , x k are arranged in some fixed lexicographical order), and the state information aux = (S, γ) such that (V, aux) was produced by Eval(P K, S), compute

P S [Z] = ∏ n ′ j=1 (Z -y j ) = ∑ n ′ j=0 m j • Z j and define the corresponding vector ⃗ m = (m 0 , m 1 , . . . , m n ′ , 0, . . . , 0) ∈ Z n N . For each ℓ ∈ [1, k], define ⃗ x ℓ = (x ℓ,1 , . . . , x ℓ,n ) = (1, x ℓ , x 2 ℓ , . . . , x n-1 ℓ ) ∈ Z n N which satisfies P S (x ℓ ) = ⟨ ⃗ m, ⃗ x ℓ ⟩ = 0. For ℓ ∈ [1, k], generate a witness that ⟨ ⃗ m, ⃗ x ℓ ⟩ = 0 by first using {U ℓn+1+j-i } j̸ =i to compute W ℓ,i = U γ ℓn-i+1 • n ∏ j=1,j̸ =i U mj ℓn+1+j-i ∀i ∈ {1, . . . , n}, (3)
which satisfies e(V,

∏ n i=1 U x ℓ,i ℓn+1-i ) = e(g, W ℓ,i ) for all ℓ ∈ [1, k] since ⟨ ⃗ m, ⃗ x ℓ ⟩ = 0.
Then, compute and output the witness

W X = ∏ k ℓ=1 ∏ n i=1 W x ℓ,i ℓ,i . Verify(P K, V, W X , X): Given an accumulator value V ∈ G, a subset X = {x 1 , . . . , x k },
where

x i ∈ Z N for each i ∈ [1, k],
and a candidate a witness W X , do the following.

1. For each ℓ ∈ [1, k], define ⃗ x ℓ = (x ℓ,1 , . . . , x ℓ,n ) = (1, x ℓ , . . . , x n ℓ ) ∈ Z n N . 2. Return 1 if and only if e(V, ∏ k ℓ=1 ∏ n i=1 U x ℓ,i ℓn+1-i ) = e(g, W X ).
From an efficiency standpoint, the size of P K is quadratic in n when we set d ≈ n so as to handle queries for arbitrary subsets of size ≤ n. In comparison with [START_REF] Papamanthou | Optimal Verification of Operations on Dynamic Sets[END_REF], we thus achieve security under simple assumptions at the expense of a somewhat larger public key. We see it as an interesting open problem to retain O(n)-size public keys under simple, constant-size assumptions.

We prove that the scheme provides collision-freeness (as defined in Appendix A) in the sense that no PPT adversary can output a set S (of size ≤ n -1) along with a verifying witness W X for another set X which is not contained in S. We thus use a natural analogue of the the definition of collision-freeness used in [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF]: since our evaluation algorithm is randomized, we assume that the adversary outputs the set S and the random coins γ of the evaluation algorithm that lead to the accumulator value for which W X properly verifies.

The proof crucially relies on the fact that the adversary outputs both the hashed set S and the random coins γ of the hashing algorithm. It allows the reduction to use W X in order to extract a membership witness for the difference X \ S by taking advantage of the homomorphic properties of the underlying commitment. Having obtained W X\S , the reduction is also able to compute an aggregation of non-membership witnesses for the same difference X \ S. From these two conflicting witnesses, it is possible to extract some linear combination of the secret key components {U ℓn+1 } d ℓ=1 . In turn, when we adapt the proof of Theorem 1, this forces the adversary to predict a linear combination of random function evaluations (which is statistically unpredictible) in the final step of the sequence of games.

Theorem 2. The scheme is collision-free if Assumption 1 and Assumption 2 hold. (The proof is available in Appendix D.)

A Security Definitions for Cryptographic Accumulators

This section recalls two important security notions for accumulators.

Informally undeniability requires that no PPT attacker be able to generate both membership and non-membership witnesses for any element of the domain.

Definition 6 (Undeniability). A cryptographic accumulator is undeniable if every PPT adversary A has negligible advantage in winning the following game.

-The challenger generates a pair of keys (P K, SK) by running the Setup algorithms and provides P K to the adversary A. -The adversary A eventually halts and outputs (V, x, W, W ). It wins if the conditions Verify(P K, V, W, x, 1) = 1 and Verify(P K, V, W , x, 0) = 1 are simultaneously satisfied.

As shown by [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF], the notion of undeniability implies that of collision-freeness and is actually strictly stronger. It was shown that there exist accumulators that are collisionfree but are not undeniable.

The notion of indistinguishability captures that the accumulations of any two distinct sets be computationally indistinguishable.

Definition 7 (Indistinguishability). An accumulator if for any PPT adversary A has negligible advantage in winning the following game.

-The challenger generates a pair of keys (P K, SK) by running the Setup algorithms and provides P K to the adversary A.

-A returns two sets S 0 , S 1 . The challenger picks a random bit β ∈ {0, 1}, computes (V, aux) ← Eval(P K, S b ) and provides V to A. -A returns a bit β ′ . A wins the game if β = β ′ .

Definition 8 (Collision-Freeness

). An accumulator supporting subset queries is collision free if every PPT adversary A has negligible advantage in winning the following game.

-The challenger generates a pair of keys (P K, SK) by running the Setup algorithms and provides P K to the adversary A. -A outputs (S, aux, X, W X ) with |S| ≤ n, |X| ≤ d and wins if Verify(P K, V, W X , X) = 1 and X ̸ ⊂ S, where V is the accumulator value produced by Eval on input of X and the randomness contained in aux.

B A Concrete Universal Accumulator based on Subgroup Decision Assumptions

Our universal accumulator uses a randomized evaluation algorithm so as to achieve the indistinguishability property of [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF]. It can be made deterministic setting γ = 0. The construction is a universal accumulator in that it supports both membership and nonmembership witnesses. The scheme can be seen as a variant of Nguyen's accumulator [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF] and goes as follows.

Gen(1 λ , 1 n ): Choose bilinear groups (G, G T ) of composite order N = p 1 p 2 p 3 , where p i > 2 l(λ) for each i ∈ {1, 2, 3}, for a suitable polynomial l : N → N. Choose g, u R ← G p1 , R 3 R ← G p3 and α R ← Z N at random in order to define G 1 = g α , G 2 = g (α 2 ) , . . . , G n = g (α n )
and

U 1 = u α • R 3,1 , . . . . . . , U n = u (α n ) • R 3,n U n+2 = u (α 2 ) • R 3,n+2 , . . . . . . , U 2n = u (α 2n ) • R 3,2n ,
where R 3,j R ← G p3 for each j ∈ [1, 2n]\{n + 1}. Define the public key as

P K := ( g, {G j } n j=1 , {U j } j∈[1,2n]\{n+1} , R 3
) .

The secret key is SK := α.

Eval(P K, S):

To hash a set S = {y 1 , . . . , y n ′ } of cardinality n ′ ≤ n -1, define the polynomial P [Z] = ∏ n ′ j=1 (Z -y j ) = ∑ n ′ j=0 a j • Z j (where a n ′ = 1) and the vector ⃗ m = (m 1 , . . . , m n ) = (a 0 , a 1 , . . . , a n ′ -1 , 1, 0, . . . , 0) ∈ Z n N . Then, choose γ R ← Z N and compute V = g γ • n ∏ j=1 G mj j = g γ+α•P (α) (4)
and output V and aux = (m 1 , . . . , m n , γ).

WitCreate(P K, V, S, aux, x, type): Given a set S = {y 1 , . . . , y n ′ } and the state information aux = (y 1 , . . . , y n ′ , γ) such that (V, aux) was produced by Acc(P K, S) and a Boolean value type ∈ {0, 1}, do the following:

-If type = 1, return ⊥ if x ̸ ∈ S. Otherwise, a membership witness is generated as a witness showing that V is a deterministic commitment to ⃗ m = (a 0 , a 1 , . . . , a n ′ -1 , 1, 0, . . . , 0) such that ⃗ m • (1, x, x 2 , . . . , x n-1 ) = 0. Namely, for the linear function ⃗ m • ⃗ x = ∑ n i=1 m i • x i by computing W i = U γ n-i+1 n ′ -1 ∏ j=1,j̸ =i U aj-1 n+1+j-i • U n+1+n ′ -i ∀i ∈ {1, . . . , n},
and outputting the witness

W = n ∏ i=1 W (x i-1 ) i . -If type = 0, return ⊥ if x ∈ S.
Otherwise, a non-membership witness obtained by first defining the vector ⃗ m = (a 0 , a 1 , . . . , a n ′ -1 , 1, 0, . . . , 0) containing the coefficients of

P [Z] = ∑ n ′ -1 j=0 a j Z j + Z n ′ = ∏ u∈S (Z -u).
The first part of the witness is the value

w x = ⃗ m • (1, x, x 2 , . . . , x n-1 ) = P (x) and the witness W x showing that ⃗ m • ⃗ x = w x .
The non-membership witness (w x , W X ) is returned. Verify(P K, V, W, x, type): Given an accumulator value V ∈ G, a witness W , an element

x of the universe Z N and a bit type ∈ {0, 1}, do the following:

-If type = 1, parse the witness as W ∈ G (and return 0 if it does not parse properly), define the vector ⃗ x = (1, x, x 2 , . . . , x n-1 ) ∈ Z n N and return 1 if and only if

e(V, n ∏ i=1 U (x i-1 ) n-i+1 ) = e(g, W ). (5)
Otherwise, return 0. -If type = 0, parse the witness W as (w x , W x ) ∈ Z N ×G and output 0 if it does not parse properly. Using x ∈ Z N , define ⃗ x = (1, x, x 2 , . . . , x n-1 ) ∈ Z n N and return 1 if and only if y ̸ = 0 and

e(V, n ∏ i=1 U (x i-1 ) n-i+1 ) = e(G 1 , U n ) wx • e(g, W x ). (6)
Otherwise, return 0.

From relation (4), we immediately see the similarity between Nguyen's accumulator [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF] and ours. In both schemes, the public key contains {g (α i ) } n i=0 and, in the deterministic version of our scheme (i.e., when γ = 0), the accumulator value is generated in the same way. The main difference is that, by introducing O(n) additional elements {U i } i∈ [1,2n]\{n+1} in the public key (which only increases its length by a small constant factor), we can generate witnesses in a different way.

Theorem 3. The above universal accumulator is unconditionally indistinguishable and provides undeniability if Assumption 1 and Assumption 2 hold.

Proof. The proof of indistinguishability is straightforward. As for the undeniability property, let us assume that, on input of a public key P K, an adversary A can produce an accumulator value V ∈ G and an element x ∈ Z N for which it manages to output accepting membership and non-membership witnesses W and (w x , W x ) that satisfy ( 5) and [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Signatures[END_REF], respectively. Such an adversary immediately implies an algorithm B that breaks the binding property of the functional commitment in Section 3. In the game of Definition 3, the binding adversary B outputs the vector ⃗ x = (1, x, x 2 , . . . , x n-1 ) ∈ Z n N and witnesses

W , W x , which convincingly prove ⃗ m • ⃗ x = 0, ⃗ m • ⃗ x = x x , respectively. ⊓ ⊔

C Proof of Theorem 1

Proof. Recall that, in order to break the binding property of the scheme, an adversary A must come up with a commitment C ∈ G, a vector

⃗ x = (x 1 , . . . , x n ) ∈ Z n N and two distinct values y, y ′ ∈ Z N with witnesses W y , W y ′ ∈ G such that e(C, n ∏ i=1 U xi n-i+1 ) = e(G 1 , U n ) y • e(g, W y ), (7)
e(C,

n ∏ i=1 U xi n-i+1 ) = e(G 1 , U n ) y ′ • e(g, W y ′ ).
By dividing the two equations of ( 7), we find that e(G 1 , U n ) y-y ′ = e(g, W y ′ /W y ). We first assume that y ′ ̸ = y mod p i for each i ∈ {1, 2, 3} since, otherwise, the reduction would be able to find a non-trivial factor of N , which would contradict either Assumption 1 or Assumption 2. If gcd(y

′ -y, N ) = 1, ∆W = ( W y ′ /W y ) 1/(y-y ′ ) is thus of the form ∆W = u (α n+1 ) • g r2 2 • g r3 3 ,
for some r 2 ∈ Z p2 and r 3 ∈ Z p3 . Note that ∆W can be seen as a "semi-functional" trapdoor in that it is equivalent to a product of the normal trapdoor T K with a G p2 component.

In the proof, we will distinguish two kinds of attacks against the binding property.

Type A attacks: are those for which ∆W = ( W y ′ /W y ) 1/(y-y ′ ) lives in the subgroup G p1p3 . Type B attacks: are such that ∆W has a G p2 component (i.e., r 2 ̸ = 0) and is thus a semi-functional trapdoor.

The proof proceeds via a sequence of games involving alternative distributions of the commitment key CK and the trapdoor T K. To define these alternative distributions, it will be convenient to define a family of functions

{F k : [1, 2n] → Z p2 } 2n k=0 such that F k (i) = k ∑ j=1 r j • α i j mod p 2 ∀k ∈ [1, 2n], F 0 (i) = 0 ∀i ∈ [1, 2n],
where r 1 , . . . , r 2n , α 1 , . . . , α 2n R ← Z p2 are chosen at random by the challenger that generates CK for the adversary. Having defined the function family {F k (.)} 2n k=1 , we can further consider several sub-classes of Type B attacks, where the semi-functional component of ∆W is determined by {F k (.)} 2n k=1 :

Lemma 1. In Game 0, any adversary producing a Type B attack implies a distinguisher for Assumption 1. We have Pr[win 0 ∧ ¬E 0 ] ≤ Adv 1 B (λ).

Proof. Let A be an adversary that mounts a Type B attack when fed with a commitment key CK of Type A. We build an algorithm B that takes as input (g ∈ G p1 , X 3 ∈ G p3 , T ) and finds an element η of G p2p3 with a non-trivial G p2 component. In turn, such an η ∈ G p2p3 allows deciding whether T ∈ G p1 or T ∈ G p1p2 since e(η, T ) = 1 GT when T ∈ G p1 . Algorithm B can faithfully generate the commitment key CK using its input elements g ∈ G p1 and X 3 ∈ G p3 . By hypothesis, A outputs a commitment C, two distinct values y, y ′ ∈ Z N and their corresponding witnesses W y , W y ′ ∈ G such that relations [START_REF] Benabbas | Verifiable Delegation of Computation over Large Datasets[END_REF]

| Pr[win k ∧ E k ] -Pr[win k-1 ∧ E k-1 ]]| ≤ Adv 2 B (λ).
Proof. Let us assume that there exist an index k ∈ [1, 2n] and an adversary A such that

ϵ = | Pr[win k ∧ E k ] -Pr[win k-1 ∧ E k-1 ]]|
G i = g (α i )
∀i ∈ [1, n].

It also chooses α 1 , . . . , α k-1 , r 1 , . . . , r k-1 R ← Z N and computes

U i = T (α i ) • (Y 2 Y 3 ) ∑ k-1 j=1 rj •α i j • R 3,i ∀i ∈ [1, 2n],
for randomly drawn R 3,i R ← G p3 , so that u is implicitly defined to be the

G p1 component of T . The commitment key CK = ( g, {G j } n j=1 , {U j } j∈[1,2n]\{n+1} , Z 3
) is given to A while B keeps the trapdoor T K := U n+1 to itself. Then, A is expected to output C ∈ G, y, y ′ ∈ Z N and W y , W y ′ ∈ G such that y ̸ = y ′ and which satisfy relations [START_REF] Benabbas | Verifiable Delegation of Computation over Large Datasets[END_REF]. At this point, B

computes ∆W = ( W y ′ /W y ) 1/(y-y ′ ) , which must be of the form ∆W = u (α n+1 ) • Y r2 2 • Y r3 3 . From ∆W , checks whether the equality e(X 1 X 2 , ∆W/U n+1 ) = 1 GT (8)
holds, which means that ∆W and U n+1 are identical in their G p1p2 component. If so, it also means that ∆W is a trapdoor of the same type as the commitment key CK. If [START_REF] Blum | Coin Flipping by Telephone[END_REF] is indeed satisfied, B thus outputs 1. Otherwise, it outputs 0. We remark that, if T ∈ R G p1p2 , then B is playing Game k -1 with A since we have

U i = u (α i ) • Y ∑ k-1 j=1 rj •α i j 2 • R3,i ∀i ∈ [1, 2n], for some random R3,i ∈ R G p3 . If T ∈ R G, it can be written T = u • Y s2 2 • Y s3
3 , so that we have

U i = u (α i ) • Y s2•α i + ∑ k-1 j=1 rj •α i j 2 • R3,i ∀i ∈ [1, 2n],
with uniformly random R3,i ∈ R G p3 . In this case, A's view is identical to its view in Game k, where r k = s 2 mod p 2 and α k = α mod p 2 (note that α mod p 2 is uncorrelated to α mod p 1 , so that α mod p 2 does not appear anywhere but in {U i } i̸ =n+1 ). As a consequence, if moving from Game k -1 to Game k significantly increases A's probability of mounting an attack of a different type than CK, then B outputs 1 with noticeably different probabilities when T ∈ R G p1p3 and T ∈ R G. This clearly contradicts Assumption 2.

⊓ ⊔

D Proof of Theorem 2

Proof. To break the collision-freeness of the scheme, the adversary must produce a set

S = {y 1 , . . . , y n ′ } of size n ′ ≤ n -1, another set X = {x 1 , . . . , x k } such that X ̸ ⊆ S, an exponent γ ∈ Z N , and a witness W X such that e(V, k ∏ ℓ=1 n ∏ i=1 U (x i-1 ℓ ) ℓn+1-i ) = e(g, W X ), (9)
where

⃗ x ℓ = (x ℓ,1 , . . . , x ℓ,n ) = (1, x ℓ , x 2 ℓ , . . . , x n-1 ℓ ) ∀ℓ ∈ [1, k]
and V is computed by defining the polynomial

P S [Z] = ∏ n ′ j=1 (Z -y j ) =
∑ n ′ j=0 m j Z j and its corresponding vector ⃗ m = (m 0 , . . . , m n ′ , 0, . . . , 0) ∈ Z n N before computing the accumulator value

V = g γ • ∏ n ′ +1 j=1 G mj-1 j
. By hypothesis, we know that there exists t ∈ [1, k] such that x t ∈ X \ S. For each x t ∈ X \ S, we assume that there exists no element y i ∈ S such that x t = y i mod p 1 , but x t ̸ = y i mod p 2 or x t ̸ = y i mod p 3 . Otherwise, a non-trivial factor of N would be exposed.

For each x t ∈ X \ S (where t denotes the position of x t in X in lexicographical order), we know that the vector ⃗ m = (m 0 , . . . , m n ′ , 0, . . . , 0) ∈ Z n N satisfies w t = ⟨ ⃗ m, ⃗ x t ⟩ ̸ = 0 mod N . We can assume w.l.o.g. that w t = ⟨ ⃗ m, ⃗ x t ⟩ ̸ = 0 mod p 2 since, otherwise, a factor of N would be extractable.

Knowing the vector ⃗ m = (m 0 , . . . , m n ′ , 0, . . . , 0) ∈ Z n N and the adversarially-supplied randomness

γ ∈ Z N such that V = g γ • ∏ n ′ +1 j=1 G mj-1 j , for each such x t ∈ X \ S, the reduction B can compute W t ∈ G such that e(V, n ∏ i=1 U (x i-1 t ) tn+1-i ) = e(G 1 , U tn ) wt • e(g, W t ), (10)
(where t ∈ [1, k] is the position of x t in X in lexicographical order) so that their product

W X\S = ∏ {t:xt∈X\S} W t satisfies e ( V, ∏ t:xt∈X\S n ∏ i=1 U (x i-1 t ) tn+1-i ) = ∏ t:xt∈X\S e(G 1 , U tn ) wt • e(g, W X\S ). (11)
Moreover, for each ℓ such that x ℓ ∈ X ∩ S (where ℓ ∈ [1, k] is the position of x ℓ in X in lexicographical order), the reduction can compute a witness W ℓ such that e(V,

n ∏ i=1 U x (i-1) ℓ ℓn+1-i ) = e(G 1 , U ℓn ) 0 • e(g, W ℓ ), since ⟨ ⃗ m, ⃗ x ℓ ⟩ = 0 mod N . If we compute the witness product W X∩S = ∏ {ℓ:x ℓ ∈X∩S} W ℓ , it thus satisfies e ( V, ∏ ℓ:x ℓ ∈X∩S n ∏ i=1 U (x i-1 ℓ ) ℓn+1-i ) = e(g, W X∩S ). (12)
Dividing ( 12) from ( 9), the reduction

B can compute WX\S = W X /W X∩S such that e ( V, ∏ ℓ:x ℓ ∈X\S n ∏ i=1 U (x i-1 ℓ ) ℓn+1-i ) = e(g, WX\S ).
If we further divide the above equality out of [START_REF] Boneh | Bivariate Polynomials Modulo Composites and Their Applications[END_REF], we find that W = WX\S /W X\S satisfies ∏

t:xt∈X\S e(G 1 , U tn ) wt = e(g, W ). (13)
From [START_REF] Boneh | Functional Encryption: Definitions and Challenges[END_REF], it is clear that W is of the form

W = u ∑ t:x t ∈X\S wt•(α tn+1 ) • g t2 2 • g t3 3 , (14)
for some t 2 ∈ Z p2 and t 3 ∈ Z p3 . The exponent of u in W is thus a linear combination of the discrete logarithms of secret key components U n+1 , U 2n+1 , . . . , U dn+1 .

In the proof, we will distinguish two kinds of attacks against the collision-freeness property.

Type A attacks: are those for which W lives in the subgroup G p1p3 (i.e., t 2 = 0). Type B attacks: are such that W has a G p2 component (i.e., t 2 ̸ = 0). The proof is organized as a hybrid argument over a sequence of (d + 1)n + 1 games with gradually varying distributions of P K and SK which are determined by a family of functions

{F ν : [1, (d + 1)n] → Z p2 } (d+1)n ν=0
such that for all j ∈ [1, (d + 1)n],

F ν (j) = { 0 if ν = 0 ∑ ν i=1 r j • α j i mod p 2 if ν ∈ [1, (d + 1)n]
where r 1 , . . . , r (d+1)n , α 1 , . . . , α (d+1)n are randomly distributed in Z p2 .

The sequence of games is -Game 0 (the real security game) followed by Game 1, Game 2, . . . , Game (d + 1)n. In Game ν (ν ∈ [0, (d + 1)n]), the challenger provides the adversary with Type ν public keys, which are defined analogously to Type ν parameters in the proof of Theorem 1. In particular, Type 0 public keys refer to normal public keys, which are distributed as in the real scheme as {U j } j∈ [1,(d+1)n] do not contain a G p2 component. In Type ν public keys, the group element U j (for j ∈ [1, (d + 1)n],) has a G p2 component determined by F ν :

U j = u α j • g Fν (j) 2 • R 3,
w t • F ν (tn + 1) mod p 2 . ( 15
)
For notational convenience, we define Type B.0 attacks to be identical to Type A attacks.

As in the proof of Theorem 1, for each ν ∈ [1, (d+1)n], we call win ν the event that the adversary A wins in Game ν. We also denote by E ν the event that A mounts a Type B.ν attack when provided with a Type ν public key. We now describe the games and prove that, unless either Assumption 1 or Assumption 2 is false, A always mounts a Type B.ν attack when run on input of Type ν parameters. In Game (d+1)n, we also argue that the probability Pr[E (d+1)n ] can only be statistically negligible because F ν (tn + 1) is totally unpredictable and, since w t ̸ = 0 mod p 2 , relation [START_REF] Camenisch | Solving Revocation with Efficient Update of Anonymous Credentials[END_REF] holds with negligible probability.

In Game 0, the public key P K provided to the adversary is generated as in the real scheme. We have Pr Proof. Let A be an adversary that mounts a Type B attack when given a public key P K of Type A. We build an algorithm B that takes as input (g ∈ G p1 , X 3 ∈ G p3 , T ) and finds an element η of G p2p3 with a non-trivial G p2 component. In turn, such an η ∈ G p2p3 allows deciding whether T ∈ G p1 or T ∈ G p1p2 since e(η, T ) = 1 G T when T ∈ G p1 .

Algorithm B can faithfully generate P K using its input elements g ∈ G p1 and X 3 ∈ G p3 . By hypothesis, A outputs set S and randomness γ that determine an accumulator value V as well as X ̸ ⊆ S for which W = WX\S /W X\S (as computed in the proof of Theorem 2) has a non-trivial G p2 component. Moreover, from [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF] se see that B can cancel out the G p1 component of W by computing η = W /u

is satisfied. If so, it means that W and ∏ t:xt∈X\S U wt tn+1 are identical in their G p1p2 component (and not only in their G p1 component). It also means that the G p2 component g t2 2 of W satisfies the condition [START_REF] Camenisch | Solving Revocation with Efficient Update of Anonymous Credentials[END_REF]. If [START_REF] Camenisch | Composable & Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] holds, B deduces that A's attack and the resulting W match the distribution of P K and outputs 1. Otherwise, it outputs 0.

We remark that, if T ∈ R G p1p2 , then B is playing Game ν -1 with A since we have

U j = u (α j ) • Y ∑ ν-1 i=1 ri•α j i 2 • R3,j ∀j ∈ [1, (d + 1)n],
for some R3,j ∈ R G p3 and relation [START_REF] Camenisch | Composable & Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] implies that event win ν-1 ∧ E ν-1 has occurred.

If T ∈ R G, it can be written

T = u • Y s2 2 • Y s3
3 , so that we have

U j = u (α j ) • Y s2•α j + ∑ ν-1 i=1 ri•α j i 2 • R3,j ∀j ∈ [1, (d + 1)n],
with uniformly random R3,j ∈ R G p3 . In this case, A's view is identical to its view in Game ν, where r ν = s 2 mod p 2 and α ν = α mod p 2 (note that α mod p 2 is uncorrelated to α mod p 1 ) and relation ( 16) is equivalent to event win ν ∧ E ν . As a consequence, if moving from Game ν -1 to Game ν significantly modifies A's probability of mounting an attack of the same type as P K, so does it affect B's probability of outputting 1 when T ∈ R G p1p3 is replaced by T ∈ R G.

⊓ ⊔ Lemma 5. Pr[win (d+1)n ∧ E (d+1)n ] ≤ 1/q 2 .

Proof. In the adversary's view, F (d+1)n (•) is a random function. For this reason, the values F (d+1)n (n+1), F (d+1)n (2n+1), . . . , F (d+1)n (dn+1) are independent and uniformly distributed over Z p2 conditioned on {F (d+1)n (j)} j∈ [1,(d+1)n]\{n+1,2n+1,...,dn+1} .

In the expression of W in the proof of Theorem 2, to keep the exponent t 2 of g 2 consistent with the public key, the adversary has to predict ∑ t:xt∈X\S w t • F (d+1)n (tn + 1) mod p 2 , which is a linear combination of random function outputs. Since this combination has at least one non-zero coefficient w t ̸ = 0 mod p 2 , the probability of predicting the above (and thus the probability that ( 16) holds true) value is at most 1/p 2 . ⊓ ⊔

Lemma 3 .

 3 [win 0 ] = Pr[win 0 ∧ E 0 ] + Pr[win 0 ∧ ¬E 0 ]. The second term is bounded above by the advantage in breaking Assumption 1, as established by Lemma 3. Essentially, it says that a PPT adversary can only mount a Type A attack when fed with Type 0 parameters. To bound the first term, Lemma 4 first implies that, if Assumption 2 holds, then Pr[win 0 ∧ E 0 ] and Pr[win (d+1)n ∧ E (d+1)n ] are negligibly far apart. Lemma 4 provides evidence that the probability Pr[win ν ∧ E ν ] of A mounting an attack of the same type as the public key remains essentially the same throughout the entire sequence of games. It only remains to show that Pr[win (d+1)n ∧ E (d+1)n ] is negligible. This is established in the proof of Lemma 5. Thus we have, Pr[win 0 ] ≤ Adv 1 B (λ) + (d + 1)n • Adv 2 B (λ) + 1 q2 , which is negligible under Assumption 1 and Assumption 2. ⊓ ⊔ If A is given a Type 0 public key and produces a Type B attack, then there exists an algorithm B such that Pr[win 0 ∧ ¬E 0 ] ≤ Adv 1 B (λ), where Adv 1 B (λ) denotes B's advantage in breaking Assumption 1.

∑Lemma 4 . 3 )

 43 t:x t ∈X\S wt•(α tn+1 ) , which indeed lives in G p2p3 and has a non-trivial G p2 component. At this point, B returns 1 (meaning that T ∈ G p1 ) if e(η, T ) = 1 GT and 0 otherwise.⊓ ⊔ | Pr[win ν ∧ E ν ] -Pr[win ν-1 ∧ E ν-1 ]| ≤ Adv 2 B (λ), where Adv 2 B (λ) denotes the advantage of an algorithm B in breaking Assumption 2. Proof. Algorithm B inputs (g, X 1 X 2 , Z 3 , Y 2 Y 3 , T ) and uses A to decide if T ∈ R G p1p3 or T ∈ R G.To this end, B generates the public key P K and the secret key SK as follows. It picks α R ← Z N and definesG j = g (α j ) ∀j ∈ [1, n].It also chooses α 1 , . . . , α ν-1 , r 1 , . . . , r ν-1 R ← Z N and computesU j = T (α j ) • (Y 2 Y 3 ) ∑ ν-1 i=1 rj •α j i • R 3,j ∀j ∈ [1, (d + 1)n], for random R 3,j R ← G p3 , so that u coincides with the G p1 component of T . The public key P K = ( g, {G j } n j=1 , {U j } j∈[1,(d+1)n]\{n+1,2n+1,...,dn+1} , Zis given to A while B keeps the secret key SK := {U n+1 , U 2n+1 , . . . , U dn+1 }. Then, A is expected to output At this point, B computes W = WX\S /W X\S as in the proof of Theorem 2. We know that W is of the form W = u∑ t:x t ∈X\S wt•(α tn+1 ) • g t2 2 • g t3 3 ,where u ∈ G p1 is the G p1 component of T . From W , checks whether the equality e   X 1 X 2 , W / ∏

  tuple of four (possibly probabilistic) polynomial time algorithms -(Setup, Commit, Open, Verify).

	Setup(1

λ , 1 n ): takes in a security parameter λ ∈ N, a desired message length n ∈ poly(λ) and outputs a commitment key CK and, optionally, a trapdoor T K. Commit(CK, ⃗ m): takes as input the commitment key CK, a message vector ⃗ m ∈ D n and outputs a commitment C for ⃗ m and auxiliary information denotes aux. Open(CK, C, aux, ⃗ x): takes as input the commitment key CK, a commitment C (to ⃗ m), auxiliary information (possibly containing ⃗ m) and a vector ⃗ x ∈ D n ; computes a witness W y for y = ⟨⃗ x, ⃗ m⟩ i.e., W y is a witness for the fact that the linear function defined by ⃗ x when evaluated on ⃗ m gives y. Verify(CK, C, W y , ⃗ x, y): takes as input the commitment key CK, a commitment C, a witness W y , a vector ⃗ x ∈ D n and y ∈ D; outputs 1 if W y is a witness for C being a commitment for some ⃗ m ∈ D n such that ⟨⃗ x, ⃗ y⟩ = y and outputs 0 otherwise.

  the two distributions {CK, Commit(CK, ⃗ m 1 )} and {CK, Commit(CK, ⃗ m 2 )} are identical given that the random coins of Commit are chosen according to the uniform distribution from the respective domain.The binding property requires the infeasibility of generating a commitment C and accepting witnesses for two distinct values y, y ′ without knowing the trapdoor T K. Commit, Open, Verify) for (D, n, ⟨•, •⟩) is said to be computationally binding if any PPT adversary A has negligible advantage in winning the following game.1. The challenger generates (CK, T K) by running Setup(λ, n) and gives CK to A. 2. The adversary A outputs a commitment C, a vector ⃗ x ∈ D n , two values y, y ′ ∈ D and two witnesses W y , W y ′ . We say that A wins the game if the following conditions hold.

	Definition 3 (Function Binding). A functional commitment scheme FC = (Setup,

  ′ ) has a non-trivial G p2 component. Moreover, B can cancel out the G p1 component of ∆W by computing η = ∆W/u (α n+1 ) , which is indeed an element of G p2p3 with a non-trivial G p2 component. At this point, B returns 1 (meaning that T ∈ G p1 ) if e(η, T ) = 1 GT and 0 otherwise. Under Assumption 2, the probability of A's attack to be a Type B.k attack in Game k is negligibly far apart from its probability of being a Type B.(k -1) attack in Game k -1. Concretely, there exists a distinguisher B running in about the same time as A and such that

	satisfied and ∆W =	( W y ′ /W y	are ) 1/(y-y ⊓ ⊔
	Lemma 2.

  is non-negligible. We build a distinguisher B with advantage ≥ ϵ against Assumption 2.Algorithm B takes as input (g, X 1 X 2 , Z 3 , Y 2 Y 3 , T ) and uses A to decide if T ∈ R G p1p3 or T ∈ R G. To this end, B generates the commitment key CK and the trapdoor T K as follows. It picks α

R

← Z N and defines

Acknowledgements

The first two authors were funded by the "Programme Avenir Lyon Saint-Etienne de l'Université de Lyon" in the framework of the programme "Investissements d'Avenir" (ANR-11-IDEX-0007). Part of this work was done while the third author was with Google Inc. and visiting the Simons Institute for Theory of Computing at U.C. Berkeley.

Type B.k attacks (0 ≤ k ≤ 2n): are such that ∆W = ( W y ′ /W y ) 1/(y-y ′ ) is of the form

• S 3 , for some S 3 ∈ G p3 . In this case, we say that ∆W is a Type B.k semi-functional trapdoor.

Using the function family {F k } 2n k=1 , we finally define gradually modified distributions for the commitment key CK and the trapdoor T K := U n+1 .

Type k parameters (0 ≤ k ≤ 2n): are parameters where elements {U i } i∈ [1,2n] now have a G p2 component determined by the function F k (.): namely,

These elements induce a modified joint distribution of CK, which contains the group elements {U i } i∈ [1,2n]\{n+1} , and

For convenience, we define Type B.0 attacks and Type 0 keys (CK, T K) as being identical to Type A attacks and normal keys (i.e., distributed like those of the real scheme), respectively.

The sequence of games begins with the real attack game, where the adversary is given a normal commitment key (with the same distribution as in the real scheme). Then, we gradually modify the distribution of CK and prove that, unless either Assumption 1 or Assumption 2 is false, the adversary will produce an attack of Type B.k when fed with parameters of Type k. In the last game, CK consists of Type B.2n parameters and we argue that the adversary's advantage in producing a Type B.2n attack is statistically negligible.

For each index 0 ≤ k ≤ 2n, we denote by win k the event that the adversary wins in Game k. We also define E k to be the event that A mounts a Type B.k attack when the commitment key CK is generated using Type k parameters. Game 0: The adversary A receives a commitment key CK which is as in the real scheme.

In

The commitment key CK and the trapdoor T K := U n+1 now have a modified distribution obtained by having the challenger generate Type k parameters before giving CK to A. Specifically, elements {U j } j∈ [1,2n] now have a G p2 component determined by the function F k (.):

Lemma 2 shows that, under Assumption 2, the probability that A's attack reveals a semi-functional T K of the same type as CK is about the same in Game k -1 and Game

. We conclude the proof by arguing that Pr[win 2n ∧ E 2n ] ≤ 1/p 2 , which is negligible. To see this, it suffices to observe that F 2n : [1, 2n] → Z p2 is a random function in the adversary's view, as shown in [START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF]Theorem 2]. Hence, conditionally on {F 2n (j)} j∈ [1,2n]\{n+1} , the function evaluation F 2n (n + 1) is uniformly distributed over Z p2 .

⊓ ⊔