On the Impossibility of Algebraic Vector

Commitments in Pairing-Free Groups

;4 Dario Catalano¹, Dario Fiore², Rosario Gennaro³, Emanuele Giunta²

¹ University of Catania, Italy. catalano@dmi.unict.it

² IMDEA Software Institute, Madrid, Spain.

{dario.fiore, emanuele.giunta}@imdea.org

³ Protocol Labs.

rosario@protocol.ai

⁴ Universidad Politecnica de Madrid, Spain.

Abstract. Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, al- gebraic constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes. In spite of their popularity, algebraic vector commitments remain poorly understood objects. In particular, no construction in standard prime order groups (without pairing) is known.

In this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize.

Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases. This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.

Table of Contents

1 Introduction 3

1.1 Our Results ..... 4 1.2 Our Techniques ..... 5 1.3 Interpretation of our impossibility and further implications ..... 7 1.4 Related Work ..... 7 1.5 Organization of the paper ..... 8

2 Preliminaries 8

2.1 Vector Commitments ..... 9 2.2 Digital Signatures ..... 10

3 Algebraic Vector Commitments 10

3.1 Generic Transformation from VCs to Signatures ..... 11 3.2 $\vartheta$-Unforgeability ..... 12

4 Algebraic Signatures 14

4.1 Relations among CRS elements ..... 15 4.2 Attack to Schemes with Strictly Linear Verification ..... 15 4.3 Attack to Schemes with Generic Verification ..... 16

5 Conclusions 18

5.1 Impossibility of Algebraic Vector Commitments ..... 18 5.2 Impossibility of Algebraic Signatures ..... 20

A More Preliminaries 24

A.1 Linear Algebra ..... 24 A.2 Min-Entropy ..... 25 A.3 Arithmetic circuits and R1CS ..... 25 A.4 Generic Group Model ..... 26

B Examples and Constructions 27

B.1 Linear vs Generic Verification for Signatures ..... 27 B.2 Secure Signatures with Linear Verification ..... 29 B.3 Succinct Vector Commitments with Linear Verification ..... 31 B.4 Tightness of Algebraic VC Lower Bounds ..... 33 B.5 Tightness of Algebraic Signatures Lower Bounds ..... 35

C Postponed Proofs 36

C.1 Generic Transformation to Signatures ..... 36 C.2 Attack to Schemes with Strictly Linear Verification ..... 37 C.3 Attack to Schemes with Generic Verification ..... 39

1 Introduction

Vector commitments [LY10, CF13] (VC) are a class of commitment schemes that allow a sender to commit to a vector v of n messages, in such a way that she can later open the commitment at selected positions. Namely, the sender can convince anyone that the i-th message in the committed vector is v_i. A secure scheme shall satisfy position binding, i.e. generating valid openings to different values v_i6= v_i0for the same position i is computationally infeasible.

$$ v_{i} $$

$$ v_{i}\neq v_{i}^{\prime} $$

The distinguishing feature of vector commitments is that commitments and openings must be succinct. In the original notion of [LY10, CF13], this means that their size is independent of n, the length of the vector, but a relaxed notion allowing a logarithmic dependence in n may be considered, as in the case of the celebrated Merkle tree construction [Mer88].

Mainly thanks to their succinctness property, vector commitments have been shown to be a useful building block in several applications, such as zero-knowledge sets [MRK03, LY10, CF13], verifiable databases [BGV11, CF13], succinct arguments [Kil94, Mic94, BBF19, LM19], proofs of retrievability [JK07, Fis18], and stateless blockchains [CPZ18, BBF19].

Analyzing the state of the art of VC schemes, we see that VC constructions are based on two main approaches.

On one side, we have tree-based VCs, notably Merkle trees [Mer88] and their generalizations [Kus18]. These constructions have the advantage of being realizable from collision resistant hash functions, and thus can be based on the hardness of virtually any cryptographic problem including factoring, discrete logarithm, SIS and many more. In fact, we notice that VCs with logarithmic-size openings are equivalent to collision-resistant hash functions. The main drawback of tree-based schemes is that their openings are of size O(logn). Additionally, the tree-based approach seems to inherently impede the realization of properties + such as subvector openings [BBF19, LM19] and aggregation [CFG 20], that turn useful in both theoretical and practical applications of VCs.

On the other side, we have algebraic vector commitments, notably based on bilinear pairings [LY10, KZG10, CF13], groups of unknown order [CF13], and lattices [PSTY13, PPS21]. Roughly speaking, an algebraic VC is one in which the commitment and verification algorithm only use algebraic operations over the group that underlies the construction (this rules out hashing group elements for example). The main advantage of these constructions is that they admit open- 5 ings of constant size, that are virtually optimal – a single group element in most constructions. Moreover, algebraic schemes naturally achieve useful properties such as (additive) homomorphism, stateless updatability [CF13], subvector open- + ings [BBF19, LM19] and aggregation [CFG 20]. Yet, the powerful versatility of existing VCs with constant-size openings contrasts with the limited theoretical understanding of their foundations.

$$ [\mathrm{C F G}^{+}20] $$

⁵ We include lattice-based schemes in the ‘algebraic’ category although they do not perfectly fit our notion of using a group in a black box way; also, existing schemes still need (poly) logarithmic-size openings.

We see two main open questions related to algebraic VCs. The first one concerns the minimal general assumption that implies them. While tree-based schemes with logarithmic openings are well understood, being de facto equivalent to collision-resistant hash functions, we have no generic recipe to build algebraic 6 VCs with constant-size openings. The second question is whether algebraic VCs can be built from “standard” prime-order groups without pairings. In this setting, known constructions rely either on the tree-based approach (e.g., building a Merkle tree on top of Pedersen hash function), or on inner-product arguments

• • in the random oracle model [BCC 16, BBB 18]. Both these approaches entail logarithmic-size openings and a non-algebraic verification.

We believe that settling these two questions would improve our understanding of vector commitments. In this work, we focus on the second question for two important reasons: (i) on the theoretical front, studying algebraic VCs in this minimal setting helps us understand conceptually what are the “ingredients” needed to build them; (ii) on the practical side, pairing-free groups of known order are the simplest and most efficient cryptographic setting, and yet we know of no construction of algebraic VCs there.

Our results are negative: we show that a broad class of VC schemes in this setting cannot both be succinct and satisfy position binding.

1.1 Our Results

We informally call a vector commitment built on top of a group G of prime order q “algebraic” if all its procedures use G in a black box way, i.e. without relying on the representation of group elements. We show the following two main results.

$$ \mathbb{G} $$

Impossibility of algebraic VCs with linear verification. We start by looking at the class of algebraic VC schemes in which the verification algorithm is a set of linear equations over G. Specifically, for a message m and position i the verification consists of checking that

$$ A(\mathbf{z},m,i)!\cdot!\mathbf{X},\stackrel{?}{=},B(\mathbf{z},m,i)!\cdot!\mathbf{Y} $$

(1)

where X = (X₁*;X₂) are the group elements appearing respectively in the public parameters and the commitment, openings are of the form (Y;*z) with Y being a vector of group elements and z of field elements, and A;B are functions defining matrices with coefficients in F_q.

$$ \mathbf{X}=(\mathbf{X}{1},\mathbf{X}{2}) $$

$$ \mathbb{F}_{\boldsymbol{q}} $$

We believe this to be the simplest and most natural form of verification using only group operations. However we show that whenever A depends affinely on z*;m* and B is independent from them (we say such a scheme has strictly linear verification), then it is impossible to achieve both position binding and succinctness. More specifically we prove that if a scheme has position binding, commitments of bit-length ‘_cand opening proofs of bit-length ‘, then asymptotically

$$ \ell_{c} $$

$$ \ell_{\pi} $$

⁶ The only generic construction with constant size opening is the folklore one that combines a hash function and a constant-size SNARK; yet this is non-algebraic due to the need of encoding the hash computation in the SNARK’s constraint system.

their product is lower bounded by the length of the vector we are committing p p to, i.e. ‘_c‘ = (n). Thus either ‘_c= ( n) or ‘ = ( n). Interestingly, this family of schemes captures generalizations of Pedersen commitments [BG12] which, as we show in the Appendix B.4, achieve this lower bound.

$$ \ell_{c}\cdot\ell_{\pi}=\varOmega(n) $$

$$ \ell_{c}=\ \ \Omega({\sqrt{n}}) $$

$$ \ell_{\pi}=\mathit\Omega({\sqrt{n}}) $$

Next, we investigate how crucial are our requirements on the dependence of A( ) and B( ) on z*;m*. We show they are necessary. Indeed, if we allow either A to depend quadratically, or B affinely, on z*;m* then there exist succinct VC constructions whose verification can be written in the above form over a group G. We provide examples in the Appendix B.3. The schemes we find however rely on arithmetization techniques to encode arbitrary circuits as constraint systems of degree 2 over a finite field [GGPR13]. This for instance means that, for proper choice of A and B, it is possible to express, using an algebraic verification equation as (1), computations like the validity tests for a Merkle tree path, or any arbitrary VC verification algorithm.

$$ A(\cdot) $$

Despite being secure and succinct, VC schemes built this way do not satisfactorily answer our question in a positive way, as they appear to bypass the underlying group as their source of hardness. Indeed, either their security comes from problems unrelated to G, or if they depend on G, they must do it in a non-black-box way⁷.

Impossibility of algebraic VCs with generic group verification. Motivated by these findings, we investigate whether VCs can be built given only black-box access to a cryptographic group. To study this case, we just assume the VC (which we call algebraic with generic verification) to use the underlying group generically, without any further constraint on its verification procedure.

Eventually we provide a black-box separation in Maurer’s Generic Group Model [Mau05]. This informally implies that any VC using G generically and whose position binding reduces to a hard problem in G (such as DLP or CDH) cannot be succinct, as it must hold ‘_c‘ = (n).

$$ \ell_{c}\cdot\ell_{\pi}=\varOmega(n) $$

1.2 Our Techniques

Our strategy to prove our impossibility results on algebraic vector commitments consists of two main steps. (A) We show that from a VC it is possible to construct a class of signature schemes. In particular, if the VC is algebraic with linear (resp. generic) verification, the resulting signature scheme’s verification has analogous algebraic properties. (B) We prove the insecurity of this class of signature schemes in pairing-free groups of known order. To achieve the latter + result we build on, and extend, the recent techniques of [DHH 21], that provide negative results for a somewhat smaller family of algebraic signatures.

In what follows we give an overview on each step.

⁷ For example, one may consider a Merkle-tree of Pedersen commitments which must use the group representation to go from one level to another.

From VCs to Signatures. Given a VC scheme for vectors of length n our transformation produces a signature scheme with polynomially bounded message space f1*;:::;ng*. In a nutshell, the public key is a commitment c to a vector of n random values (s₁;:::;s_n). The signature on the message i 2 [n] is the pair (s_i;_i) where_iis the VC opening proof that c opens to s_iat position i. Verification simply runs the VC verification algorithm to check that the opening is valid.

$$ {1,\ldots,n} $$

$$ \left(s _ {1}, \dots , s _ {n}\right) $$

$$ s_{i} $$

$$ i\in[n] $$

$$ \pi_{i} $$

$$ (s_{i},\pi_{i}) $$

Conveniently, this transformation maps algebraic VCs with linear/generic verification to signature schemes with the analogous property, which we then call algebraic signatures with linear/generic verification. This happens since the verification algorithm is essentially the same in both primitives.

The resulting signature however may not be proved existentially unforgeable if it comes from a VC satisfying only position binding. Indeed the latter property does not imply that every opening proof is hard to compute. However, assuming that the scheme is also succinct, an adversary who produces ‘many’ correct openings should have to correctly guess the value of several messages s_iused to generate the commitment. This can be shown to be information-theoretically hard if the commitment and opening proofs provided have significantly smaller bit-length than the min-entropy of those messages.

$$ s_{i} $$

For this reason we introduce a relaxed security notion, called #-unforgeability, where an adversary must provide not only one but at least more than #-many⁸ forgeries for non-queried messages. Setting # as a proper function of the number of queries made by the adversary, we prove that signatures from VCs are #- unforgeable.

$$ \scriptstyle\ \ {vartheta mathrm m m a y}^{8} $$

$$ \vartheta $$

Impossibility of Algebraic Signatures, revisited. To conclude our impossibility result for VCs, we finally provide an impossibility result and a black-box separation for algebraic signatures with strictly linear and generic verification respectively. In particular, we show in both cases that the message space in a #-unforgeable construction is upper-bounded by n + # with n being the number of group elements in the verification key. We also show this to be tight by providing a construction that achieves this bound in Appendix B.5.

$$ \vartheta. $$

$$ n+\vartheta $$

• Notice that similar results were already proved in [DHH 21]. In their work signatures are assumed to be of the form (Y*;t*) with Y a vector of group elements and t 2f0*;* 1g. Moreover the verification procedure is assumed to consist of a linear check as in Equation 1. For this class of signatures, which can be shown equivalent to our notion of algebraic with linear verification, they provide an attack running in time O(2 poly()).

$$ [\mathrm{H D H^{+}21}] $$

$$ (\mathbf{Y},t) $$

$$ t\in{0,1}^{\kappa} $$

$$ O(2^{\kappa}\cdot{\mathsf{p o l y}}(\lambda)) $$

Thus their adversary is efficient only when t = O(log), whereas our impossibility result applies to schemes with strictly linear verification, where signatures may contain several field elements. Likewise, their black-box separation only captures schemes with linear verification, while we extend it to signatures where all procedures are simply required to be generic. To show that this class of schemes is indeed more general we provide examples in Appendix B.1.

$$ t=O(\log\lambda) $$

⁸ Where # may depend on the public parameters as well as the number of queries.

$$ \vartheta $$

• We finally stress that, as in [DHH 21], our results hold in Maurer’s Generic Group Model [Mau05]. For a comparison with other models of generic computation, such as Shoup’s Generic Group Model [Sho97], we refer to the discussion in [Zha22].

$$ [\mathrm{D H D^{+}2]} $$

1.3 Interpretation of our impossibility and further implications

As mentioned earlier, both our impossibility results specify precise bounds and conditions under which VCs cannot be built generically in pairing-free groups. The bottom line is that, whenever a position-binding VC scheme uses the group in a black box way (and relies on it for security), then it cannot be succinct, which we recall is the distinguishing feature of this primitive.

Another interesting aspect of our impossibility results is that they imply analogous impossibilities for any primitive that allows one to construct algebraic VCs (with either strictly linear or generic-group verification) in pairing-free groups. Notably, our impossibility applies to polynomial commitments [KZG10], and functional commitments [LRY16] supporting any class of functions that includes projections, i.e., C_i(v) = v_i(already captured by linear forms). Indeed, each of these primitives allows one to build a VC with exactly the same succinctness 9 and type of verification. Therefore we obtain that any secure functional commitment or polynomial commitment using a pairing-free group in a black-box way cannot be succinct (or, more precisely, they must satisfy ‘_c‘ = (n)).

$$ C_{i}(\mathbf{v})=v_{i} $$

$$ \ell_ {c} \cdot \ell_ {\pi} = \Omega (n)) $$

Our impossibility for algebraic signatures instead can be shown to imply analogous results for verifiable random functions [MRV99] and identity-based encryption [Sha84, BF01], the latter through the Naor-trick reduction, as ob- + served in [DHH 21]. In this way our black-box separation for signatures yield a simpler argument for the tight result in [SGS21].

An interesting question left open by our work is understanding if our results can imply the impossibility of further cryptographic primitives via a connection to the classes of algebraic signatures and vector commitments that we rule out. Another open question concerns the minimal assumptions required to describe a VC with constant-size commitment and openings. We notice that our impossibility for VCs with generic verification holds in Maurer’s generic group model [Mau05]. When using Shoup’s GGM [Sho97], our results may not hold as one could use the group oracle as a random oracle [ZZ21], e.g., to build a Merkle + tree of Pedersen hashes (see a similar discussion for signatures in [DHH 21]). However, to the best of our knowledge all these techniques would in the best case lead to schemes with logarithmic-size openings.

1.4 Related Work

The study of impossibility results about the construction of cryptographic primitives in restricted models is an important area of research that provides insights on the foundations of a cryptographic problem. Starting with the seminal paper

⁹ These constructions are trivial/folklore and we do not elaborate further on them.

of Impagliazzo and Rudich [IR89], a line of works study the (in)feasibility of constructing cryptographic primitives in a black-box way from general assumptions, such as one-way functions or trapdoor permutations (e.g. [Sim98, KST99, + GT00, GKM 00, GMR01, GGK03]).

Another line of works (more closely related to ours), initiated by Papakonstantinou, Rackoff and Vahlis [PRV12], considers the problem of proving impossibility of cryptographic primitives that make black-box use of a cryptographic group without pairings. Specifically, [PRV12] prove that identity-based encryption (IBE) algorithms built in this model of computation cannot be secure. Following [PRV12], more recent works study the impossibility, in generic group models for pairing-free groups of known order, of other cryptographic primitives, such as verifiable delay functions [RSS20], identity-based encryption (with a re- + sult tighter than [PRV12]) [SGS21] and signature schemes [DHH 21]. In addition to proving impossibility for algebraic signatures with generic-group algorithms, ⁺ [DHH 21] also prove the generic impossibility of a class of algebraic signatures whose verification is a system of linear equations over a group.

Finally, we mention the work of Abe, Haralambiev and Ohkubo [AHO12] that also considers a question related to constructing vector commitments. Following a research line on structure-preserving cryptography, Abe et al. [AHO12] investigate if it is possible to construct commitment schemes in bilinear groups in which messages, keys, commitments, and decommitments are elements of bilinear groups, and whose openings are verified by pairing product equations. For this class of schemes, they prove that the commitment cannot be shrinking. Implicitly this result also implies the impossibility of constructing succinct vector commitments in this structure-preserving setting in bilinear groups.

1.5 Organization of the paper

In Section 3 we define algebraic VCs and show our transformation to #-unforgeable signatures. Section 4 presents the definition of algebraic signatures and our impossibility results for strictly linear verification and generic group verification. Finally, in Section 5 we illustrate how to relate the parameters of our VC-tosignatures transformation with those needed by the impossibility of algebraic signatures. In Appendix B we present several constructions showing: the tightness of our impossibility, secure signatures and succinct vector commitment with linear, but not strictly linear, verification.

2 Preliminaries

Notation. We denote the security parameter by and negligible functions with negl(). We call significant a function of that is non-negligible. We say that an algorithm is PPT if it runs in probabilistic polynomial time. For a positive integer n, [n] denotes the set f1*;:::;ng*. We use (G*;*+) to denote a group of known prime order q with canonical generator G, and F_qfor the field of order

$$ \lambda $$

$$ {1,\ldots,n} $$

$$ (\mathbb{G},+) $$

$$ \mathbb{F}_{q} $$ n q. The identity (or zero) element is denoted as 0 2 G. Given a vector x 2 F_q, we deⁿote a ‘multi-exponentiation’ in G as x G = (x₁G;:::;x_nG).

$$ 0\in\mathbb{G} $$

$$ \mathbf{x}\in\mathbb{F}_{q}^{n} $$

$$ \mathtt{x}\cdot G=(x_{1}G,\dots,x_{n}G) $$

^n;m F_qis the space of matrices A with m columns and n rows and entries in F_q. rkA denotes the rank of A, i.e. the maximum number of linearly independent

n rows. A is the transposed of A. All x 2 F_qare assumed to be column vectors,

whereas row vectors are denoted as x.

$$ \mathbb{F}_{q}^{n,m} $$

$$ \mathbb{F}_{q} $$

$$ A^{\top} $$

$$ \mathbf{x}\in\mathbb{F}_{q}^{n} $$

$$ \mathbf{x}^{\top} $$

In what follows ‘GGM’ stands for Maurer’s Generic Group Model [Mau05] for a group of known prime order q. This model can be defined through two 0 stateful oracles O_addand O_eqsuch that: group element are labeled with progressively increasing indices, the first being associated to the canonical generator G, 0 O_add(X;Y) associate the next index to the element X + Y and O_eq(X) returns 1 if X equals the identity element, 0 otherwise. See Appendix A.4 for more details.

$$ \ {cal O O}_{\sf a d d} $$

$$ \mathcal {O} _ {\mathrm {e q}} ^ {0} $$

$$ G, $$

$$ \mathcal{O}_{\mathsf{a d d}}(X,Y) $$

$$ X+Y $$

$$ \mathcal{O}_{\mathsf{e q}}^{0}(X) $$

2.1 Vector Commitments

We recall the definition of vector commitments from [CF13].

Definition 1(VC). A Vector Commitment scheme is a tuple of algorithms (VC*:* Setup*;VC:* Com*;VC:* Open*;VC:* Vfy) and a message space VC*:* M such that

$ – VC*:* Setup(1)! pp generates the public parameters.

$$ \mathsf{V C.S e t u p(1^{\lambda})\stackrel{\S}{\sim}} $$

$$ .\mathord{\bigcirc(}\mathsf{C o}(\mathsf{p p},m_{1},\ldots,m_{n}\ \ ^{\sharp}\to\mathcal{C} $$

$ – VC*:* Com(pp*;m₁;:::;m*_n)! c; aux produce a commitment to m₁;:::;m_n2 VC*:* M together with some auxiliary information.

$$ m_{1},\ldots,m_{n}\in $$

$ – VC*:* Open(pp*;m;i;* aux)! return an opening proof that the i-th entry of a given commitment is m_i.

$$ \mathsf{O p e n}(\mathsf{p p},m,i,\mathsf{a u x})\stackrel{\S}{\to}\pi $$

$$ m_{i} $$

– VC*:* Vfy(pp*;c;m;i;)!* 0*=*1 verifies the opening proof’s correctness.

We require a vector commitment scheme to satisfy perfect correctness, that is, $ $ given public parameters pp VC*:* Setup(1), commitment c; aux VC*:* Com(pp*;m₁;* $ :::;m_n) for any m_i2 VC*:* M, and opening VC*:* Open(pp*;m*_i;i; aux), it holds

$$ \mathsf{p p}\leftarrow^{\S}\mathsf{V C}.\mathsf{S e t u p}(1^{\lambda}) $$

$$ c_{\gamma} $$

$$ \leftarrow^{\S}\mathsf{V C.C o m((p p,}{{}}m m{{}} $$

$$ \cdots,m_{n}) $$

$$ m_{i}\in\mathsf{V C}M $$

$$ \pi\leftarrow^{\ \ circ}V(\ .p p e m_{i},i,!!!\sf a{x}) $$

Moreover, to avoid trivial cases, in this paper we assume jVC*:* Mj 2.

$$ |\mathsf{V C}.\mathsf{M}|\geq2. $$

The main security property for a vector commitments is the so called position binding, which informally states that no adversary can open the same position of a given commitment to two different values. Formally

Definition 2(Position binding). A vector commitment scheme satisfies po- sition binding if for any PPT adversary A there exists a negligible function "() such that 2 3

$$ \varepsilon(\lambda) $$

$$ \operatorname*{P r}\left[\begin{matrix}{\mathsf{V C N j y}(\mathsf{p p},c,m,i,\pi)\to1}&{\mathsf{p p}\leftarrow^{8}\mathsf{V C}S e t u p(1^{\lambda})}\ {\mathsf{V C}.mathsf{N f y}(\mathsf{p p},c,m^{\prime},i,\pi^{\prime})\to1}&{\mathcal{A}(\mathsf{p p})\to(c,m,m^{\prime},i,\pi,\pi^{\prime})}\ \end{matrix}\right]\leq\varepsilon(\lambda). $$

The property that distinguishes VCs from classical binding commitments is succinctness Following [LY10, CF13], a VC scheme is said succinct if there is a fixed p() = poly() such that for any n the size of honestly generated commitments and openings is bounded by p(). One may also consider weaker notions where the size may be bounded by p() logn or p(;logn).

$$ p(\lambda),=,{\mathsf{p o l y}}(\lambda) $$

$$ p(\lambda) $$

$$ p(\lambda) $$

$$ p(\lambda,\log n) $$

Since in our work we are interested in understanding the feasibility of VCs based on their level of succinctness, we consider a parametric notion. We say that a VC has succinctness (‘_c;‘) if for any m₁;:::;m_n2 VC*:* M, commitment $ ^$ c; aux VC*:* Com(pp*;m₁;:::;m*_n) and opening VC*:* Open(pp*;m*_i;i; aux) for any i 2 [n], we have that c (resp.) has bit-length ‘_c(;n) (resp. ‘ (;n)).

$$ (\ell_{c},\ell_{\pi}) $$

$$ m_{1},\ldots,m_{n}\in\ \mathsf{V C.M} $$

$$ c_{\ } $$

$$ \pi\leftarrow^{\ \ circ} $$

$$ i\in[n] $$

$$ \ell_{c}(\lambda,n);(\mathrm{r e s p.};\ell_{\pi}(\lambda,n)) $$

2.2 Digital Signatures

Definition 3. A signature scheme is a tuple of PPT algorithms (S*:* Setup*,* S*:* Sign*,* S*:* Vfy) and a message space set S*:* M such that

$ – S*:* Setup(1)! (sk*;*vk) generates the secret and verification keys

$ – S*:* Sign(sk*;m*)! returns the signature of a message m 2 S*:* M

$$ -\ {\mathsf S.\ \sf S{S g n}}({\mathsf s!k\sf,{m}})\ {\stackrel{\S}{\to}} $$

$$ n\in\mathsf{S}.\mathbb{M} $$

– S*:* Vfy(vk*;m;)!* 0*=1 verifies the signature for a message m 2 S:* M

$$ -mathbb S!{\mathsf{V f y}}(\mathsf{v}{\mathsf{k}},m,\sigma)\to0/1} $$

$$ m\in\mathsf{S}.\mathbb{N} $$

We further require a signature scheme to satisfy perfect correctness, meaning $ $ that if (sk*;vk) S:* Setup(1) and S*:* Sign(sk*;m*) for any m 2 S*:* M then the verification algorithm accepts always, i.e.

$$ (\mathsf{s k},\mathsf{v k})\leftarrow^{\S}\mathsf{S..S e t u p}(1^{\lambda}) $$

$$ \sigma\leftarrow^{\S}\mathsf{S.S.g i n(s k,)} $$

$$ m\in{\mathsf{S}}.{\mathsf{M}} $$

$$ \operatorname*{P r}\left[\mathsf{S.V f y}(\mathsf{v k},m,\sigma)\to1\right]=1. $$

3 Algebraic Vector Commitments

In this paper we focus on vector commitments built on a pairing-free group of known order, using it in a black box way. We start by introducing a notion of algebraic vector commitments where the verification algorithm only consists of a system of linear equations.

Definition 4(Algebraic VCs with linear verification). A vector commit- ment scheme is said to be algebraic with linear verification if the message space is VC*:* M=F_qand

$$ \mathsf{V C.}M=\mathbb{F}_{q} $$

$ 1 – VC*:* Setup(1)! pp such that pp = (X₁*;s₁*) 2 G f0*;* ¹g .

$$

• \mathrm {V C}. \mathrm {S e t u p} \left(1 ^ {\lambda}\right) ^ {$} \rightarrow \mathrm {p p} $$

$$ {\mathfrak{p p}}=\left({mathbb X}{1},s{1}\right)\in{\mathbb{G}}^{\nu_{1}}\times\left{0,1\right}^{*} $$

$ 2 – VC*:* Com(pp*;m₁;:::;m*_n)! c; aux such that c = (X₂*;s₂*) 2 G f0*;* 1g .

$$ {mathsf C..o m}(\mathsf{p p},m_{1},\ldots,m_{n}),^{,\natural}!c\ \to\ epsilon c, $$

$$ c=\left(\mathbb{X}{2},\mathfrak{s}{2}\right)\in\mathbb{C}^{\nu_{2}}\times\left{0,\mathbb{l}\right}^{*} $$

k h – VC*:* Open(pp*;m;i;* aux)! such that = (Y*;z) with Y 2 G and z 2 F_q.*

$$ \mathbf{Y}\in\mathbb{G}^{k} $$

$$ \pi = (\mathbf {Y}, \mathbf {z}) $$

$$ C.p e n(\ \ p,,m,,,,\ !!!\sf{a u x})\to\pi $$

$$ \mathbf{z}\in\mathbb{F}_{q}^{h} $$

h+1 ‘;n h+1 ‘;k – There exist A : F_q[n]f0*;* 1g! F_qand B : F_q[n]f0*;* 1g! F_q matrices such that VC*:* Vfy(pp*;c;m;i;)!* 1 if and only if, calling X = X₁jjX₂ and s = s₁jjs₂

$$ B:\mathbb{F}{q}^{h+1}!\times![n]!\times!{0,1}^{*}!\rightarrow!\mathbb{F}{q}^{\ell,h} $$

$$ A: \mathbb {F} _ {q} ^ {h + 1} \times [ n ] \times {0, 1 } ^ {*} \rightarrow \mathbb {F} _ {q} ^ {\ell , n} $$

$$ V.C V y(\ \mathsf{p p},c,m,i,\dot{\pi})\to1\ i $$

$$ \mathbf{X}{1}||\mathbf{X}{2} $$

$$ {\bf X},= $$

$$ i i,f, $$

$$ s=s_{1}||s_{2} $$

$$ A (\mathbf {z}, m, i, s) \cdot \mathbf {X} = B (\mathbf {z}, m, i, s) \cdot \mathbf {Y}. $$

For the ease of presentation we will omit s in A and B when clear from the context. Notice that the definition imposes linearity only with respect to group elements while it allows procedures A;B to depend non-linearly on the field vector element z.

As we shall see, our first impossibility result states that whenever A is an affine function of z*;m* and B does not depends on z*;m*, then the resulting scheme cannot be both “succinct” and position binding. We call these schemes strictly linear since their verification equations depend linearly both in z and Y.

Definition 5(Algebraic VCs with strictly linear verification). A vector commitment is said to be algebraic with strictly linear verification if it satisfies Definition 4, A(z*;m;i*) is an affine function¹⁰ of z*;m and B*(i) does not depends on z*;m.*

However, if we allow A to depend quadratically, or B linearly, on z*;m* then we could use an arithmetization technique, such as R1CS, to encode a circuit representing for example a Merkle tree verification into the verification equation of Definition 4. This means that we can construct algebraic VC schemes with linear verification that are succinct and position binding. We formalize this result in Appendix B.3.

$$ \mathbf{Z{,} $$

This technique however either bypasses the underlying group and may reduce security to external problems, or rely on non-black-box usage of the group. An example of the latter comes by encoding a Merkle tree built using an hash function whose collision resistance is based on discrete logarithm over the same group G, such as Pedersen hash. Note that this construction would not retain algebraic properties from the underlying group. For this reason, following an + approach similar to [PRV12, DHH 21], we study whether in the Generic Group Model (GGM) the security of a VC can be reduced to hard problems on the underlying group. To this aim we provide the following more general definition.

Definition 6(Algebraic VCs with generic verification). A vector com- mitment scheme is said to be algebraic with generic verification if, in the GGM, the algorithms VC*:* Setup*;VC:* Com*;VC:* Open*;VC:* Vfy have oracle access to O_add ⁰ and O_eq.

$$ \mathcal{O}_{\mathsf{a d d}} $$

$$ \ {mathcal O O}_{\mathtt{e q}}^{0} $$

3.1 Generic Transformation from VCs to Signatures

The strategy we adopt to show our impossibility results is to establish a connection between vector commitments and signatures, providing a way to construct the latter from the former generically. This way we will be able to bridge ex- + tensions of the impossibility results in [DHH 21] for algebraic signatures to algebraic vector commitments.

More specifically, for a given VC (not necessarily algebraic) our transformation produces a signature scheme with polynomially bounded message space

$$ ^{10}\ \ mathbf i.\ (\mathbf z,m,i)=A_{0}(i)+z_{1}A_{1}(i)+\ldots+z_{h}A_{h}(i)+m A_{h+1}(i) $$

f1*;:::;ng*. The high-level idea is to compute a commitment c to random messages m₁;:::;m_n, and use (pp*;c*) as the verification key and the auxiliary information aux as the secret key. In order to sign a message i 2f1*;:::;ng*, the signer returns m_iand, the message and opening proof for the i-th position, while verification is performed by checking the correctness of. A formal description of the transformation is presented in Fig. 1.

$$ {1,\ldots,n} $$

$$ m_{1},\ldots,m_{n} $$

$$ (\mathsf{p p},c) $$

$$ i\in{1,\ldots,n} $$

$$ m_{i} $$

$$ \pi: $$

$$ \sigma=(m_{i},\pi) $$

Fig. 1. Generic transformation from VCs to signature schemes

3.2 #-Unforgeability

In terms of security the transformation in Fig. 1 fails in general to realize a UF- CMA-secure signature scheme. Informally, the problem is that position binding and succinctness do not imply, per se, that every opening proof is hard to compute, after having seen other openings. Indeed the latter property could be easily violated, for example, by a VC where VC*:* Open attaches to every opening the proof (m₁;₁) for position 1. Notice that one could modify any VC to do so without violating succinctness nor position binding. Yet starting from such a VC would allow an adversary to easily forge a signature for message 1 in the scheme in Fig. 1.

$$ (m_{1},\pi_{1}) $$

Observe that if the VC scheme were hiding, meaning that no information about messages in unopened positions is leaked, and jVC*:* Mj is large enough, then the associated signature would be secure, since an adversary would have to guess the right message in the i-th position. This intuition can be extended to the non-hiding case assuming that the scheme is succinct. Indeed, even though the commitment c or its openings may leak information about m₁;:::;m_n, if their bit length is significantly smaller than n, no adversary can produce “too many” forgeries given only a few openings, as correctly guessing these message would be information-theoretically hard.

$$ m_{1},\ldots,m_{n}. $$

For this reason we introduce a relaxed notion of unforgeability for signatures, called #-unforgeability, which is enough for our purposes. In a nutshell, it requires a winning adversary to produce at least # forgeries on distinct messages, with

being a function of the queries performed and the public parameters. Next,

using the intuition above, we prove that signature schemes obtained through the transformation in Fig. 1 satisfy this weaker notion.

Definition 7(#-UF). Given a function # : f0*;* 1g! N and a signature scheme we define the #-Unforgeability Experiment as in Fig. 2. The advantage of an adversary A is defined as h i

$$ \vartheta:{0,1}^{*}\to\mathbb{N} $$

$$ \mathsf{A d v}^{\vartheta\mathrm{-U F}}(\mathcal{A});=;\operatorname*{{P}}!\left[\mathsf{E x p}_{\mathcal{A}}^{\vartheta\mathrm{-U F}}=1\right] $$

A scheme is #-Unforgeable if any PPT adversary has negligible advantage.

#-UF ExpAwith adversary A: $ 1 : Initialize Q?, generate sk;vk S: Setup(1) and send A vk 2 : When A! m 2 S: M: $ 3 : Sign S: Sign(sk;m), store Q Q [ (m;) and send A 4 : When A! F: 5 : Return 1 if the following conditions are satisfied: 6 : For all (m;) 2 F, the signature is correct, i.e. S: Vfy(vk;m;)! 1 7 : Messages in F were not queried, i.e. (m;) 2 F) (m;) 2= Q 8 : jfm : (m;) 2 F gj > #(vk;Q) 9 : Else return 0

$$ (m,\sigma)\in F $$

Fig. 2. #-Unforgeability Experiment for a given signature scheme

To provide more intuition about this notion we observe that setting # = 0 yields the classic unforgeability under chosen message attacks (UF-CMA) [GMR88] security definition. For higher values of # we obtain progressively weaker definitions until #(vk*;Q*) = jS*:* Mj, which is trivially true for any scheme. The notion of t-time security is also captured by our definition setting (

$$ \vartheta $$

$$ \vartheta(\mathsf{v k},Q)=|\mathsf{S.M}| $$

$$ \vartheta(\mathsf{v k},Q);=;\begin{cases}{0}&{\ \mathrm{I f}|Q|\leq t}\ {|\mathsf{S.M}|}&{\ mathrm{I f}|Q|>t}\end{cases} $$

Finally we can show that a signature scheme obtained from a “succinct” VC satisfy this notion. A full proof appears in Appendix C.1.

Theorem 1. Given a Vector Commitment with commitments of bit-length ‘_c= ‘_c(n;) and opening proofs of bit-length ‘ = ‘ (n;), then there exists a PPT black box reduction R of #-UF for the derived signature scheme described in Fig. 1 to the position binding property, where

$$ \ell_{\pi}=\ell_{\pi}(n,\lambda) $$

$$ \ell_{c}(n,\lambda) $$

$$ \ell_{c}= $$

$$ \vartheta(\mathsf{v k},Q):=:\frac{\lambda+\ell_{c}+|Q|\cdot\ell_{\pi}}{\log|\mathsf{V C.M}|}. $$

In particular for any position binding VC, the resulting signature is #-UF with

as specified above.

$$ \vartheta-U F $$

4 Algebraic Signatures

Having established a connection between VC and signatures we now provide the analogous of algebraic VC with (strictly) linear/generic verification in the signature setting. The first one is equivalent to the notion of algebraic signature + in [DHH 21] and simply constrain the verification procedure to test a system of linear equations, albeit with a minor addition: as these signatures may come in our case from a VC, we split S*:* Setup in a CRS-generator S*:* SetupCRS which returns the public parameters (a list of group elements X₁) and the actual key generation algorithm S*:* SetupKey(X₁) which produces vk and sk. Note there is no loss of generality assuming this structure as S*:* SetupCRS may return an empty vector which could then be ignored by S*:* SetupKey.

$$ \mathbf{X}_{1} $$

Definition 8. A signature scheme (S*:* Setup*;* S*:* Sign*;* S*:* Vfy) is said to be algebraic with linear verification if

– S*:* Setup is divided into two algorithms S*:* SetupCRS and S*:* SetupKey such that $ n1 $ S*:* SetupCRS(1)! (X₁*;s₁*) 2 G and S*:* SetupKey(1*;X₁)!* sk*;*vk with

$$ \S.S e t u p\ (R!\ S(1^{\lambda})!!
$$

$$ S. \mathrm {S e t u p K e y} \left(1 ^ {\lambda}, \mathbf {X} _ {1}\right) ^ {$} \rightarrow s $$

$$ \mathsf{M k}=\underset{}{(\mathbf{X},s)\in\mathbb{G}^{n}}{\asymp}{0,\mathbf{1}}^{*}\quad:\quad\mathbf{X}=\mathbf{X}{1}||\mathbf{X}{2},\qquad\mathbf{X}{2}\in\mathbb{G}^{n{2}},\qquad s=s_{1}||s_{2}. $$

$ k h – S*:* Sign(sk*;m*)! where = (Y*;z) with Y 2 G and z 2 F_q.*

$$ -\ {mathsf S..S i g n(k,)}\stackrel{\S}{\to}\sigma $$

$$ \boldsymbol{\sigma}=(\mathbf{Y},\mathbf{z}) $$

$$ \mathbf{z}\in\mathbb{F}_{q}^{h}. $$

$$ \mathbf{Y}\in\mathbb{G}^{k} $$

h ‘;n h ‘;k – There exist A : F_qS*:* M f0*;* 1g! F_qand B : F_qS*:* M f0*;* 1g! F_q matrices such that S*:* Vfy(vk*;m;)!* 1 if and only if = (z*;*Y) and

$$ A:\mathbb{F}{q}^{h}\times\S{.}\mathsf{M}\times{0,1}^{*}\to\mathbb{F}{q}^{\ell,n} $$

$$ B:\mathbb{F}{q}^{h}\times\mathsf{S.M}\times{0,1}^{*}\to\mathbb{F}{q}^{\ell,k} $$

$$ S.V y(\mathsf{v k},m,\sigma)\to1\ i $$

$$ i f,\sigma=(\mathbf{z},\mathbf{Y}) $$

$$ A({\bf z},m,s){\bf X},=,B({\bf z},m,s){\bf Y}. $$

Furthermore the scheme is said to have strictly linear verification if A(z*;m;s*) is an affine function of z and B(m;s) does not depend on z*.*

$$ i f,A(\mathbf{z},m,s) $$

$$ B(m,s) $$

When clear from the context we will omit for clarity the argument s in the matrices A;B above. Next we provide an analogous for algebraic vector commitments with generic verification. As in the previous definition we split the setup algorithm into a procedure that prepares the CRS and another one that uses the CRS, oblivious to any trapdoor information about it, to compute the secret and verification keys.

$$ A,B $$

Definition 9. A signature scheme (S*:* Setup*;* S*:* Sign*;* S*:* Vfy) is said to be alge- braic with generic verification if, in the GGM, all algorithms have access to 0 O_addand O_eq. Furthermore we require S*:* Setup to be divided into two algo- $ rithms S*:* SetupCRS and S*:* SetupKey such that S*:* SetupCRS(1)! (X₁*;s₁*) 2 ⁿ¹ $ G f0*;* 1g and S*:* SetupKey(1*;X₁)!* sk*;*vk with

$$ \mathcal{O}_{\mathsf{a d d}} $$

$$ {\mathcal{O}}_{\ \mathsf{e q}}^{0}. $$

$$ \mathrm {S}. \mathrm {S e t u p C R S} \left(1 ^ {\lambda}\right) ^ {$} \rightarrow \left(\mathbf {X} _ {1}, s _ {1}\right) \in $$

$$ \mathbb{G}^{n_{1}}\times{0,1}^{*} $$

$$ \mathsf{S.S e t u p K e y}(\mathbf{1}^{\lambda},\mathbf{\dot{X}}_{1})\stackrel{\mathfrak{g}}{\to}\mathsf{s}| $$

$$ \mathsf{w}\mathsf{k}=(\mathbf{X},s)\in\mathbb{G}^{n}\times{0,1}^{*}\quad:\quad\mathbf{X}=\mathbf{X}{1}||\mathbf{X}{2},\qquad\mathbf{X}{2}\in\mathbb{G}^{n{{}{{}{{2}}}}}\\ \\ s=={1}||s_{2}. $$

4.1 Relations among CRS elements

The main technical advantage of treating a part of the verification key as an honestly generated (possibly structured) CRS is that the signer has no extra information about it than the verifier. In other words, any relation among the exponents of X₁ that an adversary cannot extract is unknown to the signer as well, whereas any linear relation the signer can extract is also accessible to any adversary.

$$ \mathbf{X}_{1} $$

To use properly this intuition in our attacks we say that an algorithm generating a vector X of group elements is*-hard* if is the smallest integer such that extracting independent linear condition on X is infeasible. Formally

Definition 10. Given a PPT algorithm Gen we say it is-hard if is the small- $ n est integer such that for all A PPT*, sampling* Gen(1)! (X*;s*) 2 G f0*;* 1g

$$ i f\nu $$

$$ {\mathsf{G e n}}(1^{\lambda}),^{\sharp}\to\left(\mathtt{X},s mathfrak{s}\right)\in\mathbb{G}^{n}\times\left{0,1\right}^{\star} $$

$$ \operatorname*{P r}[\begin{matrix}{\ \ mathsf r k k(A)=\nu}\ {A\mathbf X{=b b}}\ \end{matrix}\ |\ mathcal(\mathbf X,s)\to A,\mathbf{b}]\leq\mathsf{n e g l}(\lambda) $$

Analogously, Gen is-generically-hard if Gen is generic and is the smallest integer such that the above condition is verified for all unbounded A performing 0 in the GGM a polynomially bounded number of queries to O_addand O_eq.

$$ \mathcal{O}_{\mathsf{a d d}} $$

$$ \mathcal {O} _ {\mathrm {e q}} ^ {0} $$

Notice that 1 n+1 as it is impossible to extract n+1 or more independent linear relations among n group element. Moreover, as is the smallest integer satisfying the above condition, there has to exist an algorithm able to extract 1 linearly independent relations for elements in X with significant probability.

$$ n{+}1 $$

$$ 1\leq\nu\leq n{1} $$

$$ \nu!-!1 $$

4.2 Attack to Schemes with Strictly Linear Verification

We now provide an attack for algebraic signatures with strictly linear verification. The same notation of Definition 8 will be used below without further reference.

Theorem 2. Given a signature scheme with strictly linear verification, for any

polynomially bounded such that n₂+# jS: Mj there exists a PPT algorithm A

that in the unforgeability experiment in Fig. 2 performs at most n₂ queries and produces # distinct forgeries with significant probability.

$$ n_{2}!+!\vartheta\leq|\mathsf{S.M}| $$

$$ n_{2} $$

• Proof. Similarly to the attack described in [DHH 21], upon receiving the verification key (X*;s*), A (described formally in Figure 3) keeps track of all possible n exponents of X in an affine space L F_q. Theⁿ for each message m_ieither a forgery can be produced or a new condition on X is found, thus decreasing dimL, at the cost of a signature query. This is done by checking if the system h A(z*;m*)x = B(m)y can be solved for a given z 2 F_qand all x 2 L. More specifically we define S(L;m), the solutions set, as the collection of all those z for which any x 2 L makes the systems solvable, formally

$$ [\mathrm{D H D^{+}2]} $$

$$ (\mathbf{X},s),\mathcal{A} $$

$$ L\subseteq\mathbb{F}_{q}^{n} $$

$$ m_{i} $$

$$ A(\mathbf{z},m)\mathbf{x}=B(m)\mathbf{y} $$

$$ \mathbf{z}\in\mathbb{F}_{q}^{h} $$

$$ \mathbf{x}\in L $$

$$ S(L,m) $$

$$ \mathbf{x}\in L $$

$$ S(L,m)\ =\ {\mathbf{z}\in\mathbb{F}_{q}^{h}\ :\ A(\mathbf{z},m)\cdot L\subseteq\operatorname{I m}B(m)}. $$

If S(L;m) is easy to compute, a strategy for A is to check whether S(L;m) 6= ? and in this case to get any z 2 S(L;m) and find, using pseudo-inverses or Gausk sian elimination, a vector Y 2 G such that A(z*;m*)X = B(m)Y. Conversely, if S(L;m) = ?, A may request a signature (Y*;z), which implies that the exponent x of X satisfies the condition A(z;m*)x 2 ImB(m). Notice that, unlike + the attack presented in [DHH 21], A is required to be PPT and thus computing S(L;m) efficiently is essential in our argument. This will follow as we assumed the verification to be strictly linear, implying that S(L;m) is an affine space. Finally, to give a tight bound on the number of signature queries, we assume S*:* SetupCRS to be-hard for some 2 N, i.e. such that it is unfeasible to extract or more independent linear relations of the CRS. By the minimality of there has to exist a PPT extractor E which with significant probability () returns 1 independent linear relations among the CRS elements. Thanks to this, A will only be able to extract, up to negligible probability, relations among group elements that are not in the CRS, thus making at most n₂ queries instead of n = n₁ + n₂.

$$ S(L,m)\neq\varnothing $$

$$ S(L,m) $$

$$ \mathbf{z}\in S(L,m) $$

$$ \mathbb{Y}\in\mathbb{G}^{k} $$

$$ A(\mathbf{z},m)\mathbf{X}=B(m)\mathbf{Y} $$

$$ S(L,m)=\varnothing,,\mathcal{A} $$

$$ (\mathbf{Y},\mathbf{z}) $$

$$ A(\mathbf{z},m)\mathbf{x}\in\operatorname{I m}B(m) $$

$$ S(L,m) $$

$$ S(L,m) $$

$$ \nu\in\mathbb{N},\mathrm{i.e} $$

$$ \eta(\lambda) $$

$$ \mathcal{E} $$

$$ \nu-1 $$

$$ n=n_{1}+n_{2} $$

$$ n_{2} $$

A more detailed proof appears in the appendix, Section C.2.

$$ s=s_{1}||s_{2} $$

$$ \mathbf{X}=\mathbf{X}{1}||\mathbf{X}{2} $$

$$ \mathsf{V}\mathsf{k}=(\mathsf{X},\mathsf{s}) $$

Adversary A(vk): 1 : Parse vk = (X*;s*) with X = X₁jjX₂ and s = s₁jjs₂ $ 2 : Run R;b E(X₁;s₁) and abort if E fails, rk (R) 6= 1 or RX₁ 6= b n1+n2n 3 : Set L = fx₁jjx₂ 2 F_q: Rx₁ = bg F_q 4 : Iⁿitialize the set of forgeries F? and call n₂ + # 5 :$ Sample m₁;:::;m S*:* M distinct messages 6 : For i 2f1*;:::;g*: 7 : If S(L;mi) 6= ?: 8 : Get a vector z 2 S(L;mi) k 9 : Find a solution Y 2 G such that A(z*;mi*)X = B(mi)Y 10 : Set (Y*;z) and store F F [f(mi;)g 11 : Else: 12 : Query mi to the challenger and get = (Y;z) n 13 : Update L L \fx 2 F_q: A(z;mi*)x 2 ImB(mi)g 14 : Return F

$$ R,\mathbf{b}\leftarrow^{\S}\mathcal{E}(\mathbf{X}{1},s{1}) $$

$$ (R)\neq\nu-1 $$

$$ R\mathbf{X}_{1}\neq\mathbf{b} $$

$$ L={\mathbf{x}{1}||\mathbf{x}{2};\in;\mathbb{F}{q}^{n{1}+n_{2}};:;R\mathbf{x}{1}=\mathbf{b}}\subseteq\mathbb{F}{q}^{r} $$

$$ F\gets\varnothing $$

$$ \theta\leftarrow n_{2}+\vartheta $$

$$ i\in{1,\ldots,\theta} $$

$$ S \left(L, m _ {i}\right) \neq \varnothing $$

$$ \mathbf{z}\in S(L,m_{i}) $$

$$ \mathbf{Y}\in\mathbb{G}^{k} $$

$$ \boldsymbol{\sigma}\leftarrow(\mathbf{Y},\mathbf{z}) $$

$$ m_{i} $$

$$ F\leftarrow F\cup{(m_{i},\sigma)} $$

$$ \sigma = (\mathbf {Y}, \mathbf {z}) $$

$$ L\mathrel{\leftarrow}L\cap{\mathbf{x}\in\mathbb{F}{q}^{n};:;A(\mathbf{z},m{i})\mathbf{x}\in\operatorname{I m}B(m_{i})} $$

Fig. 3. A breaking #-UF of an algebraic signature with strictly linear verification.

4.3 Attack to Schemes with Generic Verification

Theorem 3. Given an algebraic signature scheme with generic verification, for any # such that n₂ + # jS*:* Mj there exists an adversary A that in the unforge-

$$ n_{2}+\vartheta\leq|\mathsf{S.M}| $$

ability experiment in Fig. 2 performs at most n₂ signature queries and produces

distinct forgeries.

Moreover, calling an upper bound on the signature bit-length, and an 0 upper bound on the number of queries S*:* Vfy performs to O^eq, then A runs in 0 time O(# 2 2 poly()) and performs O(# poly()) queries to O_addand O_eq.

$$ n_{2} $$

$$ \chi $$

$$ {\mathcal{O}}_{\mathsf{e q}}^{0}. $$

$$ \mathcal{O}_{\mathsf{a d d}} $$

$$ O(\vartheta\cdot\mathsf{p o l y}(\lambda)) $$

$$ O(\vartheta\cdot2^{\kappa}\cdot2^{\chi}\cdot\mathsf{p o l y}(\lambda)) $$

$$ {\mathcal{O}}_{\mathrm{e q}}^{0}. $$

Proof. At a high level the attacker, given the verification key vk = (X*;s*), will keep track of all possible exponents of X in a set L and for each message m either the dimension of L decreases by one or A finds a forgery. Assume without loss of k generality that signatures are of the form (Y⁰*;t⁰*) with Y⁰ 2 G and t⁰ 2f0*;* 1g.

$$ \mathsf{v}\mathsf{k}=(\mathbf{X},s) $$

$$ (\mathbf{Y}^{\prime},t^{\prime}) $$

$$ \mathbf{Y}^{\prime}\in\mathbb{G}^{k} $$

$$ t^{\prime}\in{0,1}^{\kappa} $$

For any m, our adversary attempts to produce a forgery as follows: For all possible t 2f0*;* 1g, it executes the verification algorithm by simulating a generic e e e0 group G with oracles O_addand O_eq. More specifically, since S*:* Vfy requires as input the verification key (X*;s*), the message m and the signatures (Y*;t*), A reproduces all the group elements involved by assigning dummy indexes for Xe, Ye and runs S*:* Vfy((Xe*;s*);m; (Ye*;t*)). During the execution, each query to Oe is _add e0 emulated by simply returning new incremental indexes, while to emulate O_eq, bits₁;:::; are chosen at the beginning of the execution so that the answer to the i-th query will beⁱ. Note that each element Tⁱthe verifier queries to e0 O_eqhas to be a linear combination of the initial group elements he received,

e>e e obtained though e i.e. Tⁱ= aⁱX b_iY ciG O_add, and A can extract these coeff_icients.

$$ t\in{0,1}^{\kappa} $$

$$ \tilde{\mathcal{O}}_{\mathsf{a d d}} $$

$$ \tilde{\mathbb G} $$

$$ \tilde{O}sb{{\mathrm{e a}}}^{0}} $$

$$ (\mathbf{X},s) $$

$$ (\Upsilon{},t{,},\mathcal{A} $$

$$ \mathsf{S.V f y}((\widetilde{\mathtt{X}},s),m,(\widetilde{\mathtt{Y}},t)) $$

$$ {mathbf\mathbf x{}.} $$

$$ \tilde{\mathcal{O}}_{\mathsf{a d d}} $$

$$ \widetilde{\mathcal{O}}_{\mathtt{e q}}^{0},,\chi $$

$$ \beta_{1},\ldots,\beta_{\chi} $$

$$ \beta_{i} $$

$$ T_{i} $$

$$ \tilde{\mathcal{O}}_{\mathrm{e q}}^{0} $$

$$ T_{i}=\mathbf{a}{i}^{\top}\widetilde{\mathbf{X}}-\mathbf{b}{i}^{\top}\widetilde{\mathbf{Y}}-c_{i}\cdot\widetilde{G}} $$

$$ \tilde{\mathcal{O}}_{\mathsf{a d d}} $$

$$ \mathcal{A} $$

Repeating the execution of S*:* Vfy for different values of₁;:::; implicitly defines a tree of height in which paths are determined by the replies A gave at e0 the i-th query to O_eq. If at some point a path₁;:::; that makes the verifier accept is found, A can try to find a vector Y in the real GGM, such that the 0 i-query S*:* Vfy would do to O_eqwill be answered with_i. If such a Y is found, then (Y*;t*) will be a valid forgery for m.

$$ \beta_{1},\ldots,\beta_{\chi} $$

$$ \tilde{\mathcal{O}}_{\mathrm{e q}}^{0} $$

$$ \beta_{1},\ldots,\beta_{\chi} $$

$$ \mathcal {O} _ {\mathrm {e q}} ^ {0} $$

$$ \beta_{i} $$

Recalling that the i-th query has the form T = a Xe b Ye c G, then A i i i i needs to find a vector Y such that for all i 2f1*;:::;g*

$$ T_{i}=\mathbf{a}{i}\tilde{\mathbf{X}}-\mathbf{b}{i}\tilde{\mathbf{Y}}-c_{i}\cdot\mathcal{G} $$

$$ i\in{1,\ldots,\chi} $$

$$ \mathbf{a}{i}^{\top}\mathbf{X}=\mathbf{b}{i}^{\top}\mathbf{Y}+c_{i}\cdot G\ \ \operatorname{w h e n}\ \ \beta_{i}=1,\qquad\mathbf{a}{i}^{\top}\mathbf{X}\not\sim\mathbf{b}{i}^{\top}\mathbf{Y}+c_{i}\cdot G\ \ operatorname w h h n\ beta_{i}=0 $$

Regarding the equations on the left side, they can be packed up into a system AX = BY + c G. Through pseudo-inverses or Gaussian elimination is easy to check if solutions exists for all x 2 L (as in the proof of Theorem 2). If this is not the case A simply discards this path and continues its brute-force search. However, even if the previous condition is satisfied, for some of the points x in L it may be the case that any vector y satisfying Ax = By + c fails to satisfy some

k of the inequalities above aⁱx 6= bⁱy +cⁱ, implying that no solution Y 2 G can be found if x is the discrete logarithm of X. We call these points x 2 L faulty and, more specifically, the set of faulty points is defined as

$$ A\mathtt{X}=B\mathtt{Y}+\mathtt{c}\cdot G $$

$$ \mathbf{x}\in L $$

$$ \mathbf{a}{i}^{\top}\mathbf{x}\neq\mathbf{b}{i}^{\top}\mathbf{y}+c_{i} $$

$$ A\mathbf{x}=B\mathbf{y}+\mathbf{c} $$

$$ \mathbf{Y}\in\mathbb{G}^{k} $$

$$ \mathbf{x}\in L $$

$$ \mathcal {F} _ {\mathbf {a}, \mathbf {b}, c} ^ {A, B, \mathbf {c}} = \left{\mathbf {x}: A \mathbf {x} \in \operatorname {I m} B + \mathbf {c}, \quad \forall \mathbf {y} \in \mathbb {F} _ {q} ^ {m} \quad A \mathbf {x} = B \mathbf {y} + \mathbf {c} \Rightarrow \mathbf {a} ^ {\top} \mathbf {x} = \mathbf {b} ^ {\top} \mathbf {y} + c \right}. $$

Three possible cases may occur now:

– If all points in L are faulty with respect to some inequality constraint, then A gives up on the path as the solution Y does not exist.

– If not all points are faulty A attempts to solve the system, which requires 0 expensive queries to O_add; O_eq: if a solution Y satisfying all constraints is found, this is a valid forgery.

$$ \mathcal{O}{\mathsf{a d d}},\mathcal{O}{\mathsf{e q}}^{0}. $$

– If not all points are faulty, but no solution can be found, it means that x, the discrete log of X, has to be a faulty point. This information reduces the dimension of L as not all points in L are faulty.

$$ \mathbf{X}_{i} $$

Finally, if no solution can be found for any t 2f0*;* 1g and path₁;:::;, A queries a signature for m and uses this information to reduce the dimension of L. Finally, assuming the CRS generation algorithm is-generically-hard, there exists an extractor E returning with significant probability (), 1 independent linear relations among the elements of X₁. This is necessary to ensure than any new relation found involves X₂, meaning that the dimension of L decreases at most n₂ times. A detailed description of A appears in Fig. 4, while a more detailed proof of the Theorem appears in the appendix, Section C.3.

$$ t\in{0,1}^{\kappa} $$

$$ \beta_{1},\ldots,\beta_{\chi} $$

$$ \mathcal{E} $$

$$ \eta(\lambda) $$

$$ \mathbf{X}_{1} $$

$$ \mathbf{X}_{2} $$

$$ n_{2} $$

5 Conclusions

5.1 Impossibility of Algebraic Vector Commitments

Using both the negative results provided in the previous sections for algebraic signatures and Theorem 1 connecting the efficiency of a VC to the security of the associated signature scheme, we obtain two lower bounds for algebraic vector commitments

Theorem 4. Given a position binding algebraic VC with strictly linear verifica- tion, let ‘_c= ‘_c(n) and ‘ = ‘ (n) be respectively the commitment and opening bit length to commit to a vector of n entries. Then

$$ \ell_{c}=\ell_{c}(n) $$

$$ \ell_{\pi}=\ell_{\pi}(n) $$

$$ \nu_{2}+\frac{\lambda+\ell_{c}+\nu_{2}\cdot\ell_{\pi}}{\operatorname{l o g}|\mathsf{V C}M|};\geq;n. $$

Proof. Assume there exists an algebraic VC with strictly linear verification contradicting the above inequality and satisfying position binding. Then by Theorem 1 the signature scheme obtained through the transformation in Fig. 1 would satisfy #-UF with + ‘ + jQj ‘

$$ \vartheta(\mathsf{v k},Q)\ =\ \frac{\lambda+\ell_{c}+|Q|\cdot\ell_{\pi}}{\operatorname{l o g}|\mathsf{V C.M}|} $$

and its message space would have size jS_VC: Mj = n. Since vk contains₂group elements excluding those that belong to the CRS, i.e. the public parameters of the original Vector Commitment, the attacker A from Theorem 2 can produce at least n₂forgeries performing at most₂queries. Called Q the set of queries performed by A we would have that

$$ |\mathsf{S}_{\mathsf{V C}}.\mathsf{M}|=n $$

$$ \nu_{2} $$

$$ n-\nu_{2} $$

$$ \nu_{2} $$

$$ \mathcal{A} $$

$$ \vartheta(\mathsf{v k},Q):\leq:\frac{\lambda+\ell_{c}+\nu_{2}\cdot\ell_{\pi}}{\log|\mathsf{V C}.\mathsf{M}|}:<:n-\nu_{2} $$

Adversary A(vk): n1 1 : Parse vk = (X*;s*) with X = X₁jjX₂ such that X₁ 2 G aⁿd s = s₁jjs₂ $ 2 : Run R;b E(X₁;s₁) and abort if E fails, rk (R) 6= 1 or RX₁ 6= b 3 : Initialize F? the set of forgeries n1+n2n 4 : Call L = fx₁jjx₂ 2 F_q: Rx₁ = bg F_qthe set of possible exponents of X 5 :$ Call = n + # and sample m₁;:::;m S*:* M distinct messages 6 : For m 2fm₁;:::;m g: 7 : For t 2f0*;* 1g and ( 1*;:::;) 2f0;* 1g : e with generator e and oracles e e0 8 : Simulate a Generic Group G G O_addand Oeq 9 : e ene ek Assign indices for two vectors X 2 G and Y 2 G 10 : Run S*:* Vfy((Xe*;s*);m; (Ye*;t*)) using Ge 11 : When S*:* Vfy queries Oe (T;S): _add 12 : Store a way to express T + S as a linear combination of Xe, Ye and Ge 13 : Return to S*:* Vfy a label for T + S e0 14 : When S*:* Vfy queries Oeq(Ti) the i-th time: n k >e>e e 15 : Store ai 2 F_q, bi 2 F_qand ci 2 Fq such that Ti = a_iX b_iY ci G 16 : Return i to S: Vfy 17 : When S: Vfy halts and returns b 2f0*;* 1g: 18 : Let A = (ai : i = 1), B = (bi : i = 1) and c = (ci : i = 1) 19 : If b = 0: 20 : Continue cycle in line 7 21 : Elif A L * ImB + c: 22 : Continue cycle in line 7 A;B;c 23 : Elif 9i : i = 0 _and L Fa_;b;^c_i: i i 24 : Continue cycle in line 7 A;B;c 25 : Elif 9i : i = 0 _and X 2Fa_;b;^c_iG: i i A;B;c 26 : Update L L \F_a;b;c_{i i} i 27 : Break cycle in line 7 28 : Else: 29 :k > > Find Y 2 G s.t. AX = BY + cG and aiX 6= b_iY + ciG for i = 0 30 : Store (Y*;t*) and F F [f(m;)g 31 : Break cycle in line 7 32 : If the cycle ended without interruptions: 33 : Query a signature for m and wait for (Y*;t*) 34 : Reconstruct A;B; c as in step 18 using (X*;s;m;Y;t*) and the group G n 35 : Update L L \fx 2 F_q: Ax 2 ImB + cg 36 : Return F

$$ \mathbb{X}{1}\in\mathbb{G}^{n{1}} $$

$$ s=s_{1}\ \ |s_{2} $$

$$ \mathbf{X}=\mathbf{X}{1}||\mathbf{X}{2} $$

$$ \mathsf{V}\mathsf{k}=(\mathsf{X},s) $$

$$ (R)\neq\nu-1 $$

$$ R,\mathbf{b}\leftarrow^{\S}\mathcal{E}(\mathbf{X}{1},s{1}) $$

$$ \mathcal{E} $$

$$ F\gets\Phi $$

$$ L={\mathbf{x}{1}||\mathbf{x}{2};\in;\mathbb{F}{q}^{n{1}+n_{2}};:;R\mathbf{x}{1}=\mathbf{b}}\subseteq\mathbb{F}{q}^{n} $$

$$ \mathbf{X} $$

$$ \theta=n+\vartheta $$

$$ m\in{m_{1},\dots,m_{\theta}} $$

$$ t\in{0,1}^{\kappa} $$

$$ m_{1},\ldots,m_{\theta}\leftarrow^S{S}\S $$

$$ (\beta_{1},\ldots,\beta_{\chi})\in{0,1}^{\chi} $$

$$ \tilde{G} $$

$$ \widetilde{\mathbb{G}} $$

$$ \tilde{\cal{O}}_{\mathsf{a d d}} $$

$$ \widetilde{\mathbf{X}}\in\widetilde{\mathbb{G}}^{n} $$

$$ \widetilde{\mathbf{Y}}\in\widetilde{\mathbb{G}}^{k} $$

$$ \widetilde {\mathcal {O}} _ {\mathrm {e q}} ^ {0} $$

$$ \mathsf{S}V.\mathsf{f y}((\widetilde{\mathbf{X}},s),m,(\widetilde{\mathbf{Y}},t)) $$

$$ \widetilde{\mathbb{G}} $$

$$ \tilde{\mathcal{O}}_{\mathsf{a d d}}(T,S) $$

$$ T+S $$

$$ \widetilde{\mathbf{X}},\widetilde{\mathbf{Y}} $$

$$ T+S $$

$$ \tilde{G} $$

$$ \mathsf{S..V f y} $$

$$ \widetilde{\mathcal O{}}{\mathsf{e q}}^{0}(T{i}) $$

$$ \mathbf{a}{i}\in\mathbb{F}{q}^{n},:\mathbf{b}{i}\in\mathbb{F}{q}^{k} $$

$$ c_{i}\in\mathbb{F}_{q} $$

$$ T_{i}=\mathbf{a}{i}^{\top}\widetilde{\mathbf{X}}-\mathbf{b}{i}^{\top}\widetilde{\mathbf{Y}}-c_{i}\cdot\widetilde{G} $$

$$ \beta_{i} $$

$$ b\in{0,1}\colon $$

$$ A={\bigl(}\mathbf{a}{i}\ :\beta{i}=1{\bigr)},,B={\bigl(}\mathbf{b}{i}\ :\beta{i}=1{\bigr)} $$

$$ \mathbf{c}=(c_{i},:,\beta_{i}=1) $$

$$ b=0 $$

$$ A\cdot L\not\in $$

$$ B+\mathbf{c} $$

$$ \beta_{i}=0 $$

$$ L\subseteq\mathcal{F}{\mathbf{a}{i},\mathbf{b}{i},c{i}}^{A,B,\mathsf{c}}. $$

$$ \beta_{i}=0 $$

$$ \mathbf{X}\in\mathcal{F}{\mathbf{a}{i},\mathbf{b}{i},c{i}}^{A,B,\mathbf{c}}\cdot G: $$

$$ L\leftarrow L\cap\mathcal{F}{\mathbf{a}{i},\mathbf{b}{i},c{i}}^{A,B,\mathbf{c}} $$

$$ \mathbf{Y}\in\mathbb{G}^{k};{\mathrm{s.t.}};A\mathbf{X}=B\mathbf{Y}+\mathbf{c}\mathcal{G} $$

$$ \mathbf{a}{i}^{\top}\mathbf{X}\neq\mathbf{b}{i}^{\top}\mathbf{Y}+c_{i}G $$

$$ \boldsymbol{\sigma}\leftarrow(\mathbf{Y},t) $$

$$ \beta_{i}=0 $$

$$ F\leftarrow F\cup\left{\left(m,\sigma\right)\right} $$

$$ (\mathbf{Y},t) $$

$$ A,B,\mathbf{c} $$

$$ (\mathbf{X},s,m,\mathbf{Y},t) $$

$$ \mathbb{G} $$

$$ L\gets L\cap\left{\mathtt{x}\in\mathbb{F}_{q}^{n},:,A\mathtt{x}\in\operatorname{I m}B+\mathtt{c}\right} $$

Fig. 4. A breaking security of an algebraic signature scheme with generic verification.

where we use the fact that jQj₂in the first inequality. This is then a contradiction since A would breaks the #-UF of the derived signature, implying that the given vector commitment was not binding.

$$ |Q|\leq\nu_{2} $$

$$ \vartheta\mathrm{-}\mathrm{U F} $$

Theorem 5. Given an algebraic VC with generic verification that is position binding against unbounded adversaries performing polynomially bounded queries 0 to the GGM oracles O_add, O_eq, using the same notation of Theorem 4, then

$$ 4{,} $$

$$ \mathcal{O}{\mathsf{a d d}},,\mathcal{O}{\mathsf{e q}}^{0}. $$

$$ \nu_{2}+\frac{\lambda+\ell_{c}+\nu_{2}\cdot\ell_{\pi}}{\log|\mathsf{V C}.\mathsf{M}|};\geq;n. $$

Proof. Assuming again by contradiction that the above inequality is not satisfied, Theorem 1 implies that the associated signature scheme is #-UF against any unbounded adversary B making at most polynomially many signature and B group operations queries, or otherwise R would break position binding with sig- B nificant advantage. Notice that since R is PPT, R still performs polynomially many generic group operations. As in the proof of Theorem 4 then, our initial assumption implies # n₂. Since the adversary A of Theorem 3 returns n₂signatures performing at most₂queries, this contradicts the #-UF of the associated signature against this adversary.

$$ \vartheta\mathrm{-}\mathrm{U F} $$

$$ \mathcal{R}^{\mathcal{B}} $$

$$ \mathsf{P P T},\mathcal{R}^{\mathcal{B}} $$

$$ \vartheta,\leq,n-,\nu_{2} $$

$$ n-\nu_{2} $$

$$ \nu_{2} $$

Corollary 1. Given an algebraic vector commitment with strictly linear verifi- cation, then ‘_c‘ = (n). Analogously, given an algebraic vector commitment with generic verification position binding against unbounded adversary perform- ing at most polynomially many queries to the GGM oracles, ‘_c‘ = (n).

$$ \ell_{c}\cdot\ell_{\pi}=\varOmega(n) $$

$$ \ell_{c}\cdot\ell_{\pi}=\varOmega(n) $$

p Note that this lower bound implies in both cases that either ‘c= ( n) or p ‘ = ( n).

$$ \ell_ {c} = \Omega (\sqrt {n}) $$

$$ \ell_{\pi}=\varOmega(\sqrt{n}) $$

5.2 Impossibility of Algebraic Signatures

As a by-product of our study on VC we also obtain the following two impossibility + results for algebraic signatures which extend the one presented in [DHH 21].

$$ \left[ \mathrm {D H H} ^ {+} 2 1 \right] $$

Theorem 6. For any UF-CMA algebraic signature scheme with strictly linear verification, n₁ jS*:* Mj.

$$ n_{1}\geq|\mathsf{S}\mathsf{M.}| $$

Theorem 7. For any algebraic signature scheme with generic verification UF- CMA secure against any unbounded adversary performing at most polynomially many queries to the GGM oracles, n₁ jS*:* Mj.

$$ n_{1}\geq|\mathsf{S}M| $$

Acknowledgements

This work has received funding in part from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program under project PICOCRYPT (grant agreement No. 101001283), by the

Spanish Government under projects SCUM (ref. RTI2018-102043-B-I00), RED2018- 102321-T, and SECURING (ref. PID2019-110873RJ-I00), by the Madrid Regional Government under project BLOQUES (ref. S2018/TCS-4339), by a research grant from Nomadic Labs and the Tezos Foundation, by the Programma ricerca di ateneo UNICT 35 2020-22 linea 2 and by research gifts from Protocol Labs.

References

AHIV17.Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 2087–2104. ACM Press, October / November 2017. AHO12.Masayuki Abe, Kristiyan Haralambiev, and Miyako Ohkubo. Group to group commitments do not shrink. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 301– 317. Springer, Heidelberg, April 2012. ⁺ BBB 18.Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy, pages 315–334. IEEE Computer Society Press, May 2018. BBF19.Dan Boneh, Benedikt Bünz, and Ben Fisch. Batching techniques for accumulators with applications to IOPs and stateless blockchains. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 561–586. Springer, Heidelberg, August 2019. ⁺ BCC 16.Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 327–357. Springer, Heidelberg, May 2016. BF01.Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 213–229. Springer, Heidelberg, August 2001. BG12.Stephanie Bayer and Jens Groth. Efficient zero-knowledge argument for correctness of a shuffle. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 263–280. Springer, Heidelberg, April 2012. BGV11.Siavosh Benabbas, Rosario Gennaro, and Yevgeniy Vahlis. Verifiable delegation of computation over large datasets. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 111–131. Springer, Heidelberg, August 2011. CF13.Dario Catalano and Dario Fiore. Vector commitments and their applications. In Kaoru Kurosawa and Goichiro Hanaoka, editors, PKC 2013, volume 7778 of LNCS, pages 55–72. Springer, Heidelberg, February / March 2013. ⁺ CFG 20.Matteo Campanelli, Dario Fiore, Nicola Greco, Dimitris Kolonelos, and Luca Nizzardo. Incrementally aggregatable vector commitments and applications to verifiable decentralized storage. In Shiho Moriai and Huaxiong

Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 3–35. Springer, Heidelberg, December 2020. CPZ18.Alexander Chepurnoy, Charalampos Papamanthou, and Yupeng Zhang. Edrax: A cryptocurrency with stateless transaction validation. Cryptology ePrint Archive, Report 2018/968, 2018. https://eprint.iacr.org/ 2018/968. ⁺ DHH 21.Nico Döttling, Dominik Hartmann, Dennis Hofheinz, Eike Kiltz, Sven Schäge, and Bogdan Ursu. On the impossibility of purely algebraic signatures. In Theory of Cryptography Conference, pages 317–349. Springer, 2021. Fis18.Ben Fisch. PoReps: Proofs of space on useful data. Cryptology ePrint Archive, Report 2018/678, 2018. https://eprint.iacr.org/2018/678. GGK03.Rosario Gennaro, Yael Gertner, and Jonathan Katz. Lower bounds on the efficiency of encryption and digital signature schemes. In 35th ACM STOC, pages 417–425. ACM Press, June 2003. GGPR13.Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 626–645. Springer, Heidelberg, May 2013. ⁺ GKM 00.Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, and Mahesh Viswanathan. The relationship between public key encryption and oblivious transfer. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 325–335. IEEE Computer Society, 2000. GMR88.Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, April 1988. GMR01.Yael Gertner, Tal Malkin, and Omer Reingold. On the impossibility of basing trapdoor functions on trapdoor predicates. In 42nd FOCS, pages 126–135. IEEE Computer Society Press, October 2001. Gol87.Oded Goldreich. Two remarks concerning the Goldwasser-Micali-Rivest signature scheme. In Andrew M. Odlyzko, editor, CRYPTO’86, volume 263 of LNCS, pages 104–110. Springer, Heidelberg, August 1987. GT00.Rosario Gennaro and Luca Trevisan. Lower bounds on the efficiency of generic cryptographic constructions. In 41st Annual Symposium on Foun- dations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 305–313. IEEE Computer Society, 2000. IR89.Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In 21st ACM STOC, pages 44–61. ACM Press, May 1989. JK07.Ari Juels and Burton S. Kaliski Jr. Pors: proofs of retrievability for large files. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007, pages 584–597. ACM Press, October 2007. Kil94.Joe Kilian. On the complexity of bounded-interaction and noninteractive zero-knowledge proofs. In 35th FOCS, pages 466–477. IEEE Computer Society Press, November 1994. KST99.Jeong Han Kim, Daniel R. Simon, and Prasad Tetali. Limits on the efficiency of one-way permutation-based hash functions. In 40th Annual Sym- posium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA, pages 535–542. IEEE Computer Society, 1999.

Kus18.John Kuszmaul. Verkle trees, 2018. KZG10.Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 177–194. Springer, Heidelberg, December 2010. LM19.Russell W. F. Lai and Giulio Malavolta. Subvector commitments with application to succinct arguments. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 530–560. Springer, Heidelberg, August 2019. LRY16.Benoît Libert, Somindu C. Ramanna, and Moti Yung. Functional commitment schemes: From polynomial commitments to pairing-based accumulators from simple assumptions. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, ICALP 2016, volume 55 of LIPIcs, pages 30:1–30:14. Schloss Dagstuhl, July 2016. LY10.Benoît Libert and Moti Yung. Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In Daniele Micciancio, editor, TCC 2010, volume 5978 of LNCS, pages 499–517. Springer, Heidelberg, February 2010. Mau05.Ueli M. Maurer. Abstract models of computation in cryptography (invited paper). In Nigel P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, volume 3796 of LNCS, pages 1–12. Springer, Heidelberg, December 2005. Mer88.Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, CRYPTO’87, volume 293 of LNCS, pages 369–378. Springer, Heidelberg, August 1988. Mic94.Silvio Micali. CS proofs (extended abstracts). In 35th FOCS, pages 436– 453. IEEE Computer Society Press, November 1994. MPZ20.Ueli Maurer, Christopher Portmann, and Jiamin Zhu. Unifying generic group models. Cryptology ePrint Archive, Report 2020/996, 2020. https: //eprint.iacr.org/2020/996. MRK03.Silvio Micali, Michael O. Rabin, and Joe Kilian. Zero-knowledge sets. In 44th FOCS, pages 80–91. IEEE Computer Society Press, October 2003. MRV99.Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. Verifiable random functions. In 40th FOCS, pages 120–130. IEEE Computer Society Press, October 1999. PPS21.Chris Peikert, Zachary Pepin, and Chad Sharp. Vector and functional commitments from lattices. In Theory of Cryptography Conference, pages 480– 511. Springer, 2021. PRV12.Periklis A. Papakonstantinou, Charles Rackoff, and Yevgeniy Vahlis. How powerful are the DDH hard groups? Electron. Colloquium Comput. Com- plex., page 167, 2012. PSTY13.Charalampos Papamanthou, Elaine Shi, Roberto Tamassia, and Ke Yi. Streaming authenticated data structures. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 353–370. Springer, Heidelberg, May 2013. RSS20.Lior Rotem, Gil Segev, and Ido Shahaf. Generic-group delay functions require hidden-order groups. In Anne Canteaut and Yuval Ishai, editors, EU- ROCRYPT 2020, Part III, volume 12107 of LNCS, pages 155–180. Springer, Heidelberg, May 2020.

SGS21.Gili Schul-Ganz and Gil Segev. Generic-Group Identity-Based Encryption: A Tight Impossibility Result. In Stefano Tessaro, editor, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), volume 199 of Leib- niz International Proceedings in Informatics (LIPIcs), pages 26:1–26:23, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Sha84.Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David Chaum, editors, CRYPTO’84, volume 196 of LNCS, pages 47–53. Springer, Heidelberg, August 1984.

Sho97.Victor Shoup. Lower bounds for discrete logarithms and related problems. In Walter Fumy, editor, EUROCRYPT’97, volume 1233 of LNCS, pages 256–266. Springer, Heidelberg, May 1997.

Sim98.Daniel R. Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In Advances in Cryptology - EUROCRYPT ’98, volume 1403 of Lecture Notes in Computer Science, pages 334–345. Springer, 1998.

Zha22.Mark Zhandry. To label, or not to label (in generic groups). Cryptology ePrint Archive, Report 2022/226, 2022. https://eprint.iacr.org/2022/ 226.

ZZ21.Mark Zhandry and Cong Zhang. The relationship between idealized models under computationally bounded adversaries. Cryptology ePrint Archive, Report 2021/240, 2021. https://eprint.iacr.org/2021/240.

A More Preliminaries

A.1 Linear Algebra

We recall basic definitions and facts from linear algebra that we use in our proofs.

n;m m;n Definition 11. Given A 2 F_q, a weak left inverse of A is a matrix H 2 F_q such that AHA = A.

$$ A\in\mathbb{F}_{q}^{n,m} $$

$$ H\in\mathbb{F}_{q}^{m,n} $$

$$ A H A=A $$

n;m m;n Proposition 1. Given A 2 F_qand H 2 F_qthen H is a weak left inverse of A if and only if for any y 2 Im A, AHy = y*.*

$$ A\in\mathbb{F}_{q}^{n,m} $$

$$ H\in\mathbb{F}_{q}^{m,n} $$

$$ \mathbf{y}\in $$

$$ ,\ A A H\mathbf{y}=\mathbf{y} $$

n;m Proposition 2. There exists a PPT algorithm that given a matrix A 2 F_q returns a weak left inverse of A.

$$ A\in\mathbb{F}_{q}^{n,m} $$

Proof sketch. Calling V = ImA, let k = dimV and v₁*;:::;v_kbe a base of V, n m which can be extended to v₁;:::;vⁿbase of F^q. Theⁿ, since the map A : F^q!* _n ^m V F_qis surjective, there exists w_i2 F_qsuch that Aw_i= v_ifor all i k. n m Then, letti_ng H : F_q! F_qa linear function such that Hv_i= w_ifor i k and Hv_i= 0 otherwise, we show H is a weak left inverse for A.

$$ V=\operatorname{I m}A. $$

$$ V, $$

$$ \mathbf{v}{1},\ldots,\mathbf{v}{k} $$

$$ \mathbf{v}{1},\ldots,\mathbf{v}{n} $$

$$ \mathbb{F}_{q}^{n} $$

$$ A:\mathbb{F}_{q}^{m}\rightarrow $$

$$ V\leq\mathbb{F}_{q}^{n} $$

$$ \mathbf{w}{i}\in\mathbb{F}{q}^{m} $$

$$ A\mathbf{w}{i},=,\mathbf{v}{i} $$

$$ i\leq k $$

$$ H:\mathbb{F}{q}^{n}\to\mathbb{F}{q}^{m} $$

$$ H\mathbf{v}{i}=\mathbf{w}{i} $$

$$ H\mathrm{v}_{i}=0 $$

$$ i\leq k $$

n n To do this is enough to prove that the linear map AH : F_q! F_qis the identity over V, which is equivalent to show AH is the identity over a base of V. Indeed for all v_i, AHv_i= Aw_i= v_i.

$$ A H,:,\mathbb{F}{q}^{n},\to,\mathbb{F}{q}^{n} $$

$$ \mathbf{v}{i},,A H\mathbf{v}{i}=A\mathbf{w}{i}=\mathbf{v}{i} $$

Finally we remark that computing a base of ImA, extending it, finding preimages w_i, and computing the matrix H are all steps that can be performed in polynomial time.

$$ \mathbf{W}_{i}. $$

n Definition 12. Given L F^qbe an affine space, we call its direction dir L the n n only linear subspace of F_qsuch that L = x + dir L for some x 2 F_q.

$$ L\leq\mathbb{F}_{q}^{n} $$

$$ L $$

$$ \mathbb{F}_{q}^{n} $$

$$ L=\mathbf{x}+\dim $$

$$ \mathbf{x}\in\mathbb{F}_{q}^{n} $$

A.2 Min-Entropy

For a given random variable, the min-entropy measures informally how hard is it to correctly guess it without any information.

Definition 13. Given X X random variable distributed over a finite set X we define its min-entropy as

$$ \mathrm{H}{\infty}(X boldsymbol);=;-\log\left(\operatorname*{m a x}{x\in\mathcal{X}}\operatorname*{P r}\left[X=x\right]\right). $$

Definition 14. Given X X and Y Y two random variables over finite sets, the conditional min-entropy of X given Y is defined as 0 1

$$ \operatorname{H}{\infty}(X|Y);=;-\operatorname{l o g}\left(\sum{y\in\mathcal{Y}}\operatorname*{P P}\left[Y=y\right]\cdot\operatorname*{m a x}_{x\in\mathcal{X}}\operatorname*{P r}\left[X=x|Y=y\right]\right). $$

Proposition 3. Given X X and Y Y random variables over finite sets, then H₁(XjY) H₁(X) log jYj

$$ X \sim \mathcal {X} $$

$$ \mathrm{H}{\infty}(X|Y)\succeq\mathrm{H}{\infty}(X)-\mathrm{l o g}|\ {mathcal Y||} $$

Proof. X

$$ \begin{aligned}{\sum_{y\in\mathcal{Y}}\operatorname*{P r}\left[Y=y\right]\cdot\operatorname*{m a x}{x\in\mathcal{X}}\operatorname*{P r}\left[X=x|Y=x\right]\ =}&{{}\sum{y\in\mathcal{Y}}\operatorname*{m a x}{x\in\mathcal{X}}\operatorname*{P r}\left[X=x|Y=y\right]\operatorname*{P r}\left[Y=y\right]}\ {\ =}&{{}\sum{y\in\mathcal{Y}}\operatorname*{m a x}{x\in\mathcal{X}}\operatorname*{P r}\left[X=x,Y=y\right]}\ {\ }&{{}\leq\sum{y\in\mathcal{Y}}\operatorname*{m a x}{x\in\mathcal{X}}\operatorname*{P r}\left[X=x\right]}\ {\ }&{{}=|\mathcal{Y}|\cdot\operatorname*{m a x}{x\in\mathcal{X}}\operatorname*{P r}\left[X=x\right].}\ \end{aligned} $$

Applying log() to both sides yields the claimed inequality.

A.3 Arithmetic circuits and R1CS

In this section we introduce circuit satisfiability and the rank one constraint system relations, which will be used later to provide examples of secure algebraic signatures with linear verification. Informally we define an arithmetic circuit C as a tuple (n;g₁;:::;g_m) where there first n gates (g₁;:::;g_n) = (1*;:::;n*) are input gates and the remaining gates giare of the form (;j;k) where j;k < i or (;j;) with j < i and 2 Fqand 2f+; g is a binary operator. The last gate g_mis also considered to be the output gate.

$$ (n,g_{1},\ldots,g_{m}) $$

$$ {(}g_{1},\ldots,g_{n}{{\big)}}={(}1,\ldots,n{\big)} $$

$$ g_{i} $$

$$ (\circ,j,\alpha) $$

$$ (\circ,j,k) $$

$$ j<i $$

$$ j,k<i $$

$$ \alpha\in\mathbb{F}_{q} $$

$$ \circ\in{+,\cdot} $$

$$ g_{m} $$

n Given an arithmetic circuit and an input x 2 F_qwe caⁿ define the evaluation function ev_xfrom the gates of C to F_qrecursively as 8

$$ \mathbf{x}\in\mathbb{F}_{q}^{n} $$

$$ C $$

$$ \mathrm{e V}_{\mathbf{x}} $$

$$ \mathbb{F}_{q} $$

$$ \begin{cases}{\mathsf{e v}{\mathbf{x}}(g{i})=x_{i}}&{\operatorname{I f}\ i\leq n}\ {\mathsf{e v}{\mathbf{x}}(g{i})=\mathsf{e v}{\mathbf{x}}(g{j})\circ\mathsf{e v}{\mathbf{x}}(g{k})}&{\operatorname{I f}\ g_{i}=(\circ,j,k)}\ {\mathsf{e v}{\mathbf{x}}(g{i})=\mathsf{e v}{\mathbf{x}}(g{j})\circ\alpha}&{\operatorname{I f}\ g_{i}=(\circ,j,\alpha)}\ \end{cases} $$

A circuit it said to return a value y on input x, in symbols C(x) = y, if the output gate evaluates to ev_x(g_m) = y.

$$ \mathbf{x{,} $$

$$ \mathcal{C}(\mathtt{x})=\ y $$

$$ \mathsf{e v}{\mathbf{x}}(g{m})=y $$

The problem of determining whether a circuit is satisfiable, i.e. if there exists an input x such that C(m) returns 1, is notoriously NP-complete and tightly related to the more algebraic rank one constraints system (R1CS in short) satisfiability problem. Informally an instance of R1CS is a system of quadratic equations of the form M₁w M₂w = M₃w + b

$$ C(m) $$

$$ M_{1}\mathrm{w}*M_{2}\mathrm{w}=M_{3}\mathrm{w}+\mathrm{b} $$

where is the entry-wise product between same length vectors, M₁;M₂;M₃ 2 ^n;m m F^qand b 2 F^q. A given instance is said to be satisfiable if the above equation n admits a solutio_n w 2 F_q.

$$ M_{1},M_{2},M_{3}\in $$

$$ \mathbb{F}_{a}^{n,m} $$

$$ \in\mathbb{F}_{q}^{m} $$

$$ \mathbf{w}\in\mathbb{F}_{q}^{n} $$

As both circuit satisfiability and R1CS relations are NP-complete, there exists an efficient reduction T that takes as input a circuit C and return a R1CS n instance *M₁;M₂;M₃;*b, and, if provided an input x 2 F_qthat satisfies C, it further returns w satisfying the produced R1CS. Moreover, if *M₁;M₂;M₃;*b are obtained from C as above, there also exists an efficient procedure that, given in input a witness w for the R1CS, returns an input x satisfying C.

$$ M{{1}},M{{2}},M{_{3}},\mathbf{b} $$

$$ \mathbf{x}\in\mathbb{F}_{q}^{n} $$

$$ M_{1},M_{2},M_{3} $$

A detailed description of the reduction T can be found in [AHIV17, GGPR13], although we provide a sketch here for completeness. Given a circuit C = (n;g₁; m;m n+1 m;m n+1 :::;g_m), T builds the matrices M₁;M₂;M₃ 2 F_q; b 2 F_qaddiⁿg:

$$ \mathcal{C}=(n,g_{1} $$

$$ \cdots,g_{m}) $$

$$ M_{1},M_{2},M_{3}\in\mathbb{F}{q}^{m,m-n+1},\mathbf{b}\in\mathbb{F}{q}^{m,m-n+1} $$

– for each gate g_i= (+;j;k) [resp. g_i= (+;j;)] the constraint w_i= w_j+ w_k [resp. w_i= w_j+]

$$ g_{i}=(+,j,k) $$

$$ w_{i}=w_{j}+\alpha] $$

$$ g_{i}=(+,j,\alpha)] $$

$$ w_{i}=w_{j}+w_{k} $$

– for each gate g_i= (;j;k) [resp. g_i= (;j;)] the constraint w_i= w_jw_k [resp. w_i= w_j]

$$ g_{i},(,=,(cdot j j,k) $$

$$ g_{i},=,(\cdot,j,\alpha),] $$

$$ w_{i},=,w_{j}\cdot w_{k} $$

$$ w_{i}=w_{j}\cdot\alpha $$

– the constrain w_m= 1.

$$ w_{m}=1 $$

Furthermore if an input x such that C(x) = 1 is provided, T returns also a solution w such that w_i= ev_x(g_i). By the way ev was defined is immediate to verify by induction that w satisfies the given set of constraints if C(x) = 1. Moreover if w is a solution to the given system, then x = (w₁;:::;w_n) is such that C(x) = 1, implying that from any solution, a satisfying input for C can be computed efficiently.

$$ C(\mathbf{x}),=,1 $$

$$ w_{i}=\mathsf{e v}{\mathbf{x}}(g{i}) $$

$$ C(\mathbf{x}),=,1 $$

$$ \mathbf{x}=\ w_{1},\ldots,w_{n}) $$

$$ C(\mathbf{x})=1 $$

A.4 Generic Group Model

We now introduce more in details the Generic Group Model proposed by Maurer in [Mau05] and revised by Maurer, Portmann and Zhu [MPZ20]. Even though the definitions proposed in these papers are given in higher generality to capture a broad class of generic algorithms and problems, below we only present their instantiation to the case of a group of known prime order q.

Definition 15. A generic group of prime order q is an interactive Turing ma- chine B which at any step stores a list of elements L = (V₁;:::;V_m) with V_i2 F_q. Initially L is empty and m = 0*. Furthermore, upon receiving:*

$$ L=(V_{1},\dots,V_{m}) $$

$$ V_{i}\in\mathbb{F}_{q} $$

$$ m=0 $$

$$ V_{m+1}\leftarrow1 $$

$$ V_{m+1} $$

– (gen): Sets V_m+11*, appends V*_m+1to L and increments m m + 1*.*

$$ m\leftarrow m+1 $$

– (add*;i;j*): if i;j 2f1*;:::;mg, sets V*_m+1V_i+ V_j, appends V_m+1to L and increments m m + 1*.*

$$ -,!({\mathsf{a d d}},i,j)\colon!i f,i,j\in{1,\dots,m} $$

$$ V_{m+1}\gets V_{i}+V_{j} $$

$$ V_{m+1} $$

$$ n\leftarrow m+1 $$

A remarkable difference between this computational model and Shoup Generic Group Model [Sho97] is that a machine interacting with B has no access to a representation of group elements, and has to “remember” their indices as it queries them. This To avoid the issue of explicitly keeping track of them, which may render the description of generic algorithms more verbose, we may assume without loss of generality that after (gen) or (add*;i;j*), B returns m + 1, the newly generated element’s index. Furthermore, for notational simplicity, we model usage of the generic group through three oracles O_gen, O_add, O_eqsuch that

$$ \mathcal{O}{\mathsf{g e n}},\thinspace\mathcal{O}{\mathsf{a d d}},\thinspace\mathcal{O}_{\mathsf{e q}} $$

$$

• \mathcal {O} _ {\mathrm {g e n}} () $$

– O_gen() queries (gen) to B and return the new group element’s index G.

$$ G,. $$

– O_add(X;Y), queries (add*;X;Y*) to B and return the new group element’s index Z

$$ -\ {\mathcal O}_{\mathsf{a d d}}(X,Y) $$

– O_eq(X;Y), queries (eq*;X;Y*) to B and return the bit b it receives back from B.

$$ -\ \ \mathcal{O}_{\mathsf{e q}}(X,Y) $$

$$ (\mathfrak{e q},X,Y) $$

Noticeably, without loss of generality, one may assume that O_genis queried only once at the beginning of any algorithm’s execution – or equivalently that the list L maintained by B is initialized with 1 in its first entry. Similarly one may also assume that, up to performing at most 2 logq queries to O_add, an index for the group identity 0 is known - which could be obtained by computing q G. Analogously, given the index of an element X, its inverse can be computed in at most 2 logq queries to O_addby computing (q 1)X. Finally we observe that, since inverses can be computed efficiently, for algorithms that are bounded to perform at most a polynomial number of queries to B, it is enough to provide 0 access to the identity equality test oracle O_eqdefined as

$$ \ {\mathcal O}_{\mathrm{g e n}} $$

$$ \mathcal{O}_{\mathsf{a d d}} $$

$$ q\cdot G $$

$$ \mathcal{O}_{\mathsf{a d d}} $$

$$ (q-1)X $$

$$ Bbeta, $$

$$ \ {mathcal O O}_{\mathtt{e q}}^{0} $$

⁰ – O_eq(X): Given a precomputed index for 0, it queries (eq*;X;* 0) to B and returns the bit b it receives back from B.

$$ -\mathrm\ {{}normalfont~\mathcal{O}}_{\mathtt{e q}}^{0}(X) $$

$$ (\mathsf{e q},X,0) $$

0 Given access to this oracle O_eq(X;Y) can then be simulated querying O_eq(X Y).

$$ \mathcal{O}_{\mathsf{e q}}(X,Y) $$

$$ \mathcal{O}_{\mathsf{e q}}^{0}\bigl(X-!!Y\bigr) $$

B Examples and Constructions

B.1 Linear vs Generic Verification for Signatures

In this section we compare the definitions of algebraic signature with linear and generic verification. The first one, as mentioned, is equivalent to the notion of + algebraic signatures proposed in [DHH 21] whereas the second, seemingly more general, only requires the algorithms involved to use the group generically.

$$ [\mathrm{H D H^{+}21}] $$

In order to prove that the second notion is strictly more general we will provide an algebraic signature scheme that has generic verification but is not equivalent to any scheme with linear verification. The core idea is that, when 0 S*:* Vfy has no restriction it can test through O_eqwhether a given group element X has discrete logarithm in base G equals to 0 or 1, and continue the verification according to the result. In this way, given any signature scheme in the standard model, the signer can encode in the exponent a bit representation of a given signature while the verifier can extract these exponents and then verify the extracted string is a valid signature.

$$ {\mathcal{O}}_{\ \mathsf{e q}}^{0} $$

More formally, let (S*:* Setup*;* S*:* Sign*;* S*:* Vfy) be a secure signature scheme in the standard model (e.g., stateless constructions are known from trapdoor clawfree permutations, [GMR88, Gol87]). Then an algebraic signature scheme can be constructed as shown in Fig. 5.

S : Setup(1) $ 1 : vk*;sk S:* Setup(1) n 2 : Parse vk = ( 1*;:::;n*) 2f0*;* 1g 3 : Set X = ( 1G;:::;nG) 4 : Set vk X and sk sk 5 : Return vk*;*sk S : Vfy(vk;m;) 1 : Parse vk = X = (X₁;:::;Xn) and

S : Sign(sk;m) ^$ 1 : S*:* Sign(sk*;m*) k 2 : Parse = ( 1*;:::;k*) 2f0*;* 1g 3 : Set Y = ( 1G;:::;kG) 4 : Return Y = Y = (Y₁;:::;Yk)

0 2 : For each i 2f1*;:::;ng* set i the outcome of O_eq(Xi G) 0 3 : For each i 2f1*;:::;kg* set i the outcome of O_eq(Yi G) n k 4 : Set vk = ( 1*;:::;n*) 2f0*;* 1g aⁿd = ( 1*;:::;k*) 2f0*;* 1g $ 5 : Run b S*:* Vfy(vk*;;m*) and return b

$$ \mathsf{v k}=\mathsf{X}=\left(X_{1},\ldots,X_{n}\right) $$

$$ \boldsymbol{\sigma}^{*}=\mathbf{Y}=\left(Y_{1},\ldots,Y_{k}\right) $$

$$ i\in{1,\ldots,n} $$

$$ \beta_{i} $$

$$ \mathcal{O}{\mathsf{e q}}^{0}(X{i}-G) $$

$$ i\in{1,\ldots,k} $$

$$ \gamma_{i} $$

$$ \mathcal{O}{\mathsf{e q}}^{0}(Y{i}-G) $$

$$ \sigma=\left(\gamma_{1},\ldots,\gamma_{k}\right)\in{0,1}^{k} $$

Fig. 5. Algebraic Signature Scheme with linear verification

A PPT adversary against the unforgeability of this scheme clearly reduces to the security of the underlying signature. Thus using an existentially unforgeable scheme for this construction we would end up with a secure algebraic signature with generic verification.

To conclude, we prove that this scheme does not have linear verification

Proposition 4. There exist no matrices A;B such that S*:* Vfy(X*;m;* Y) accepts if and only if A(m)X = B(m)Y

$$ A(m)\mathbf{X}=B(m)\mathbf{Y} $$

Proof. Assuming by contradiction such A and B exist, then (S : Setup*;* S : Sign*;* S : Vfy) would be an algebraic scheme with linear verification and in particular + the adversary A described in [DHH 21] for algebraic signatures can be used to break the security of this construction. Note that for a general algebraic

$$ \mathsf{S}^{*}.\mathsf{V f y}) $$

$$ (\mathsf{S}^{}.\mathsf{S e t u p},\mathsf{S}^{}.\mathsf{S i g n} $$ scheme with linear verification, assuming each signature is of the form (Y*;t*) k with Y 2 G and t 2f0*;* 1g, the adversary A runs in time O(2 poly()). Since for the scheme described in Fig. 5 = 0 the adversary A would run in polynomial time, contradicting our assumption on the underlying signature scheme.

$$ \mathbf{Y}\in\mathbb{G}^{k} $$

$$ t\in{0,1}^{\kappa} $$

$$ \mathcal{A} $$

$$ O\big(2^{\kappa}\cdot\mathsf{p o l y}(\lambda)\big) $$

$$ \ \kappa kappa=0 $$

B.2 Secure Signatures with Linear Verification

The first attack we describe in Theorem 2 for algebraic signature schemes with linear verification only holds if the equation tested by the verifier is of the form

$$ A(\mathbf{z},m)\mathbf{X}=B(m)\mathbf{Y} $$

with the entries A(z*;m*) being polynomials of degree one in z, and B(m) being independent from z.

$$ A(\mathbf{z},m) $$

$$ \mathbf{Z{,} $$

$$ B(m) $$

In this section we show that secure signatures with exponential message space and linear verification which do not satisfy at least one of these two hypotheses exist. To get these results we only assume the existence of a secure signature schemes (S*:* Setup*;* S*:* Sign*;* S*:* Vfy) in the plain model with exponential message space, e.g. stateless constructions form trapdoor claw-free permutations [GMR88, Gol87].

First we propose a scheme where in the verification equation A(z*;m*) depends quadratically from z. The high-level idea is to observe that the satisfiability of a circuit (in this case S*:* Vfy(vk*;m;)) can be checked by testing whether a system of equations of degree at most 2 admits solutions. In this way, using the transformation sketched in Section A.3 we can compile C = S:* Vfy(vk*;m;) to an k R1CS instance M₁;M₂;M₃;b such that, from any witness 2f0; 1g* satisfying C() = 1, a vector w can be computed so that

$$ A(\mathbf{z},m) $$

$$ \mathsf{S}V.\mathsf{f y}(\mathsf{v k},m,,\cdot,) $$

$$ \ \ C=mathsf S\mathsf{V/y}(\mathsf{v k},m,,\cdot) $$

$$ M_{1},M_{2},M_{3} $$

$$ \sigma\in{0,1}^{k} $$

$$ C(\sigma)=1 $$

$$ M_{1}\mathrm{w}*M_{2}\mathrm{w}=M_{3}\mathrm{w}+\mathrm{b} $$

where is the entry-wise multiplication of two vectors with the same length. Moreover we recall that given any vector w satisfying the above system of k quadratic equations, a string 2f0*;* 1g such that C() = 1 can be computed efficiently.

$$ \sigma\in{0,1}^{k} $$

$$ {mathcal C(\sigma)}=1 $$

A detailed description of the resulting scheme is presented in Figure 6

Proposition 5. If (S*:* Setup*;* S*:* Sign*;* S*:* Vfy) is a UF-CMA secure signature, so is the scheme described in Figure 6.

Proof. First of all correctness comes from the underlying scheme and the properties of the reduction between circuit satisfiability and rank one constraint sys- $ tems. Indeed, for any m 2 S*:* M, S*:* Sign(sk*;m*) implies S*:* Vfy(vk*;m;)!* 1. Hence is a witness for that circuit, implying that M₁w M₂w = M₃w + b. Thus S₁*:* Vfy(vk*;m;* w) accepts.

$$ m\in\mathsf{S}.\mathsf{M},\sigma\leftarrow^{\vartheta}\mathsf{S}.\mathsf{S i g n}(\mathsf{s}\mathsf{k},m) $$

$$ \mathsf{S}V f y(\mathsf{v k},m,\sigma)\to1 $$

$$ M_{1}\mathrm{w}*M_{2}\mathrm{w}=M_{3}\mathrm{w}+\mathrm{b} $$

$$ \mathsf{S}_{1}.\mathsf{V f y}(\mathsf{v k},m,\mathsf{w}) $$

Next, if A is a PPT adversary for the scheme in Figure 6, we describe an adversary B for the underlying signature. Upon receiving vk, B forwards vk to A. Each time A queries a signature for m, B forwards the request to its

S₁: Setup(1) S₁: Sign(sk;m) $ $ 1 : vk*;sk S:* Setup(1) 1 : S*:* Sign(sk*;m*) 2 : Return vk*;sk 2 : Compile S:* Vfy(vk*;m;);* to M₁;M₂;M₃; b*;* w 3 : Return w S₁: Vfy(vk;m;) 1 : Compile S*:* Vfy(vk*;m;*) to M₁;M₂;M₃; b 2 : Return 1 if (M₁w M₂w M₃w b) G = 0

$$ \left(M_{1}\mathrm{w}\ M_{2}\mathrm{w}-M_{3}\mathrm{w}-\mathrm{b}\right)\cdot\hat{\mathcal G}=0 $$

Fig. 6. Algebraic signature scheme with linear verification

signing oracle, getting. Later, it compiles S*:* Vfy(vk*;m;);* to M₁;M₂;M₃; b*;* w and returns w. Finally, when A outputs m; w, B compiles S*:* Vfy(vk*;m;*) to *M₁;M₂;M₃;*b and check if M₁w M₂w = M₃w + b. If that is the case it recover a witness for that circuit from w and returns (m;).

$$ \mathsf{S}V.\mathsf{f y}(\mathsf{v k},m,\cdot),\sigma $$

$$ M_{1},M_{2},M_{3}, $$

$$ \mathsf{S}V.\mathsf{f y}(\mathsf{v k},m,\cdot) $$

$$ M_{1},M_{2},M_{3} $$

$$ M_{1}\mathrm{w}!*!M_{2}\mathrm{w}=M_{3}\mathrm{w}!+!\mathrm{b} $$

$$ (m,\sigma) $$

Clearly B perfectly simulates S₁*:* Sign(sk*;*) as it performs the same steps and, when A successfully return a valid forgery (m; w), the couple (m;) is a forgery for B since:

$$ \mathsf{S}_{1}.\mathsf{S i g n}(\mathsf{s k},\cdot,) $$

– B queries the same messages queried by A, thus m was not queried by both.

– By the property of the reduction from circuit satisfiability to rank one constraints system, M₁w M₂w = M₃w + b implies that S*:* Vfy(vk*;m;)!* 1.

$$ M_{1}\mathrm{w}*M_{2}\mathrm{w}=M_{3}\mathrm{w}+\mathrm{b} $$

$$ {\mathsf{S}}.{\mathsf{V f y}}(\mathsf{v k},m,\sigma)\to1 $$

Thus Adv(A) = Adv(B).

$$ \mathsf{A d v}(\mathcal{A})=\mathsf{A d v}(\mathcal{B}) $$

Next we sketch a scheme where the verification equation is of the form A(z*;m*)X = B(z*;m*)Y, where both A(z*;m*) and B(z*;m*) have an affine dependence on z (i.e. each of their entries is a polynomial of degree at most one in z). The idea is identical to the previous construction with the exception that now the terms of degree 2 have to come from B(z*;m*)Y. To do this, having compiled for a given signed message (m;) the circuit S*:* Vfy(vk*;m;);* into M₁;M₂;M₃; b*;w, the signer simply set Y = w G and returns (Y;*w). The verifier then locally checks

$$ A(\mathbf{z},m)\mathbf{X},=,B(\mathbf{z},m)\mathbf{Y} $$

$$ A(\mathbf{z},m) $$

$$ B(\mathbf{z},m) $$

$$ B(\mathbf{z},m)\mathbf{Y} $$

$$ (m,\sigma) $$

$$ \mathsf{S}V.\mathsf{f y}(\mathsf{v k},m,\cdot,),\sigma $$

$$ M_{1},M_{2},M_{3},\mathbf{b}w $$

$$ \mathbf{Y},=,\mathbf{w}\cdot G $$

$$ \mathbf{Y}=\mathbf{w}\cdot G,\qquad(M_{3}\mathbf{w}+\mathbf{b})\cdot G=M_{1}\mathbf{w}\ M_{2}\mathbf{Y}. $$

To see why the equation on the right hand side can be expressed in the form m m B(z*;m*) observe that the map f_z: G*!* G ^mapping Y 7! M₁z M₂Y is linear and depends linearly on z. Moreover, if both checks are satisfied, then

$$ f_{\mathbf{z}}:\mathbb{G}^{m},\rightarrow,\mathbb{G}^{m} $$

$$ \mathbf{Y}\mapsto M_{1}\mathbf{z}*M_{2}\mathbf{Y} $$

$$ B(\mathbf{z},m) $$

$$ \mathbf {Y} = \mathbf {w} \cdot G \quad \Rightarrow \quad \left(M _ {3} \mathbf {w} + \mathbf {b}\right) \cdot G = \left(M _ {1} \mathbf {w} * M _ {2} \mathbf {w}\right) \cdot G $$

which immediately yields that w is a solution for the given R1CS.

B.3 Succinct Vector Commitments with Linear Verification

In Section B.2 we showed how dropping the assumption of strict linear verification in algebraic signatures implies the existence of secure constructions under mild assumptions. Because of this, there is no hope to obtain lower bounds for algebraic VCs from analogous results on signatures when the verification procedure is linear but not strictly. In this section we prove that this is the case because, when either A(z*;m;i*) is allowed to depend quadratically or B(z*;m;i*) affinely on z*;m*, there exist succinct VCs.

$$ B(\mathbf{z},m,i) $$

$$ A(\mathbf{z},m,i) $$

Given a (not necessarily algebraic) position binding and succinct VC (VC*:* Setup; VC*:* Com*;VC:* Open*;VC:* Vfy) such that F_qVC*:* M, the key idea as before is to exploit the quadratic terms in the verification equations to encode arbitrary circuits, in this case C(;) = VC*:* Vfy(pp*;c;;i;) which takes in input a message m and an opening proof. More specifically, the new setup algorithm simply forwards the CRS produced by VC:* Setup. Analogously a commitment to (m₁;:::;m_n) can simply be set as the commitment c returned by VC*:* Com. In order to open to a message m we can compute an opening through VC*:* Open, compile VC*:* Vfy(pp*;c;;i;);m;* to a R1CS M₁;M₂;M₃;w where w₁ = m, and return w. Finally, the verification algorithm simply compiles VC: Vfy(pp*;c;;i;) to the same R1CS M₁;M₂;M₃ and, on input m;w;i verifies the following conditions: (M₁w M₂w M₃w) G = 0;* (w₁ m) G = 0*:*

$$ \mathbb{F}_{q},\subseteq,\mathsf{V C}.\mathsf{M} $$

$$ \mathcal{C}(\cdot,cdot)=\mathsf{V C.V f y}(\mathsf{p p},c,\cdot,i,\cdot) $$

$$ (m_{1},\ldots,m_{n}) $$

$$ \mathsf{V C.V f y}p(\mathsf{p p},c,\cdot,,i,\cdot\ ),m,\pi $$

$$ M_{1},M_{2},M_{3} $$

$$ w_{1}=m. $$

$$ \mathsf{V C.V f y}(\mathsf{p p},c,,\cdot,i,\cdot,) $$

$$ M_{1},M_{2},M_{3} $$

$$ (M_{1}{\bf w}*M_{2}{\bf w}-M_{3}{\bf w})\cdot G={\bf0},\qquad(w_{1}-m)\cdot G=0. $$

where the last test ensure that the first input of the circuit is precisely the message m. A more detailed construction appears in Figure. 7

VC : Setup(1) VC : Com(pp;m₁;:::;mn) $ 1 : ppS*:* Setup(1) 1 : c; aux VC*:* Com(pp*;m₁;:::;mn*) 2 : Return pp 2 : Return (c; auxjjc) VC : Open(pp*;m;i;* auxjjc) 1 : VC*:* Open(pp*;m;i;* aux) 2 : Compile VC*:* Vfy(pp*;c;;i;);* (m;) to M₁;M₂;M₃; w 3 : Return w VC : Vfy(pp;c;m;i; w) 1 : Compile VC*:* Vfy(pp*;c;;i;*) to M₁;M₂;M₃. 2 : Accept if the following conditions are satisfied: 3 : (M₁w M₂w M₃w) G = 0 4 : (m w₁) G = 0

$$ \ _.\mathsf{V f y}(\mathsf{p p},c,\thinspace\cdot,i,\thinspace\cdot\thinspace) $$

$$ \left(M_{1}\mathtt{w}*M_{2}\mathtt{w}-M_{3}\mathtt{w}\right)\cdot G=0 $$

Fig. 7. Algebraic VC scheme with linear verification

Proposition 6. The VC scheme described in Figure 7 is algebraic with linear verification. Furthermore if (VC*:* Setup*;VC:* Com*;VC:* Open*;VC:* Vfy) satisfy posi- tion binding, so does this construction.

Proof. The first part is immediate as B can be simply set to be the zero matrix while A(w;m;i; (ppjjc)) = (M₁w M₂w M₃w) jj(m w₁)

$$ A(\mathbf{w},m,i,\left(\mathbf{p}\mathbf{p}|c\right))\ =\ \left(M_{1}\mathbf{w}*M_{2}\mathbf{w}-M_{3}\mathbf{w}\right)|(m-w_{1}) $$

depends quadratically on w and m, and arbitrarily on ppjjc and i which are hard-coded into the circuit that is later compiled to the R1CS M₁;M₂;M₃.

$$ m $$

$$ M_{1},M_{2},M_{3} $$

To prove that the resulting scheme is secure let A(pp) be a PPT adversary breaking positing binding. Then we can describe an adversary B that breaks the position binding property of the underlying VC. To do so, B(pp) runs A on input pp and waits for it to return (c;m;m⁰;i;w;w⁰) with m 6= m⁰. Then it checks whether (m; w) and (m⁰;w⁰) are both correct openings for position i, i.e. such that, calling M₁;M₂;M₃ matrices representing the R1CS obtained from the circuit C = VC: Vfy(pp;c;;i;), they satisfy

$$ {mathrm s o},,{\mathcal{B}}({\mathfrak{p p}}) $$

$$ (c,m,m^{\prime},i,\mathbf{w},\mathbf{w}^{\prime}) $$

$$ (m,\mathbf{w}) $$

$$ (m^{\prime},\mathrm{w}^{\prime}) $$

$$ m\neq m^{\prime} $$

$$ M_{1},M_{2},M_{3} $$

$$ i, $$

$$ \mathcal{C}=\mathsf{V C.V f y}(\mathsf{p p},c,\cdot,i,\cdot $$

$$ M_{1}\mathbf{w}*M_{2}\mathbf{w}=M_{3}\mathbf{w}\qquad M_{1}\mathbf{w}^{\prime}*M_{2}\mathbf{w}^{\prime}=M_{3}\mathbf{w}^{\prime}. $$

0 and m = w₁, m⁰ = w₁. If this is the case it finally extracts, as detailed in Section A.3, two inputs (*m;e e) and (me⁰;*e⁰) that make the circuit C evaluate to 1, i.e. such that

$$ m,=,w_{1},,m^{\prime},=,w_{1}^{\prime} $$

$$ (\widetilde{m},\widetilde{\pi}) $$

$$ (\widetilde{m}^{\prime},\widetilde{\pi}^{\prime}) $$

$$ \mathsf{V C.V f y}(\mathsf{p p},c,\widetilde{m},i,\widetilde{\pi})\to\ 1\qquad\mathsf{V C.V f y}(\mathsf{p p},c,\widetilde{m}^{\prime},i,\widetilde{\pi}^{\prime})\to1. $$

and returns (*c; m;e me⁰;i;;*e e⁰). Note that, since the extraction of an input that makes C return 1 from a solution to the related R1CS is performed by taking the 0 first t elements, where t is the arity of C, then me = w₁ = m and me⁰ = w₁ = m⁰ implying that me 6= me⁰. This concludes the argument.

$$ (c,\widetilde{m},\widetilde{m}^{\prime},i,\widetilde{\pi},\widetilde{\pi}^{\prime}) $$

$$ \widetilde{m}=w_{1}=m $$

$$ \widetilde{m}^{\prime}=w_{1}^{\prime}=m^{\prime} $$

$$ \tilde{m}\neq\tilde{m}^{\prime} $$

Although the construction in Figure 7 provides us a way to construct algebraic vector commitments with linear verification from any VC in the standard model, it is yet not enough to show that our lower bounds may not be extended to this case. Indeed, the reduction preserves the commitment length of the underlying VC but not the opening proof size. Indeed, as mentioned in Section A.3, the length of w equals the number of gates in the circuit from which we built the R1CS instance. This means that even though the underlying VC has short opening proof, if the verifier performs a significant number of operations which depends on n, the resulting scheme may not be succinct.

Thus, in order to show that this construction leads to VCs with constant size commitment and opening proof length, we need to provide a (non necessarily algebraic) scheme in which the circuit VC*:* Vfy(pp*;c;;i;) has a constant number of gates. One such example is the pairing based construction provided in [CF13] whose security is equivalent to CDH. More specifically in that case, given a pairing e : G G!* G_Tand a generator G 2 G the setup produces the following $ CRS for uniformly random z_iF_q

$$ \mathrm {V C}. \mathrm {V f y} (\mathrm {p p}, c, \cdot , i, \cdot) $$

$$ e:\mathbb{G}\times\mathbb{G}\to\mathbb{G}_{T} $$

$$ G\in\mathbb{G} $$

$$ z_{i}\leftarrow^{\Re}\mathbb{F}_{q} $$

$$ \forall i\in{1,\ldots,n}\quad H_{i}\leftarrow z_{i}\cdot G,\qquad\forall i,j\in{1,\ldots,n},\ i\neq j\quad H_{i,j}\leftarrow z_{i}z_{j}\cdot G. $$

Next a commitment to m₁;:::;m_nis defined as K = m₁H₁ +:::+ m_nH_nwhile an opening proof for position i is computed as X X

$$ m_{1},\ldots,m_{n} $$

$$ K=m_{1}H_{1}
$$

$$ \varLambda_{i}\leftarrow\sum_{j\neq i}m_{i}H_{i,j};=;z_{i}\sum_{j\neq i}m_{i}H_{i}. $$

Finally, the verification algorithm on input (pp*;K;m;i;*) recovers from the public parameter the group element H_iand checks that

$$ (\mathsf{p p},K,m,i,\varLambda) $$

$$ H_{i} $$

$$ e\big(K-m_{i}H_{i}\big),=,e\ \ (\varLambda_{i},G). $$

Observe that in the circuit we want to compile to a R1CS, pp and i are hardcoded constants, so is H_i, meaning that the circuit does not have to read the whole pp to recover it. Finally we have that in this case VC*:* Vfy(pp*;K;;i;) as an arithmetic circuit requires only one exponentiation m_iH_i, one inversion/addition over G to compute K m_iH_i, two pairings and one equality check over G_T. Since the number of gates required to express these operations as circuits only depends on, and we only need a constant number of them, we conclude that with respect to n the circuit VC:* Vfy(pp*;K;;i;*) can be expressed with a constant number of gates. The following proposition follows

$$ H_{i}. $$

$$ \mathsf{V C.V f y}p(\mathsf{p p},K,\cdot,,i,\cdot,) $$

$$ m_{i}\cdot H_{i}. $$

$$ \mathbb{G} $$

$$ K!-!m_{i}H_{i} $$

$$ \mathbb{G}_{T} $$

$$ \lambda, $$

$$ \mathsf{V C.V f y}p(\mathsf{p p},K,,\cdot,i,\cdot,) $$

Proposition 7. Given a symmetric pairing e : G G*!* G_Tsuch that CDH is hard in G*, then there exists an algebraic VC with linear verification such that* A(z*;m;i*) depends quadratically in z*;m, B*(i) does not depends on z*;m and,* calling ‘_c;‘ respectively the commitment and opening proof bit length, ‘_c;‘ = O (1).

$$ e:\mathbb{G}\times\mathbb{G}\to\mathbb{G}_{T} $$

$$ \mathbb{G} $$

$$ A(\mathbf{z},m,i) $$

$$ \mathbf{z},m,\ B(i) $$

$$ \mathbf{z},m $$

$$ \ell_{c},\ell_{\pi} $$

$$ \ell_{c},\ell_{\pi}= $$

$$ O_{\lambda}(1) $$

We finally informally remark that the same construction can be repeated if we let A(z*;m;i*) and B(z*;m;i*) both depend affinely on z*;m*.

$$ A(\mathbf{z},m,i) $$

$$ B(\mathbf{z},m,i) $$

B.4 Tightness of Algebraic VC Lower Bounds

We now show the tightness of the asymptotic lower bound ‘_c‘ = (n) proved in Corollary 1 for an algebraic VC with strictly linear verification, where n is the length of the vector, ‘_cthe commitment bit-length and ‘ the opening proof bit length. To this end, calling ‘_Gthe bit length of a group element representation, we describe a family of schemes parameterized by = (n) n where ‘_c= ‘_G and ‘ = ‘_Gwith n

$$ \ell_{c}\cdot\ell_{\pi}=\varOmega(n) $$

$$ \ell_{c} $$

$$ \ell_{\pi} $$

$$ \ell_{\mathrm{{G}}} $$

$$ \alpha=\alpha(n)\leq n $$

$$ \ell_{c}={\boldsymbol{\alpha}}{\cdot}\ell_{\mathbb{G}} $$

$$ \ell_{\pi}=\beta\cdot\ell_{\mathbb{G}} $$

$$ \beta (n) = \left\lceil \frac {n}{\alpha (n)} \right\rceil . $$

Since ‘_Gis polynomially bounded in but independent from n we have that asymptotically ‘_c‘ = (n) as

$$ \ell_{\mathrm{{G}}} $$

$$ \lambda $$

$$ \ell_ {c} \cdot \ell_ {\pi} = \Theta (n) $$

$$ \begin{array}{l} \frac {n}{\alpha (n)} \leq \beta (n) \leq \frac {n}{\alpha (n)} + 1 \Rightarrow n \leq \alpha (n) \beta (n) \leq n + \alpha (n) \leq 2 n \ \Rightarrow \quad \ell_ {\mathbb {G}} ^ {2} \cdot n \leq \ell_ {c} \cdot \ell_ {\pi} \leq 2 \ell_ {\mathbb {G}} ^ {2} \cdot n. \ \end{array} $$

In particular this family of schemes achieves our asymptotic bound. The high level idea, assuming for the moment that (n) divides n, is to perform the commitment to a vector of n message m₁;:::;m_nby dividing them into smaller vectors of entries each, and perform a regular (non-hiding) Pedersen commitment to each sub-vector. To open a position i we simply open the entire sub-vector containing the desired message, resulting in an opening proof of field elements.

$$ \alpha(n) $$

$$ n, $$

$$ m_{1},\ldots,m_{n} $$

$$ \beta $$

$$ \beta $$

As a final note, we remark that the security of a Pedersen commitment reduces to the hardness of the DLP in the underlying group. Thus this scheme would also be secure for the class of unbounded adversaries which perform at most a polynomial number of generic operations. In particular we conclude that even against this class of adversaries our lower bound in Corollary 1 is tight.

VC: Setup(1;n) VC: Com(pp;m₁;:::;mn) 1 :$ 1 : d n=e; H₁;:::;H G 2 : pp (H₁;:::;H) 2 : (mn+1*;:::;m*) (0*;:::;* 0) 3 : Return pp 3 : For k 2f0*;:::;* 1g: P 4 : ck j₌₁m_j+kHj 1 5 : c (ck); aux (mi) k=0 _i=1 6 : Return c; aux VC: Open(pp;m;i; aux) 1 : Write i = j + k with j 2f0*;:::;* 1g and k 2f1*;:::;g* 2 : (m1+k;:::;m_(k+1)). Return VC: Vfy(pp;c;m;i;) 1 : Write i = j + k with j 2f1*;:::;g* and k 2f0*;:::;* 1g 2 : Parse = (m⁰1*;:::;m⁰*), c = (c₀;:::;c1) and pp = (Hj)_j=1 P0j 0j 3 : If c_k=_j=1m H_j and m = m : 4 : Return 1 5 : Else: Return 0

$$ k\in{0,\ldots,\beta-1}; $$

$$ j\in{1,\ldots,\alpha} $$

$$ k\in{0,\ldots,\beta-1} $$

Fig. 8. Vector commitment over a prime order group, parameterized by

Proposition 8. The vector commitment in Figure 8 is algebraic with strictly linear verification. Moreover if the DLP problem is hard in G*, it satisfies position* binding.

Proof. To show the first part of the proof we have to provide matrices A, B that characterize the verification algorithm. Since Y is not provided, B can only be the zero matrix, which is indeed independent from the field elements in the opening proof. Conversely, calling X₁ = (G;H₁;:::;H), X₂ = (c₀;:::;c₁), = (m⁰₁;:::;m⁰), i = j + k, the matrix A(;m;i) is

$$ \mathbf{X}{1}\ {=}\ (G,H{1},\ldots,H_{\alpha}),;\mathbf{X}{2}\ {=}\ (c{0},\ldots,c_{\beta-1}) $$

$$ \pi=\left(m_{1}^{\prime},\ldots,m_{\alpha}^{\prime}\right),,i=j+k^{*}\alpha $$

$$ A(\pi,m,i) $$

$$ A = \left[ \begin{array}{c c c c c c c} m - m _ {1} ^ {\prime} & 0 & \dots & 0 & 0 & \dots & 0 \ 0 & m _ {1} ^ {\prime} & \dots & m _ {\alpha} ^ {\prime} & 0 & \dots & - 1 & \dots \end{array} \right] $$

where 1 is in the (1 + + k)-th column. Notice each entry is a polynomial of 0i degree at most 1 in m and m.

$$ (1+\alpha+k) $$

$$ m_{i}^{\prime} $$

0i Regarding position binding, given an adversary A which returns (c; mb_i; mb*;i*ⁱ;_i0) ⁰ⁱ with m_i6= m, we can trivially transform this into an adversary B breaking the binding property of Pedersen commitment. Having decomposed i = j + k for j 2f1*;:::;g*, k 2f0*;:::;* 1g, and parsed

$$ m_{i}\neq m_{i}^{\prime} $$

$$ \left(c,\widehat{m}{i},\widehat{m}{i}^{\prime},i\pi_{i},\pi_{i}^{\prime}\right) $$

$$ i=j+\alpha k $$

$$ j \in {1, \dots , \alpha }, k \in {0, \dots , \beta - 1 } $$

$$ c=(c_{0},\ldots,c_{\beta-1}),\qquad\pi_{i}=(m_{1},\ldots,m_{\alpha}),\qquad\pi_{i}^{\prime}=(m_{1}^{\prime},\ldots,m_{\alpha}^{\prime}) $$

B returns (c_k; (m₁;:::;m); (m⁰₁;:::;m⁰)). If A succeeds in returning two valid openings for different messages, then B succeed as well. Indeed since m_k= 0i 0k mbi6= mb = m, the two vectors are distinct and, as both openings are val_id, P P ^j₌₁m_jH_j= c_k=_j=1m⁰_jH_j. This concludes the proof as (generalized) Pedersen commitments are binding if the DLP is hard.

$$ \left(c_{k},(m_{1},\ldots,m_{\alpha}),(m_{1}^{\prime},\ldots,m_{\alpha}^{\prime})\right) $$

$$ m_{k} $$

$$ \hat {m} _ {i} \neq \hat {m} _ {i} ^ {\prime} = m _ {k} ^ {\prime} $$

$$ \sum_ {j = 1} ^ {\alpha} m _ {j} \cdot H _ {j} = c _ {k} = \sum_ {j = 1} ^ {\alpha} m _ {j} ^ {\prime} \cdot H _ {j} $$

B.5 Tightness of Algebraic Signatures Lower Bounds

As done for the impossibility results of algebraic vector commitments, we show that our lower bounds for algebraic signatures with strictly linear/general verification (Theorems 6 and 7) cannot be improved. We do so by providing for each n a family of UF-CMA secure signatures whose verification key contains n group elements and the message space has cardinality n. The idea is simply to set vk = (x₁ G;:::;x_nG) and, in order to sign the message i 2f1*;:::;ng* the signer returns x_i. In this way producing a forgery reduces to breaking the discrete logarithm of at least one group element in the verification key, implying intuitively that the scheme is secure.

$$ {\mathsf{v k}}=\left(x_{1}\cdot G,\ldots,x_{n}\cdot G\right) $$

$$ i\in{1,\ldots,n} $$

$$ x_{i} $$

Proposition 9. The scheme in figure 9 is algebraic with strictly linear verifica- tion. Moreover, if the DLP is hard in G*, it is UF-CMA secure.*

Proof. The strictly linear property of verification follows trivially by setting X = (G;H₁;:::;H_n), A(;m)=(; 0*;:::;1;:::;* 0) with 1 being in the m + 1-th position, and B(m) as the zero matrix.

$$ \mathbf{X}= $$

$$ (G,H_{1},\ldots,H_{n}),;A(\sigma,m):=:(-\sigma,0,\ldots,1,\ldots,0) $$

$$ B(m) $$

To prove security, we reduce any adversary A executed in game 2 to an adversary B which solves the DLP. Given a random H U(G), B samples an index j 2f1*;:::;ng* which is a guess on the message that A will chose for his $ forgery, and set H_j= H and H_i= x_iG for all other i by sampling x_iF_q. If A queries j B aborts. If it queries i 6= j, send A x_i. Finally when A returns (m;), abort if m 6= j, otherwise return.

$$ j\in{1,\ldots,n} $$

$$ H\sim U(\mathbb{G}) $$

$$ H_{j}=H $$

$$ H_{i}=x_{i}\cdot G $$

$$ x_{i}\leftarrow^{\S}\mathbb{F}_{q} $$

$$ \mathcal{A}\gets x_{i} $$

$$ i\neq j $$

$$ (m,\sigma) $$

$$ m\neq j $$

$$ \sigma $$

Since A has no information on j the probability it will attempt to forge that message is 1*=n*. Moreover if A returns a correct signature, then H = H_j= G, meaning that B correctly solved the DLP. Hence Adv(A) = n Adv(B) that is negligible.

$$ 1/n $$

$$ H=H_{j}={\boldsymbol{\sigma}}{\boldsymbol{\cdot}}{\boldsymbol{G}} $$

$$ \mathsf{A d v}(\mathcal{A})=n\cdot\mathsf{A d v}(\mathcal{B}) $$

S*:* Setup(1): 1 :$ Sample x₁;:::;xn Fq and compute Hi xi G 2 : sk (x₁;:::;xn); vk (H₁;:::;Hn). Return (sk*;vk) S:* Sign(sk*;m*): 1 : Parse sk = (x₁;:::;xn). Return xm S*:* Vfy(vk*;m;*): 1 : Parse vk = (H₁;:::;Hn). Return Hm == G

$$ H_{m}==\sigma\cdot G $$

Fig. 9. Secure algebraic signature scheme with strictly linear verification and message space S*:* M = f1*;:::;ng*.

C Postponed Proofs

C.1 Generic Transformation to Signatures

$$ {\mathsf{S}}.{\mathsf{M}}={1,\ldots,n} $$

Proof of Theorem 1. Given an adversary A breaking #-UF for this signature scheme, we provide a PPT algorithm R that breaks the underlying VC’s position binding using A in a black-box way. For notational convenience let us denote Q = f(i_j;m_j;_j)g_j2Jthe set of all queries recorded in the experiment 2 and S = fi_jg_j2Jthe set of queried positions.

$$ Q={(i_{j},m_{j},\pi_{j})}_{j\in J} $$

$$ \boldsymbol{S}=\left{\dot{i_{j}}\right}_{j\in}\boldsymbol{J}} $$

$$ m _ {1}, \dots , m _ {n} \leftarrow^ {$} $$

Adversary R(pp): $ $ 1 : Samples random m₁;:::;mn VC*:* M and get c; aux VC*:* Com(pp*;m₁;:::;mn*) 2 : Set vk (pp*;c*), S? and send A vk 3 : When A queries j 2f1*;:::;ng*: $ 4 : Compute the opening VC*:* Open(pp*;mj;j;* aux) and set (mj;) 5 : Update S S [fjg and send A 6 : When A returns a set F : 7 : If 9(i;) 2 F : i 62 S ^ = (m; b b) ^ mb 6= mi: 8 : Compute VC*:* Open(pp*;mi;i;* aux) and return (c;m; m;i;; b b) 9 : Else: Return*?* Fig. 10. #-Unforgeability Experiment for a given signature scheme

$$ j\in{1,\ldots,n} $$

As a first step we argue that with overwhelming probability, if A produces more than # forgeries, then at least one them contains an opening to a message that differs from the committed one.

Claim 1 Calling F = f(i; mb_i; b_i)g_i2I, if jIj #(vk*;Q*) and I \ S = ? then calling bad the event mb_i= m_i; 8i 2 I we have Pr [bad] 2

$$ I\cap S,=,\emptyset $$

$$ F = \left{\left(i, \widehat {m} _ {i}, \widehat {\pi} _ {i}\right) \right} _ {i \in I}, i f | I | \geq \vartheta (\mathrm {v k}, Q) $$

$$ \widehat{m}{i}=m{i},,\forall i\in I $$

$$ \operatorname*{P r}\left[{\ \ {sf b b a d}}\right]\leq2^{-\lambda} $$

Proof of Claim 1. fm_ig_i2Iare uniformly distributed and independent from fm_ig_i2S and pp, but may not be independent from c and f_jg_j2J. Notice that, by the ‘c +jJ j‘ way we defined ‘_cand ‘, we have that (c; f_jg_j2J) is a string in f0*;* 1g and therefore by Proposition 3

$$ \ .\ {m_{i}}_{i\in I} $$

$$ {m_{i}}_{i\in S} $$

$$ {\pi_{j}}_{j\in J} $$

$$ \ell_{c} $$

$$ \ell_{\pi} $$

$$ \left(\ ,mathcal{C},\big{\pi_{j}\big}_{j\in J}\right) $$

$$ {0,1}^{\ell_{c}+|J|\ell_{7tau}} $$

$$ \begin{array}{l} \mathrm {H} _ {\infty} \left(\left{m _ {i} \right} _ {i \in I} \mid c, \left{\pi_ {j} \right} _ {j \in J}\right) \geq \mathrm {H} _ {\infty} \left(\left{m _ {i} \right} _ {i \in I}\right) - \log \left| \left{0, 1 \right} ^ {\ell_ {c} + | J | \ell_ {\pi}} \right| \ = | I | \cdot \log | V C. M | - \ell_ {c} + | Q | \ell_ {\pi} \ \geq \vartheta (\mathrm {v k}, Q) \cdot \log | V C. M | - \ell_ {c} + | Q | \ell_ {\pi} \ = \lambda \ \end{array} $$

Therefore the probability of correctly guessing fm_ig_i2Igiven c and f_jg_j2Jis smaller than 2.

$$ {m_{i}}_{i\in I} $$

$$ {\pi_{j}}_{j\in J} $$

$$ 2^{-\lambda} $$

To conclude the Theorem’s proof, if A would win in game 2 then all the forgeries returned are correct signatures of non-queried messages. In particular if bad does not occur, among the forgeries returned by A, R will find mb_i6= m_i and b_isuch that

$$ \hat{m}{i}\neq m{i} $$

$$ \widehat{\pi}_{i} $$

$$ \mathsf{V C.V f y}(\mathsf{p p},c,m_{i},i,\pi)\to1\qquad\mathsf{V C.V f y}(\mathsf{p p},c,\widehat{m}{i},i,\widehat{\pi}{i})\to1. $$

which breaks the position binding. Therefore Adv(A) Adv(R) + 2 which is negligible.

$$ \mathsf{A d v}(A)\leq\mathsf{A d v}(\mathcal{R})+2^{-\lambda} $$

C.2 Attack to Schemes with Strictly Linear Verification

Proof of Theorem 3. Having provided in the main body of the paper a detailed description of the adversary A, below we prove through a sequence of claims that A indeed breaks the given signature scheme.

Claim 1 If L is an affine space, S(L;m) is an affine space. Moreover an affine base for S(L;m) can be computed in polynomial time.

$$ S(L,m) $$

$$ S(L,m) $$

Claim 2 Let x be the discrete log of X*, i.e.* X = x G. Then at any step x 2 L.

$$ \mathbf{X}=\mathbf{x}\cdot G $$

$$ \mathbf{x}\in L $$

Claim 3 A runs in polynomial time and does not abort with significant proba- bility greater than ().

Claim 4 If for a given m_ithe condition at step 7 is not satisfied, i.e. S(L;m_i) = ?, then after step 13 the dimension of L decreases strictly.

$$ m_{i} $$

$$ i.e.;S(L,m_{i})= $$

Claim 5 After step 3, dimL = n + 1*. Moreover up to negligible probability* "(), when A halts dim L > n₁ + 1*.*

$$ L=n-\nu+1 $$

$$ \varepsilon(\lambda) $$

$$ L>n_{1}-\nu+1 $$

Before proving the claims we observe that combining Claim 5 and 4, up to negligible probability, the condition on step 7 is not satisfied at most n₂ times. Thus for n₂ = # messages the above condition is satisfied and, by Claim 3, A successfully finds # forgeries (Y*;*z). Again by Claim 3, we conclude that A succeeds with probability larger than () "().

$$ n_{2} $$

$$ \theta-n_{2}=\vartheta $$

$$ (\mathbf{Y},\mathbf{z}) $$

$$ \eta(\lambda)-\varepsilon(\lambda) $$

Next, we provide a proof for each of these claims:

Proof of Claim 1. We start observing that if L is any set and x₁*;:::;xd2 L* is Td a base for the linear span of L then S(L;m) =_i=1S(x_i;m). By construction, d x_i2 L implies S(L;m) S(x_i;m), and in particular S(L;m) *_i=1S(x_i;m*). Conversely let z be a vector in the intersection of all S(x_i;m). We can find k vectors u_i2 F_qsuch that A(z*;m*)x_i= B(m)u_i. Since x₁*;:::;*x_dis a base for the linear span of L, for any x 2 L we can express it as a linear combination 1x₁ + ::: +dxd. In conclusion

$$ \mathbf{x}{1},\ldots,\mathbf{x}{d}\in L $$

$$ S(L,m)=\bigcap_{i=1}^{d}S(\mathtt x_{i},m) $$

$$ \mathbf{x}_{i}\in L $$

$$ S(L,m)\subseteq S(\mathbf{x}_{i},m) $$

$$ S(L,m)\subseteq\cap_{i=1}^{d}S(\mathtt{x}_{i},m) $$

$$ \mathbf{u}{i}\in\mathbb{F}{q}^{k} $$

$$ \mathcal{S}(\mathbf{x}_{i},m) $$

$$ A(\mathbf{z},m)\mathbf{x}{i}=B(m)\mathbf{u}{i} $$

$$ \mathbf{x}{1},\ldots,\mathbf{x}{d} $$

$$ \mathbf{x}\in L $$

$$ \alpha_{1}\mathtt{x}{1}+\ldots+\alpha{d}\mathtt{x}_{d} $$

$$ A(\mathbf{z},m)\mathbf{x};=;\sum_{i=1}^{d}\alpha_{i}A(\mathbf{z},m)\mathbf{x}{i};=;\sum{i=1}^{d}\alpha_{i}B(m)\mathbf{u}{i};=;B(m)\sum{i=1}^{d}\alpha_{i}\mathbf{u}_{i}. $$

Thus A(z*;m*)x 2 ImB(m) and in particular z 2 S(L;m).

$$ A(\mathbf{z},m)\mathbf{x}\in\operatorname{I m}B(m) $$

$$ \mathbf{z}\in S(L,m) $$

In order to show that S(L;m) is efficiently computable it suffices to show that S(x*;m*) can be computed in polynomial time for any point x. To this aim let h ‘q f_x: F_q! F be such that f(z) = A(z*;m*)x. Since the scheme has strictly linear verification (Definition 8) A(;m) is an affine map and so is f. Furthermore by construction S(x*;m*) = f_{x 1}(ImB(m)) since z 2 S(x*;m*) if and only if A(z*;m*)x 2 ImB(m). This concludes the argument as the preimage through an affine map of a linear space is an affine space which can be computed in polynomial time.

$$ S(L,m) $$

$$ S(\mathbf{x},m) $$

$$ f(\mathbf{z})=A(\mathbf{z},m)\mathbf{x} $$

$$ f_{\mathbf{x}}:\mathbb{F}{q}^{h}\to\mathbb{F}{q}^{\ell} $$

$$ A(,\cdot,,m) $$

$$ \mathbf{z},\in,S(\mathbf{x},m) $$

$$ A(\mathbf{z},m)\mathbf{x},\in,\mathrm{I m},B(m) $$

Proof of Claim 2. If A does not halt at step 2 then RX₁ = b implying that x 2 L. Next assume by induction x 2 L in all previous steps. The only operation that may modify L is in step 13 and when that action is executed, since (Y*;*z) is a valid signature, we have

$$ R\mathrm{X}_{1}=\mathrm{b} $$

$$ \mathbf{x}\in L $$

$$ \mathbf{x}\in L $$

$$ (\mathbf{Y},\mathbf{z}) $$

$$ A(\mathbf{z},m_{i})\mathbf{X}=B(m_{i})\mathbf{Y}\ \ \ \ \Rightarrow\ \ \ \ A(\mathbf{z},m_{i})\mathbf{x}\in\operatorname{I m}B(m_{i}). $$

Proof of Claim 3. First of all we observe that A aborts only if E fails to return a valid set of relations. Since by our assumption E succeeds with significant probability () the second half of the claim is proven.

To prove that A is a PPT algorithm, we observe that E is PPT, and = n₂ + # is polynomially bounded. Thus all steps preceding the loop are efficient. Inside the loop, which is executed # times, checking S(L;m_i) 6= ? and possibly computing a z 2 S(L;m_i) can be done efficiently from Claim 1 by computing a base for it. Next, calling x the discrete logarithm of X, we have that A(z*;m*_i)x 2 ImB(m_i) because

$$ \eta(\lambda) $$

$$ \mathsf{P P T} $$

$$ n_{2}+\vartheta $$

$$ \theta $$

$$ \mathbf{z}\in S(L,m_{i}) $$

$$ S(L,m_{i})\neq\emptyset $$

$$ \vartheta $$

$$ A(\mathbf{z},m_{i})\mathbf{x}\in $$

$$ B(m_{i}) $$

$$ \mathbf{z}\in S(L,m_{i})\quad\ Rightarrow quad A(\mathbf{z},m_{i})\cdot L\subseteq\operatorname{I m}B(m_{i})\quad\Rightarrow\quad A(\mathbf{z},m_{i})\mathbf{x}\in\operatorname{I m}B(m_{i}) $$ where the last implication follows as x 2 L by Claim 2. Thus, calling H a weakinverse of B(m_i), which can be computed efficiently by Proposition 2, the vector Y can be set as H A(z*;m*_i)X. Indeed, as A(z*;m*_i)X 2 ImB(m_i) there exists a k vector Z 2 G such that A(z*;m*_i)X = B(m_i)Z and in particular

$$ \mathbf{x}\in L $$

$$ B(m_{i}) $$

$$ H\cdot A(\mathbf{z},m_{i})\mathbf{X} $$

$$ A(\mathbf{z},m_{i})\mathrm{X}\in\ln{B(m_{i})} $$

$$ \mathbf{Z}\in\mathbb{G}^{k} $$

$$ A(\mathbf{z},m_{i})\mathbf{X}=B(m_{i})\mathbf{Z} $$

$$ B(m_{i})\mathbf{Y};=;B(m_{i})H A(\mathbf{z},m_{i})\mathbf{X};=;B(m_{i})H B(m_{i})\mathbf{Z};=;B(m_{i})\mathbf{Z};=;A(\mathbf{z},m_{i})\mathbf{X}. $$

Finally, given the bases of two affine spaces, a base of their intersection can be also computed efficiently. The claim therefore follows.

Proof of Claim 4. Since the condition at step 7 is not satisfied, S(L;m_i) = ? and in particular z 2= S(L;m_i) implying that A(z*;m*_i)x 2= ImB(m_i) for some x 2 L. Therefore L is not contained in the space of all x such that A(z*;m*_i)x 2 ImB(m_i) and in particular its dimension decreases after the execution of step 13

$$ S(L,m_{i})=\emptyset $$

$$ \mathbf{z}\notin S(L,m_{i}) $$

$$ A({mathbf z},m_{i}){\mathbf{x}}\notin $$

$$ B(m_{i}) $$

$$ \mathbf{x}\in L $$

$$ A(\mathbf{z},m_{i})\mathbf{x}\in\operatorname{I m}B(m_{i}) $$

Proof of Claim 5. The first part follows as rkR = 1 or else A aborts. About the second part, let "() be the probability that dim L < n₁ + 1 when $ A halts. We can then produce a PPT algorithm B which, on input X₁ S*:* SetupCRS(1), generates sk*;vk from S:* SetupKey(1*;*X₁) and simulates the game in Fig. 2 using sk. When A halts, it reads L from its state and if l := n l;n dim L < n₁ + 1, it finds in polynomial time a matrix S 2 Fqwith full n l rank n l and a vector c 2 F_qsuch that

$$ R=\nu-1 $$

$$ \varepsilon(\lambda) $$

$$ L,<,n_{1}-\nu+1 $$

$$ \ {bf X}_{1},{leftarrow\ }^{\S} $$

$$ \mathsf{S}.\mathsf{S e t u p C R S}(1^{\lambda}) $$

$$ {\sf{S}.{e t u p K e y}((1^{\lambda},X_{1})} $$

$$ l:= $$

$$ L<n_{1}-\nu+1 $$

$$ S\in\mathbb{F}_{q}^{n-l,n} $$

$$ \mathbf{c}\in\mathbb{F}_{q}^{n-l} $$

$$ \mathbf {x} \in L \quad \Longleftrightarrow \quad S \mathbf {x} = \mathbf {c}. $$

Through Gaussian elimination it is then possible to extract a full rank matrix en1 l;n₁ S 2 F_qand a vector ec such that

$$ \widetilde{S}\in\mathbb{F}{q}^{n{1}-l,n_{1}} $$

$$ \mathbf {x} _ {1} | \mathbf {x} _ {2} \in L \Rightarrow \widetilde {S} \mathbf {x} _ {1} = \widetilde {\mathbf {c}}. $$

Notice rkSe = n₁ l > 1 implies rkS while, by Claim 2, we have that the discrete logarithm of X₁jjX₂ lies in L, meaning that SeX₁ = ec. Since S*:* SetupCRS is-hard, this can happen only with negligible probability, therefore "() is negligible.

$$ {\widetilde{S}},=,n_{1}-l,>,\nu-1 $$

$$ S,\geq,\nu $$

$$ \mathbf{X}{1}||\mathbf{X}{2} $$

$$ L\cdot $$

$$ \varepsilon(\lambda) $$

C.3 Attack to Schemes with Generic Verification

Proof of Theorem 3. Having provided a description of the adversary A in Figure 4, we now show that this adversary satisfies the requirements of the Theorem. As in the previous section we break down the proof into a sequence of Claims which imply the thesis.

A;B;c Claim 1 For all B;c and a; b*;c, the set F is an affine space.* a;b;c

$$ \mathcal{F}_{\mathbf{a},\mathbf{b},c}^{A,B,\mathbf{c}} $$

A;B;c Claim 2 An affine base for F is efficiently computable. a;b;c

$$ \mathcal{F}_{\mathbf{a},\mathbf{b},c}^{A,B,\mathbf{c}} $$

n Claim 3 Let x be the discrete logarithm of X*. Then at each step L* F_qis an affine subspace and x 2 L.

$$ L\subseteq\mathbb{F}_{q}^{n} $$

$$ \mathbf{x}\in L $$

Claim 4 Every time either condition at step 25 or 32 is satisfied, when step 26 or 35 respectively are executed, the dimension of L strictly decreases.

Claim 5 When step 29 is executed, then (Y*;t*) is a correct signature for m.

Claim 6 After step 4, dimL = n + 1*. Moreover up to negligible probability* "(), when A halts dim L > n₁ + 1*.*

$$ L = n - \nu + 1 $$

$$ \varepsilon(\lambda) $$

$$ L>n_{1}-\nu+1 $$

A;B;c Proof of Claim 1. Given u*;* v*;* w 2F we should show that w + (u v) 2 a;b;c ^A;B;c m F. Let d = u v. Then Au*;Av 2 ImB*+c implies the existence of r*;* s 2 F^q a;b;c such that Au = Br + c and Av = Bs + c, therefore Ad = B(r s). Moreover by construction

$$ \mathbf{u},\mathbf{v},\mathbf{w}\in\mathcal{F}_{\mathbf{a},\mathbf{b},c}^{A,B,\mathbf{c}} $$

$$ \mathbf{w}+(\mathbf{u}-\mathbf{v})\in $$

$$ \mathcal{F}_{\mathbf{a},\mathbf{b},c}^{A,B,\mathfrak{c}} $$

$$ \mathbf{r},\mathbf{s}\in\mathbb{F}_{q}^{m} $$

$$ A\mathbf{u}=B\mathbf{r}+\mathbf{c} $$

$$ A\mathbf{v}=B\mathbf{s}+\mathbf{c} $$

$$ A\mathbf{d}=B(\mathbf{r}-\mathbf{s}) $$

$$ \mathbf{a}^{\top}\mathbf{u}=\mathbf{b}^{\top}\mathbf{r}+\mathbf{c},\qquad\mathbf{a}^{\top}\mathbf{v}=\mathbf{b}^{\top}\mathbf{s}+\mathbf{c}\quad\Rightarrow\quad\mathbf{a}^{\top}\mathbf{d}=\mathbf{b}^{\top}(\mathbf{r}-\mathbf{s}). $$

Turning our attention to the vector w + d, its image through A lies in ImB + c m because Ad 2 ImB. Furthermore for all y 2 F_qsuch that By + c = A(w + d)

$$ \mathbf{w}+\mathbf{d} $$

$$ B+\mathbf{c} $$

$$ A\mathbf{d}\in\ \ \mathrm{I m}\ B B $$

$$ \mathbf{y}\in\mathbb{F}_{q}^{m} $$

$$ B\mathbf{y}+\mathbf{c}=A(\mathbf{w}+\mathbf{d}) $$

$$ \begin{array}{l} B \left(\mathbf {y} - (\mathbf {r} - \mathbf {s})\right) = A \mathbf {w} \Rightarrow \mathbf {a} ^ {\top} \mathbf {w} = \mathbf {b} ^ {\top} \left(\mathbf {y} - (\mathbf {r} - \mathbf {s})\right) + c \ \Rightarrow \quad \mathbf {a} ^ {\top} \mathbf {w} + \mathbf {a} ^ {\top} \mathbf {d} = \mathbf {b} ^ {\top} \mathbf {y} + c \ \Rightarrow \quad \mathbf {a} ^ {\top} (\mathbf {w} + \mathbf {d}) = \mathbf {b} ^ {\top} \mathbf {y} + c. \ \end{array} $$

A;B;c Thus w + d 2F proving the claim. a;b;c

$$ \mathbf{w}+\mathbf{d}\in\mathcal{F}_{\mathbf{a},\mathbf{b},c}^{A,B,\mathbf{c}} $$

A;B;c Proof of Claim 2. Let H a weak left inverse of B, then we can rewrite F _a;b;c as the set of all x such that Ax 2 ImB + c and

$$ \mathcal{F}_{\mathbf{a},\mathbf{b},c}^{A,B,\mathbf{c}} $$

$$ A\mathbf{x}\in\operatorname{I m}B+c $$

$$ \forall{\mathbf{w}}\ \ \ \ \ \ {\mathbf{a}}^{\top}{\mathbf{x}}={\mathbf{b}}^{\top}(H A{\mathbf{x}}+(I-B H){\mathbf{w}})-{\mathbf{b}}^{\top}H{\mathbf{c}}+c $$

using the fact that all solutions to By+c = t are of the form H(t c)+(I BH)w for arbitrary w. Next we introduce an auxiliary space V_r;s;tdefined as

$$ H (\mathbf {t} - \mathbf {c}) + (I - B H) \mathbf {w} $$

$$ \mathcal{V}_{\mathbf{r},\mathbf{s},t} $$

$$ \mathcal{V}{\mathbf{r},\mathbf{s},t}\ =\ {(\mathbf{x},\mathbf{z})\in\mathbb{F}{q}^{n}\times\mathbb{F}_{q}^{n}\ :\ \mathbf{r}^{\top}\mathbf{x}=\mathbf{s}^{\top}\mathbf{z}+t} $$

n Calling : V_r;s;t! F_qthe projection on the first component (x*;*w) 7! x then it’s

easy to prove that, letting r = a A H b, s = (I BH) b and t = b Hc +c

$$ \pi:\mathcal{V}{\mathbf{r},\mathbf{s},t}\to\mathbb{F}{q}^{n} $$

$$ (\mathbf{x},\mathbf{w})\mapsto\mathbf{z} $$

$$ \mathbf {r} = \mathbf {a} - A ^ {\top} H ^ {\top} \mathbf {b}, \mathbf {s} = (I - B H) ^ {\top} $$

$$ t=-\mathbf{b}^{\top}H\mathbf{c}!+!c $$

$$ \begin{array}{r l r}{\mathbf{0}\times\mathbb{F}{q}^{n}\nsubseteq\operatorname{d i r}\left(\mathcal{V}{\mathbf{r},\mathbf{s},t}\right)}&{{\Rightarrow}}&{\mathcal{F}_{\mathbf{a},\mathbf{b},c}^{A,B,\mathbf{c}},=,\mathcal{D}}\end{array} $$

$$ \mathbf{0}\times\mathbb{F}{q}^{n}\subseteq\operatorname{d i r}\left(\mathcal{V}{\mathbf{r},\mathbf{s},t}\right)\quad\Rightarrow\quad\mathcal{F}{\mathbf{a},\mathbf{b},c}^{A,B,\mathbf{c}},=,\pi(\mathcal{V}{\mathbf{r},\mathbf{s},t})\cap{\mathbf{{x}}A\mathbf{x}\in\operatorname{I m}B+\mathbf{c}} $$

Since V_r;s;tis an affine hyper-plane, a base of ImB + c is efficiently computable, and so is its preimage through A. Thus the thesis follows.

$$ \mathcal{V}_{\mathbf{r},\mathbf{s},t} $$

n Proof of Claim 3. L is an affine subspace since initially L = F_q. By iⁿduction, assume that, at a given step, L is an affine subspace. Then it is only updated at step 26 or 35. In both cases, by Claim 1, we have that L is the intersection of two affine subspaces.

$$ L=\mathbb{F}_{q}^{n} $$ n For the second part, initially x 2 L = F_q. Next assume by induction x 2 L. A;B;c If step 26 is executed then the condition 25 is true, meaning that x 2F. ^ai^;bi^;ci Therefore x still lies in L. Conversely, if step 35 is executed then by construction the signature satisfies AX = BY + c meaning that Ax 2 ImB + x. Thus again x 2 L after step 35.

$$ \mathbf{x}\in L=\mathbb{F}_{q}^{n} $$

$$ \mathbf{x}\in L $$

$$ \mathbf{x}\in\mathcal{F}{\mathbf{a}{i},\mathbf{b}{i},c{i}}^{A,B,\mathfrak{c}} $$

$$ A\mathbf{x}\in\operatorname{I m}B+\mathbf{x} $$

$$ A\mathbf{X}=B\mathbf{Y}+\mathbf{c} $$

$$ \mathbf{x}\in L $$

Proof of Claim 4. First of all, if condition at step 25 is satisfied, then by construction the condition at step 23 is not (or step 25 is not executed). Hence ^A;B;c L \F is ^a proper subspace of L, which implies that after step 26 the ai;bi;ci dimensⁱon of L decreases strictly.

$$ L\cap\mathcal{F}{\mathbf{a}{i},\mathbf{b}{i},c{i}}^{A,B,\mathfrak{c}} $$

If instead the condition at step 35 is satisfied, as done for the proof of Claim 5, we can assume with loss of generality that Xe and Ye share the same labels of X and Y. Executing S*:* Vfy on input (X*;s;m;Y;t*) and calling₁;:::; the bits 0 returned by O_eqinvoked during this execution, we have that at least one of the conditions on steps 19, 21 or 23 is satisfied (since the other conditions would break the cycle). However

$$ ^{5} $$

$$ \tilde{\mathbf{Y}} $$

$$ (\mathbf{X},s,m,\mathbf{Y},t) $$

$$ \ {cal O O}_{\mathrm{e q}}^{0} $$

– If the check on step 19 is satisfied then S*:* Vfy on input (X*;s;m;Y;t*) would output 0, meaning that the queried signature is rejected. This contradicts correctness of the underlying scheme.

$$ (\mathbf{X},s,m,\mathbf{Y},t) $$

– If the test on step 23 is satisfied, by Claim 3 x 2 L and in particular X 2 A;B;c F for some i such thatⁱ= 0. By construction this means th^at for ai^;bi;ci

any Y⁰ that satisfies AX = BY + c G, then a_iX = b_iY⁰ + c_iG. As A;B; c consist of the linear constraints tested by S*:* Vfy that X, Y and G

verifies, then AX = BY + c G. In particular a_iX = bⁱY + cⁱG, which 0 contradicts the hypothesis that O_eq() returns_i= 0 for the i-th query.

$$ 3;\mathbf{x}\in L $$

$$ \mathbf{X}\in $$

$$ \mathcal{F}{\mathbf{a}{i},\mathbf{b}{i},c{i}}^{A,B,\mathbf{c}} $$

$$ \beta_{i}=0 $$

$$ {mathbf\mathbf Y{}}^{\prime} $$

$$ A\mathbf{X}=B\mathbf{Y}+\mathbf{c}\cdot G $$

$$ \mathbf{a}{i}^{\top}\mathbf{X}=\mathbf{b}{i}^{\top}\mathbf{Y}^{\prime}+c_{i}\cdot G $$

$$ A,B,\mathsf{c} $$

$$ A\mathtt{X}=B\mathtt{Y}+\mathtt{c}\cdot G $$

$$ \mathbf{a}{i}^{\top}\mathbf{X}=\mathbf{b}{i}^{\top}\mathbf{Y}+c_{i}\cdot\boldsymbol{G} $$

$$ \mathcal{O}_{\mathtt{e q}}^{0}(,\cdot,) $$

$$ \beta_{i}=0 $$

In conclusion we obtain that A L * ImB + c, implying that fx 2 L : Ax 2 ImB + cg is a proper subspace of L. Hence after step 35 the dimension of L strictly decreases.

$$ A \cdot L \subsetneq $$

$$ {\mathbf{x}\in L,:,A\mathbf{x}\in $$

$$ B+\mathbf{c} $$

$$ B+\mathbf{c}} $$

$$ L $$

Proof of Claim 5. First of all we remark that step 29 can be efficiently computed since A L ImB + c, which by Claim 3 implies that, calling x the discrete A;B;c logarithm of X, Ax 2 ImB + c, and x 2F =. In p^art^icular, calling V the ai;bi;ci k affine space of solutions y 2 F_qsuch that Ax = By + c, and V_ithe subspace of

V such that a_ix = b_iy + c_iwe have two possible cases:

$$ A\cdot L\subseteq\operatorname{I m}B+{\mathfrak{c}} $$

$$ B+\mathbf{c}. $$

$$ \mathtt{x}\notin\mathcal{F}{\mathtt{a}{i},\mathtt{b}{i},c{i}}^{A,B,\mathtt{c}} $$

$$ \mathbf{y}\in\mathbb{F}_{q}^{k} $$

$$ A\mathbf{x}=B\mathbf{y}+\mathbf{c}, $$

$$ V_{i} $$

$$ \mathbf{a}{i}^{\top}\mathbf{x}=\mathbf{b}{i}^{\top}\mathbf{y}+c_{i} $$

– dimV = 0: then since condition on step 25 is not satisfied, V_i( V, which means that V_i= ? for all i such that_i= 0. In particular Y is the only solution to the system AX = BY + c G, which is obtained by

$$ V=0; $$

$$ V_{i}=\emptyset $$

$$ V_{i}\subseteq V $$

$$ \beta_{i}=0 $$

$$ A\mathtt{X}=B\mathtt{Y}+\mathtt{c}\cdot G $$

$$ \mathbf {Y} = H \cdot \left(A \mathbf {X} - \mathbf {c} \cdot G\right) $$

with H a left weak inverse of B, and it automatically satisfies all the condi-

tions of the form a_iX 6= b Y + c_iG.

$$ \mathbf{a}{i}^{\top}\mathbf{X}\neq\mathbf{b}^{\top}\mathbf{Y}+c{i}\cdot G $$

– dimV 1: then since condition on step 25 is not satisfied, Vi( V is a proper S dimV 1 subspace of V. It follows that_{i: =0}V_icontains at most q points. i

$$ V\geq1. $$

$$ V _ {i} \subsetneq V $$

$$ \cup_{i:\beta_{i}=0}V_{i} $$

$$ \chi\cdot,q^{\mathrm{d i m},V-1} $$

Since is polynomially bounded (or the verification algorithm would not be S efficient) < q and in particular the set V ni: =0Viis not empty and a i vector Y satisfying the above conditions can be obtained for instance with 1 overwhelming probability greater than ¹ q by setting

$$ \chi<q $$

$$ V \setminus \bigcup_ {i: \beta_ {i} = 0} V _ {i} $$

$$ 1-\chi\cdot q^{-1} $$

$$ \mathbf{Y}=H(A\mathbf{X}-\mathbf{c}\cdot G)+(I-H B)\mathbf{w}\cdot G $$

$ n with H a weak left inverse of B aⁿd w F_q.

$$ \mathbf{w}\leftarrow^{\S}\mathbb{F}_{q}^{n}. $$

Finally to show that (Y*;t*) is a valid signature we first observe that without loss of generality we may assume that X and Y have the same labels of Xe and Ye. Indeed A can set Xe with the same labels of X and Ye with large enough k labels so that, for a given Y 2 G, up to performing dummy operations (adding zeroes for instance), it is possible to obtain a new vector Y⁰ representing the same group elements of Y and with the same labels of Y.

$$ \widehat{\bf{X}} $$

$$ \mathbf{Y}\in\mathbb{G}^{k} $$

$$ \mathbf{Y}^{\prime} $$

As the inputs (X*;s;m;Y;t*) and (Xe*;s;m;Ye;t*) are equal, the deterministic 0 algorithm S*:* Vfy performs the same queries to O_addand O_eq. In particular, for

0 the i-th query, if_i= 0 then a_iX 6= b_iY +c_iG, meaning that O_eq() returns 0 0 =_i. Conversely if_i= 1, then a X = b Y + c_iG, meaning that O_eq() returns 1 =ⁱ. Hence the execution of S*:* Vfy produces the same output b it returns when executed with the simulated group Ge. As condition on step 19 is not satisfied, b = 1, meaning that the signature (Y*;t*) is valid for m.

$$ (\mathbf{X},s,m,\mathbf{Y},t) $$

$$ (\ddot{\mathbf{X}},s,m,\ddot{\mathbf{Y}},t) $$

$$ \mathcal{O}_{\mathsf{a d d}} $$

$$ \mathcal{O}_{\mathrm{e q}}^{0} $$

$$ \beta_{i}=0 $$

$$ \mathbf{a}{i}^{\top}\mathbf{X}\neq\mathbf{b}{i}^{\top}\mathbf{Y},+,c_{i}\cdot,G, $$

$$ \mathcal{O}_{\mathrm{e q}}^{0}(\cdot) $$

$$ 0=\beta_{i} $$

$$ \beta_{i}=1 $$

$$ \mathbf{a}^{\top}\mathbf{X}=\mathbf{b}^{\top}\mathbf{Y}+c_{i}\cdot G, $$

$$ \mathcal{O}_{\mathtt{e q}}^{0}(\cdot) $$

$$ 1=,\beta_{i} $$

$$ \tilde{\mathbb{Q}}. $$

$$ (\mathbf{Y},t) $$

Proof of Claim 6. Analogous to the proof of Claim 5 in Theorem 2.