Benoît Libert

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

Mahshid Riahinia
email: mahshid.riahinia@ens-lyon.fr

PointProofs, Revisited

Keywords: Vector commitments, aggregation, provable security

Vector commitments allow a user to commit to a vector of length n using a constant-size commitment while being able to locally open the commitment to individual vector coordinates. Importantly, the size of position-wise openings should be independent of the dimension n. Gorbunov, Reyzin, Wee, and Zhang recently proposed PointProofs (CCS 2020), a vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments, allowing to drastically reduce the cost of block propagation in blockchain smart contracts. Gorbunov et al. provide a security analysis combining the algebraic group model and the random oracle model, under the weak n-bilinear Diffie-Hellman Exponent assumption (n-wBDHE) assumption. In this work, we propose a novel analysis that does not rely on the algebraic group model. We prove the security in the random oracle model under the n-Diffie-Hellman Exponent (n-DHE) assumption, which is implied by the n-wBDHE assumption considered by Gorbunov et al. We further note that we do not modify their scheme (and thus preserve its efficiency) nor introduce any additional assumption. Instead, we prove the security of the scheme as it is via a strictly improved analysis.

Introduction

As introduced in [START_REF] Catalano | Vector commitments and their applications[END_REF][START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF], vector commitments (VCs) allow a user to commit to a vector of messages by generating a short commitment string. Later, the committer should be able to concisely reveal individual coordinates of the message vector. Here, "concisely" means that the partial opening information (called "proof" hereafter) should have constant size -no matter how large the committed vector is -and still convince the verifier that the opened coordinate is correct. As in standard commitments, a vector commitment scheme should satisfy two security properties: (1) A binding property which asserts that no efficient adversary should be able to generate a commitment of a vector that can be opened to two different values at the same position, and (2) a hiding property which guarantees that revealing a subset of components should not reveal any information about messages at non-revealed positions. Vector commitments enable significant savings in terms of storage, by storing only a constant-size commitment to a vector instead of commitments to individual coordinates, and bandwidth, thanks to the ability to provably and succinctly open individual positions.

In 2020, Gorbunov, Reyzin, Wee, and Zhang [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] introduced a vector commitment scheme, called PointProofs, which additionally supports non-interactive aggregation of proofs across multiple commitments. Two types of aggregation are supported:

-Same-commitment aggregation allows anyone to publicly aggregate singleposition proofs for the same vector commitment into a single proof; -Cross-commitment aggregation allows anyone to further aggregate samecommitment-aggregated proofs for distinct commitments (and possibly distinct subsets of positions) and fold them into a single constant-size proof.

Supporting proof aggregations is particularly useful for optimizing distributed applications, such as blockchain propagation. In this context, a third party (the validator) validates blocks by performing operations that depend on data owned by several distinct users. Vector commitments that support proof aggregation make it possible to drastically reduce storage: Instead of storing all users' data, each user can commit to their data individually so that a validator stores only their respective (concise) commitments. When needed, a user can compute proofs for opening positions relevant to the block validation, and aggregate these proofs into a single proof using same-commitment aggregation. Cross-commitment aggregation further allows a validator to aggregate all proofs from distinct users into a single proof that can be included in a block, letting other validators verify the block using a single proof. We also note that PointProofs supports updates of commitments, allowing a user who has already committed to a vector to update some components of this vector without having to compute a new vector commitment from scratch.

In [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], Gorbunov et al. consider the use case of blockchain smart contracts. They show that using their scheme instead of former state-of-the-art vector commitments allows a 60%-reduction of bandwidth overheads for propagating a block of transactions. In this work, we focus on improving the security analysis of the scheme without modifying it. We thus refer to [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] for further applications as well as for a detailed efficiency analysis of PointProofs in terms of space and time.

The security requirements of vector commitments with aggregation are easily defined by extending the standard hiding and binding requirements. Specifically, the hiding property requires that (possibly aggregated) proofs for opened positions do not reveal any information about unopened messages. The binding property is extended as follows: For same-commitment (resp. cross-commitment) aggregation, binding requires that no efficient adversary be able to come up with a vector commitment C (resp. a set of vector commitments C 1 , . . . , C ) together with two conflicting aggregated proofs, which open a position of an output vector commitment to two distinct values. While the PointProofs commitment is perfectly hiding (like its underlying vector commitment scheme [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF]), its computational binding property is argued in the algebraic group model, as well as in the random oracle model (ROM), under the n-wBDHE assumption in bilinear groups.

Recall that the algebraic group model (AGM) is an intermediate idealized model, introduced in [START_REF] Fuchsbauer | The Algebraic Group Model and its Applications[END_REF], that stands between the generic group model and the standard model. As a reminder, in the generic group model, adversaries do not have access to the bit representation of group elements: From the adversary's standpoint, each group element is represented by a unique uniformly random bitstring, and group operations are performed by querying an oracle that returns the representation of the resulting group element (to ensure uniqueness, the oracle keeps track of all group elements known to the adversary). In the generic group model, computational problems and their decisional variants are equivalent, and the Discrete Logarithm problem is provably intractable, as shown by Shoup in [START_REF] Shoup | Lower Bounds for Discrete Logarithms and Related Problems[END_REF]. This illustrates why proofs in the generic group model are more often considered as sanity checks rather than proofs of security.

The algebraic group model is a security model weaker than the generic group model, in which one only considers algebraic adversaries. Unlike the generic group model, no restriction is made regarding access to the group elements in the AGM: Algebraic adversaries have the same access to group elements as in the standard model. Yet, adversaries are restricted to only handle group elements that are computed by applying group operations to known group elements, similarly as in the generic group model. That is, given elements g 1 , . . . , g from a multiplicative group G, an algebraic adversary can only access elements of the form i=1 g λi i for coefficients λ i 's of its choice. Hence, the main difference between the generic group model and the algebraic group model is that the latter allows using coefficients λ i that depend on the actual bit representation of elements g i 's, while the former forbids it. Despite this minor relaxation, the algebraic group model is still considered as being very idealistic and to be avoided when it is possible.

Our Contribution. In this work, we provide a different security analysis of Point-Proofs, which relies on the Generalized Forking Lemma [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF] and the Local Forking Lemma [START_REF] Bellare | The Local Forking Lemma and its Application to Deterministic Encryption[END_REF]. Using these tools, we prove the scheme to be binding in the random oracle model, under the n-Diffie-Hellman Exponent (n-DHE) assumption in groups equipped with a bilinear map. As opposed to the original proof of Gorbunov et al. [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], we circumvent the use of algebraic group model, and rely on a weaker assumption; the n-DHE assumption being implied by the aforementioned n-wBDHE assumption. In the ROM, we thus prove the binding property under the same assumption as the one used in the underlying vector commitment scheme due to Libert and Yung [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF].

We believe this result to be important in the context of vector commitments as it proves the security of PointProofs as a vector commitment scheme supporting cross-commitment aggregation with constant-size openings under a falsifiable assumption [START_REF] Naor | On Cryptographic Assumptions and Challenges[END_REF] without restricting oneself to algebraic adversaries. Moreover, PointProofs is extremely efficient [START_REF] Tomescu | Aggregatable Subvector Commitments for Stateless Cryptocurrencies[END_REF] and, among known candidates supporting cross-commitment aggregation [START_REF] Boneh | Efficient polynomial commitment schemes for multiple points and polynomials[END_REF][START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF][START_REF] Srinivasan | Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments[END_REF], it is the only one that simultaneously provides optimal proof length and linear-size public parameters. Even if we only consider same-commitment aggregation, it implies one of the most efficient schemes with sub-vector openings among those [START_REF] Chepurnoy | Edrax: A Cryptocurrency with Stateless Transaction Validation[END_REF][START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF][START_REF] Kate | Constant-Size Commitments to Polynomials and Applications[END_REF][START_REF] Tomescu | Aggregatable Subvector Commitments for Stateless Cryptocurrencies[END_REF] that simultaneously feature linear-size public parameters and optimal-size proofs (recall that elements of a pairing-friendly group usually have a shorter representation than those of hidden-order groups).

We insist that we do not introduce any additional assumptions in Point-Proofs, neither do we alter the efficiency of the scheme in the process. Our approach thus provides a strict improvement over the prior analysis. Before outlining our security proof, we first briefly recall the PointProofs construction.

Construction. PointProofs builds on the vector commitment of [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF] and can also be seen as an application of the inner product functional commitment scheme of [START_REF] Libert | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions[END_REF], which are both inspired by the broadcast encryption scheme of Boneh, Gentry and Waters [START_REF] Boneh | Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]. Let n denote the dimension of committed vectors, and consider cyclic groups G = g and Ĝ = ĝ of prime order p equipped with an asymmetric bilinear map e : G × Ĝ → G T . Let g T = e(g, ĝ) be the generator of G T . The scheme uses public parameters g, ĝ, ) i and ĝi = ĝ(α) i , where α is chosen uniformly at random from Z p , and H : {0, 1} * → Z p is a hash function modeled as a random oracle.

{g i } i∈[2n]\{n+1} , {ĝ i } i∈[n] , H , with g i = g (α
To commit to a vector m = (m 1 , . . . , m n ) ∈ Z n p , one chooses γ ← U (Z p ) uniformly and computes a multi-base Pedersen commitment [START_REF] Pedersen | Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[END_REF] of the form

C = g γ • n j=1 g mj j = g γ+ n j=1 mi•α j
, which can be seen as raising g to the evaluation of a polynomial defined by the coefficients contained in m. To open a position i ∈ [n] of m to m i , the committer reveals a proof

π i = g γ n+1-i • n j=1,j =i g mj n+1-i+j = C/g mi•α i α n+1-i ,
which is an element of G whose discrete logarithm is the same polynomial evaluation as in C, except that the coefficient m i is lacking, and the polynomial is multiplied by α n-i+1 , so that π i does not depend on the monomial α n+1 . This proof can be easily verified by checking that

e(C, ĝα n+1-i ) = e(π i , ĝ) • g mi•α n+1 T ,
where g α n+1 T = e(g 1 , ĝn ) is computable from the public parameters. In order to aggregate multiple proofs (π i ) i∈S involving the same commitment C, where S ⊆ [n], anyone can derive randomness for each proof π i from the random oracle as t i ← H(i, C, S, m[S]), with m[S] being the sub-vector (m i ) i∈S , and define the aggregated proof as π S = i∈S π ti i . Verification is achieved in a similar way to the single position case, by additionally verifying the linear combination for coefficients provided by the random oracle evaluations. That is, the verifier checks that e(C,

ĝ i∈S α n+1-i •ti ) = e(π S , ĝ) • g α n+1 i∈S mi•ti T .
Finally, the cross-commitment aggregation of proofs (π S (j) ) j∈[ ] (which might result from the same-commitment-aggregation process) proceeds in a similar way. Again, some randomness t j ← H (j, {C (j) , S (j) , m (j) [S (j) ]} j∈ [d] ) is first derived from random oracle evaluations (of a second random oracle H ), and the cross-commitment aggregated proof is defined to be π = j=1 (π S (j) )

t j . Verification is performed in a similar way to the same-commitment-aggregated case: The verifier first derives all random coefficients (the t (j) i for i ∈ S (j) for each underlying same-commitment-aggregated proof, as well as the t j ) before verifying that

j∈[ ] e(C (j) , ĝ i∈S (j) α n+1-i •t (j) i ) t j = e(π, ĝ) • j∈[ ] g α n+1 • i∈S (j) m (j) i •t (j) i T t j . (1)
Technical Overview. As already mentioned, our proof strategy relies on the Local [START_REF] Bellare | The Local Forking Lemma and its Application to Deterministic Encryption[END_REF] and Generalized [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF] Forking Lemmas. We first briefly remind the intuition behind these lemmas. The standard Forking Lemma [START_REF] Pointcheval | Security Arguments for Signature Schemes[END_REF] considers the setting in which a probabilistic polynomial time adversary A, given access to a random oracle H, succeeds with non-negligible probability in some experiment which consists of outputting a pair (y, aux), where y lies in the domain of H and aux is some auxiliary information, such that the triplet (y, H(y), aux) satisfies a target condition. Let us denote by x 1 , . . . , x q the q queries made by A to the random oracle, and let us assume that y is the j-th query for some j ∈ [q]4 . The Forking Lemma states that running A again with the same coins but replacing H with another random oracle H which satisfies H (x i ) = H(x i ) for i < j, results in A succeeding again with some non-negligible probability with output (y, H (y), aux ). The important bit here is that A's output involves the same y, but now H (y) differs (with overwhelming probability) from H(y). This new triplet (y, H (y), aux ) is called a fork. This lemma has notably been used in the context of signature schemes based on applying the Fiat-Shamir paradigm to 3-round identification protocols [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF] with special-soundness, where the triplet (y, H(y), aux) is a transcript and the target condition is for it to be valid.

On one hand, the Local Forking Lemma [START_REF] Bellare | The Local Forking Lemma and its Application to Deterministic Encryption[END_REF] is a refinement of the standard Forking Lemma, which states that one is able to create a fork by replacing H by a random oracle H that only differs from H on the specific input y.

On the other hand, the Generalized Forking Lemma [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF] is an extension to the setting where multiple y's are generated by the adversary. That is, the output of A is of the form (y 1 , H(y 1 ), . . . , y , H(y ), aux) and allows to create forks for different y i 's, e.g., a first fork (y 1 , H (y 1 ), . . . , y , H(y ), aux ) and a second fork (y 1 , H(y 1 ), . . . , y , H (y ), aux ). Each fork is obtained by using a different random oracle that outputs the same values as H for all the queries preceding the forking point, and whose values are sampled uniformly at random and independently of H as soon as the forking point is hit. In the previous example, y 1 is the forking point of the first tuple and y is that of the second one.

We start by explaining how we reduce binding in the case of same-commitment aggregation to the hardness of the n-DHE problem. First, we recall that the n-DHE problem asks to compute g n+1 given g, ĝ,

{g i } i∈[2n]\{n+1} , {ĝ i } i∈[n]
(borrowing the notation from the construction described in the previous part). Consider an adversary A that manages to break the binding property with nonnegligible probability. Our n-DHE solver sets the public parameters to be the n-DHE instance and uses A as follows.

A is able to generate a tuple (C,

S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 ) containing a commitment C as well as two sets S 0 , S 1 ⊆ [n] such that S 0 ∩ S 1 = ∅ and valid proofs π 0 , π 1 with respect to sub-vectors m 0 [S 0 ] ∈ Z |S0| p , m 1 [S 1 ] ∈ Z |S1| p such that m 0 [i * ] = m 1 [i * ] for some i * ∈ S 0 ∩ S 1 .
The following holds for this output: 2to hold. One can then apply the Generalized Forking Lemma in order to create forks. In our case, the auxiliary information aux is the pair of proofs. We aim to obtain two forks: a first one of the form (C,

e(C, ĝα n+1-i ) i∈S b t (b) i = e(π b , ĝ) • g α n+1 i∈S b mi•t (b) i T , (2) where t (b)
S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 ), related to a random oracle H such that H(i * , C, S 0 , m 0 [S 0 ]) = H (i * , C, S 0 , m 0 [S 0 ]), and a second one of the form (C, S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 ), related to H and such that H(i * , C, S 1 , m 1 [S 1 ]) = H (i * , C, S 1 , m 1 [S 1 ]). In addition, we need that for all i ∈ S 0 \ {i * }, H(i, C, S 0 , m 0 [S 0 ]) = H (i, C, S 0 , m 0 [S 0 ]) and that for all i ∈ S 1 \ {i * }, H(i, C, S 1 , m 1 [S 1 ]) = H (i, C, S 1 , m 1 [S 1 ]).
Such forks are obtained by applying the Generalized Forking Lemma as follows: to ensure that the mentioned conditions about the values of H, H , H are satisfied, we design the reduction algorithm to simulate the random oracle such that all hash values for inputs (i,

C, S 0 , m 0 [S 0 ]) where i ∈ S 0 \ {i * } (resp. (i * , C, S 1 , m 1 [S 1 ]) where i ∈ S 1 \ {i * }) are set before setting the hash values for (i * , C, S 0 , m 0 [S 0 ]) (resp. (i * , C, S 1 , m 1 [S 1 ])).
More precisely, our reduction first makes a random guess about the value of i * , which is a correct guess with probability 1/n. Then, on receiving a query (i, C, S, m[S]), it checks whether i * ∈ S. If so, it first defines the hash values for inputs (i, C, S, m[S]) for all i = i * , and finally sets the value of H(i * , C, S, m[S]) at the end. Doing so, the conditions on the values of H, H , H are satisfied, and the Generalized Forking Lemma guarantees that the two desired forks can be obtained.

To conclude the proof, one simply re-writes Equation ( 2) with each fork using b = 0 and b = 1, respectively. The first fork leads to equation:

e(C, ĝα n+1-i ) i∈S 0 t i = e(π 0 , ĝ) • g α n+1 i∈S 0 mi•t i T ,
where t i = H (i, C, S 0 , m 0 ). A similar equation is obtained for the second fork. Thanks to the conditions satisfied by H, H , H values, it follows that for all i = i * , we have t

(0) i = t i and t (1) i = t i , where t i = H (i, C, S 1 , m 1 ).
Finally, combining these equations allows to recover an equation that depends only on terms e(g n+1 , ĝ), e(π 1 , ĝ), e(π 1 , ĝ), e(π 0 , ĝ), e(π 0 , ĝ). Setting aside the term e(g n+1 , ĝ) and focusing on the G-component, the reduction manages to compute g n+1 as a combination of π 1 , π 1 , π 0 , π 0 , which is the solution to the n-DHE problem.

In the supplementary material, we also propose a different proof which relies on the Local Forking Lemma, and compare this approach to the above one. These two proofs provide different bounds for the advantage and run-time of the reduction, and we believe that, in the context of PointProofs, the proof based on the Generalized Forking Lemma provides a tighter reduction.

The case of cross-commitment aggregation follows a similar strategy, but this time we reduce the binding property of the cross-commitment aggregations to that of the same-commitment aggregations. This proof is also in the random oracle model. Given an adversary A against the binding property of the cross-commitment scheme, we construct an adversary B against the binding property of the same-commitment scheme as follows: B splits the random oracles queries made by A into two categories: those corresponding to same commitment evaluations (the t (j) i 's in the above description), which are redirected by B to the random oracle to which it has access, and those corresponding to cross-commitment evaluations (the t j 's). B simulates the response to the queries of the second category. It first runs A which outputs two tuples of the form

π 0 , {C (j) 0 , S (j) 0 , m (j) 0 [S (j) 0 ]} j∈[d0] , π 1 , {C (j) 1 , S (j) 1 , m (j) 1 [S
(j) 1 ]} j∈[d1] ,
that breaks the binding property. In other words, there exist

j 0 ∈ [d 0 ], j 1 ∈ [d 1 ] such that C (j0) 0 = C (j1) 1
and m

(j0) 0 [i * ] = m (j1) 1 [i * ] for some i * ∈ S (j0) 0 ∩ S (j1) 1
. B then uses the Local Forking Lemma twice. In the first fork, it redefines the hash value of the query (j 0 , {C

(j) 0 , S (j) 0 , m (j) 0 [S (j) 0 } j∈[d0]
). The output of A in this fork involves the same first collection of commitments {C

(j) 0 , S (j) 0 , m (j) 0 [S (j) 0 ]} j∈[d0]
as in the initial execution, together with a proof π 0 . The equation obtained by running the verification algorithm (Equation 1) on this collection of commitments is such that the value of all t j 's are the same as A's first run except if j = j 0 . By forking a second time on query (j 1 , {C

(j) 1 , S (j) 1 , m (j) 1 [S (j) 1 } j∈[d1]
) and repeating the same arguments, B obtains two pairs of equations, that can be combined using a similar gymnastic as in the same-commitment proof to recover a valid attack against the binding property of the same-commitment aggregations.

We emphasize that using the Generalized Forking Lemma instead of the Local Forking Lemma does not seem to be an option in this case. Indeed, focusing on the first fork, our proof relies on the capacity to create a fork for the query (j 0 , {C

(j) 0 , S (j) 0 , m (j) 0 [S (j) 0 } j∈[d0]
) without changing every other hash values H(j, {C

(j) 0 , S (j) 0 , m (j) 0 [S (j) 0 } j∈[d0] ), for j ∈ [d 0 ] \ {j 0 }.
Using the Generalized Forking Lemma would require to set all the latter hash values before the value for (j 0 , {C

(j) 0 , S (j) 0 , m (j) 0 [S (j) 0 } j∈[d0]
), but contrary to the previous case, one cannot simply guess j 0 as it lies in an arbitrary range. For this reason, we rely on the Local Forking Lemma for proving the binding property in this case.

Related Work. Historically, vector commitments with logarithmic-size openings have been known for 3 decades, with the folklore construction based on Merkle trees [START_REF] Merkle | A Certified Digital Signature[END_REF]. In 2008, Catalano et al. [START_REF] Catalano | Zero-Knowledge Sets with Short Proofs[END_REF] called for constructions with constant-size openings with the motivation of compressing proofs in zero-knowledge databases [START_REF] Micali | Zero-Knowledge Sets[END_REF]. Vector commitments with O(1)-size openings appeared later on [START_REF] Catalano | Vector commitments and their applications[END_REF][START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF], with a first realization based on a q-type assumption put forth by Libert and Yung [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF]. Catalano and Fiore [START_REF] Catalano | Vector commitments and their applications[END_REF] obtained constructions from the standard RSA assumption and the Computational Diffie-Hellman assumption in pairingfriendly groups. Peikert et al. [START_REF] Peikert | Vector and Functional Commitments from Lattices[END_REF] recently came up with the first candidate under standard lattice assumptions. Meanwhile, applications of vector commitments were considered in the context of zero-knowledge databases [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF], verifiable data streaming [START_REF] Krupp | Nearly Optimal Verifiable Data Streaming[END_REF], authenticated dictionaries [START_REF] Leung | Aardvark: A Concurrent Authenticated Dictionary with Short Proofs[END_REF][START_REF] Tomescu | Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation[END_REF], de-centralized storage [START_REF] Campanelli | Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage[END_REF], succinct arguments [START_REF] Boneh | Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains[END_REF][START_REF] Lai | Subvector Commitments with Application to Succinct Arguments[END_REF], cryptocurrencies [START_REF] Chepurnoy | Edrax: A Cryptocurrency with Stateless Transaction Validation[END_REF][START_REF] Tomescu | Aggregatable Subvector Commitments for Stateless Cryptocurrencies[END_REF] and blockchain transactions [START_REF] Boneh | Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains[END_REF][START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], or certificates of collective knowledge [START_REF] Micali | Compact Certificates of Collective Knowledge[END_REF].

Back in 2010, Kate, Zaverucha and Goldberg [START_REF] Kate | Constant-Size Commitments to Polynomials and Applications[END_REF] introduced the related notion of polynomial commitments, which allows committing to a polynomial in such a way that the committer can later prove that the committed polynomial evaluates to specific values on certain inputs. They showed that their scheme enables batch openings, where a constant-size proof convinces the verifier about multiple polynomial evaluations at once. Libert, Ramanna and Yung [START_REF] Libert | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions[END_REF] suggested inner product functional commitments, which imply both vector commitments and polynomial commitments.

Lai and Malavolta [START_REF] Lai | Subvector Commitments with Application to Succinct Arguments[END_REF] and Boneh et al. [START_REF] Boneh | Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains[END_REF] independently generalized VCs by introducing the notion of sub-vector commitments, where the sender can generate a short proof π S that opens a sub-vector m[S] of m, for some subset S ⊆ [n]. Lai and Malavolta [START_REF] Lai | Subvector Commitments with Application to Succinct Arguments[END_REF] provided instantiations in hidden order groups and also showed that a variant of the Catalano-Fiore commitment [START_REF] Catalano | Vector commitments and their applications[END_REF] allows sub-vector openings under a constant-size assumption (namely, the cube-CDH assumption) in pairing-friendly groups. We remark that sub-vector commitments can also be realized from polynomial commitments with batch openings, as shown by Camenisch et al. [9, Section 3.1]. However, their construction intentionally prevents proof aggregation.

The property of proof aggregation was considered in [START_REF] Boneh | Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains[END_REF][START_REF] Campanelli | Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage[END_REF][START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF][START_REF] Srinivasan | Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments[END_REF][START_REF] Tomescu | Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation[END_REF]. Boneh, Bünz and Fisch [START_REF] Boneh | Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains[END_REF] and Tomescu et al. [START_REF] Tomescu | Aggregatable Subvector Commitments for Stateless Cryptocurrencies[END_REF] independently considered samecommitment aggregation in hidden-order groups and under q-type assumptions in pairing-friendly groups, respectively. Campanelli et al. [START_REF] Campanelli | Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage[END_REF] defined incrementally aggregatable VCs, where different sub-vector openings can be merged into a constant-size opening for the union of their sub-vectors. Moreover, aggregated proofs support further aggregation. They showed how to realize incrementally aggregatable VCs in hidden-order groups.

Gorbunov et al. [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] proposed PointProofs as the first construction enabling cross-commitment aggregation. They also showed [16, Appendix A] that a variant of the Lai-Malavolta commitment [START_REF] Lai | Subvector Commitments with Application to Succinct Arguments[END_REF] supports same-commitment aggregation, but still at the cost of quadratic-size public parameters. As underlined in [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], same-commitment aggregation implies sub-vector openings by having the committer aggregate same-commitment proofs.

In [16, Appendix B], Gorbunov et al. also showed that the restriction to algebraic adversaries is unnecessary if one just aims at a relaxed binding property -which may be sufficient in certain blockchain applications -which assumes honestly generated commitments. Here, we remove the restriction to algebraic adversaries even when commitments are adversarially generated.

The recent Hyperproofs construction of Srinivasan et al. [START_REF] Srinivasan | Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments[END_REF] also allows crosscommitment aggregation and makes it possible to update all proofs in sublinear time when the vector changes. On the downside, it loses the conciseness of PointProofs as its proofs have size O(log n). Besides [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF][START_REF] Srinivasan | Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments[END_REF], we are only aware of one alternative VC scheme supporting cross-commitment aggregation, which was proposed by Boneh et al. [START_REF] Boneh | Efficient polynomial commitment schemes for multiple points and polynomials[END_REF]. However, it is only known to be secure in the combined AGM+ROM setting.

Preliminaries

We use λ to denote the security parameter. For a natural integer n ∈ N, the set {1, 2, • • • , n} is denoted by [n]. We denote by negl(λ) a negligible function in λ, and PPT stands for probabilistic polynomial-time. For a finite set S, we write x R ← S to denote that x is sampled uniformly at random from S. We denote vectors by bold characters e.g. m. For a vector m = (m 1 , . . . , m n ) and a subset of indices S ⊆ [n], we denote by m[S] the sub-vector (m i1 , . . . , m i |S| ), where S = {i 1 , . . . , i |S| } with i j < i j+1 for each j ∈ {1, . . . , |S| -1}. For a single index i ∈ [n], we sometimes denote m i by m[i].

Bilinear Maps and Complexity Assumptions

Let (G, Ĝ, G T ) be cyclic groups of prime order p that are equipped with a bilinear map e : G × Ĝ → G T . We rely on a parameterized assumption which was introduced by Boneh, Gentry and Waters [START_REF] Boneh | Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]. While this assumption was originally defined using symmetric pairings [START_REF] Boneh | Hierarchical Identity-Based encryption with Constant Size Ciphertext[END_REF][START_REF] Boneh | Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF], we consider a natural extension to asymmetric pairings, which were used in PointProofs.

Definition 1. Let (G, Ĝ, G T ) be asymmetric bilinear groups of prime order p. The n-Diffie-Hellman Exponent (n-DHE) problem is, given (g, g α , g (α 2 ) , . . . , g (α n ) , g (α n+2 ) , . . . , g (α 2n ) , ĝ, ĝα , ĝ(α 2 ) , . . . , ĝ(α n ) )

where α R ← Z p , g R ← G, ĝ R ← Ĝ, to compute g (α n+1 ) .
We note that this assumption is the same as the one underlying the binding property of the vector commitment scheme of Libert and Yung [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF]. As an artifact of the algebraic group model, Gorbunov et al. [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] considered a stronger version of the above assumption where g (α 2n+1 ) , . . . , g (α 3n ) are also given.

Generalized Forking Lemma

Here, we recall the Generalized Forking Lemma as stated in [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF] which is later used in one of our proofs. Let SAMP() be a probabilistic algorithm that returns a value π which we think of as parameters. Also, consider an algorithm A that takes as input the parameters π and uses some randomness f = (ρ, h 1 , . . . , h Q ), where ρ is value of the random tape of A and h 1 , . . . , h Q are responses received by querying a random oracle H : {0, 1} * → Z p , and Q is the maximal number of the hash queries. We denote by F the space of all such randomness. Also, for any f ∈ F and i ∈ [Q], we denote by f |i the sub-vector (ρ, h 1 , . . . , h i-1 ). Algorithm A outputs a pair (L, {out } ∈L ), where L is a subset of [Q], and each out is a string, for ∈ L. We consider L = ∅ as failure, and L = ∅ as success. Let be the probability that the output of A(π, f ) is successful. We define the game G π,A as in Figure 1 parameterized by π and A, where π R ← SAMP(). We now state the lemma as proven by Bagherzandi et al. [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF] and used in [START_REF] Boneh | Compact Multi-Signatures for Smaller Blockchains[END_REF].

f = (ρ, h1, . . . , hQ) R ← F (L, {out } ∈L ) ← A(π, f ) If L = ∅ output 0. Else, let L = ( 1, . . . , m) such that 1 ≤ • • • ≤ m For i = 1, . . . , m do Set succi ← 0, ki ← 0, kmax ← 8mQ/ • ln(8m/ ) While succi = 0 and ki < kmax do f R ← F such that f | i = f | i Let f = (ρ, h1, . . . , h i -1 , h i , . . . , h Q ) (L , {out } ∈L ) ← A(π, f ) If h i = h i
Lemma 1 (Generalized Forking Lemma [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF]). Let SAMP, A, and H : {0, 1} * → Z p be as described, where A runs in time τ and succeeds with probability . If p > 8mQ/ , then the game G π,A runs in time at most τ • 8m 2 Q/ • ln(8m/ ), and is successful with probability at least /8.

Local Forking Lemma

We also recall the Local Forking Lemma of Bellare et al. [START_REF] Bellare | The Local Forking Lemma and its Application to Deterministic Encryption[END_REF], which will be used in our proof for the cross-commitment case. The difference with the classical Forking Lemma is that the random oracle is only reprogrammed on the forking point, instead of all points from the forking point onwards.

Let SAMP() be a probabilistic algorithm that returns a value π which we think of as parameters. We also consider a deterministic algorithm A, that given π R ← SAMP(), and having access to a random oracle H ∈ H, outputs an integer α ≥ 0, and a string x. We consider α = 0 as failure, and α ≥ 1 as success. If α ≥ 1, we require x to be the α-th query that A has issued to the oracle H. We consider the two following games parameterized by π and A, where π R ← SAMP():

H R ← H (α, x) ← A H (π) If α ≥ 1 Return 1 Otherwise Return 0 Game G single π,A H R ← H (α, x) ← A H (π) H ← H H [x] R ← {0, 1} * (α , x ) ← A H (π) If (α = α ) ∧ (α ≥ 1) Return 1 Otherwise Return 0 Game G double π,A
Fig. 2. Game G single π,A , and Game G double π,A , where the local forking happens in the latter.

We now recall the statement of the lemma.

Lemma 2 (Local Forking Lemma, [START_REF] Bellare | The Local Forking Lemma and its Application to Deterministic Encryption[END_REF]). Let SAMP and A be as described, and let q be the number of H-queries issued by A. It holds that:

Pr[G double π,A = 1] ≥ 1/q • Pr[G single π,A = 1] 2 .

Vector Commitments with Aggregation

We recall the formal definition of vector commitments with aggregation introduced in [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF]. As in [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], we divide the definition into two parts; the case of same-commitment aggregation, and the case of cross-commitment aggregation.

Same-Commitment Aggregation

Definition 2 (Vector Commitment with Same-Commitment Aggregation [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF]). A vector commitment with same-commitment aggregation for message space M consists of six algorithms Setup, Commit, UpdateCommit, Prove, Aggregate, Verify as follows:

Setup(1 λ , 1 n ) → pp : On input the security parameter λ and a number n which is the length of underlying vector of a commitment in the scheme, it outputs public parameters pp that is used by all other algorithms. Prove pp (i, m i , aux) → π i : On input an index i ∈ [n] and a message bit m i ∈ M, uses the auxiliary information aux that was used in the algorithm Commit to output a proof π i for this message bit. We require a vector commitment scheme with same-commitment aggregation to satisfy the following properties:

Correctness of Opening. For all λ, n, m = (m 1 , . . . , m n ) ∈ M n , and Binding. For all λ, n, and any PPT adversary A, the probability of finding a tuple (C,

S ⊆ [n], Pr      Verify(C, S, m[S], π S ) = 1 : pp ← Setup(1 λ , 1 n ) C ← Commit pp (m; aux) {π i ← Prove pp (i, m i , aux)} i∈S π S ← Aggregate(C, S, m[S], {π i } i∈S )      = 1.

Correctness of

S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 ), such that Verify(C, S 0 , m 0 [S 0 ], π 0 ) = Verify(C, S 1 , m 1 [S 1 ], π 1 ) = 1 and m 0 [i] = m 1 [i] for some i ∈ S 0 ∩ S 1 , is negligible in λ.

Cross-Commitment Aggregation

Definition 3 (Vector Commitment with Cross-Commitment Aggregation [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF]). A vector commitment with cross-commitment aggregation for message space M consists of the six algorithms Setup, Commit, UpdateCommit, Prove, Aggregate, Verify as in the same-commitment case, and two additional algorithms AggregateAcross, and VerifyAcross that are as follows:

AggregateAcross pp ({C j , S j , m j [S j ], π j } j∈[d]
) → π: Takes as input a collection of commitments C j together with each of their aggregated proofs π j with respect to subset S j and message sub-vector m j [S j ], and outputs a crossaggregated proof π.

VerifyAcross pp (π, {C j , S j , m j [S j ], π j } j∈[d]
) → b: Given a cross-aggregated proof π, and a collection of underlying commitments, subsets, and message subvectors {C j , S j , m j [S j ], π j } j∈ [d] , this algorithm outputs a bit b ∈ {0, 1}.

We require a vector commitment scheme with cross-commitment aggregation to satisfy the correctness of opening as in Definition 2 extended to crosscommitment aggregations. Also, it should satisfy an extension of binding property as follows:

Binding (for cross-commitments). For all λ, n, and any PPT adversary A, the probability of finding the two following tuples with the following described properties is negligible in λ:

(π 0 , {C (j) 0 , S (j) 0 , m (j) 0 [S (j) 0 ]} j∈[ 0] ), and (π 1 , {C (j) 1 , S (j) 1 , m (j) 1 [S (j) 1 ]} j∈[ 1] ), such that VerifyAcross(π 0 , {C (j) 0 , S (j) 0 , m (j) 0 [S (j) 0 ]} j∈[ 0] ) = VerifyAcross(π 1 , {C (j) 1 , S (j) 1 , m (j) 1 [S (j) 1 ]} j∈[ 1 ] ) = 1
and there exist j 0 ∈ [ 0 ], and

j 1 ∈ [ 1 ], for which it holds that C (j0) 0 = C (j1) 1
, and m (j0)

0 [i] = m (j1) 1 [i], for some i ∈ S (j0) 0 ∩ S (j1) 1 .

Statistical Hiding

As stated in [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], one can optionally require a vector commitment scheme to generate commitments that are hiding. Intuitively, this property requires that any commitment C that is generated in the scheme must reveal no information about its underlying message vector m. Also, any proof π i generated with respect to the i-th element m i of a message vector m = (m 1 , . . . , m n ) should not reveal any information about any other element m j of the message, where j = i.

Since PointProofs were already proven to be statistically hiding in [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], we rather focus only on the binding property and do not further detail hiding. We refer the reader to [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] for a details regarding the hiding property.

The Case of Same-Commitment Aggregation

We first consider the simpler variant of PointProofs [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] which only allows aggregating proofs for sub-vectors contained in the same commitment. This construction implicitly uses the functional commitment scheme of [START_REF] Libert | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions[END_REF] to aggregate proofs using randomizers derived from a random oracle. Its description is as follows.

Setup(1 λ , 1 n ): To generate public parameters, do the following:

1. Choose bilinear groups (G, Ĝ, G T ) of prime order p > 2 λ and g R ← G, ĝ R ← Ĝ. 2. Pick a random α R
← Z * p and compute g 1 , . . . , g n , g n+2 , . . . , g 2n ∈ G as well as ĝ1 , . . . , ĝn ∈ Ĝ, where g i = g (α i ) for each i ∈ [2n] \ {n + 1} and ĝi = ĝ(α i ) for each i ∈ [n]. 3. Choose a hash function H : {0, 1} * → Z p that will be modeled as a random oracle in the analysis.

The public parameters are defined to be

pp = g, ĝ, {g i } i∈[2n]\{n+1} , {ĝ i } i∈[n] , H
and the trapdoor is tk = g n+1 = g (α n+1 ) .5

Commit pp (m 1 , . . . , m n ; aux): To commit to a vector (m 1 , . . . , m n ) ∈ Z n p , choose γ R ← Z p and compute

C = g γ • n j=1 g mj j .
The output is C and the auxiliary information is aux = (m 1 , . . . , m n , γ).

UpdateCommit pp (C, S, m[S], m [S], aux): Given C ∈ G and the state informa- tion aux = (m 1 , . . . , m n , γ), choose γ R ← Z p and compute C = g γ • C • j∈S g m [j]-m[j] j
together with aux = ( m1 , . . . , mn , γ + γ ), where mi = m i if i ∈ S and mi = m i if i ∈ S. Prove pp (m i , i, aux): Parse aux as (m 1 , . . . , m n , γ) and compute

π i = g γ n+1-i • n j=1,j =i g mj n+1-i+j . (3)
The opening of C at position i consists of π i ∈ G. Aggregate pp (C, S, m[S], {π i } i∈S ): Given a commitment C ∈ G, a sub-vector m[S] with S ⊆ [q], and the corresponding proofs {π i } i∈S , compute

π S = i∈S π ti i where t i = H(i, C, S, m[S]). Verify pp (C, S, m[S], π S ): Given π S ∈ G return 1 if C ∈ G and e(C, i∈S ĝti n+1-i ) = e(π S , ĝ) • e(g 1 , ĝn ) i∈S m[i]•ti (4)
where

t i = H(i, C, S, m[S]
) for each i ∈ S. Otherwise, it returns 0.

In [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF], the scheme was proven binding in the algebraic group model and in the random oracle model. We now show that, using the Forking Lemma [START_REF] Pointcheval | Security Arguments for Signature Schemes[END_REF] (more precisely, its generalization used in [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF][START_REF] Boneh | Compact Multi-Signatures for Smaller Blockchains[END_REF]), we can prove its security in the random oracle model (i.e., without using the algebraic group model) under the n-DHE assumption, which already underlies the binding property of the vector commitment scheme in [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF].

In Supplementary Material A, we provide an alternative proof using the Local Forking Lemma [START_REF] Bellare | The Local Forking Lemma and its Application to Deterministic Encryption[END_REF] and give a comparison between the advantage/running-time ratios of the two reductions.

We note that the security analysis of [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] highlighted the necessity of including S and m[S] among the inputs of the hash function when the coefficient {t i } i∈S are computed in the aggregation algorithm. Consistently with this observation, the proof of Theorem 1 crucially relies on the fact that (S, m[S]) are hashed along with (i, C).

In order to rely on the General Forking Lemma, we need to answer random oracle queries in a careful way, by adapting a technique used by Boneh et al. [START_REF] Boneh | Compact Multi-Signatures for Smaller Blockchains[END_REF] in the context of multi-signatures supporting key aggregation.

Theorem 1. The above commitment is binding in the random oracle model if the n-DHE assumption holds.

Proof. Suppose that the adversary A is able to generate a commitment C as well as two sets S 0 , S 1 ⊂ [n] such that S 0 ∩S 1 = ∅ and convincing proofs π 0 , π 1 respectively for sub-vectors m

0 [S 0 ] ∈ Z |S0| p , m 1 [S 1 ] ∈ Z |S1| p such that m 0 [i] = m 1 [i] for some i ∈ S 0 ∩ S 1 .
Let Pr[¬Bind] be the probability of A generating such tuple. In the random oracle model, we build an algorithm C that uses A to solve the n-DHE problem. Let q H be the maximum number of queries that A can issue to the random oracle H.

Consider an algorithm SAMP that generates an n-DHE instance

π = g, ĝ, {g i } i∈[2n]\{n+1} , {ĝ i } i∈[n]
, and an algorithm B that on input π and randomness f = (ρ, h 1 , . . . , h Q ), where Q = n • q H , does as follows.

B begins by drawing a random index i

† R ← U ([n]). It runs A on input g, ĝ, {g i } i∈[2n]\{n+1} , {ĝ i } i∈[n]
and randomness ρ. First, B initializes a counter = 0, which it increments every time it sets a new hash value. When A makes a H-query (i, C, S, m[S]), B uses the values in (h 1 , . . . , h Q ) to respond as follows:

-If the input (i, C, S, m[S]) is such that the hash value H(i, C, S, m[S]) was previously defined, B returns the previously-defined value. C,S,m[S]) is such that i † ∈ S, then B does the following: For each index i ∈ S \ {i † }, it increments and sets H(i , C, S, m[S]) ← h . Finally, it increments and sets H(i † , C, S, m[S]) ← h . Note that B programs H on |S| inputs at once for such hash queries and that

H(i † , C, S, m[S]
) is set after all other inputs for indices i ∈ S \ {i † }. Then, B returns the corresponding value of H(i, C, S, m[S]) to A. -Else, B increments and returns h as the value for H(i, C, S, m[S]).

Since A makes at most q H and B sets at most n hash values at each query, at most Q = n • q H values are set in the process.

With probability := Pr

[¬Bind], A outputs (C, S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 ) such that e(C, i∈S0 ĝt (0) i n+1-i ) = e(π 0 , ĝ) • e(g 1 , ĝn ) i∈S 0 m0[i]•t (0) i (5) e(C, i∈S1 ĝt (1) i n+1-i ) = e(π 1 , ĝ) • e(g 1 , ĝn ) i∈S 1 m1[i]•t (1) i (6) where t (b) i = H(i, C, S b , m b [S b ]) for each i ∈ S b and b ∈ {0, 1}. Then, B de- termines the smallest i ∈ S 0 ∩ S 1 such that m 0 [i ] = m 1 [i ]. If i = i † , it
aborts and outputs (∅, ∅). Otherwise, if i = i † (which is the case with probability 1/n since i † is drawn uniformly and independently of A's view), let 0 ∈ [Q] be the index of the random oracle query H(i , C, S 0 , m 0 [S 0 ]) and let 1 ∈ [Q] be the index of the random oracle query H(i , C, S 1 , m 1 [S 1 ]). Let h 0 , h 1 ∈ Z p be the corresponding responses. Note that, due to the way B sets the responses to random oracle queries, any value

H(i, C, S b , m b [S b ]) for an in- dex i ∈ S b \ {i } is set before H(i , C, S b , m b [S b ]) = h b , for b ∈ {0, 1}. Finally, B outputs (L = { 0 , 1 }, {out 0 , out 1 }), where out 0 = out 1 = (C, S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 , h 0 , h 1 ) (7)
Note that B outputs a-non empty subset L = { 0 , 1 } successfully with probability at least /n. Now, we describe a reduction C that solves an n-DHE instance g, ĝ, {g i } i∈[2n]\{n+1} , {ĝ i } i∈[n] using A. Algorithm C runs the game G B,π defined in Figure 1, where π is the given n-DHE instance, and B is the algorithm that uses the adversary A as described above. If the game outputs 0, then C aborts. By Lemma 1, with probability at least ( /n)/8, G B,π outputs (L = { 0 , 1 }, {out 0 , out 1 }, {out 0 , out 1 }) after having forked twice. Then, C parses out 0 and out 1 as in [START_REF] Boneh | Compact Multi-Signatures for Smaller Blockchains[END_REF] 5)- [START_REF] Boneh | Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments[END_REF]. It also parses out 0 and out 1 as described hereunder and performs the following computations:

• For the first forking, it parses

out 0 = (C, S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 , h 0 , h 1 ),
where Verify outputs 1 on both (C, S 0 , m 0 [S 0 ], π 0 ), and (C, S 1 , m 1 [S 1 ], π 1 ). Note that (S 1 , m 1 [S 1 ]) may differ from their counterparts (S 1 , m 1 [S 1 ]) of the first execution but it does not matter. What matters is that the second run involves the same (S 0 , m 0 [S 0 ]) as in the first execution and the hash query

H(i , C, S 0 , m 0 [S 0 ]
) is also the 0 -th hash query in the second execution, where it obtains a different response h 0 . This holds since the forking occurs at the 0 -th oracle query and the executions are identical up to that point. Hence, the 0 -th query is indeed issued on the input (i , C, S 0 , m 0 [S 0 ]) during the forking. Now, since the index i ∈ S 0 ∩ S 1 determined in the first run belongs to S 0 , we know that

t (0) i = H(i , C, S 0 , m 0 [S 0 ]) = h 0 = h 0 , but
i n+1-i ) = e(π 0 /π 0 , ĝ) • e(g 1 , ĝn ) m0[i ]•∆t (0) i , (0)
where ∆t

(0) i h 0 -h 0 = 0.
• For the second forking, the reduction C parses out

1 as out 1 = (C, S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 , h 0 , h 1 )
. Here, (S 0 , m 0 [S 0 ]) may differ from the pair (S 0 , m 0 [S 0 ]) extracted from out 1 at the very first execution, but it does not matter. The forking point being the 1 -th hash query, we know that the first and third executions are identical up to that point. Consequently, the 1 -th query is issued on the input (i , C, S 1 , m 1 [S 1 ]) in this forking, where it obtains a different response h

1 than in the very first run. With non-negligible probability, Lemma 1 ensures that B's output in this forking involves the same (S 1 , m 1 [S 1 ]) as in the first run and the hash query H(i , C, S 1 , m 1 [S 1 ]) is also the 1 -th hash query. Since i ∈ S 1 , we can repeat the same arguments as in the first fork and, by dividing out the verification equations ( 6) of the first and third runs, B obtains e(C, ĝ∆t

i

n+1-i ) = e(π 1 /π 1 , ĝ) • e(g 1 , ĝn ) m1[i ]•∆t (1) i , (9)
where ∆t

(1) i h 1 -h 1 = 0.
Then, raising both members of (9) to the power ω ∆t

(0) i /∆t (1) i yields e(C, ĝ∆t (0) i n+1-i ) = e((π 1 /π 1 ) ω , ĝ) • e(g 1 , ĝn ) m1[i ]•∆t (0) i . ( 10
)
If we now use the hypothesis that m 0 [i ] = m 1 [i ], the combination of ( 10) and ( 8) implies

e(π 0 /π 0 , ĝ) • e(g 1 , ĝn ) m0[i ]•∆t (0) i = e((π 1 /π 1 ) ω , ĝ) • e(g 1 , ĝn ) m1[i ]•∆t (0) i .
Now, since e(g 1 , ĝn ) = e(g n+1 , ĝ), we have:

e(g n+1 , ĝ) ∆t (0) i •(m0[i ]-m1[i ]) = e((π 1 /π 1 ) ω , ĝ)/e(π 0 /π 0 , ĝ),
which then allows B to compute the sought-after n-DHE solution, by looking only at the G-components, as

g n+1 (π 1 /π 1 ) ω π 0 /π 0 1 ∆t (0) i •(m0[i ]-m1[i ]) . (11)
By Lemma 1, with probability at least ( /n)/8, the reduction C succeeds in solving the n-DHE problem.

The Case of Cross-Commitment Aggregation

Let H : {0, 1} * → Z p be a hash function modeled as a random oracle. Algorithms AggregateAcross and VerifyAcross are as follows:

AggregateAcross pp ({C (j) , S (j) , m (j) [S (j) ], π j } j∈[d] ): Given a collection of ({C (j) , S (j) , m (j) [S (j) ], π j } j∈[d] ), where each π j is the same-commitmentaggregated proof of C (j) with respect to the sub-vector of message m (j) limited to indices in S (j) , compute and output

π = d j=1 (π j ) t j ,
where t j = H (j, {C (j) , S (j) , m (j) [S (j) ]} j∈ [d] ).

VerifyAcross(π, {C (j) , S (j) , m (j) [S (j) ],

π j } j∈[d] ): Given π ∈ G, return 1 if C (j) ∈ G for all j ∈ [d],
and

d j=1 e   C (j) , i∈S (j) ĝtj,i n+1-i   t j = e(π, ĝ) • e (g 1 , ĝn ) j∈[d],i∈S (j) m (j) [i]•tj,i•t j where t j,i = H(i, C (j) , S (j) , m (j) [S (j) ]), t j = H (j, {C (j) , S (j) , m (j) [S (j) ]} j∈[d] ).
We now prove the cross-commitment binding property under the n-DHE assumption in the ROM, without restricting ourselves to algebraic adversaries.

Here, we rely on the Local Forking Lemma instead of the Generalized Forking Lemma. The reason is that the proof of Theorem 2 proceeds with a reduction from the same-commitment case. In the process, it has to fork on the hash function H . For this purpose, if we were to use the Generalized Forking Lemma as in the proof of Theorem 1, we would have no way to guess which hash query should be defined after other hash queries involving related inputs. Therefore we need the Local Forking Lemma to force all but one of the cross-commitment aggregation coefficients {t j } j∈[d] to be identical in two adversarial runs.

Theorem 2. The above cross-commitment scheme is binding in the random oracle model assuming the hardness of the n-DHE problem.

Proof. For the sake of contradiction, let us assume that an adversary A has non-negligible probability of contradicting the binding property of the crosscommitment aggregation in PointProofs. Namely, with probability , A can generate two tuples

π 0 , {C (j) 0 , S (j) 0 , m (j) 0 [S (j) 0 ]} j∈[d0] , π 1 , {C (j)
1 , S

1 , m

(j) 1 [S (j) 1 ]} j∈[d1] ,
such that VerifyAcross accepts (π b , {C

b , S

b , m

(j) b [S (j) b ]} j∈[d b ]
) for each value of b ∈ {0, 1}, and there exist indices j 0 ∈ [d 0 ] and j

1 ∈ [d 1 ] for which C (j0) 0 = C (j1) 1 and m (j0) 0 [i] = m (j1) 1 [i], for some i ∈ S (j0) 0 ∩ S (j1) 1
. In the random oracle model, we give a reduction B that uses A to break the binding property of the samecommitment aggregation of PointProofs.

B receives public parameters pp = g, ĝ, {g i } i∈[2n]\{n+1} , {ĝ i } i∈[n] from its own challenger in the same-commitment aggregation game and runs A on pp. Note that B, which is attacking the binding property of the same-commitment aggregation of PointProofs, has oracle access to H, but A has also oracle access to H . Algorithm B responds to A's oracle queries to H by redirecting the query to H (so, it does not simulate H itself for A). It responds to A's queries to the second random oracle H in the following way. In a first execution, it answers H -queries with values h 1 , h 2 , . . . , h Q ∈ Z p , where Q denotes the total number of queries made by A to H . We assume w.l.o.g. that all these queries are distinct. With probability , A outputs

π 0 , {C (j) 0 , S (j) 0 , m (j) 0 [S (j) 0 ]} j∈[d0] , π 1 , {C (j)
1 , S

1 , m

(j) 1 [S (j) 1 ]} j∈[d1] ,
such that the aggregated verification algorithm returns 1 running on both tuples. Namely,

d0 j=1 e   C (j) 0 , i∈S (j) 0 ĝt (0) j,i n+1-i    t (0) j = e(π 0 , ĝ) • e (g 1 , ĝn ) j∈[d 0 ],i∈S (j) 0 m (j) 0 [i]•t (0) j,i •t (0) j ( 12
) d1 j=1 e   C (j) 1 , i∈S (j) 1 ĝt (1) j,i n+1-i    t (1) j = e(π 1 , ĝ) • e (g 1 , ĝn ) j∈[d 1 ],i∈S (j) 1 m (j) 1 [i]•t (1) j,i •t (1) j (13)
where t (b)

j,i = H(i, C (j)
b , S

b , m Local Forking Lemma (Lemma 2) ensures that with probability at least equal to 1/Q • 2 , A's second run outputs (C, S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 ). Note that (S 1 , m 1 [S 1 ]) may differ from their counterparts (S 1 , m 1 [S 1 ]) of the first execution but this run involves the same (S 0 , m 0 [S 0 ]) as in the first execution and the hash query H(i , C, S 0 , m 0 [S 0 ]) is also the 0 -th hash query in this execution, where A receives a different response h 0 . Since i ∈ S 0 , we know that t

i n+1-i ) = e(π 0 /π 0 , ĝ) • e(g 1 , ĝn )

m0[i ]•∆t (0) i , (20)
where ∆t (0) i h 0 -h 0 = 0 except with probability 1/p.

Then, B locally forks A a second time on the hash query H(i , C, S 1 , m 1 [S 1 ]), which was the 1 -th hash query in the first execution. Namely, it runs A a second time with the same random tape as in the first run and now answers all random oracle queries using the outputs h 1 , . . . , h 1-1 , h 1 , h 1+1 , . . . , h Q ∈ Z p , where h 1 R ← Z p is freshly sampled and all other outputs h for = 1 are the same as in the first execution. Here again, regarding the Local Forking Lemma, with probability at least equal to 1/Q • 2 , A's third run outputs (C, S 0 , S 1 , m 0 [S 0 ], m 1 [S 1 ], π 0 , π 1 ). Note that (S 0 , m 0 [S 0 ]) may differ from the pair (S 0 , m 0 [S 0 ]) of the first execution but this run involves the same (S 1 , m 1 [S 1 ]) as in the first execution of A and the hash query H(i , C, S 1 , m 1 [S 1 ]) is also the 1 -th query in the this run, where A receives a different response h 1 . Since i ∈ S 1 , we can repeat the same arguments as in the first fork and, by dividing out the verification equations [START_REF] Lai | Subvector Commitments with Application to Succinct Arguments[END_REF] of the first and third runs, B obtains e(C, ĝ∆t

i n+1-i ) = e(π 1 /π 1 , ĝ) • e(g 1 , ĝn )

m1[i ]•∆t (1) i , (21)
where ∆t

(1) i h 1 -h 1 = 0 except with probability 1/p. Then, raising both sides of (21) to the power ω ∆t

If we now use the hypothesis that m i = m i , the combination of ( 22) and ( 8) implies e(π 0 /π 0 , ĝ) • e(g 1 , ĝn ) m0[i ]•∆t (0) i = e((π 1 /π 1 ) ω , ĝ) • e(g 1 , ĝn ) m1[i ]•∆t (0) i , which allows B to compute and output

g n+1 (π 1 /π 1 ) ω π 0 /π 0 1 ∆t (0) i • (m0[i ]-m1[i ]) . (23)
Thus, with probability at least equal to (1/Q) • 2 2 , the reduction B succeeds in solving the n-DHE problem.

A.2 Local vs Generalized Forking Lemma

We provided two proofs for the binding property of same-commitment aggregation of the vector commitment scheme proposed in [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] as PointProofs. In one technique, we used the Generalized Forking Lemma (Lemma 1) to prove the binding property (Theorem 1), and in the other technique, we used the Local Forking Lemma (Lemma 2) to prove the same (Theorem 3). Here, we compare the two techniques in terms of the advantage/run-time ratio of the reduction in each case.

Let , t be respectively the winning probability and run-time of A which is the adversary of PointProofs' binding property. Furthermore, let q be the number of oracle queries that A issues to H. We denote by m the number of forkings (i.e. the number of times an n-DHE adversary re-runs A) which is equal to 2 in both of our proofs. The advantage/run-time ratio in each case is as follows:

• Using Local Forking Lemma Adv t = (1/q • 2 ) m t = 4 t • q 2
• Using Generalized Forking Lemma Since q, the number of oracle queries, can be potentially very large, using Generalized Forking Lemma seems to give a tighter reduction in the case of PointProofs.

i

  = H(i, C, S b , m b ), for both b = 0 and b = 1. Random oracle queries made by A are of the form (i, C, S, m[S]), and both (i * , C, S 0 , m 0 [S 0 ]) and (i * , C, S 1 , m 1 [S 1 ]) must have been queried for Equation

Fig. 1 .

 1 Fig.1. Game Gπ,A where an algorithm is forked in the Generalized Forking Lemma.

  Commit pp (m; aux) → C : On input a message vector m = (m 1 , . . . , m n ) of length n, uses some auxiliary information (i.e. randomness) aux to output a commitment C. UpdateCommit pp (C, S, m[S], m [S], aux) → C : Takes as input a commitment C, a subset S ⊆ [n], and m[S] = (m i ) i∈S as the underlying message vector of C, and uses some auxiliary information aux to change m[S] to m [S] = (m i ) i∈S and outputs a new commitment C for this new vector of messages.

  Aggregate pp (C, S, m[S], {π i } i∈S ) → π S : Takes as input a commitment C, a subset S ⊆ [n], a subset of message bits m[S] = (m i ) i∈S , and a set of proofs {π i } i∈S where each π i for i ∈ S is the proof generated for m i using the algorithm Prove. It outputs an aggregated proof π S . Verify pp (C, S, m[S], π S ) → b : On input a commitment C, a subset S ⊆ [n], a sub-vector of messages m[S], and an aggregated proof π S , and outputs a bit b ∈ {0, 1}.

  Updates. For all parameters λ, n, message vectors m = (m 1 , . . . , m n ), m = (m 1 , . . . , m n ) ∈ M n , subset S ⊆ [n], and aux such that m i = m i for all i ∈ [n] \ S, we have UpdateCommit pp (C, S, m[S], m [S], aux) = Commit pp (m ; aux), where C ← Commit pp (m; aux), and pp ← Setup(1 λ , 1 n ).

  and obtains C and (S b , m b [S b ], π b ) for b ∈ {0, 1} satisfying equations (

  other hash values of the form H(i, C, S 0 , m 0 [S 0 ]) for i = i are the same as in the initial execution because B assigned the values of H(i, C, S 0 , m 0 [S 0 ]) for i = i before the forking point. Let us now consider the proofs π 0 , π 0 obtained in the first run of B and the first forking, respectively. By dividing out the equations (5) of both runs, we have e(C, ĝ∆t

  , for each j ∈ [d b ], i ∈ S

  j∈[d b ] ), for each j ∈ [d b ] and b ∈ {0, 1}. same-commitment aggregation construction from Section 3, which contradicts the statement of Theorem 1.

=

  H(i , C, S 0 , m 0 [S 0 ]) = h 0 = h 0 with overwhelming probability 1-1/p, but other hash values t (0) i for i ∈ S 0 \{i } are the same as in the initial execution because of the local forking. If we now consider the two proofs π 0 , π 0 obtained in the two runs, by dividing out the equations (18) of both runs, we have e(C, ĝ∆t

  ) = e((π 1 /π 1 ) ω , ĝ) • e(g 1 , ĝn ) m1[i ]•∆t (0) i .

8 • 2 t≥ 2 t 2 870

 8222 m 2 • q • 1/ • ln(8m/ ) = • 256 • q • ln(16/ ) , Since we can consider ≥ 1/2, we have ln(16/ ) = ln(16) -ln( ) ≤ ln(16)ln(1/2) ≈ 3.4. So, for the Generalized Forking Lemma case, we have Adv t • 256 • q • 3.4 ≥ • t • q

Typically, the target condition is sparse and the range of H is exponentially large, therefore A must query H(x) to succeed with non-negligible probability.

The trapdoor is only used to prove the hiding property.

Acknowledgements. The second and third authors were supported by the French ANR RAGE project (ANR-20-CE48-0011) and the PEPR Cyber France 2030 programme (ANR-22-PECY-0003).

Then, B determines the two indices j 0 ∈ [d 0 ], j 1 ∈ [d 1 ], for which the binding property is contradicted, i.e., C The reduction B then locally forks the adversary twice. It first runs A a second time with the same random tape and answers all random oracle queries using the outputs h 1 , . . . , h 0-1 , h 0 , h 0+1 , . . . , h Q ∈ Z p , where h 0 R ← Z p is chosen afresh and all other outputs h for = 0 are identical to those of the first execution. The Local Forking Lemma (Lemma 2) ensures that with probability at least equal to 1/Q • 2 , A's second run outputs

Note that the second collection {C 1

1 ]} j∈[d1] of the first run, but what matters is that this run involves the same collection {C

as the first execution of A and the hash query H (j 0 , {C

) is also the 0 -th query issued by A where it receives a different response h 0 . Since j 0 ∈ d 0 , we know that

but other hash values t (0) j for j ∈ [d 0 ] \ {j 0 } are the same as in the initial execution because of the local forking. If we now consider the two proofs π 0 , π 0 obtained in the two runs, by dividing out the equations ( 12) of both runs, we have

where ∆t

Raising both sides of equation ( 14) to the power ω 0 1/(∆t

Then, B locally forks A a second time on the hash query

), which was the 1 -th H -query in the first execution. Namely, it runs A a second time with the same random tape as in the first run and now answers A's random oracle queries to H using the outputs

← Z p is freshly sampled and all other outputs h for = 1 are the same as in the first execution. By the Local Forking Lemma, with probability at least equal to 1/Q • 2 , A's third run outputs

1 , S

1 , m

Again, the collection {C 0 (j) , S 0 (j) , m 0 (j) [S 0 (j) ]} j∈[d 0 ] might differ from its counterpart {C 0 (j) , S 0 (j) , m 0 (j) [S 0 (j) ]} j∈[d0] of the first execution of A, yet, this run involves the same collection {C

1 , m

as in the first run and the hash query H (j 1 , {C

) is also the 1 -th query to H where A receives a different response h 1 . Since j 1 ∈ d 1 , we can repeat the same arguments as in the first fork and, by dividing out the verification equations ( 13),

where ∆t [START_REF] Bagherzandi | Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma[END_REF] j1 = h 1 -h 1 = 0. Again, by raising both members of equation ( 14) to the power ω 1 1/(∆t

Finally, B outputs the tuple

. Regarding equations ( 15) and ( 17), Verify accepts both

and there exists an index i ∈ S for which m (j0)

thus breaks the binding property of the

Supplementary Material

A Proof via Local Forking Lemma

In this section, in order to compare with the reduction obtained from the Generalized Forking Lemma, we prove the binding property of same-commitment aggregation of PointProofs [START_REF] Gorbunov | PointProofs: Aggregating Proofs for Multiple Vector Commitments In ACM-CCS[END_REF] in the random oracle model via Local Forking Lemma [START_REF] Bellare | The Local Forking Lemma and its Application to Deterministic Encryption[END_REF].

A.1 The Case of Same-Commitment Aggregation Theorem 3. The vector commitment scheme described in Description 3 is binding in the random oracle model if the n-DHE assumption holds.

Proof. Suppose there exists an adversary A, that with a non-negligible probability generates a commitment C as well as two sets S 0 , S 1 ⊂ [n], such that S 0 ∩S 1 = ∅, together with convincing proofs π 0 , π 1 for sub-vectors m

We build an algorithm B in the random oracle model that uses A to solve the n-DHE problem.

B first runs A on input of an n-DHE instance g, ĝ, {g i } i∈[2n]\{n+1} , {ĝ i } i∈[n] set as the public parameters pp of the vector commitment scheme. In a first execution, it answers random oracle queries with values h 1 , . . . , h Q ∈ Z p , where Q denotes the total number of H-queries made by A. We assume w.l.o.g. that all random oracle queries are distinct. With probability , A outputs a tuple The reduction then locally forks the adversary twice. It first runs A a second time with the same random tape and answers all random oracle queries using the outputs h 1 , . . . , h 0-1 , h 0 , h 0+1 , . . . , h Q ∈ Z p , where h 0 R ← Z p is chosen afresh and all other outputs h for = 0 are identical to those of the first execution. The