Caulk: Lookup Arguments in Sublinear Time

1 Arantxa Zapico, Vitalik Buterin², Dmitry Khovratovich², Mary Maller², Anca Nitulescu³, and Mark Simkin²

1 Universitat Pompeu Fabra y 2 Ethereum Foundation z 3 Protocol Labs x

¹ y Universitat Pompeu Fabra ² z Ethereum Foundation ³ x Protocol Labs

Abstract

We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or m values that comprise commitment cm all belong to the vector of size N committed to in C. Our construction Caulk can be used for membership proofs and lookup arguments and outperforms all existing alternatives in prover time by orders of magnitude.

For both single- and multi-membership proofs the Caulk protocol beats SNARKed Merkle proofs by the factor of 100 even if the latter is instantiated with Poseidon hash. Asymptotically our prover needs O(m² + mlogN) time to prove a batch of m openings, whereas proof size is O(1) and verier time is O(log(logN)).

$$ O(m^{2}+m\log N $$

As a lookup argument, Caulk is the rst scheme with prover time sublinear in the table size, assuming O(N logN) preprocessing time and O(N) storage. It can be used as a subprimitive in veriable computation schemes in order to drastically decrease the lookup overhead.

Our scheme comes with a reference implementation and benchmarks.

1 Introduction

A vector commitment is a basic cryptographic scheme, which lies at the foundation of numerous constructions and protocols. In a nutshell, a vector commitment is a compact data structure that contains a potentially very large number of elements and allows proving that a specic element has been committed to it. A natural requirement is that a proof is succinct and unforgeable. A Merkle tree is a well-known example of a vector commitment.

For privacy-preserving applications it is vital to make proofs zero-knowledge, i.e. hiding the element that is asserted to be in the commitment, while still establishing a certain relationship, or link, to that element. A vector commitment to c = (c₁;:::;c_N) is linkable, if it permits proving that you know a secret s_imathematically linked to c_i. The simplest example is a proof of authorization where a party proves knowledge of a secret key belonging to one of multiple public keys in a set. A more elaborate example is a proof of coin ownership in private cryptocurrencies: coins are stored as hashes of a secret k and values v in a list or a tree and to spend v one proves knowledge of v and k without revealing them. A third example are lookup arguments in veriable computation: prove that intermediate values a₁;a₂;:::;a_mare all contained in a certain table, e.g., a table of all 16-bit numbers for the purpose of overow checks in nancial or mathematical computations. Other applications also include membership proofs, ring signatures, anonymous credentials and other schemes.

$$ c=(c_{1},\ldots,c_{N}) $$

$$ s_{i} $$

$$ c_{i} $$

$$ a_{1},a_{2},\ldots,a_{m} $$

Currently, all of the above examples are being solved using heavy cryptography machinery involving signicant computational overheads, which limits their scalability and adoption. The rst version of

This work was done while Arantxa Zapico was an intern at the Ethereum Foundation.

^yarantxa.zapico@upf.edu

^zfv buterin, mary.maller, mark.simking@ethereum.org, khovratovich@gmail.com ^xanca@protocol.ai the Zcash cryptocurrency [30] used a SHA-2-based Merkle tree to store the coins and the Groth16 [20] SNARK to prove coin ownership. The relatively high costs of Groth16 and the large prime-eld circuits of SHA-2 made the resulting prover time of 40 seconds barely usable in practice. Even the most recent developments of algebraic hashes [1, 19] reduce prover time by an order of magnitude only. Another application of concern, lookup tables, so far has required the generic construction of Plookup [17], that makes the prover be at least as big as the table itself, no matter how many values they look up.

1.1 Our Contributions

In this paper we present a novel construction, named Caulk, that allows to link a public set with a hidden subset in zero-knowledge and performs with unprecedented eciency. We construct a proof of membership, with asymptotic complexity of O(logN) for N-sized commitments, with a concrete eciency improvement of a factor of 100x over SNARKs on top of a Merkle trees that uses the Poseidon hash function. The prover benets of our construction are even more extreme when compared with Merkle trees that use SHA-2. Our construction achieves statistical zero-knowledge and soundness in the algebraic group model, requires a universal setup, and O(N) storage.

Our construction naturally extends to proof of subset memberships, thus leading the way to more ecient lookup arguments. We are the rst to remove the bottleneck of big tables by achieving a O(mlogN + m²) prover cost for m-subvector lookups. The verier is succinct as it requires only O(log(logN)) scalar operations as well as constant number of pairings to verify a constant-size proof. We envision the widespread deployment of our construction both in generic lookup-equipped proof systems [17,27] and specic applications with membership proofs.

$$ O(m\log N+m^{2}) $$

We have implemented Caulk¹ in Rust, and we use that implementation for concrete comparison with other solutions as well.

1.2 Paper Structure

We start with a technical overview of Caulk in Section2and related work is discussed in Section3. In Section4we provide a self-contained description of the tools we use, in particular the polynomial commitment scheme by Kate, Zaverucha and Goldberg [22] (KZG) and associated precomputation techniques, which can be skipped by a knowledgeable reader.

In Section5we identify our constructions as special cases of a more general family of protocols that add a property that we call position-hiding linkability to vector commitment schemes. This primitive asserts that all (hidden) entries committed in an element cm are also (publicly) committed to in C. Position-hiding refers to the fact that no information about which elements were taken to construct cm should be leaked. We formalize its denition as well as the security notions it should satisfy.

In Section6we formally describe Caulk for the case of proving membership of a single element (m = 1) and show that it is sound in the algebraic group model and statistically zero-knowledge. As an important building block we also present a construction of a proof system that demonstrates that a Pedersen commitment contains a root of unity. In Section7we extend Caulk even further to m-subset (m > 1) proofs, with some values possibly repeating. In this scenario Caulk can be seen as a lookup table, and is thus a prover ecient alternative to schemes such as Plookup [17]. We discuss various optimizations in Section8.

Caulk comes with an open source reference implementation in Rust using arkworks library. In Section9 we compare its eciency with some rival schemes.

2 Caulk in a nutshell

In the following we explain the high-level ideas behind our constructions for the case of proving membership of a single element (m = 1) and the case of proving membership of multiple elements (m > 1). The starting point of both is the KZG polynomial commitment scheme, which we describe in Section4.2, that allows for committing to a polynomial C(X) and then later on opening evaluations C() for some PN publicly known. We note that a vector ~c can be encoded as a polynomial C(X) =ⁱ₌₁c_{i i}(X), N where f_i(X)g_i=1are the Lagrange interpolation polynomials corresponding to some set of roots of unity

$$ C(X) $$

$$ C(\alpha) $$

$$ \vec{c} $$

$$ C(X)=\sum_{i=1}^{N}c_{i}\lambda_{i}(X) $$

$$ {\lambda_{i}(X)}_{i=1}^{N} $$

¹https://github.com/caulk-crypto/caulk

N 1 N i 1 j H = f1*;!;:::;! g* with*!* = 1. That is,_i(!) = ¹ and_i(!) = 0 for all j =6 i 1*:* Opening position i in the vector is done by simply revealing the corresponding evaluation of the polynomial at i 1 element*!*. P

$$ \lambda_{i}(\omega^{i-1})=1 $$

$$ \mathbb{H}={1,\omega,\ldots,\omega^{N-1}} $$

$$ \lambda_{i}(\omega^{j})=0 $$

$$ j\neq i-1 $$

$$ \omega^{N}=1 $$

$$ \omega^{i-1} $$

N A KZG commitment to C(X) is an element C =ⁱ⁼¹cⁱ[ⁱ(x)]¹where x is secret and [:]¹denotes it is given in the source group G₁ of some (asymmetric) bilinear group. A proof of opening for value v at position i is an element [Q_i]₁such that

$$ C(X) $$

$$ C = \sum_ {i = 1} ^ {N} c _ {i} \left[ \lambda_ {i} (x) \right]; $$

$$ x $$

$$ [. ] _ {1} $$

$$ \mathbb{G}_{1} $$

$$ e:(\mathsf{C}-[\upsilon]{1},:[1]{2})=e:([Q_{i}]{1},[x-\omega^{i-1}]{2}):. $$

P A proof of opening for a subset of positions I [N] is an element [HI]1, such that if CI(X) =i2Ici i(X) Q i 1 and zI(X) =_i2I(X!), where f_i(X)g_i2Iare the Lagrange interpolation polynomials of H_I= i ₁ f! g_i2I, then e(C [C (x)];[1]) = e([H]; [z (x)]):

$$ I\subset\left|N\right| $$

$$ [H_{I}]_{1} $$

$$ C_{I}(X)=\sum_{i\in I}c_{i}\tau_{i}(X) $$

$$ \mathbb{H}_{I}= $$

$$ z_{I}(X)=\ \ {\tilde{\prod_{i\in I}}}(X-\omega^{i-1}) $$

$$ {\tau_{i}(X)}_{i\in I} $$

$$ {\omega^{i-1}}_{i\in I}, $$

$$ e(\mathsf{C}-[C_{I}(x)]{1},[1]{2})=e([H_{I}]{1},[z{I}(x)]_{2}). $$

Our prover time is almost unaected by the computation of the non-hiding KZG proofs [Q_i]₁and [H_I]₁. Indeed, the former can be pre-computed along with all proofs for individual positions using N logN group operations, and the latter can be obtained from the pre-computed proofs for all i 2 I, in time dependent on jIj, as shown in [28, 13] and discussed in Section4.3. As a result, note that our prover does require linear storage.

$$ [Q_{i}]_{1} $$

$$ [H_{I}]_{1} $$

$$ i\in I $$

$$ |I| $$

In our case, we would like to show that a secret committed value (or a set of committed values) is at a secret position of our committed vector. On a very high level, the idea behind Caulk is to re-randomize the values provided as part of a KZG opening by appropriate blinders, such that no information about which element is at which position is revealed. The main technical challenge lies in eciently proving that the blinded KZG opening is still well-formed. We outline the technical ideas between the single and multiple element cases separately.

Single Element. Instead of directly revealing value v, the prover now demonstrates knowledge of v and r behind a Pedersen commitment cm = [v + hr]₁, for unknown h given as [h]₁in the setup. Next, the prover would like to convince the verier that v is stored somewhere in the vector. For this, the prover i 1 i 1 publishes [z(x)]₂= [a(x!)]₂and shows that it is a blind commitment to polynomial X!, ^{i 1} which implies proving that it is a polynomial of degree 1 and that*!* ⁱs an Nth root of unity i.e. that ^{i 1 N} (!) = 1.

$$ v, $$

$$ \mathsf{c m}=[v+\mathsf{h}r]_{1} $$

$$ [\mathsf{h}]_{\ ]}^{\phantom{(}}] $$

$$ [z(x)]{2}=[a(x-\omega^{i-1})]{2} $$

$$ X-\omega^{i-1} $$

$$ \omega^{i-1} $$

$$ (\omega^{i-1})^{N}\bar{=}1 $$

To prove well-formation of z(X), the prover additionally commits to an auxiliary polynomial f (X) of degree n = log(N) + 6, which eectively encodes a set of constraints on z(X). Crucially important n 1 n for eciency, we dene f (X) over a small subgroup of roots of unity V_n= f¹;:::; g with = 1. i 1 Concretely, the rst 5 coecients of f (X) are used to, by comparing it to z(X), extract !, the next i 1 1 log(N) log(N) coecients are used to obtain the 2-powers of (!) up to 2 = N, and the last one to log(N) i 1 1 2 i 1 1 N i 1 N prove that ((!)) = ((!⁾) = (!) = ¹.

$$ z(X) $$

$$ f(X) $$

$$ z(X) $$

$$ n=\log(N)+6 $$

$$ f(X) $$

$$ \mathbb{V}_{n}={1,\ldots,\sigma^{n-1}} $$

$$ \sigma^{n}=1 $$

$$ f(X) $$

$$ z(X) $$

$$ \omega^{i-1} $$

$$ (\omega^{i-1})^{-1} $$

$$ 2^{\log(N)}=N $$

$$ ((\omega^{i-1})^{-1})^{2^{\operatorname{l o g}(N)}}=((\omega^{i-1})^{-1})^{N}=(\omega^{i-1})^{N}=\mathtt{1} $$

Multiple Elements. For the case of multiple elements, the prover would like to convince the verier that all elements in vector ~a = (a₁;:::;am) that are committed to in a KZG commitment P cm, are alsom somewhere in the vector ~c committed as C. We rst encode ~a as a polynomial (X) =^j=1a^{j j}(X), m where f_j(X)g_j=1are Lagrange interpolation polynomials over a subgroup of roots of unity V_m= m 1 m f¹;;:::; g with = 1, and set cm = [ (x)]₁.

$$ {\vec{a}}=(a_{1},\ldots,a_{m}) $$

$$ \vec{c} $$

$$ \mathsf{C} $$

$$ \phi(X)=\sum_{j=1}^{m}a_{j}\mu_{j}(X) $$

$$ \vec{a} $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ \mathbb{V}_{m}= $$

$$ \left{1,\nu,\ldots,\nu^{m-1}\right} $$

$$ \nu^{m}=1 $$

$$ {\mathsf{c m}}=[\phi(x)]_{!} $$

To prove linkability between ~c and ~a, the prover rst sets ~c_Ito be the subvector of ~c that contains all the elements c_isuch that c_i= a_jfor some a_j, without repetitions, and comptues C_I(X) using the i 1 Lagrange polynomials f_i(X)g_i2Ithat correspond to H_I= f! gⁱ2I. Using KZG proofs of openings for blinded commitments to C_I(X) and z_I(X), the prover sends [H_I(x)]₁where H_I(X) is a blinded version of the polynomial H_I0(X) such that

$$ \vec{c} $$

$$ {\vec{a}}, $$

$$ c_{i}=a_{j} $$

$$ \vec{c}_{I} $$

$$ \vec{c} $$

$$ c_{i} $$

$$ C_{I}(X) $$

$$ a_{j} $$

$$ \mathbb{H}{I}={\omega^{i-1}}{i\in I} $$

$$ {\tau_{i}(X)}_{i\in I} $$

$$ C_{I}(X) $$

$$ H_{I}^{\prime}(X) $$

$$ [H_{I}(x)][ $$

$$ z_{I}(X) $$

$$ H_{I}(X) $$

$$ \mathcal{C}(X)-\mathcal{C}{I}(X)=z{I}(X)H_{I}^{\prime}(X). $$

Then, it remains to prove that zI(X) has the right form and [CI(x)]1is a commitment to the same Pm values as c^m =ja^{j j}(X), just in a dierent basis, namely fⁱ(X)g vs f^j(X)g. For the rst statement Pm ij 1 i 1 we again introduce an auxiliary polynomial u(X) =_j=1!^j(X) that includes all the*!* w_ith i 2 I, but with the corresponding repetitions. We prove that u(X)’s coecients are Nth roots of unity by providing a proof that u_j(X) = u_{j 1}(X)u_{j 1}(X) for j = 1*;:::;m*, when evaluated at elements in V_m,

$$ z_{I}(X) $$

$$ [C_{I}(x)]_{1} $$

$$ \mathsf{c m}=\sum_{j}^{m}a_{j}\mu_{j}(X) $$

$$ \left{\tau_{i}(X)\right} $$

$$ {\mu_{j}(X)} $$

$$ u(X)=\sum_{j=1}^{m}\omega^{i_{j}-1}\mu_{j}(X) $$

$$ \omega^{i-1} $$

$$ i\in I. $$

$$ u(X) $$

$$ u_{j}(X)=u_{j-1}(X)u_{j-1}(X) $$

$$ j=1,\ldots,m $$

$$ \mathbb{V}_{m} $$ and showing that u₀(X) = u(X) and u_n(X) = 1. Then it remains to prove that z_I(X) vanishes at every coecient of u(X) i.e. z_I(u(X)) vanishes at all elements of V_m. This is done by providing H₂(X) such that z^I(u(X)) = z^H(X)H₂(X). Note that the argument holds also when Pu(X) has repeating coecients. m ij 1 For the rst statement, we introduce an auxiliary polynomial u(X) =_j=1!_j(X) that includes i 1 n all the*!* wⁱth i 2 I but with the corresponding repetitions. We also dene polynomials fu_j(X)g_j⁼⁰aⁿd show that u(X)’s coecients are Nth roots of unity by providing a proof that u_j(X) = u_{j 1}(X)u_{j 1}(X) for j = 1*;:::;m*, when evaluated at elements in V_m, and that u₀(X) = u(X) and u_n(X) = 1. Then it remains to prove that z_I(X) vanishes at every coecient of u(X) i.e. z_I(u(X)) vanishes at all elements of V_m. This is done by providing H₂(X) such that z_I(u(X)) = z_H(X)H₂(X). Note that the argument holds also when u(X) has repeating coecients.

$$ u_{n}(X)=1 $$

$$ u_{0}(X)=u(X) $$

$$ z_{I}(X) $$

$$ \mathbb{V}_{m} $$

$$ z_{I}(u(X)) $$

$$ H_{2}(X) $$

$$ \iota(X) $$

$$ z_{I}(u(X))=z_{H}(X)H_{2}(X) $$

$$ u(X)=\sum_{j=1}^{m}\omega^{i_{j}-1}\mu_{j}(X) $$

$$ \omega^{i-1} $$

$$ i\in I $$

$$ {u_{j}(X)}_{j=0}^{n} $$

$$ u(X) $$

$$ u_{j}(X)=u_{j-1}(X)\mathring{u}_{j-1}(X) $$

$$ \mathbb{V}_{m}; $$

$$ j=1,\ldots,m $$

$$ u_{0}(X)=u(X) $$

$$ u_{n}(X)=1 $$

$$ z_{I}(X) $$

$$ u(X)\ {\mathrm{i.e.~}}z_{I}(u(X)) $$

$$ \mathbb{V}_{m} $$

$$ H_{2}(X) $$

$$ z_{I}(u(X))=z_{H}(X)H_{2}(X) $$

$$ u(X) $$

(ii) is proven by asserting the polynomial equation

$$ \mathcal{C}{I}\big(u(X)\big)-\phi\big(X\big)=z{H}\big(X\big)H_{3}\big(X\big) $$

m holds for some H₃(X), thus linking an input (X) in the known basis f_j(X)g_j=1to C_I(X) in the unknown basis f_i(X)g_i2I.

$$ H_{3}(X) $$

$$ \phi(X) $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ C_{I}(X) $$

$$ {\tau_{i}(X)}_{i\in I}. $$

3 Related Work

Merkle-SNARK. Zcash protocol [30] proposed a SNARK over a circuit describing a Merkle tree opening for the anonymous proof of coin ownership. It remains a very popular approach for various set membership proof protocols [29, 31]. The prover costs are logarithmic in the number of tree leafs, but the concrete eciency varies depending on the hash function that comprises the tree [1, 19]. Regular hash functions such as SHA-2 are known to be very slow, whereas algebraic alternatives are rather novel and some applications are reluctant to use them.

Pairing Based. Camenisch et al.[9] describe a vector commitment that only requires constant prover and verier costs. However the commitments themselves are computed by a trusted third party and have 1 linear size because the prover requires access to []¹for all cⁱin the vector and x secret. Benarroch et x ci al. introduced in [5] what we dene as position-hiding linkability for a commitment C corresponding to the PST vector commitment scheme [26] and a commitment cm to one element using Pedersen’s scheme. Similar to ours, their construction consists on opening a public polynomial encoding a vector at some i 1 hiding position s (instead of at element*!) and prove that the output is the element committed in cm, along with well formation of the input (by showing that s < N). Still, their construction has a proof of size logarithmic in N and asks the verier to perform O(logN*) group operations and log(N) pairings.

$$ [\frac{1}{x-c_{i}}]_{1} $$

$$ c_{i} $$

$$ \omega^{i-1}\Big) $$

$$ s<N. $$

Discrete-Log Based. In the discrete-logarithm setting a series of works have looked into achieving logarithmic sized zero-knowledge membership proof [3, 21, 7, 8]. These have the advantage that there is no trusted setup or pairings. The prover and verier costs are asymptotically dominated by a linear number of eld operations. For modest sized vectors this can be practical because the number of more computationally intensive group operations is logarithmic.

RSA Accumulators. Camenisch and Lysyanskaya [10] design a proof of knowledge protocol for linking a commitment over a prime ordered group to an RSA accumulator. There are no a-priori bounds on the size of the vector and nicely, RSA based schemes have constant size public parameters. This approach is used by Zerocoin [25] which is a privacy preserving payments system (the predecessor to Zerocash [4]). Benarroch et al. [5] improve on this result by allowing the use of prime ordered groups of \standard" size, e.g., 256 bits, whereas [10] needs a much larger group. As opposite to Merkle tree constructions, [5] has prover time constant on the size of the table, and gets up to almost four times faster for elements of arbitrary size and between 4.5 and 23.5 for elements that are large prime numbers; as drawback, proof size goes from 4 to 5 KB. Later, Campanelli et al. [11] present also an scheme for position-hiding linkability of RSA accumulators for large prime numbers and Pedersen commitments. Their proving times does not depend on the size of the accumulator and outperforms Merkle tree approaches by orders of magnitude; however they require either a trusted RSA modulus or class groups.

4 Preliminaries

A bilinear group gk is a tuple gk = (q; G₁*;G₂;* G_T;e; [1]₁;[1]₂) where G₁*;G₂ and G_Tare groups of prime order q, the elements [1]₁;[1]₂are generators of G₁;*G₂ respectively. We also consider [h]₁another

$$ g k=(q,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}{T},e,[1]{1},[1]_{2}) $$

$$ \mathbb{G}{1},\mathbb{G}{2} $$

$$ q, $$

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

$$ [1]{1},[1]{2} $$

$$ \mathbb{G}{1},\mathbb{G}{2} $$

$$ [\mathsf{h}]_{1} $$

| Scheme | Trusted Params | |srs| | Proof size | Prover work | Verifier work | | --- | --- | --- | --- | --- | --- | | Merkle trees+zkSNARKs | Updatable | m log(N) | 13G1,8F | $\tilde{O}(m\log(N))$ | 2P | | RSA accumulators | Yes | O(1) | 2G | O(log(m)) | m exp | | Caulk single opening(Sec.6) | Updatable | O(N) | 6G1,2G2,4F | $\tilde{O}(\log(N))$ | 4P | | Caulk lookup(Sec.7) | Updatable | O(N) | 14G1,1G2,4F | $\tilde{O}(m^{2}+m\log(N))$ | 4P |

$$ 13\mathbb{G}_{1},8\mathbb{F} $$

$$ \ {\tilde{O}}(m\operatorname{l o g}(N)) $$

$$ m\log(N) $$

$$ 2\mathrm{P} $$

$$ O(\log(m)) $$

$$ \ 66{\tt G}{1},,2{{\mathbb G}}{2},,4{\mathbb F} $$

$$ {\tilde{O}}(\log(N)) $$

$$ 14\mathbb{G}{1},1\mathbb{G}{2},4\mathbb{F} $$

$$ \tilde{O}\bigl(m^{2}+m,\tilde{\log}(N)\bigr) $$

Table 1: Cost comparison of our scheme with alternative proofs for membership and lookups. N is the size of the table and m the size of the set to be opened. We consider that Merkle trees + zk-SNARKs are implemented using Marlin [12] and note that these numbers are dierent with other SNARKs. Note that the asymptotic prover work for the Merkle trees + zkSNARKs hides the large constants involved in arithmetising hash functions. The RSA accumulator asymptotics hides large constants: for example G denotes a hidden order group that has larger size than G₁, G₂.

$$ \mathcal{G} $$

$$ \mathbb{G}{1},,\mathbb{G}{2} $$

generator of G₁, where h is unknown and h[1]₁= [h]₁. e : G₁ G₂*!* G_Tis an eciently computable, non-degenerate bilinear map, and there is no eciently computable isomorphism between G₁ and G₂. Elements in G, are denoted implicitly as [a] = a[1], where 2f1*;* 2*;T g* and [1]_T= e([1]₁;[1]₂): With this notation, e([a]₁; [b]₂) = [ab]_T.

$$ \mathbb{G}_{1} $$

$$ {\mathsf{h}}{\big[}1\big]{1}=[{\mathsf{h}}]{1},;e:{\mathbb{G}}{1}\times{\mathbb{G}}{2}\to{\mathbb{G}}_{T} $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2} $$

$$ [a]{\gamma}=a[1]{\gamma} $$

$$ \mathbb{G}_{\gamma}. $$

$$ \gamma\in{1,2,T} $$

$$ [1]{T}=e([1]{1},[1]_{2}) $$

$$ e([a]{1},[b]{2})=[a b]_{T} $$

Let 2 N denote the security parameter and 1 its unary representation. A function negl : N*!* R is 1 called negligible if for all c > 0, there exists k₀ such that negl(k) k₀. For a non-empty set k S, let x S denote sampling an element of S uniformly at random and assigning it to x.

$$ 1^{\lambda} $$

$$ \lambda\in\mathbb{N} $$

$$ \cdot\mathbb{N}\to\mathbb{R} $$

$$ c>0 $$

$$ \mathsf{n e g l}(k)<{textstyle\frac{1}{k^{c}}} $$

$$ k>k_{0} $$

$$ k_{0} $$

$$ x\gets S $$

$$ S $$

Let PPT denote probabilistic polynomial-time. Algorithms are randomized unless explicitly noted otherwise. Let y A(x; r) denote running algorithm A on input x and randomness r and assigning its output to y. Let y A(x) denote y A(x; r) for a uniformly random r.

$$ y\leftarrow A(x;r) $$

$$ y\leftarrow A(x) $$

$$ y\leftarrow A(x;r) $$

$$ {\boldsymbol{r}}. $$

Lagrange Polynomials and Roots of Unity. We use*!* to denote a root of unity such that N ^N 1 th ! = 1, and dene H = f1*;!;:::;! g*. Also, we leti(X) denote ^the i lagrange polynomial, i.e., Q ^s QN 1 X! ⁱ N _i(X) =^{s6=i 1i 1 s}and z_H(X) =ⁱ⁼⁰(X!) = X 1 the vanishing polynomial of H. We !! will additionally consider smaller groups of roots of unity in Sections6,7and7.2, that will be introduced accordingly.

$$ \omega $$

$$ \ {omega{}^{N}}=1 $$

$$ \mathbb{H}=\left{1,\omega,\ldots,\omega^{N-1}\right} $$

$$ \lambda_{i}(X) $$

$$ i^{\mathrm{t h}} $$

$$ \textstyle{\lambda_{i}(X)=\prod_{s\neq i-1}\frac{X-\omega^{s}}{\omega^{i-1}-\omega^{s}}} $$

$$ \begin{array}{r}{z_{H}(X),{=},\prod_{i=0}^{N-1}(X-\omega^{i}),{\mathrm{=}},X^{N},-,1\end{array} $$

4.1 Cryptographic Assumptions

The security of our protocols holds in the Algebraic Group Model (AGM) of Fuchsbauer et al. [15], using the bilinear version of the dlog, qDHE, qSFrac, and qSDH assumptions [18,6]. In the AGM adversaries are restricted to be algebraic algorithms, namely, whenever A outputs a group element [y] in a cyclic group G of order p, it also outputs its representation as a linear combination of all previously received group Pm elements. In other words, if [y] A ([x₁];:::;[x_m]); A must also provide ~z such that [y] =_j=1z_j[x_j]. This denition generalizes naturally in asymmetric bilinear groups with a pairing e : G₁ G₂*!* G_T, where the adversary must construct new elements as a linear combination of of elements in the same group.

$$ p, $$

$$ [y]\leftarrow\mathcal{A}\ \ [[x_{1}],\dots,[x_{m}] $$

$$ \vec{z} $$

$$ [y]=\sum_{j=1}^{m}z_{j}[x_{j}] $$

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

4.2 The KZG Polynomial Commitment Scheme

Our constructions heavily rely on the KZG polynomial commitment scheme (Def.A.3) that we describe below, as well as its adaptation for vector commitments that we explain in the next section. For eciency, we slightly modify the polynomial commitment in order to add degree checks to the original protocol, without incurring in extra proof elements or pairings. The polynomial commitment introduced by Kate, Zaverucha and Goldberg in [22] is a tuple of algorithms KZG*:* Setup*;* KZG*:* Commit*;* KZG*:* Open*;* KZG*:* Verify such that:

srs_KZGKZG*:* Setup par_KZG;d : On input the system parameters and a degree bound d, it outputs i d a structured reference string srs_KZG= f[x]_1;2gⁱ₌₁.

$$ \leftarrow\mathsf{K Z G.S e t u p}\big(\mathsf{p a r}_{\mathsf{K Z G}},d\big) $$

$$ d, $$

$$ \mathsf{s r s_{K Z G}}=\left({[x^{i}]{1,2}}{i=1}^{d}\right) $$

C KZG*:* Commit srs_KZG;p(X) : It outputs C = [p(x)]₁.

$$ {\mathsf{C}}\leftarrow{\mathsf{K}}{\mathsf{Z}}{\mathsf{G}} $$

$$ \left({mathsf{s r s K Z G}},p(X)\right) $$

$$ {\hat{\mathsf{C}}}=\ p(x){\hat{\mathsf{C}}}. $$

(s;KZG) KZG: Open srsKZG;p(X); : Let deg < d be the degree of p(X). Prover computes

$$ p(X) $$

$$ \bullet\ (s,\pi_{\mathsf{K Z G}})\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s}{_{\mathsf{K Z G}}},p(X),\alpha) $$

$$ q(X)=\ {\frac{p(X)-p(\alpha)}{X-\alpha}}\ , $$

d deg +2 sets s = p(); [Q]₁= [q(x)x]₁, an^d outputs (s;_KZG= [Q]₁).

$$ s=p(\alpha),[Q]{1}=[q(x)x^{d-\deg+2}]{1} $$

$$ (s, \pi_ {\mathrm {K Z G}} = [ Q ] _ {1}) $$

1*=0 KZG:* Verify srs_KZG; C*;deg;;s;*_KZG: Verier accepts if and only if

$$ e(\mathsf{C}-s,[x^{d-\operatorname{d e g}+2}]{2})=e([Q]{1},[x-\alpha]_{2}). $$

Security. It has been proven in [22, 12, 16] that the original KZG protocol, i.e., where [Q]₁= [q(x)]₁ and the pairing equation is e(C s; [1]₂) = e([Q]₁; [x]₂), is a polynomial commitment scheme that satises completeness, evaluation blinding and extractability as in Def.A.3in the AGM, under the dlog assumption. What is more, Marlin presents an alternative version of KZG with degree checks that does d deg +2 not require additional powers in G₂. For our construction, we claim that ad^ding x to the pairing and element [Q]₁does not aect completeness or extractability. We also argue that under the AGM, no PPT adversary A can break soundness by providing a commitment to a polynomial p(X) such that deg(p) > deg. Indeed, if that is the case, deg(Q) = d + 1 for Q(X) the algebraic representation of [Q]₁, i which will imply an attack to the d-DHE assumption, as the srs only contains powers [x]₁up to d.

$$ e\big({\hat{\mathsf{C}}}-{\mathfrak{s}},[1]{2}\big)=e\big([{\hat{\mathsf{Q}}}]{1},[{\hat{\mathsf{x}}}-{\mathfrak{a}}]_{2}\big) $$

$$ [Q]_{1}=[q(x)]. $$

$$ \mathbb{G}_{2} $$

$$ x^{\bar{d-d e g}+2} $$

$$ [Q]_{1} $$

$$ p(X) $$

$$ \deg(p)>{\mathrm{d e g}} $$

$$ \deg(Q)=d+1 $$

$$ Q(X) $$

$$ [x^{i}]_{1} $$

4.3 KZG as Vector Commitment Scheme

There is a natural isomorphism between vectors of size m and polynomials of degree m 1; where we Pm m m can represent ~c = (c₁;:::;c^m) 2 F as C(X) =^j=1c^jB_j(X), where B = fB^j(X)g_j=1is a basis of the space of polynomials of degree up to m 1, and vice versa. This fact implies as well a natural relation between polynomial and vector commitments (Def.A.2), where in particular, the former implies the latter. What is more, when the basis B chosen to encode the vector consists of Lagrange polynomials we have vector commitments with easy individual position openings: evaluating V (X) in the i 1th interpolation point returns c_i.

$$ m-1; $$

$$ {\vec{c}}=\left(c_{1},\ldots,c_{m}\right)\in\mathbb{F}^{m} $$

$$ C(X)=\sum_{j=1}^{m}c_{j}B_{j}(X) $$

$$ \mathcal{B}={B_{j}(X)}_{j=1}^{m} $$

$$ m-1 $$

$$ V(X) $$

$$ c_{i}, $$

In this work we will use the protocol by Kate et al. for both cases, polynomial and vector commitments. For the latter, we will not only consider individual openings but also subset openings. In particular, let N 1 N H = f1*;!;:::;! g* be a set of roots of unity and f_i(X)g_i⁼¹its corresponding Lagrange interpolation i 1 j set, with vanishing polynomial z_H(X). That is,_i(!) = ₁ and_i(!) = 0 for all j 6= i 1. We have that for some polynomial H(X),

$$ \mathbb{H}={1,\omega,\ldots,\omega^{N-1}} $$

$$ {\lambda_{i}(X)}_{i=1}^{N} $$

$$ z_{H}(X) $$

$$ \lambda_{i}(\omega^{i-1})=1 $$

$$ \lambda_{i}(\omega^{j})=0 $$

$$ j\neq i-1 $$

$$ H(X) $$

$$ C(X)-s=(X-\omega^{i-1})H(X){\mathrm{i fa n do n l yi f~}}C(\omega^{i-1})=c_{i}=s. $$

P For a polynomial C^I(X) =^i2Is^{i i}(X) where s_iare claimed values for v_iand f_i(X)g_i2Ithe Lagrange i 1 interpolation polynomials of the set f! g_i2I, Y

$$ C_{I}(X)=\sum_{i\in I}s_{i}\tau_{i}\big(X\big) $$

$$ s_{i} $$

$$ v_{i} $$

$$ {\tau_{i}(X)}_{i\in I} $$

$$ {\omega^{i-1}}_{i\in I} $$

$$ C(X)-C_{I}(X)=\prod_{i\in I}(X-\omega^{i-1})H(X){\mathrm{i f f}}V(\omega^{i-1})=c_{i}=s_{i}{\mathrm{f o ra l l~}}i\in I. $$

4.4 Subset openings

m For a vector ~c 2 F and a subset I [m], the subvector opening scheme of Tomescu et. al [28] that works for the VC inspired by KZG presented above, consists on algorithms Open and Verify such that: P

$$ \vec{c}\in\mathbb{F}^{m} $$

$$ I\subset[m] $$

Open(srsKZG*;I;~cI) : Compute CI(X) =i2Ici i(X), where fi(X)g are the Lagrange interpolation Q i 1 i 1 polynomials of the set f! g_i2I, and nd H(X) such that for z_I(X) =_i2I(X!);*

$$ C_{I}(X)=\sum_{i\in I}c_{i}\tau_{i}(X) $$

$$ \left{\tau_{i}(X)\right} $$

$$ {\omega^{i-1}}_{i\in I} $$

$$ z_{I}\ X\ \textstyle=\prod_{i\in I}\bigl(X-\omega^{i-1}\bigr) $$

$$ H(X) $$

$$ \mathcal{C}(X)-\mathcal{C}{I}(X)=z{I}(X)H(X). $$

Output_I= [H]₁= [H(x)]₁:

$$ \pi_{I}=[H]{1}=[H(x)]{1} $$

P Verify(srs^KZG; C*;I;~c*^I;^I) : Compute [z_I]₂= [z_I(x)]₂, C_I(X) =_i2Ic_{i i}(X), and C_I= [C_I(x)]₁ and output 1 if and only if

$$ [z_{I}]{2}:=:[z{I}(x)]{2},;C{I}(X):=:\textstyle\sum_{i\in I}c_{i}\tau_{i}(X) $$

$$ \mathsf{C}{I}=[C{I}(x)] $$

$$ e\big(\mathsf{C}-\mathsf{C}{I},[1]{2}\big)=e\big([H]{1},[z{I}]_{2}\big). $$

Open as aggregation of individual proofs We will additionally use a result by Tomescu et al. [28] that allows the prover to compute [H]₁in time O(mlog²(m)) given it already has stored proofs f[H_i]₁g_i2I i 1 that C(!) = cⁱ. Indeed the prover sets 0 1

$$ [H]_{11} $$

$$ \ {\mathcal{O}}(m\log^{2}(m)) $$

$$ {[H_{i}]{1}}{i\in I} $$

$$ C(\omega^{i-1})=c_{i} $$

$$ [H]{1}=\sum{i\in I}\left(\prod_{k=1,k\neq i}^{m}\frac{1}{(\omega^{i-1}-\omega^{k-1})}\right)[H_{i}]_{1} $$

i 1 Remark 1. We remark that precomputing all the proofs [H₁]₁;:::;[H_N]₁that C(!) = cⁱcan be achieved in time O(N logN) using techniques by Feist and Khovratovich [13]. The overview of this technique by Tomescu et al. ([28], Section 3.4.4, \Computing All u_i’s Fast") is explained well.

$$ [H_{1}]{1},\ldots,[H{N}]_{1} $$

$$ C!(\omega^{i-1}),=,c_{i} $$

$$ u_{i}\ mathrm s\ \mathrm{F a s t}) $$

4.5 Multiple Openings

A KZG proof of opening can naturally be extended to open one polynomial in many points. Indeed, let m p(X) be a polynomial, ~ 2 F a vector of opening points and ~s such that s_i= p(_i) for all i = 1*;:::;m*. Dene C(X) as the unique polynomial of degree m 1 such that C(_i) = s_ifor all i 2 [m]. We have that p(_i) = s_ifor all i = 1*;:::;m* if and only if there exists q(X) such that

$$ p(X) $$

$$ \vec{\alpha}\in\mathbb{F}^{m} $$

$$ \vec{s} $$

$$ s_{i}=p(\alpha_{i}) $$

$$ i=1,\ldots,m $$

$$ C_{\vec{\alpha}}(X) $$

$$ C_{\vec{\alpha}}(\alpha_{i})=s_{i} $$

$$ i\in[m] $$

$$ p(\alpha_{i})=s_{i} $$

$$ i=1,\ldots,m $$

$$ p(X)-C_{\vec{\alpha}}(X)=\prod_{i=1}^{m}(X-\alpha_{i})Q(X) $$

$$ q(X) $$

We can thus redene the KZG prover and verier the following way:

m (s;KZG) KZG: Open srsKZG*;p*(X);~ : Prover computes fi(X)gi=1the interpolation Lagrange QmPm m polynomials for the set f_ig_i=1, z (X) =_i=1(X_i) and dene C_~(X) =_i=1p(_i)_i(X). Then, it computes p(X) C (X)

$$ (s,\pi_{\mathsf{K Z G}})\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s_{\mathsf{K Z G}}},p(X),\vec{\alpha}) $$

$$ {\tau_{i}(X)}_{i=1}^{m} $$

$$ \left{\alpha_ {i} \right} _ {i = 1} ^ {m}, z _ {\alpha} (X) = \prod_ {i = 1} ^ {m} \left(X - \alpha_ {i}\right) $$

$$ \mathcal{C}{\vec{\alpha}}\big(X\big)=\sum{i=1}^{m}p(\alpha_{i})\tau_{i}\ X\big) $$

$$ Q(X)=\frac{p(X)-C_{\vec{\alpha}}(X)}{z_{\alpha}(X)};, $$

sets s_i= p(_i); [Q]₁= [Q(x)]₁, and outputs (~s;_KZG= [Q]₁).

$$ s_{i}=p(\alpha_{i}),[Q]{1}=[Q(x)]{1} $$

$$ \left(\vec{s},\pi_{\mathsf{K Z G}}=[Q]_{1}\right) $$

m 1*=0 KZG:* Verify srs_KZG; C*;;s;*_KZG: The verier computes f_i(X)g_i=1, C= [C(x)]₁, [z (x)]₂ and veries

$$ \ \ /0\leftarrow\mathsf{K Z G.V e r i f y}(\mathsf{s r s}{\mathsf{K Z G}},\mathsf{C},\vec{\alpha},\vec{s},\pi{\mathsf{K Z G}}) $$

$$ {\tau_{i}(X)}{i=1}^{m},\mathsf{C}{\vec{\alpha}}=[\mathsf{C}{\vec{\alpha}}(x)]{1},[z_{\alpha}(x)]_{2} $$

$$ p(X)-\mathcal{C}{\vec{\alpha}}(X)=Q\mathcal(X)z{\alpha}(X) $$

by making the pairing check

$$ e\big(\mathsf{C}-\mathsf{C}{\vec{\alpha}},[1]{2}\big)=e\big([Q]{1},[z{\alpha}(x)]_{2}\big), $$

and outputs 1 if and only if the equation is satised and deg(p) d.

$$ \operatorname{d e g}(p)\leq d. $$

4.6 KZG for Bivariate Polynomials

For the protocol in Section7.2we will use bivariate polynomials, or polynomials of higher degree. What this mean is that, if we have a bivariate polynomial P (X;Y) with degree up to d₁ 1 in X and d₂ 1 in Y then we require a universal setup with d₁d₂ powers. We work with a version of KZG that uses a univariate setup because these are already available for multiple dierent curves (i.e. we do not need a specialist setup just for our protocol and can work with prior KZG setups).

$$ P(X,Y) $$

$$ d_{1}-1 $$

$$ d_{2}-1 $$

$$ d_{1}d_{2} $$

d2 We observe that, by using the KZG open algorithm, we can commit to P (X;Y) as [P (x;x)]₁. We must open P (X;Y) in two steps. First we partially open P (X;Y) at some point X = to a commitment d2 [P (;x)]₁. The partial proof is given by a commitment [w (x;x)] to a partial witness

$$ \bigl[P(x^{d_{2}},x)\bigr] $$

$$ P(X,Y) $$

$$ \big[P(\alpha,x)\big]. $$

$$ P(X,Y) $$

$$ P(X,Y) $$

$$ [w_{\alpha}(x^{d_{2}},x)] $$

$$ X=\alpha $$

$$ w_{\alpha}(X,Y)=\frac{P(X,Y)-P(\alpha,Y)}{X-\alpha} $$

We then fully evaluate P (;Y) at Y = via a standard KZG proof with a degree bound of d₂ 1 on [P (;x)]₁.

$$ P(\alpha,Y) $$

$$ Y=\beta $$

$$ d_{2}-1 $$

$$ [P(\alpha,x)] $$

Pedersen commitment schemes are a particular case of vector commitments. We will consider them for committing to single values in a zero knowledge way. Thus, the srs will additionally output [h]₁for some secret h and the commitment to some element s is computed as v[1]₁+ r[h]₁= [v+ hr], for some randomly sampled h 2 F . We suggest a standard Fiat-Shamired Sigma protocol [24] to demonstrate knowledge of v;r such that cm = [v + hr]₁for some v;r:

4.7 Proof of Opening of a Pedersen Commitment

$$ [h]_{\ } $$

$$ v[1]{1}!+!r[\mathsf{h}]{1}=[v+\mathsf{h}r] $$

$$ h\in\mathbb{F} $$

$$ v,r $$

$$ v,r; $$

$$ {\mathsf{c}}{\mathsf{m}}=[v+{\mathsf{h}}r]; $$

$$ R_{\mathsf{p e d}}={(\mathsf{c m};\ (v,r)):\quad\mathsf{c m}=[v+\mathsf{h}r]_{1}} $$

The proof consists of R = [s₁ + hs₂]₁, t₁ = s₁ + vc and t₂ = s₂ + rc, where c = H(cm*;R*) and s₁;s₂ are elements chosen by the verier. At the end, the verier checks that R + c cm = [t₁ + ht₂]₁.

$$ \ \ {\cal R},=,[s_{1}+\ \ {sf h h}{2}]{1},t_{1}=s_{1}+v c $$

$$ c={\mathsf{H}}({\mathsf{c}}{\mathsf{m}},R) $$

$$ t_{2}=s_{2}+r c $$

$$ s_{1},s_{2} $$

$$ R+c\cdot\mathsf{c m}=[t_{1}+\mathsf{h}t_{2}]_{1} $$

5 Position-Hiding Linkable Vector Commitments

We introduce the concept of position-hiding linkable vector commitment schemes. Informally, two vector commitment schemes VC₁ and VC₂ are position-hiding linkable if a prover is able to convince a verier that for a given commitments C corresponding to VC₁ and cm corresponding to VC₂, it is true that all the elements in the vector committed in cm are also elements of the vector committed in C.

$$ \mathrm{V C}_{1} $$

$$ \mathrm{V C}_{2} $$

$$ {\mathrm{V C}}_{2}. $$

$$ \ mathrm V V C_{1} $$

$$ \mathsf{C} $$

Basicallly, position-hiding linkability allows the prover to extract or isolate in zero-knowledge elements from some public set or table, and later prove further attributes on them. This new primitive should satisfy three security notions: completeness, as usual; linkability, that captures the fact that if the proof veries then there is no element committed in cm that is not also committed in C; and position-hiding, which holds only if no information about the set of elements in C that have been used to construct cm is leaked.

$$ Cmathsf $$

$$ C; $$

Denition 5.1 (Position-Hiding Linkability for Vector Commitments). Two vector commitment schemes VC₁ and VC₂ are position-hiding linkable if there exist algorithms Setup_link*;Prove_link;Verify_link;*Simulate_link that behave as follows,

$$ \mathrm{V C}_{1} $$

$$ \mathrm{V C}_{2} $$

$$ (\mathsf{S e t u p}{\mathsf{l i n k}},\mathsf{P r o v e}{\mathsf{l i n k}},\mathsf{V e r i f y}{\mathsf{l i n k}},\mathsf{S i m u l a t e}{\mathsf{l i n k}}), $$

Setup_link(1*;d₁;d₂*) : takes as input the security parameter, bounds on the length of vectors in VC₁ and VC₂*, and outputs common parameters* srs that include srs₁ = VC₁*:* srs and srs₂ = VC₂*:* srs as well as trapdoor x, including the corresponding trapdoors x₁ and x₂.

$$ \mathsf{S e t u p}{\mathsf{l i n k}}(1^{\lambda},d{1},d_{2}) $$

$$ \ {mathrm V V C}_{1} $$

$$ \mathrm{V C}_{2} $$

$$ \mathsf{s r s}{1}=\mathsf{V C}{1} $$

$$ \mathrm {s r s} _ {2} = \mathrm {V C} _ {2} $$

$$ x_{1} $$

$$ x, $$

$$ x_{2} $$

$$ \mathsf{o v e}_{\mathsf{l i n k}}(\mathsf{s r s},r,{r}^{\prime},\vec{v},\vec{a}): $$

N Prove_link(srs*;r;r⁰;v;a*) : on input the srs*, commitment randomness r to vector ~v 2* F and commit- m ment randomness r⁰ to ~a 2 F*, outputs a proof that there exists some I* [N] such that for all j = 1*;:::;m, a*_j= v_ifor some i 2 I.

$$ \vec{v}\in\mathbb{F}^{N} $$

$$ \vec{a}\in\mathbb{F}^{m} $$

$$ I\subset[N] $$

$$ j=1,\dots,m,,a_{j}=v_{i} $$

$$ i\in I $$

Verify_link(srs*;* C*;cm;) : On input the srs, commitments C and cm, and proof, accepts or rejects.*

$$ \ e\ r f f_{\ n k(s r s,C m c)} $$

Simulate_link(x;C;cm) : On input the trapdoors x and commitments C and cm, outputs a simulated proof_sim,

$$ \mathsf{k e_{l i n k}}(x,\mathsf{C},\mathsf{c m}) $$

$$ \pi_{\mathsf{s i m}} $$

and satisfy the following properties:

N m Completeness: For all N;m with N d₁;m d₂, all ~v 2 F*, and all ~a 2* F such that for all j = 1*;:::;m, a*_j= v_ifor some i 2 I, it holds that:

$$ N,\leq,d_{1},m,\leq,d_{2} $$

$$ N,m $$

$$ \vec{v}\in\mathbb{F}^{N} $$

$$ \vec{a}\in\mathbb{F}^{m} $$

$$ j=1,\ldots,m,,a_{j}=v_{i} $$

$$ i\in I. $$

$$ \Pr \left[ \operatorname {V e r i f y} _ {\mathrm {l n k}} (\mathrm {s r s}, \mathrm {C}, \mathrm {c m}, \pi) = 1 \left| \begin{array}{l} \left(\mathrm {s r s}, x\right) \leftarrow \operatorname {S u p u} _ {\mathrm {l n k}} \left(1 ^ {\lambda}, d _ {1}, d _ {2}\right); \ \mathrm {C} \leftarrow \mathrm {V C} _ {1}. \operatorname {C o m m i t} \left(\mathrm {s r s} _ {1}, \vec {v}, r\right); \ \mathrm {c m} \leftarrow \mathrm {V C} _ {2}. \operatorname {C o m m i t} \left(\mathrm {s r s} _ {2}, \vec {a}, r ^ {\prime}\right); \ \pi \leftarrow \operatorname {P r o v e} _ {\mathrm {l n k}} \left(\mathrm {s r s}, r, r ^ {\prime}, \vec {v}, \vec {a}\right) \end{array} \right] = 1. \right. $$

Linkability For all N;m with N d₁;m d₂, and all PPT adversaries, there exists an extractor X_A such that: 2 3

$$ N\leq d_{1},m\leq d_{2} $$

$$ N,m $$

$$ \mathcal {X} _ {\mathcal {A}} $$

$$ \operatorname{P r}[\begin{matrix}{\mathsf{V e r i f y_{l i s s}}(\mathsf{a r s},\mathsf{C},\mathsf{c m},\pi)=1\ \ wedge\||\ \mathsf{S r s s},x\ \rangle\leftarrow\mathsf{S e t u y_{l l s}}}{{{\mathsf{}}}\mathsf{A}^{\lambda},d_{1},d_{2},\ ;;}\ {|\hat{mathsf v|}}{|\hat{mathsf v|}}{}\end{matrix} $$

Position-Hiding For all N;m with N d₁, m d₂, for all ~v and ~a, all PPT adversaries A, there exists a PPT algorithm Simulate_linksuch that: 2 3 2

$$ N,m $$

$$ N\leq d_{1},:m\leq d_{2} $$

$$ \vec{a}, $$

$$ [\begin{matrix}{\ {mathcal A(\ \ mathsf s s s,C m,pi)}}&{}&{}\ {}\end{matrix} $$

In the next sections, we introduce position-hiding linkability for KZG commitments of arbitrary size and Pedersen commitments for single elements (Section6), as well as for two KZG commitments (Section7).

6 Linking Vectors with Elements

N In this section we present a method to link a commitment C to a vector ~c 2 F (computed as C = [C(x)]1 PN with C(X) =_i=1c_{i i}(X)), to a Pedersen commitment cm. By this we mean a method for a prover to i 1 convince a verier that there exists an i such that C opens to v at some Nth rooth of un_ity*!* and cm = [v + hr]₁.

$$ \vec{c}\in\mathbb{F}^{N} $$

$$ {\mathsf{C}}=[C(x)]_{1} $$

$$ C(X)=\sum_{i=1}^{N}c_{i}\lambda_{i}(X). $$

$$ \omega^{i-1} $$

$$ \mathsf{I}=[v+\mathsf{h}r]. $$

We will consider two groups of roots of unity:

N 1 N N H = f1*;!;:::;! g* of size N with*!* = 1, Lagrange interpolation polynomials f_i(X)g_i=1where i 1 j _i(!) = ₁ and_i(!) = 0 if j 6= i 1, and vanishing polynomial z_H(X).

$$ \mathbb{H}=\left{1,\omega,\ldots,\omega^{N-1}\right} $$

$$ \omega^{N}=1 $$

$$ {\lambda_{i}(X)}_{i=1}^{N} $$

$$ \lambda_{i}(\omega^{i-1})=1 $$

$$ \lambda_{i}(\omega^{j})=0;\ \mathrm{i{~}!j j\neq i-1 $$

$$ z_{H}(X) $$

n 1 n V_n= f¹;;:::; g of size n = log(N) + 6 with = 1, Lagrange interpolation polynomials n 2 f_s(X)g_s=1aⁿd vanishing polynomial z_Vn(X).

$$ \mathbb {V} _ {n} = {1, \sigma , \dots , \sigma^ {n - 1} } $$

$$ n=\log(N)+6 $$

$$ \sigma^{n}=1 $$

$$ {\rho_{s}(X)}_{s=1}^{n} $$

$$ z _ {V _ {n}} (X) ^ {2} $$

Our construction can be divided into three main components. The rst one is a proof of knowledge for the element v committed in cm, that is a proof for relation R_pedas dened in Section4.7. The second is i 1 a modied protocol for computing blinded versions of KZG openings for statements C(!) = v that does not reveal the coordinate i or the evaluation v, which we describe below. The high-level idea here is to re-randomize a regular KZG opening with an additional blinding factor. Our third component then proves that the re-randomized vanishing polynomial used for the KZG opening is well-formed, i.e., a NIZK argument (as in Def.A.1) for the relation

$$ R_{\mathsf{p e d}} $$

$$ C(\omega^{i-1})=v $$

$$ R _ {\mathrm {u n i t y}} = \left{\left(\mathrm {s r s}, [ z ] _ {2}; (a, i)\right): [ z ] _ {2} = \left[ a \left(x - \omega^ {i - 1}\right) \right] _ {2} \wedge \left(\omega^ {i - 1}\right) ^ {N} = 1 \right} $$

6.1 Our Blinded Evaluation Construction

Our prover takes (r⁰ =?;~c) and (r;v) as input, where the rst tuple represents the vector inside the (deterministic) KZG commitment and the second tuple represents the randomness and value for the PN pedersen commitment. Let C(X) =_i=1c_{i i}(X) be the polynomial encoding vector ~c. In a regular C(X) v KZG opening for position i, the prover would compute Q₍X₎ =_{i 1}and re_veal Q = [Q(x)]₁. Instead, X! i 1 our prover computes a special kind of obfuscated commitment to*!* by selecting a random a and i 1 i 1 b committing to z(X) = aX b = a(X!) where*!* =, ^as an element [z]²= [z(x)]². The blinding a i 1 m i 1 factor is necessary, because the set f! gⁱ₌₁is polynomial sized, so revealⁱng [x!]¹would allow

$$ (r^{\prime}=\bot,\vec{c}) $$

$$ (r,v) $$

$$ C(X)=\sum_{i=1}^{N}c_{i}\lambda_{i}(X) $$

$$ \vec{c}. $$

$$ Q(X)=\frac{C(X)-v}{X-\omega^{i-1}} $$

$$ Q=[Q(x)]_{1} $$

$$ \omega^{i-1} $$

$$ z(X)=a X-b=a\big(X-^{{i-1}{1}}\big) $$

$$ \omega^{i-1}=\frac{b}{a} $$

$$ [z]{2}=[z(x)]{2} $$

$$ {\omega^{i-1}}_{i=1}^{m} $$

$$ [x-\omega^{i-1}]. $$

²For simplicity, we describe our scheme for n = log(N) + 6. Still, a subgroup with such size will most probably not exist, in which case we instantiate the protocol with the smallest subgroup of size bigger than n.

$$ n=\log(N)+6 $$ the verier to do a brute force search to nd the index. The prover then computes [T]₁= [T (x)]₁and [S]₂= [S(x)]₂, where Q(X)

$$ [S]{2}=[S(x)]{2} $$

$$ [T]{1}=[T(x)]{1} $$

$$ T(X)=\frac{Q(X)}{a}+\mathsf{h}s,\quad S(X)=-r-s z(X), $$

and s is a uniformly random value chosen by the prover. T (X) is the KZG quotient polynomial Q(X) divided by a (the blinding factor above) to compensate for z(X) having that blinding factor. The Q(X) additional term [hs]¹mixed in to fully blind the evaluation []^1and preserve zero-knowledge. [S]²is a a term that compensates for the h terms in both [T]₁and cm. In the pairing equation that checks these points, [S]₂will be paired with h to ensure that it can only cancel out terms containing h and cannot make incorrect quotient polynomials appear correct.

$$ T(X) $$

$$ Q(X) $$

$$ z(X) $$

$$ s[right\hbar h s]. $$

$$ [S]_{2} $$

$$ [\frac{Q(X)}{a}]_{1} $$

$$ [T]_{1} $$

$$ [S]_{2} $$

We use two proofs of knowledge_pedand_unityas described in Section4.7and Section6.2respectively. The proof_pedis for v, r such that cm = [v + hr]₁. The proof_unityis for a;b such that [z]₂= [ax b]₂ N ^N and a = b. The verier checks the pairing equation

$$ \pi_{\mathsf{p e d}} $$

$$ \pi_{\mathsf{u n i t y}} $$

$$ \pi_{\mathsf{p e d}} $$

$$ v,,r $$

$$ \mathrm {c m} = [ v + \mathrm {h} r ] _ {1} $$

$$ \pi_{\mathsf{u n i t y}} $$

$$ a^{N}=b^{\dot{N}} $$

$$ a,b $$

$$ [z]{2}=[a x-b]{2} $$

$$ e(\mathsf{C-c m},[1]{2})=e([T]{1},[z]{2})+e([h]{1},[S]_{2}). $$

This equation asserts that, for the polynomials C(X);T(X);z(X);S(X) encoded in C*;* [T]₁; [z]₂; and [S]₂ respectively, it holds that C(X) v hr = T (X)z(X) + hS(X):

$$ C(X),T(X),z(X),S(X) $$

$$ \mathsf{C},[T]{1},[\hat{z}]{2} $$

$$ [S]_{2} $$

$$ C(X)-v-\mathsf{h}r=T(X)z(X)+\mathsf{h}S(X). $$

Q(X) i 1 Now, because T (X) = + sh, z⁽X⁾ = a(X!), and S(X) = r sz(X), this is a

$$ T(X boldsymbol{\ X))==\frac{Q(\boldsymbol{X})}{a}+s\mathsf{h},\ }z\ \boldsymbol(X\boldsymbol{\boldsymbol{X}})=a\big(\boldsymbol{X}-\omega^{i-1}\big) $$

$$ S(X)=-r-s z(X) $$

$$ C(X)-v-\mathsf{h}r=\left(\frac{Q(X)}{a}+s\mathsf{h}\right)z(X)-\mathsf{h}r-\mathsf{h}s z(X)\Leftrightarrow C(X)-v=\left(\frac{Q(X)}{a}\right)z(X). $$

The full description of our protocol is given in Figure1.

$$ a,s\gets\mathbb{F} $$

Prover: Sample blinders a;s F P_N Us_ing C(X) =i₌₁c_{i i}(X), encoding of ~c and v;r such that cm = v[1]₁+ r[h]₁ Dene i 1C(X) v z(X) = a(X!); T(X) = + sh; S(X) = r sz(X) z(X) pedProve(Rped;cm; (v;r)) i 1 unityProve(Runity;(srs; [z]₂); (a;a!)) Set [z]₂= [z(x)]₂; [T]₁= [T (x)]₁; [S]₂= [S(x)]₂and return ([z]₂; [T]₁; [S]₂;_ped;_unity) Verier: Accept if and only if the following conditions hold e(C cm*;[1]₂) = e([T]₁;* [z]₂) + e([h]₁; [S]₂) 1 Verify_ped(srs*;cm;_ped) 1 Verify_unity(srs;* [z]₂;_unity)

$$ \vec{c} $$

$$ C(X)=\sum_{i=1}^{N}c_{i}\lambda_{i}(X) $$

$$ v,r $$

$$ {\mathsf{c m}}=v[1]{1}+r[\mathsf{h}]{1} $$

$$ z(X)=a(X-\omega^{i-1}),\ \ T(X)=\frac{C(X)-v}{z(X)}+s\mathsf{h},\ \ S(X)=-r-s z(X) $$

$$ \pi_{\mathsf{p e d}}\leftarrow\mathsf{P r o v e}(R_{\mathsf{p e d}},\mathsf{c m},(v,r)) $$

$$ \pi_{\mathsf{u n i t y}}\leftarrow\mathsf{P r o v e}\ R_{\mathsf{u n i t y}},(\mathsf{s r s},[z]_{2}),(a,a\omega^{i-1})\big) $$

$$ [z]{2}=[z(x)]{2},[T]{1}=[T(x)]{1},[S]{2}=[S(x)]{2} $$

$$ ([z]{2},[T]{1},[S]{2},\pi{\mathsf{p e d}},\pi_{\mathsf{u n i t y}}) $$

$$ e_{}(\mathsf{C}-\mathsf{c m},\ [1]{2})=e{}([mathsf T_{{1}},,[{]{{2}}}){}+e_{}([\mathsf{h}]{{1}},\ [S]{{2}}) $$

$$ 1\leftarrow\mathsf{V e r i f y}{\mathsf{p e d}}(\mathsf{s r s},\mathsf{c m},\pi{\mathsf{p e d}}) $$

$$ 1\leftarrow\mathsf{V e r i f y}{\mathsf{u n i t y}}(\mathsf{s r s},[z]{2},\pi_{\mathsf{u n i t y}}) $$

Figure 1: Zero-knowledge proof of membership. Shows that (v;r) is an opening of cm and that C opens i 1 to v at*!*.

$$ \omega^{i-1} $$

$$ (v,r) $$

Theorem 1. Let R_pedand R_unitybe relations for which zero-knowledge argument of knowledge systems are given. The construction in Figure1implies position-hiding linkability for the commitment schemes corresponding to C and cm in the algebraic group model under the qSDH and dlog assumptions.

$$ R_{\mathsf{p e d}} $$

$$ R_{\mathsf{u n i t y}} $$

$$ R_{\mathsf{u n i t y}} $$

$$ R_{\mathsf{p e d}} $$

Intuition. The arguments of knowledge for R_pedand R_unityimply well formation of cm and [z]₂, i.e. assert that except with negligible probability, cm is a pedersen commitment to a value v and [z]₂is a i 1 commitment to a polynomial z(X) = a(X +!) for some i 2 [N].

$$ [z]_{2} $$

$$ [z]_{\ }2 $$

$$ z(X)=a\ X+\omega^{i-1}) $$

$$ i\in\left[N\right] $$

Then, the fact that the rst verication equation is satised imply there exist polynomials T (X);S(X) such that C(X) (v + hr) = T (X)z(X) + hS(X). Because the prover does not know h in the eld, this either implies that the prover gets to know h from [h]₁, breaking dlog, or that they output a valid KZG i 1 proof for C(!) = v, therefore either the statement is true, or the adversary breaks qSDH.

$$ T(X),S(X) $$

$$ C(X)-(v+\mathsf{h}r)=T(X)z(X)+\mathsf{h}S(X) $$

$$ [\mathsf{h}]_{\ ]}^{\phantom{(1}}] $$

$$ C(\omega^{i-1})=v $$

The full proof is given in AppendixB.

$$ q\mathrm{S D H} $$

6.2 Correct computation of z(X)

$$ z(X) $$

The purpose of this section is provide a zero-knowledge proof of knowledge for relation R_unity, i.e. that N N the prover knows a;b such that [z]₂= [ax b]₂and a = b. This proof is used as a subprotocol in Fig.1’s construction for linkability of vector commitments.

$$ R_{\mathsf{u n i t y}} $$

$$ [z]{2}=[a x-b]{2} $$

$$ a^{N}=b^{N} $$

a In order to prove th^at is inside the evaluation domain i.e. is an Nth root of unity, we prove that its b Nth power is one. This can be done in time log(N) by dening elements f₀;:::;f_log(N)such that satisfy a 2 the following conditions: (i) f₀ =, (ii) for i = 1*;:::;* log(N) f_i= f_{i 1}, and (iii) f_log(N)= 1*:* b

$$ \frac{a}{b} $$

$$ f_{0},\ldots,f_{\operatorname{l o g}(N)} $$

$$ \ i)\ f_{0}={\textstyle\frac{a}{h}},,(i i) $$

$$ i{\ =\ }1,\dots,\mathrm{l o g}(N)\ f_{i}=f_{i-1}^{2}. $$

$$ (i i i)\ f_{\log(N)}=1 $$

a Because we want to assert f₁ = for the same elements a;b in z(X) = aX + b and we want to do it b without giving z(X) in the eld, we will assert this relation by adding 4 extra elements and replacing step (i) with the following constraints:

$$ f_{1}=\frac{a}{b} $$

$$ z(X)=a X+b $$

f₀ = z(1) = a b

$$ f_{0}=z(1)=a-b $$

f₁ = z() = a b

$$ f_{1}=z(\sigma)=a\sigma-b $$

$$ f_{2}=\frac{f_{0}-f_{1}}{1-\sigma}=\frac{a(1-\sigma)}{1-\sigma}=a $$

f₃ = f₂ f₁ = a a + b = b, and nally

$$ f_{3}=\sigma f_{2}-f_{1}=\sigma a-a\sigma+b=b, $$

$$ f_{4}=\frac{f_{2}}{f_{3}}=\frac{a}{b}. $$

2 Once we have (i), we redene the other conditions: (ii) For i = 0*;:::;* log(N) 1, f⁵⁺ⁱ= f⁴⁺ⁱ, and (iii) f_4+log(N)= 1*:* For succinctness, we aggregate all these constraints in a polynomial f (X) whose i coecients in the Lagrange basis associated to V_nare the f_i0s, i.e, such that f () = fⁱusing the following lemma:

$$ i=0,\dots,\mathrm{l o g}(N)-1,,f_{5+i}=f_{4+i}^{2} $$

$$ (i i i)\ f_{4+\log(N)}=1 $$

$$ f(X) $$

$$ \mathbb{V}_{n} $$

$$ f_{i}^{\prime}s,,\mathrm{i.e} $$

n Lemma 1. Let z(X) be a polynomial of degree 1*, n* = log(N) + 6 and such that = 1*: If there exists* a polynomial f(X) 2 F[X] such that

$$ n=\log(N)+6 $$

$$ \sigma^{n}=1 $$

$$ f(X)\in\mathbb{F}[X] $$

1. f (X) = z(X) for 1*;.*

$$ f(X)=z(X),f o r,1,\sigma. $$

2 2. f ()(1) = f(1) f ()

$$ f \left(\sigma^ {2}\right) (1 - \sigma) = f (1) - f (\sigma) $$

3 2 3. f () = f () f ()

$$ f!(\sigma^{3})!=\sigma f\!(\sigma^{2}!\ -f!!(\sigma!) $$

4 3 2 4. f ()f () = f ()

$$ f(\sigma^{4})f(\sigma^{3})=f(\sigma^{2}) $$

4+i+1 4+i 2 5. f () = f (), for all i = 0*;:::;* log(N) 1

$$ f!(\sigma^{4+i+1})=f!(\sigma^{4+i})^{2} $$

$$ i=0,\dots,\log(N)-1 $$

$$ f(\sigma^{5+\log(N)}\sigma^{-1})=1 $$

b Then, z(X) = aX b where is an N -th root of unity. a

$$ \frac{b}{a} $$

The proof is given in AppendixCand we also depict the constraints acting on the evaluations of f (X) in Fig.2. In this Lemma we have assumed for simplicity that n = log(N) + 6 divides jFj, however it is possible to remove this requirement with appropriate padding.

$$ n=\log(N)+6 $$

$$ f(X) $$

The prover will construct the polynomial f (X) as

$$ \ f(X)=(a-b)\rho_{1}(X)+(a\sigma-b)\rho_{2}(X)+a\rho_{3}(X)+b\rho_{4}(X)+\textstyle\sum_{i=0}^{\operatorname{l o g}(N)}\left(\frac{a}{b}\right)^{2^{i}}\rho_{5+i}(X). $$

(1)

i and commit to it in zero-knowledge. Then, it will show it is correct by comparing f () wⁱth the corresponding values from the constraints in Lemma1. Namely, for some chosen by the verier, it

$$ f(\sigma^{i}) $$

Figure 2: Coecients of f (X) in the basis f_s(X)g and relation with those in z(X) in Lemma1.

$$ {left\race{\rho_{s}(X)}}} $$

$$ z(X) $$

1 2 sets₁=,₂= and sends v₁ = f (₁) and v₂ = f (₂) along with the corresponding proofs of opening. Given v₁;v₂ it then shows that the following polynomial, which proves the constraints in Lemma1, evaluates to 0 in :

$$ \alpha_{1}=\sigma^{-1}\alpha,,\alpha_{2}=\sigma^{-2}\alpha $$

$$ v_{1}=f(\alpha_{1}) $$

$$ v_{2}=f(\alpha_{2}) $$

$$ v_{1},v_{2} $$

$$ \begin{aligned}{p_{\alpha}(X)=}&{{}-h(X)z_{V_{n}}(\alpha)+\big(f(X)-z(X)\big)(\rho_{l}(\alpha)+\rho_{2}(\alpha))+\big((1-\sigma)f(X)-f(\alpha_{2})+f(\alpha_{1})\big)\rho_{3}(\alpha)}\ {}&{{}+\big(f(X)+f(\alpha_{2})-\sigma f(\alpha_{1})\big)\rho_{4}(\alpha)+\big(f(X)f(\alpha_{1})-f(\alpha_{2})\big)\rho_{5}(\alpha)}\ {}&{{}+\big(f(X)-f(\alpha_{1})f(\alpha_{1})\big)\prod_{i\notin[0,\ldots,i+\operatorname{l o g}(N)]}(\alpha-\sigma^{i})+\big(f(\alpha_{1})-1\big)\rho_{n}(\alpha).}\ \end{aligned} $$

Note that the polynomials that are already evaluated in in p (X) are such that either the verier can compute them, or they are opened by the prover.

$$ p_{\alpha}(X) $$

Using v₁;v₂, the commitments to h(X);f(X) and after computingi() for i = 1*;* 2*;* 3*;* 4*;n* 1*;n* and Q i i62[5_{;:::;4+log(N)]}(), the verier computes a commitment [P]₁to p (X) and checks that (i) v₁;v₂ 1 2 are correct openings of f (X) at₁= and₂=, (ii) 0 is a correct opening of p (X) at, and (iii) [z]₂has degree 1.

$$ v_{1},v_{2} $$

$$ h(X),f(X) $$

$$ \rho_{i}(\alpha) $$

$$ i=1,2,3,4,n-1,n $$

$$ \textstyle{\prod_{i\not\in[5,\ldots,4+\log(N)]}(\alpha-\sigma^{i})} $$

$$ [P]{1};\mathrm{t o};p{\alpha}(X) $$

$$ (i)\ v_{1},v_{2} $$

$$ \alpha_{1}=\sigma^{-1}\alpha $$

$$ f(X) $$

$$ \alpha_{2}=\sigma^{-2}\alpha,,(i i),,0 $$

$$ p_{\alpha}(X) $$

$$ \alpha. $$

d 1 For this last check, we ask the prover to include a term X z(X) in h(X) and then the verier d computes [P]¹without the terms including z(X), i.e, without X z(X)z^Vn() z(X)(¹() +²()). It will instead add them in the group via the pairing later, to assure that it cannot be the case that deg(z) > 1, unless deg(p) > d, which is not possible under the AGM.

$$ X^{d-1}z(X) $$

$$ h(X) $$

$$ [ P ] _ {1} $$

$$ z(X) $$

$$ -X^{d}z(X)z_{V_{n}}(\alpha)-z(X)(\rho_{1}(\alpha)+\rho_{2}(\alpha)) $$

$$ \deg(z)>1 $$

$$ \operatorname{d e g}(p_{\alpha})>d $$

We describe the interactive protocol in Fig.3. In order to turn this public-coin interactive argument into a NIZK we can apply the Fiat-Shamir heuristic: all challenges sent by the verier are instead generated from a cryptographic hash function.

Theorem 2. The protocol in Fig.3is a knowledge-sound argument (as dened in Def.A.1) for relation R_unityif KZG is a sound polynomial commitment scheme, under the the Algebraic Group and Random Oracle models. When used as a building block in the argument of Figure1, the whole protocol satises zero-knowledge³.

$$ \mathsf{R}_{\mathsf{u n i t y}} $$

Intuition. We rst dene an extractor that will use the algebraic representations provided by the adversary. We must show that the output of this extractor is a valid witness with overwhelming probability. The proof proceeds via a series of games where the nal game is statistically hard. Game₀ is the knowledge soundness game for the protocol in Fig3. Game₁ is dened by Game₀ except that it checks whether f (₁) = v₁, f (₂) = v₂ and p () = 0. The advantage of A in Game₁ is negligible close to the one in Game₀ or it breaks soundness of the KZG polynomial commitment scheme. Game₂ is dened as Game₁ except that it also checks whether the degree of z(X), the algebraic representation of [z]₂, is one. Note that if deg(z) > 1 then p(X), the algebraic representation of [P]₁, would be a polynomial of degree higher than d, where d is the bound for the powers of x the adversary has access to. The advantage of the d+1 adversary in Game₂ then is the same as in Game₁ unless they are able to break qDHE and compute [x].

$$ f(\alpha_{1})=v_{1},f(\alpha_{2})=v_{2} $$

$$ p_{\alpha}(\alpha)=0 $$

$$ \mathsf{G a m e_{1}} $$

$$ \mathsf{G a m e_{2}} $$

$$ [z]_{2} $$

$$ d e g(z)>1 $$

$$ z(X) $$

$$ [P]_{1} $$

$$ p(X) $$

$$ [x^{d+1}. $$

Now, because is sent by the verier after the prover sends [F]₁; [H]₁, under the ROM we have that d 1 either p(X) (_n(X) +₁(X)) + z_Vn(X)X z(X) = 0 or is one of its roots, so we conclude that the polynomial equation holds with overwhelming probability. Finally, note that its evaluation in each of the elements of V_n, implies satisability of one of the constraints in Lemma1and as it includes them all, we have well formation of the polynomial z(X) such that [z]₂= [z(x)]₂.

$$ [F]{1},[H]{1} $$

$$ p(X)-\big((\rho_{n}(X)+\rho_{1}(X))+z_{V_{n}}(X)X^{d-1}\big)z(X)=0 $$

$$ \mathbb{V}_{n} $$

$$ z(X) $$

$$ [z]{2}=[z(x)]{2} $$

³When used as an independent argument, [z] must be an output of the prover in the rst round, or in any round of the 2 main scheme when plugged into other protocols.

Common input: [z]₂ $ 2 Prover: Sample r₀;r₁;r₂;r₃ F and let r(X) r₁ + r₂X + r₃X ^log(N)i X a² f (X) = (a b)₁(X) + (a b)₂(X) + a₃(X) + b₄(X) +5+i(X) b i=0

• r₀₅₊log(_N)(X) + r(X)zVn(X); 2 1 p(X) = f (X) (aX b)1(X) +2(X) + (1)f (X) f ( X) + f ( X)3(X) 2 1 1 2
• f (X) + f ( X) f ( X)4(X) + f (X)f ( X) f ( X)5(X) Y 1 1 i 1
• f (X) f ( X)f ( X) (X) + f ( X) 1n(X); i62[5; 4+log(N)] ^(p(X)^( d 1 Set h X) =, h(X) = h X) + X z(X) and output ([F]₁= [f (x)]₁; [H]₁= [h(x)]₁). zVn(X) Verier : Send challenge 2 F 1 2 Prover :₁=,₂=; p (X) = z_Vn()h(X) + f (X) z(X)₁() +₂() + (1)f (X) f (₂) + f (₁)₃()
• f (X) + f (₂) f (₁)⁴() + f (X)f (¹) f (₂)₅() Y i
• f (X) f (₁)f (₁) () + f (₁) 1_n(); i62[5; 4+log(N)] Compute ((v₁;v₂);₁) KZG*:* Open(srs_KZG;f(X);deg =?;(₁;₂)) (0*;₂) KZG:* Open(srs_KZG;p (X);deg =?;); and output v₁;v₂;₁;₂. 1 2 Verier : Set₁=;₂=, [P]¹= z_Vn()[H]₁+₁() +²() [F]₁+₃() (1)[F]₁+ v₁ v₂ +⁴() [F]₁+ v₂ v₁ Y i 2 +₅() v₁[F]₁v₂ +_n() v₁ 1 + () [F]₁v₁; i62[5*;:::;4+log(N)] Parse₂= [q]₁and accept if* and only if 1 KZG*:* Verify srs_KZG; [F]₁;deg =?;(₁;₂); (v₁;v₂);₁; d 1 e [P]₁;[1]₂+ e (₁() +₂()) z_Vn⁽⁾[x]¹; [z]₂= e [q]₁; [x]₂

$$ r_{0},r_{1},r_{2},r_{3}\xleftarrow{\mathfrak{F}}\mathbb{F} $$

$$ r(X)\leftarrow r_{1}+r_{2}X+r_{3}X^{2} $$

$$ \begin{aligned}{f(X)}&{{}=(a-b)\rho_{1}(X)+(a\sigma-b)\rho_{2}(X)+a\rho_{3}(X)+b\rho_{4}(X)+\sum_{i=0}^{\operatorname{l o g}(N)}\left(\frac{a}{b}\right)^{2i^{i}}\rho_{5+i}(X)}\ {}&{{}+r_{0}\rho_{5+\operatorname{l o g}(N)}(X)+r(X)z_{Y_{n}}(X),}\ \end{aligned} $$

$$ \begin{aligned}{p(X)}&{{}=\big(f(X)-(a X-b)\big)\big(\rho_{1}(X)+\rho_{2}(X)\big)+\big((1-\sigma)f(X)-f(\sigma^{-2}X)+f(\sigma^{-1}X)\big)\rho_{3}(X)}\ {}&{{}+\big(f(X)+f(\sigma^{-2}X)-\sigma f(\sigma^{-1}X)\big)\rho_{4}(X)+(f(X)f(\sigma^{-1}X)-f(\sigma^{-2}X))\rho_{5}(X)}\ {}&{{}+\big(f(X)-f(\sigma^{-1}X)f(\sigma^{-1}X)\big)\sum_{i\in[5]:\ 4+\operatorname{l o g}(N)]}(X-\sigma^{i})+\big(f(\sigma^{-1}X)-1)\rho_{0}(X),}\ \end{aligned} $$

$$ \begin{array}{r}{\operatorname{e t}\ hat h X\ {\hat{h}}(X)=\frac{p(X)}{z_{V_{0}}(X)},\ h(X)=\hat{h}(X)+X^{d-1}z(X)\ \mathrm{a a n~o u t p u t}\ ([F]{1}=[f(x)]{1},[H]{1}=[h(x)]{1}).}\end{array} $$

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

$$ \alpha_{1}=\sigma^{-1}\alpha,,\alpha_{2}=\sigma^{-2}\alpha; $$

$$ \begin{array}{l} p _ {\alpha} (X) = - z _ {V _ {n}} (\alpha) h (X) + \left(f (X) - z (X)\right) \left(\rho_ {1} (\alpha) + \rho_ {2} (\alpha)\right) + \left((1 - \sigma) f (X) - f \left(\alpha_ {2}\right) + f \left(\alpha_ {1}\right)\right) \rho_ {3} (\alpha) \ + \left(f (X) + f \left(\alpha_ {2}\right) - \sigma f \left(\alpha_ {1}\right)\right) \rho_ {4} (\alpha) + \left(f (X) f \left(\alpha_ {1}\right) - f \left(\alpha_ {2}\right)\right) \rho_ {5} (\alpha) \ + \left(f (X) - f \left(\alpha_ {1}\right) f \left(\alpha_ {1}\right)\right) \prod_ {i \notin [ 5; 4 + \log (N) ]} \left(\alpha - \sigma^ {i}\right) + \left(f \left(\alpha_ {1}\right) - 1\right) \rho_ {n} (\alpha), \ \end{array} $$

$$ \ \ {}{((\upsilon{1},\upsilon_{2}),\pi_{1})}\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s}{\mathsf{K Z G}},f(X),\operatorname{d e g}=\bot,(\alpha{1},\alpha_{2})) $$

$$ (0,\pi_{2})\xleftarrow{}\mathsf{K Z G.O p e n}(\mathsf{s r s}{\mathsf{K Z G}},p{\alpha}(X),\operatorname{d e g}=\bot,\alpha), $$

$$ \big(v_{1},v_{2},\pi_{1},\pi_{2}\big) $$

$$ \alpha_{1}=\sigma^{-1}\alpha;,\alpha_{2}=\sigma^{-2}\alpha. $$

$$ \mathrm{}{}+\rho_{5}(\alpha)\big(v_{1}[F]{1}-v{2}\big)+\rho_{n}(\alpha)\big(v_{1}-1\big)+\prod_{i\not\in[5,\dots,4+\operatorname{l o g}(N)]}(\alpha-\sigma^{i})\big([F]{1}-v{1}^{2}\big), $$

$$ \pi_{2}=[q]_{1} $$

Figure 3: NIZK argument of knowledge for R_unityand deg(z) 1.

$$ \mathsf{R}_{\mathsf{u n i t y}} $$

$$ \deg(z)\leq1 $$

The full proof is in AppendixD.

7 Lookup tables for hiding values

In this section we present the algorithms for position-hiding linkability of KZG vector commitment schemes. The aim is to prove that a commitment cm contains a subset of some larger vector committed in C. We refer to a subset and not to a subvector since our scheme proves that all the elements committed in cm are also committed in C, but with no specic order and possible repetitions. This is essentially a lookup table if we consider that C contains the honestly generated table.

Concrete eciency. Our lookup proof has preprocessing time for C of N logN G₂ operations, for N the size of the table. Prover time is mlog(N) scalar multiplications for m the size of the subset, proof size is constant and verier time log logN scalar multiplications and constant number of pairing checks; additionally, update of proofs can be done in O(N) G₂ operations;

$$ {textit\textbf N{G}}_{2} $$

$$ O(N)\ \mathbb{G}_{2} $$

Preliminaries We will consider three evaluation domains

N 1

1. H = f1*;!;:::;! g* is a group of roots of unity with Lagrange and vanishing polynomials N f_i(X)g_i=1;z_H(X).

$$ \mathbb{H},=,\left{1,\omega,\ldots,\omega^{N-1}\right} $$

$$ {\lambda_{i}(X)}{i=1}^{N},z{H}(X) $$

i 1 2. For subset H_I= f! gⁱ2Iof H dened by I [N], f_i(X)g_i2Iis the set of its interpolation Lagrange polynomials with degree jIj 1 and z_I(X) its vanishing polynomial. Note that typically H_Iis not a subgroup.

$$ \mathbb{H}{I},=,{\omega^{i-1}}{i\in I} $$

$$ I,\subset,[N],,{\tau_{i}(X)}_{i\in I} $$

$$ |I|-1 $$

$$ z_{I}(X) $$

3. For some constant m that bounds the size of the vector committed in cm, we consider another m 1 m group of roots of unity V_m= f¹;;:::; g, where = 1, as well as its Lagrange and vanishing m polynomials, f_j(X)g_j=1and z_Vm(X).

$$ \mathbb {V} _ {m} = {1, \nu , \dots , \nu^ {m - 1} } $$

$$ \nu^{m}=1 $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ z _ {V _ {m}} (X) $$

7.1 Technical Overview

Our scheme uses as subprotocol a NIZK argument of knowledge for relation R_unity, (

$$ \mathsf{R}_{\mathsf{u n i t y}} $$

$$ R_{\mathsf{o r s s f}}=\Bigg{(\mathsf{s r s},[z_{I}]{2},N;\ (I,r)):\ I\subset[N]\ \wedge\ [z{I}]{2}=r\prod{i\in I}[x-\omega^{i-1}]_{2},\ \operatorname{s.t.}(\omega^{i-1})^{N}=1,\forall i\in I\Bigg} $$

The proof for this relation will be divided in two parts, one is a proof of relation

$$ R _ {\mathrm {u n i t y}} ^ {\prime} = \left{\left(\mathsf {s r s}, [ u ] _ {1}, \mathbb {H}, \mathbb {V}\right): [ u ] _ {1} = [ u (x) ] _ {1} \text {f o r} u (X) \text {s . t .} \forall \nu^ {j} \in \mathbb {V}, u (\nu^ {j}) = \omega^ {i}, \text {f o r s o m e} \omega^ {i} \in \mathbb {H} \right}, $$

and the other a proof that there exists some polynomial H(X) s.t. zI(u(X)) = zVmH(X). P

$$ H(X),{\mathrm{s.t.}},,z_{I}(u(X))=z_{V_{m}}H(X) $$

N In our protocol, the prover takes as input a commitment C(X) =_i=1c_{i i}(X) to the lookup table ~c, a structured reference string srs, a commitment 2 3

$$ C(X)=\sum_{i=1}^{N}c_{i}\lambda_{i}(X) $$

$$ \vec{c}, $$

$$ \mathsf{c m}=\left[\phi(x)\right]{1}=\left[\sum{j=1}^{m}a_{j}\mu_{j}(x)+a_{m+1}z_{V_{m}}(x)\right]_{1} $$

to some vector ~a and the opening witness ~a = (a₁;:::;a^m+1). Here Pa_m⁺¹is a random eld element that m blinds cm. The prover must show that it knows an opening (X) =_j=1a_{j j}(X) + a_m+1z_Vm(X) to cm N such that a_j2fc_ig_i=1for all 1 j m. The full argument is given in Fig.4and can be divided into three steps.

$$ {\vec{a}}=(a_{1},\ldots,a_{m+1}) $$

$$ \vec{a} $$

$$ a_{m+1} $$

$$ \textstyle\phi(X)=\sum_{j=1}^{m}a_{j}\mu_{j}(X)+a_{m+1}z_{V_{m}}(X) $$

$$ a_{j}\in\left{c_{i}\right}_{i=1}^{N} $$

$$ 1\leq j\leq m $$

First, the prover considers the subset I [N] such that for all j = 1*;:::;m*, a_j= c_ifor some i 2 I, and constructs the subvector ~cI= (ci)i2Iof c. It commits to it in the Lagrange basis corresponding P i ₁ to f! g_i2I; namely, C_I(X) =_i2Ic_{i i}(X). Basically, the prover isolates the elements of *c* that will compare with ~a so they can work with polynomials of smaller degree.

$$ I\subset[N] $$

$$ j=1,\dots,m,,a_{j}=c_{i} $$

$$ i\in I, $$

$$ \ \ {\vec{c}}{I}=(c{i})_{i\in I} $$

$$ {\omega^{i-1}}_{i\in I}; $$

$$ C_{I}(X)=\sum_{i\in I}c_{i}\tau_{i}(X) $$

$$ \vec{c} $$

$$ z_{I}(X),H_{1}(X) $$

$$ C_{I}(X) $$

To convince the verier that all the elements in C_I(X) are elements of C(X), it provides commitments to z_I(X);H₁(X) such that C(X) C (X) = z (X)H₁(X):

$$ C(X) $$

$$ \mathcal{C}(X)-\mathcal{C}{I}(X)=z{I}(X)H_{1}(X). $$

(2)

Here is the place where the precomputation is used: C(X) has degree N and so does H₁(X). In order to compute a commitment to H₁(X), we use the method described in Section4.4. This is at the same time the most expensive step in updating a proof whenever C(X) is changed. However, if c_ivalues are updated in known order, and we precompute an opening for_i, then whenever new c_iis available all openings can be updated in O(N) time, hence the claimed update cost.

$$ H_{1}(X) $$

$$ H_{1}(X) $$

$$ 4.4 $$

$$ C(X) $$

$$ O(N) $$

$$ c_{i} $$

$$ \tau_{i:} $$

$$ c_{i} $$

Our challenge now is hiding C_I(X) and z_I(X) from the verier without breaking soundness. In our solution the prover rst demonstrates that z_I(X) is of the right form, meaning it is the vanishing polynomial of some subset H_Iof H; specically, we need not only a hiding commitment but also a zero-knowledge proof of well formation of z_I(X).

$$ C_{I}(X) $$

$$ z_{I}(X) $$

$$ z_{I}(X) $$

$$ \mathbb{H}_{I} $$

$$ z_{I}(X) $$

We divide the proof of well formation of zI(X) in two steps. First, the prover creates the polynomial Pm ij i 1 u(X) =_j=1!_j(X) of degree m 1 whose coecients are the roots of unity f! g_i2Iand prove, j in zero knowledge, its well formation. For that, it demonstrates that for all 2 V it is the case that ^{j N}0 (u()) = 1, via a call to a subprotocol _unitythat we describe in Section7.2. This guarantees that u(X) is a commitment to elements in H. Secondly, on input a commitment to u(X) as above and given that u(X) passes the verication of _unity0, we prove well formation of z_I(X) and thus that it satises m relation Runity. To achieve this we use the fact that all the coecients of u(X) in the basis f_j(X)g_j=1 are roots of z_I(X). For that, prover convinces verier that

$$ u(X)=\sum_{j=1}^{m}\omega^{i_{j}}\bar{\mu_{j}}(X) $$

$$ z_{I}(X) $$

$$ m-1 $$

$$ {\omega^{i-1}}_{i\in I} $$

$$ \nu^{j}\in\mathbb{V} $$

$$ (u(\nu^{j}))^{N}=1 $$

$$ \Pi_{\ i n i t y^{\prime}} $$

$$ u(X) $$

$$ u(X) $$

$$ \Pi_{\mathsf{u n i t y}^{\prime}} $$

$$ z_{I}(X) $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ R_{\mathsf{u n i t y}} $$

$$ u(X) $$

$$ z_{I}(X) $$

$$ z_{I}(u(X))=z_{V_{m}}(X)H_{2}(X),\ \mathrm{f o rs o m ep o l y n o m i a l}\ H_{2}(X). $$

(3)

Finally, note that C_I(X) has been committed to in an unknown-to-the-verier Lagrange basis, which is f_i(X)g. So the last step of our argument consists on linking the commitment to C_I(X) with [ (x)]₁, which is an input to the argument and a commitment to the same element in a known basis. The prover does so by providing H₃(X) such that

$$ C_{I}(X) $$

$$ {\tau_{i}(X)} $$

$$ C_{I}(X) $$

$$ [ \phi (x) ] $$

$$ H_{3}(X) $$

$$ {{C{I}}(u(X))-\phi(X)=z_{V_{m}}(X)H_{3}(X).} $$

(4)

In order to achieve zero-knowledge, upon receiving an aggregation challenge from the verier, the prover actually provides one commitment [H₂]₁+ [H₃]₁to prove equations3and4together.

$$ [H_{2}]{1}+\chi[H{3}]_{1} $$

Note that for equation2to be satised, C_I(X) cannot take more than once each of the coecients of C(X). On the other hand, when linking C_I(X) and (X) through equation4, we can only prove that all m the coecients of (X) in the basis f^j(X)g^j=1are also coecients of C^I(X) in the basis fⁱ(X)g_i2I, but we cannot say in which order or how many times each of them appears. At the end, what we get, is a lookup table argument that assures that some element [ (x)]₁is a commitment in the Lagrange basis m f^j(X)g^j=1to so^me vector ~a = (a₁;:::;a^m) such that for all j = 1*;:::;m* there exists some i 2 I such that a_j= c_i, i.e., a lookup table for potentially repeated indexes.

$$ C_{I}(X) $$

$$ C(X) $$

$$ C_{I}(X) $$

$$ \phi(X) $$

$$ \phi(X) $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ {\tau_{i}(X)}_{i\in I}. $$

$$ C_{I}(X) $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ [\phi(x)]_{1} $$

$$ {\vec{a}}=(a_{1},\ldots,a_{m}) $$

$$ i\in I $$

$$ j=1,\ldots $$

$$ a_{j}=c_{i}, $$

Theorem 3. Suppose that the argument of Fig.4is instantiated with a knowledge-sound scheme for relation R⁰^unity. Then in the AGM with non-programmable ROs, either the argument of Fig.4implies linkability for the vector commitment schemes of C and cm*, or there exists an adversary that breaks the* q-SDH assumption.

$$ \mathcal{R}_{\mathsf{u n i t y}}^{\prime} $$

Intuition. We prove linkability through a sequence of games. Game₀ is the linkability game for the protocol of Fig.4. Game₁ additionally checks that: (i) [u]₁is the commitment to a polynomial u(X) such that u() = v₁, (ii) [P]₁encodes a polynomial P₁(X) = z_I(X) + C_I(X) such that P₁(v₁) = v₂, i.e, P₁(u()) = z_I(u()) + C_I(u()) = v₂, and (iii) [P]₂is the commitment to a polynomial P₂(X) = v₂ (X) z_Vm()H₂(X) such that P₂() = 0, that is, z_I(u()) +C_I(u()) () = z_Vm()H₂(). Soundness of the KZG polynomial commitment scheme assures that the advantages of A in both games have a negligible dierence.

$$ q{\ -D}{!H} $$

$$ u(X) $$

$$ u(\alpha)=v_{1},,(i i),[P]_{1} $$

$$ P_{1}(X)=z_{I}(X)+\chi\mathcal{C}_{I}(X) $$

$$ P_{1}(v_{1})=v_{2} $$

$$ P_{1}(u(\alpha))=z_{I}(u(\alpha))+\chi C_{I}(u(\alpha))=v_{2}. $$

$$ P_{2}(X)= $$

$$ v_{2}-\chi\phi\big(X\big)-z_{V_{m}}\big(\alpha\big)H_{2}\big(X\big) $$

$$ P_{2}(\alpha)=0 $$

$$ z_{I}(u(\alpha))+\chi C_{I}(u(\alpha))-\chi\phi(\alpha)=z_{V_{m}}(\alpha)H_{2}(\alpha) $$

j N Game₂ behaves identically to Game₁ but it also veries that u(X) is such that u() = 1. The advantage of A in Game₂ is then the same as in Game₁, due to knowledge soundness of the argument for R⁰^unity. Game₃ works as Game₂ but further checks that (iv) C(X) C^I(X) = z_I(X)H₁(X). The advantage of the adversary in Game₃ is the same as in Game₂, unless the trapdoor x is a root to the polynomial, in which case we can use A as a subroutine for a successful adversary against qSDH. This

$$ u(X) $$

$$ u(\nu^{j})^{N}=1 $$

$$ \mathsf{G a m e_{2}} $$

$$ \mathsf{G a m e_{1}} $$

$$ \mathcal{R}_{\mathsf{u n i t y}}^{\prime}. $$

$$ ({i v})::C(X)\ -\ C C_I(X):=:z_{I}(X)H_{1}(X) $$

$$ \mathsf{G a m e_{2}} $$

$$ \mathsf{G a m e_{3}} $$

$$ \mathcal{A} $$

PN Common input: C = [C(x)]₁; for C(X) = c_{i i}(X) and cm = [ (x)]₁. i=1 Prover: Take as input srs and (X) and proof [Q(x)]₂attesting that fc_ig_i2Iare openings of C. I.e., P C(X)i2Ici i (X) a commitment to Q₍X₎ =_Q. _{(X!i 1) i2I} $ Choose blinders r₁;r₂;r₃;r₄;r₅;r₆;r₇ F uniformly at random. i 1 For H^I= f! gⁱ2I, compute the interpolation polynomials fⁱ(X)g^i2I. Q P i 1 2 Dene z_I(X) = r₁_i2I(X*!) and C_I(X) = ci i(X) + (r₂ + r₃X + r₄X)zI(X). i2I Compute [H₁(x)]2= [r1 1Q(x) (r₂ + r₃x + r₄x²)]2. ij i 1 Dene! as the jth element in f! gⁱ2Iand compute Xm ij u(X) =!^j(X) + (r₅ + r₆X + r₇X²)z_Vm(X):* j=1 00 Compute a proof_unityas in Fig.5, proving that [u]₁satises R_unity. Output [C_I]₁= [C_I(x)]₁; [z_I]₁= [z_I(x)]₁; [u]₁= [u(x)]₁; [H₁]₂= [H₁(x)]₂; _unity0. Verier: Send challenge 2 F Prover: F_ind H₂(X) such that z_I(u(X)) + (C_I(u(X)) (X)) = z_Vm(X)H₂(X) Output [H₂]₁= [H₂(x)]₁;. Verier : Send challenge 2 F Prover : Compute p₁(X) z_I(X) + C_I(X) p₂(X) z_I(u()) + (C_I(u()) (X)) z_Vm()H₂(X) (v₁;₁) KZG*:* Open(srs_KZG;u(X);deg =?;) (v₂;₂) KZG*:* Open(srs_KZG;p₁(X);deg =?;v₁) (0*;₃) KZG:* Open(srs_KZG;p₂(X);deg =?;) Output v₁;v₂;₁;₂;₃. Verier : Compute [P₁]₁[z_I]₁+ [C_I]₁and [P₂]₁v₂ cm z_Vm()[H₂]₁. Accept if and only if (i) V 0 accepts, (ii) unity 1 KZG*:* Verify srs_KZG; [u]₁;deg =?;;v₁;₁ 1 KZG*:* Verify srs_KZG; [P₁]₁;deg =?;v₁;v₂;₂ 1 KZG*:* Verify srs_KZG; [P₂]₁;deg =?;;0;₃; and (iii) e [C]₁[C_I]₁;[1]₂= e [z_I]₁; [H₁]₂(5)

$$ {\mathsf{c m}}=[\phi(x)]. $$

$$ {\mathsf{C}}=[C(x)]{1},\ {\mathrm{f o r}}\ C(X)=\sum{i=1}^{N}c_{i}\lambda_{i}(X) $$

$$ \phi(X) $$

$$ [Q(x)]_{2} $$

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

$$ \textstyle\ \ dot Q X\dotdot{=\ frac C C(X)-\sum_{i\in I}c_{i}\tau_{i}(\dot{X})}{\prod_{i\in I}(X-\omega^{i-1})} $$

$$ r_{1},r_{2},r_{3},r_{4},r_{5},r_{6},r_{7}\overset{\mathfrak{S}}{\leftarrow}\mathbb{F} $$

$$ \mathbb{H}{I}={\omega^{i-1}}{i\in I} $$

$$ {\tau_{i}(X)}_{i\in I}. $$

$$ \textstyle{\operatorname{X e f i n e}}z_{I}(X)=r_{1}{\textstyle\prod_{i\in I}}(X-\omega^{i-1})\ {\operatorname{a n d}}\ C_{I}(X)=\sum_{\sim}c_{i}\tau_{i}(X)+(r_{2}+r_{3}X+r_{4}X^{2})z_{I}(X). $$

$$ [H_{1}(x)]{2}=[r{1}^{-1}Q(x)-\ r_{2}+r_{3}x+r_{4}x^{2})]_{2}. $$

$$ \omega^{i_{j}} $$

$$ {\omega^{i-1}}_{i\in I} $$

$$ u(X)=\sum_{j=1}^{m}\omega^{i_{j}}\mu_{j}(X)+(r_{5}+r_{6}X+r_{7}X^{2})z_{V_{m}}(X). $$

$$ \pi_{\sf u n i t y^{\prime}} $$

$$ [u]_{1} $$

$$ R_{\mathsf{u n i t y}}^{\prime}. $$

$$ \operatorname{O u t p u t}\ [C_{I}]{1}=[C{I}(x)]{1},:[z{I}]{1}=[z{I}(x)]{1},:[u]{1}=[u(x)]{1},:[H{1}]{2}=[H{1}(x)]{2},:\pi{\mathsf{o n i f}^{\prime}}. $$

$$ \chi\in\mathbb{F} $$

$$ z_{I}(u(X))+\chi(C_{I}(u(X))-\phi(X))=z_{V_{m}}(X)H_{2}(X) $$

$$ H_{2}(X) $$

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

$$ p_{1}(X)\gets z_{I}(X)+\chi C_{I}(X) $$

$$ p_{2}(X)\leftarrow z_{I}(u(\alpha))+\chi(C_{I}(u(\alpha))-\phi(X))-z_{V_{m}}(\alpha)H_{2}(X) $$

$$ (\upsilon_{1},\pi_{1})\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s}_{\mathsf{K G G}},u(X),\operatorname{d e g}=\bot,\alpha) $$

$$ (v_{2},\pi_{2})\xleftarrow{}\mathsf{K Z G.O p e n}(\mathsf{s r s}{\mathsf{K Z G}},p{1}(X),\operatorname{d e g}=\bot,v_{1}) $$

$$ (0,\pi_{3})\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s}_{\mathsf{K G G}},\mathit p{_22(X),,\operatorname{d e g}}=\bot,\alpha) $$

$$ \left(v_{1},v_{2},\pi_{1},\pi_{2},\pi_{3}\right) $$

$$ [P_{1}]{1}\leftarrow[z{I}]{1}+\chi[C{I}]{1}\mathrm{a n d}[P{2}]{1}\leftarrow v{2}-\chi\mathsf{c m}-z_{V_{m}}(\alpha)[H_{2}]_{1}. $$

$$ ()V{{}}{}{{pi{\mathsf n i i y}^{\prime}}}{{{}_{\mathsf{}n}i t{Y{}}}} $$

$$ 1 \leftarrow \mathrm {K Z G}. \operatorname {V e r i f y} \left(\mathrm {s r s} _ {\mathrm {K Z G}}, [ u ] _ {1}, \deg = \bot , \alpha , v _ {1}, \pi_ {1}\right) $$

$$ 1\gets\mathsf{K Z G.V e r i f y}\big(\mathsf{s r s}{\mathsf{K Z G}},[P{2}]{1},\mathsf{d e g}=\bot,\alpha,0,\pi{3}\big),\ mathrm\ n $$

$$ (i i i);;e\big([C]{1}-[C{I}]{1},[1]{2}\big)=e\big([z_{I}]{1},[H{1}]_{2}\big) $$

Figure 4: Lookup table for non-repeated indexes that uses a proof for R⁰_unityas blackbox.

$$ \mathsf{R}_{\mathsf{u n i t y}}^{\prime} $$ i 1 i 1 polynomial equation implies then that C(!) C_I(!) = 0 for all i 2 I and thus C_I(X) encodes the subvector ~c_Iof ~c. Lastly, we show that the advantage of A in Game₃ is negligible.

$$ C(\omega^{i-1})-C_{I}(\omega^{i-1})=0 $$

$$ C_{I}(X) $$

$$ i\in I $$

Because was sent after prover sends [C_I]₁; [z_I]₁; [u]₁, [H₁]₁and [H₂]₁, except with negligible probability, condition (iii) holds as a polynomial equation for all X, that is, z_I(u(X)) + C_I(u(X)) (X) = z_Vm(X)H₂(X). Similarly, because was sampled by the verier after receiving [C_I]₁; [z^I]¹; [u]₁, and [H₁]₁, we have that there exist H₂₁(X) and H₂₂(X) such that H₂(X) = H₂₁(X) + H₂₂(X), z_I(u(X)) = z_Vm(X)H₂₁(X) and C_I(u(X)) (X) = z_Vm(X)H₂₂(X).

$$ \vec{C}_{I} $$

$$ [C_{I}]{1},[z{I}]{1},[u]{1},;[H_{1}]_{1} $$

$$ [H_{2}]_{1} $$

$$ z_{I}(u(X))+\chi C_{I}(u(X))- $$

$$ \chi\phi(X)=z_{V_{m}}(X)H_{2}(X) $$

$$ H_{21}(X) $$

$$ H_{22}(X) $$

$$ |H_{1}|_{1} $$

$$ [C_{I}]{1},[z{I}]{1},[u]{1} $$

$$ C_{I}(u(X))-\phi(X)=z_{V_{m}}(X)H_{22}(X) $$

$$ H_{2}(X),=,H_{21}\dot{(X)}+\dot{\chi}\dot{H_{22}}\dot{(\dot{X})} $$

m The rst equation says that z_I(X) is a polynomial with the coecients of u(X) in the basis f_j(X)g_j=1 (that are Nth roots of unity) as roots (it may have more); on the other hand, C_I(u(X)) (X) = z_Vm(X)H₂₂(X) implies that the values that C_I(X) takes in the elements of H_Iare the values that (X) takes in V_m.

$$ z_{I}(X) $$

$$ u(X) $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ C_{I}(u(X))-\phi(X)= $$

$$ z_{V_{m}}(X)H_{22}(X) $$

$$ C_{I}(X) $$

$$ \mathbb{H}_{I} $$

$$ \phi(X) $$

The full proof is given in Appendix.E

Subtables There is another nice feature that can be derived by the protocol in Fig.4and is the creation Q of sub-lookup tables. Namely, for some I [N], prover generates t(X) =_i2I(X c_i). To prove well formation of it, after having some C_I(X) that has been proven correct, it shows that there exists some H₃(X) such that t(C~ (X)) = z (X)H₃(X):

$$ I\subset[N] $$

$$ \textstyle t\bigl(X\bigr)=\prod_{i\in I}\bigl(X-c_{i}\bigr) $$

$$ C_{I}(X) $$

$$ t(\tilde{C}{I}(X))=z{V_{m}}(X)H_{3}(X). $$

$$ H_{3}(X) $$

Then, for any polynomial a(X) of degree up to m 1, if there exists H₄(X) such that

$$ a(X) $$

$$ m-1 $$

$$ H_{4}(X) $$

$$ t(a(X))=z_{V_{m}}(X)H_{4}(X), $$

m then the coecients of a(X) in the basis f_j(X)g_j=1are coecients of C_I(X) in basis f_i(X)g_i2I, with no specic order and potential repetitions.

$$ a(X) $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

$$ C_{I}(X) $$

$$ {\tau_{i}(X)}_{i\in I} $$

7.2 Multi-Unity Proof or Proving well formation of u(X)

$$ u(X) $$

The aim of this section is to prove in zero-knowledge that a commitment [u]1is well formed, that is, Pm ij ij encodes the polynomial u(X) =j=1*!_j(X) + r(X)zVm(X), where!* _is the j-th element in I. Pm Namely, that u(X) =_j=1u_{j j}(X) + r(X)z_Vm(X) is such that all its coecients are elements in H and N thus, they are all Nth roots of unity, or what is the same, that u_j= 1 for all j = 1*;:::;m*.

$$ [u]_{1} $$

$$ \omega^{i_{j}} $$

$$ u u(X):=:{\textstyle\sum_{i=1}^{m}}\omega^{i_{j}}\mu_{j}(X)\ {+}\ r(X)z_{V_{m}}(X) $$

$$ utextstyle u(X)=\sum_{j=1}^{m}u_{j}\mu_{j}(X)+r(X)z_{V_{m}}(X) $$

$$ u_{j}^{N}=1 $$

$$ j=1,\ldots,m. $$

n 1 For this argument, we will consider another group of roots of unity V_n= f¹;;:::; g of size n n n = log(N), with = 1, Lagrange interpolation polynomials f_s(X)g_s=1aⁿd vanishing polynomial z_Vn(X).

$$ n=\log(N) $$

$$ \mathbb{V}_{n}={{1,\sigma,\ldots,\sigma^{n-1}}} $$

$$ \sigma^{n}=1 $$

$$ {\rho_{s}(X)}_{s=1}^{n} $$

$$ z_{V_{n}}(X) $$

m Techniques. The prover rst denes ~u₀ = (u₁;:::;u_m) 2 F to be the vector whose elements are the coecients of u(X). They then iteratively dene ~u_j= ~u_{j 1}~u_{j 1}. I.e., they set

$$ {\vec{u}}{0}=\left(u{1},\ldots,u_{m}\right)\in\mathbb{F}^{m} $$

$$ \vec{u}{j}=\vec{u}{j-1}\circ\vec{u}_{j-1} $$

$$ \bullet,{\vec{u}}{1}={\vec{u}}{0}\circ{\vec{u}}{0}=\big(u{1}^{2},\ldots,u_{m}^{2}\big); $$

$$ \bullet\ \ {\operatorname{a n d\ f o r\ a l l\ }}j=2,\ldots,n,:\vec{u}{j}=\vec{u}{j-1}\circ\vec{u}{j-1}=(u{1}^{2^{j}},\ldots,u_{m}^{2^{j}}). $$

They then must prove three conditions to the verier: (i) ~u₀ consists on the coecients of u(X), (ii) equation ~u = ~u ~u holds for all j = 1*;:::;n* 1 and (iii) ~u ~u = ~₁. Together this gives j j 1 j 1 n 1 n 1 that all the coecients u_jare Nth roots of unity.

$$ (left\ i right))\ vec\ u{}_{0} $$

$$ \vec{u}{j}=\vec{u}{j-1}\circ\vec{u}_{j-1} $$

$$ j=1,\ldots,n-1 $$

$$ \vec{u}{n-1}\circ\vec{u}{n-1}=\vec{1}. $$

As we are working with encodings as polynomials rather than vectors, the prover sets u₀(X) = u(X), u_n(X) = id(X) (for id(X) the polynomial that evaluates to 1 over V_m), and shows to the verier that each of the following equations hold:

$$ u_{j} $$

$$ \mathbb{V}_{m}) $$

$$ u_{n}(X)={\mathsf{i d}}(X) $$

$$ u_{0}(X)=u(X) $$

$$ u(X)u(X)-u_{1}(X)\equiv z_{V_{m}}(X)H_{1}(X), $$

$$ \vdots $$

$$ {}{u{n-1}(X)}u_{n-1}(X)-\mathsf{i d}(X)\equiv z_{V_{m}}(X)H_{n}(X), $$

To aggregate all of these checks into one verication equation we consider f_s(Y)g the linear independent Lagrange interpolation polynomials over V_nand demonstrate that !!

$$ \left{\rho_{s}(Y)\right} $$

$$ \mathbb{V}_{n} $$

$$ \left(u^{2}(X)\rho_{1}(Y)+\sum_{s=2}^{n}u_{s-1}^{2}(X)\rho_{s}(Y)\right)-\left(\sum_{s=1}^{n-1}u_{s}(X)\rho_{s}(Y)+\mathsf{i d}(X)\rho_{n}(Y)\right)=z_{V_{m}}(X)h_{2}(X,Y), $$

(6)

In the remainder of this section the prover aims to demonstrate that (6) holds at a challenge point (;).

$$ h_{2}(X,Y) $$

for some polynomial h₂(X;Y).

$$ (\alpha,\beta) $$

Proving (6): Strategy We prove (6) by showing that for some polynomial h₁(Y), the polynomial

$$ h_{1}(Y) $$

$$ \begin{aligned}{p(Y)=\big(\underbrace{u^{2}(\alpha)\rho_{1}(\beta)+\sum_{s=2}^{n}u_{s-1}^{2}(\alpha)\rho_{s}(\beta)+z_{V_{n}}(\beta)(-h_{1}(\beta)}}&{{}+h_{1}(Y))\big)}\{-(bigsum_{s=1}^{n-1}u_{s}(\alpha)\rho_{s}(\beta)+\mathsf{id}(\alpha)\rho_{n}(\beta)\big)-\underbrace{z_{V_{n}}(\alpha)h_{2}(\alpha,Y)}_{\operatorname{Denote~\xi _{1}}}}\\end{aligned} $$

evaluates to 0 at Y =. For this the prover sends several values needed to reconstruct the commitment [P]₁to p(Y), and then provides a proof that [P]₁opens to 0 at.

$$ Y=\beta. $$

$$ [P]_{1}\ {\mathrm{t o}}\ p(Y) $$

$$ [P]_{1} $$

$$ \beta $$

Proving (6): Extra Notation First note that since the polynomials_s(Y) take 1 and 0 values only, we obtain that for all Y 2 V_n

$$ \rho_{s}(Y) $$

$$ Y\in\mathbb{V}_{n} $$

$$ u^{2}(X)\rho_{1}(Y)+\sum_{s=2}^{n}u_{s-1}^{2}(X)\rho_{s}(Y)=\big(u(X)\rho_{1}(Y)+\sum_{s=2}^{n}u_{s-1}(X)\rho_{s}(Y)\big)^{2} $$

Pⁿ We denote U (X;Y) =^s=2u^{s 1}(X)^s(Y) and U (X;Y) = u(X)¹(Y) + U (X;Y) The prover begins by sending one commitment [U]₁to U (X;Y) and a second commitment [h₂] to h₂(X;Y). These are bivariate commitments. While there exist bivariate polynomial commitment schemes [26], these are incompatible with universal power-of-tau setups that are publicly available [23]. We thus instead view U (X;Y) and n n h₂(X;Y) as the univariate polynomials U (X;X) aⁿd h₂(X;X). See Section4.6for more details.

$$ U (X, Y) = u (X) \rho_ {1} (Y) + \bar {U} (X, Y) $$

$$ \bar{U}(X,Y)=\sum_{s=2}^{n}u_{s-1}(X)\rho_{s}(Y) $$

$$ [bar\ U]_{\mathrm1} $$

$$ \ h_{2}] $$

$$ \bar{U}(X,Y) $$

$$ h_{2}(X,Y) $$

$$ h_{2}(X,Y) $$

$$ U(X^{n},X) $$

$$ \bar{U}(X,Y) $$

$$ h_{2}(X^{n},X) $$

The verier responds with a random challenge X =.

$$ X=\alpha $$

Proving (6): Denition of and commitment to h₁ The prover now wishes to nd h₁ such that p(Y) can be fully dened and its commitment can be computed by the verier. They rst provide a partial opening [U]₁to U (;Y) and proves this is consistent with [U]₁. They also open [u(x)]₁at to get v₁ = u(). This allows the verier to compute a commitment to the polynomial U (;Y) as U = [u()]_{1 1}(x) + [U]₁.

$$ h_{1} $$

$$ h_{1} $$

$$ p(Y) $$

$$ \ [\bar{U}{\alpha}]{1} $$

$$ \bar{U}(\alpha,Y) $$

$$ \ \bar U_{\ }1 $$

$$ [ u (x) ] _ {1} $$

$$ v_{1},=,u(\alpha) $$

$$ U(\alpha,Y) $$

$$ U=[u(\alpha)]{1}\rho{1}(x)+[\bar{U}{\alpha}]{1} $$

The prover sends a commitment [h₁]₁= [h₁(x)]₁to h₁(Y) such that

$$ [h_{1}]{1}=[h{1}(x)] $$

$$ h_{1}(Y) $$

$$ \sum_{s=1}^{n}u_{s-1}^{2}(\alpha)\rho_{s}(Y)=\left(U(\alpha,Y)\right)^{2}+h_{1}(Y)z_{V_{n}}(Y). $$

(7)

The verier responds with a second random challenge Y = and then (7) appears as

$$ Y=\beta $$

$$ \sum_{s=1}^{n}u_{s-1}^{2}(\alpha)\rho_{s}(\beta)=\left(U(\alpha,\beta)\right)^{2}+h_{1}(\beta)z_{V_{n}}(\beta) $$

(8)

Proving (6): Degree bound The prover must show that U₁(X; 1) = 0 i.e. that there is no₁(Y) term. This convinces the verier that the rst term of U (;Y) is indeed u()₁(Y). When opening [U]₁ we enforce a degree bound of n 1. This is necessary because we are capturing bivariate polynomials n with a univariate polynomial commitment scheme and we need to enforce that there are ⁿo X terms lingering in U (;X).

$$ \bar{U}_{1}(X,1)=0 $$

$$ \rho_{1}(Y) $$

$$ U(\alpha,Y) $$

$$ u(\alpha)\rho_{1}(Y) $$

$$ n-1 $$

$$ [\bar{U}{\alpha}]{1} $$

$$ X^{n} $$

$$ \bar{U}(\alpha,X) $$

Proving (6): Sending₁The prover communicates₁by opening [U]₁to v₂ at Y = and verier gets 2 2 2 = f(8)g = U (;) = (u() () + U (;)) = (v () + v)

$$ \xi_{1} $$

$$ \xi_{1} $$

$$ \left[\bar{U}{\alpha}\right]{1} $$

$$ v_{2} $$

$$ Y=\beta $$

$$ \xi_{1}=\left{\ (8)\right}=U(\alpha,\beta)^{2}=(u(\alpha)\rho_{1}(\beta)+\bar{U}(\alpha,\beta))^{2}=(v_{1}\rho_{1}(\beta)+v_{2})^{2} $$

Proving (6): Sending2The prover communicates P

$$ \xi_{2}=\sum_{s=1}^{n-1}u_{s}(\alpha)\rho_{s}(\beta) $$

$$ \xi_{2} $$

_n ^{1 2}=_s=1u_s()_s(). To do this we open [U (;Y)] = [U]₁to v₃ at Y = for the generator of V_n. Indeed Xn nX1

$$ [\bar{U}(\alpha,Y)]=[\bar{U}{\alpha}]{1} $$

$$ Y=\sigma\beta $$

$$ v_{3} $$

$$ \sigma $$

$$ \mathbb{V}_{n}. $$

$$ \bar{U}(\alpha,\sigma\beta)=\sum_{s=2}^{n}u_{s-1}(\alpha)\rho_{s}(\sigma\beta)=\sum_{s=1}^{n-1}u_{s}(\alpha)\rho_{s}(\beta) $$

(9)

Proving (6): Finale Finally the verier can compute a commitment to p(Y) as [p(Y)]₁= [(v₂ + ² v₁₁())]₁+ z_Vn()[h₁]₁[v₃ + id()_n()]₁z_Vm()[h₂]₁. Thus the prover nishes by demonstrating that p() = 0.

$$ p(Y) $$

$$ [p(Y)]{1}=[(v{2}+ $$

$$ v_{1}\rho_{1}(\beta))^{2}]{1}+z{V_{n}}(\beta)[h_{1}]{1}-[v{3}+\mathsf{i d}(\alpha)\rho_{n}(\beta)]{1}-z{V_{m}}(\alpha)[h_{2}]_{1} $$

$$ p(\beta)=0 $$

The protocol is shown in Figure5.

Eciency. In the protocol of Fig.4, the work of the prover is dominated by the computation of H(X) and p₂(X) which have degree m², because [H₁] is formed in time m by using the pre-computed individual proofs, and all the other proof elements are commitments to polynomials of degree m. In the protocol of Fig.5, prover work is dominated by the computation of [U]₁and [h₂]₁that are commitments to polynomials of degree mlog(N).

$$ p_{2}(X) $$

$$ H(X) $$

$$ m^{2} $$

$$ [ H _ {1} ] $$

$$ m. $$

$$ \ {bar U}_] $$

$$ [ h _ {2} ] $$

Theorem 4. The protocol in Figure5is a knowledge-sound argument for relation R⁰^unityunder the algebraic group model and random oracle model if the qSDH, qDHE, and qSFrac assumptions hold.

$$ R _ {\mathrm {u n i t y}} ^ {\prime} $$

Intuition. We rst dene an extractor that will use the algebraic representations provided by the adversary. We must show that the output of this extractor is a valid witness with overwhelming probability. The proof proceeds via a series of games where the nal game is statistically hard. Game₀ is the knowledge-soundness game for the protocol in Fig.5. Game₁ behaves identically except that it checks whether u() = v₁, U (1) = 0, U () = v₂, U () = v₃, and p() = 0 for u(X); U (X); p(X) being the algebraic representations of [u]₁; [U]₁; and [P]₁, respectively. Soundness of the KZG polynomial commitment asserts that the dierence of the advantages of A in Game₀ and Game₁ is negligible.

$$ u(\alpha){\ =\ }v_{1},:\bar{U}{\alpha}(1){\ =\ }0,:\bar{U}{\alpha}(\beta){\ =\ }v_{2},:\bar{U}{\alpha}(\beta\sigma){\ =\ }v{3} $$

$$ p(\beta)=0 $$

$$ u(X),,\ {\bar{U}}_{\alpha}(X),,p(X) $$

$$ [P]_{1} $$

$$ [u]{1},[\bar{U}{\alpha}]_{1} $$

Game₂ is the same as Game₁ but it additionally checks that deg(U) n 1 and deg(h₂) n 1, and aborts otherwise. To instantiate the protocol, we use the KZG polynomial commitment with the modication exposed in Section4.2and, as stated there, a prover that outputs a valid proof of opening for a polynomial with higher degree than the one declared, implies an attack to qDHE. Therefore, Game2 Game1qDHE Adv^AAdv^A+ Adv^A.

$$ \ e g(\bar{U}_{\alpha})\leq n-1 $$

$$ d e g(h_{2})\leq n-1 $$

$$ A d\ !{{\mathcal{A}}^{G a m e{2}}}\leq A d v!\ {{\ \mathcal{A}}^{G a m e{1}}}+A!!{\ {dot{\ {}}}mathrm{d d v_{\mathcal{A}}^{q B E}}} $$

Game₃ behaves as Game₂ but additionally veries that U (;Y) = U (Y), h₂(;Y) = h₂_;(Y), for U (X), h₂(X), h₂_;(X), the algebraic representations of [U]₁, [h₂]₁, and [h₂_;]₁. That is, Game₃ checks correctness of the partial evaluations (see Section4.6). In the full proof, we show that if it is not the case, the adversary can be used as a subroutine for a successful adversary against qSFrac.

$$ \bar {U} (\alpha , Y) = \bar {U} _ {\alpha} (Y), h _ {2} (\alpha , Y) = h _ {2, \alpha} (Y) $$

$$ \bar{U}{\alpha}(X),,h{2}(X),,h_{2,\alpha}(X) $$

$$ [\bar{U}{\alpha}]{1},:[h_{2}]_{1} $$

$$ [h_{2,\alpha}]_{1} $$

Finally, since p() = 0 and since [u]₁; [U]₁, [h₁]₁, [h₂]₁have been sent by the prover before it sees challenge, and [u]₁; [U]₁, [h₂]₁before it sees challenge, with overwhelming probability

$$ p(\beta)=0 $$

$$ [u]{1},[\bar{U}]{1},:[h_{1}]{1},:[h{2}]. $$

$$ \beta, $$

$$ [u]{1},[\bar{U}]{1},:[h_{2}]. $$

$$ \begin{aligned}{p(X)}&{{}=\big(u(X)\rho_{1}(Y)+\bar{U}(X,Y)\big)^{2}-h_{1}(X)z_{V_{n}}(Y)}\ {}&{{}-(\bar{U}(X,Y\sigma)+\mathsf{i d}(X)\rho_{n}(Y))-z_{V_{m}}(X)h_{2}(X,Y).}\ \end{aligned} $$

Note that the latter is equation6as at the beginning of Section7.2. That is, it is the aggregation of the constraints that prove u(X) is a polynomial such that all its coecients in the Lagrange basis f_j(X)g are Nth roots of unity.

$$ {\mu_{j}(X)}_{}^{\gamma}} $$

Proof. We proceed through a series of games to show that the protocol dened in Fig.4satises knowledge soundness. We set Game₀ to be the knowledge soundness game as dened in DenitionA.1and consider knowledge-sound an algebraic adversary A against it which has advantage Adv_A() . We dene Game₁ and Game₂ and specify reductions B₁ and B₂ such that

$$ \mathsf{A d v}_{\mathcal{A}}^{\mathsf{k n o w i e g e e-s o u n d}}(\lambda) $$

$$ \ !{\mathcal{B}}{_{1}} $$

$$ \ {{\mathcal{B}}_{2}} $$

$$ \begin{aligned}{}&{{}\mathsf{A d v}{\mathcal{A}}^{\mathsf{k-s o u n d}}(\lambda)=\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{0}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)+\mathsf{A d v}{\mathcal{B}{1}}^{\mathsf{S S D H}}(\lambda)}\ {}&{{}\qquad\qquad\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)+\mathsf{A d v}{\mathcal{A}}^{\mathsf{S S H}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{S S H H}}(\lambda)}\ {}&{{}\qquad\qquad\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{A a m e}{3}}(\lambda)+\mathsf{A d v}{\mathcal{A}}^{\mathsf{S S H H}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{S S H}}(\lambda)+\mathsf{A d v}{\mathcal{B}{3}}^{\mathsf{S S F r a c}}(\lambda)}\ {}&{{}\qquad\qquad\leq\mathsf{A d v}{\mathcal{B}{1}}^{\mathsf{S A H}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{S S H}}(\lambda)+\mathsf{A d v}{\mathcal{B}{3}}^{\mathsf{S S H}}(\lambda)+\mathsf{a d v}{\mathcal{B}_{3}}^{\mathsf{S S F r a c}}(\lambda)}\ \end{aligned} $$

Common input: [u]₁where [u]₁= [u₀(X)]₁ Prover: Take as input srs and u(X) Samples blinders t₁;:::t_nF. Pm s i 2 For s = 1*;:::;n*, dene u (X) =!^j(X) + t z (X), _s j s Vm j=1 Pn Dene U (X;Y) = u_{s 1}(X)_s(Y). s=1 Dene U (X;Y) = U (X;Y) u(X)₁(Y) P_n 2 Dene h₂(X) =s_{=1 s}(Y)H_s(X) for H_s(X) = (u_{s 1}(X) u_s(X))=z_Vm(X) n n Output [U]₁= [U (x;x)]₁; [h₂]₁= [h₂(x;x)]₁ Verier: Send challenge 2 F P_n 2 2 Prover: Dene h₁(Y) U (;Y)_s=1u_{s 1}()_s(Y) =z_Vn(Y) Output [h₁]₁= [h₁(x)]₁ Verier: Send challenge 2 F Prover: p(Y) (U²(;) h₁(Y)z_Vn()) U (;) + id()_n()) z_Vm()h₂(;Y) (v₁;₁) KZG*:* Open srs*;u*(X);deg =?;X = ([U (;x)]₁;₂) KZG*:* Open srs*; U*(X;Y);deg =?;X = ([h₂(;x)]₁;₃) KZG*:* Open srs*;h₂*(X;Y);deg =?;X = ((0*;v₂;v₃*);₄) KZG*:* Open srs*; U*(;Y);deg = n 1;Y = (1*;;) (0;₅) KZG:* Open srs*;p*(Y);deg = n 1;Y = Set [U]₁= [U (;x)]₁; [h₂_;]₁= [h₂(;x)]₁and output [U]₁; [h₂_;]₁;v₁;v₂;v₃;₁;₂;₃;₄;₅ Verier: Compute U v₁₁() + v₂, [P]₁U² [h₁]₁z_Vn() (v₃ + id()_n()) z_Vm()[h₂_;]₁ Accept if and only if 1 = KZG*:* Verify srs_KZG; [u]₁;deg =?;X =;v₁;₁ 1 = KZG*:* Verify srs_KZG; [U]₁;deg =?;X =; [U]₁;₂ 1 = KZG*:* Verify srs_KZG; [h₂]₁;deg =?;X =; [h₂_;]₂;₃ 1 = KZG*:* Verify srs_KZG; [U]₁;deg = n 1;Y = (1*;;);(0;v₂;v₃*);₄ 1 = KZG*:* Verify srs_KZG; [P]₁;deg = n 1;Y =; 0*;*₅

$$ [u]{1}=[u{0}(X)]_{1} $$

$$ u(X) $$

$$ t_{1},\ldots t_{n}\leftarrow\mathbb{F}. $$

$$ \operatorname{r}==1,\ldots,n,\ {\operatorname{d e f i n e}}\ u u_{s}(X)=\sum_{j=1}^{m}\left(\omega^{i_{j}}\right)^{2^{s}}\mu_{j}(X)+t_{s}z_{V_{m}}(X), $$

$$ U(X,Y)=\sum_{s=1}^{n}u_{s-1}(X)\rho_{s}(Y). $$

$$ {\mathrm{D e f i n e}};{\bar{U}}(X,Y)=U(X,Y)-u(X)\rho_{1}(Y) $$

$$ \mathrm{D e f i n e\mathit h}{2}(X)=\sum{s=1}^{n}\rho_{s}(Y)H_{s}(X)\mathrm{f o r~}{H_{s}(X)}=(u_{s-1}^{2}(X)-u_{s}(X))/z_{V_{m}}(X) $$

$$ \mathrm{O u t p u t}\ \big([\bar{U}]{1}=[\bar{U}(x^{n},x)]{1},[h_{2}]{1}=[h{2}(x^{n},x)]_{1}\big) $$

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

$$ \underline{{\mathbf{P r o v e r::}\ mathrm{e f f n e e~}}}h_{1}(Y)\leftarrow\left(U^{2}(\alpha,Y)-\textstyle\sum_{s=1}^{n}u_{s-1}^{2}(\alpha)\rho_{s}(Y)\right)/z_{V_{n}}(Y) $$

$$ \beta\in\mathbb{F} $$

$$ [h_{1}]{1}=[h{1}(x)]_{1} $$

$$ p(Y)\leftarrow\big(U^{2}(\alpha,\beta)-h_{1}(Y)z_{V_{n}}(\beta)\big)-\tilde{U}(\alpha,\beta\sigma)+\mathsf{i d}(\alpha)\rho_{n}(\beta)\big)-z_{V_{m}}(\alpha)h_{2}(\alpha,Y) $$

$$ (v _ {1}, \pi_ {1}) \leftarrow \mathrm {K Z G . O p e n} (\mathrm {s r s}, u (X), \deg = \bot , X = \alpha) $$

$$ ([\bar{U}(\alpha,x)]{1},\pi{2})\gets\mathsf{K Z G.O p e n}\big(\mathsf{s r s},\bar{U}(X,Y),\mathsf{d e g}=\bot,X=\alpha\big) $$

$$ \ {{((0,\mathit{v}{2},\mathit{v}_{3}),\pi{_4})}}\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s},U mathit{(\alpha{,\mathit{Y}^{\prime}})},\operatorname{d e g}=n-1,Y=(1,\beta,\beta\sigma)) $$

$$ \left(\left[ h _ {2} \left(\alpha , x\right) \right] _ {1}, \pi_ {3}\right) \leftarrow \mathrm {K Z G}. \mathrm {O p e n} \left(\mathrm {s r s}, h _ {2} (X, Y), \deg = \bot , X = \alpha\right) $$

$$ \operatorname*{S e t}\big big([\tilde{U}{a}]{1}=[\tilde{U}(a,x,){1},,[h{2,}]_{1}=[h{2}(\alpha,x)]{1}\ {}\mathrm{}{\ a n d\ o u t p u t}\ \big([\tilde{U}{a}]{1},[h{2,\alpha}]{1},v{1},v_{2},v_{3},\pi_{1},\pi_{2},\pi_{3},\pi_{4},\pi_{5}\big) $$

$$ \underline {{\mathbf {V e r i f i e r}}}: \mathrm {C o m p u t e} U \leftarrow v _ {1} \rho_ {1} (\beta) + v _ {2}, [ P ] _ {1} \leftarrow U ^ {2} - \left[ h _ {1} \right] _ {1} z _ {V _ {n}} (\beta) - \left(v _ {3} + \mathrm {i d} (\alpha) \rho_ {n} (\beta)\right) - z _ {V _ {m}} (\alpha) \left[ h _ {2, \alpha} \right] _ {1} $$

$$ 1=\mathsf{K Z G.N e r i f y}\big(\mathsf{s r s_{K Z G}},[u]{1},\deg=\bot,X=\alpha,v{1},\pi_{1}\big) $$

$$ 1=\mathsf{K Z G.V e r i f y}\big(\mathsf{s r s}{\mathsf{K Z G}},[\bar{U}]{1},\deg{}=\bot,X=\alpha,[\bar{U}{\alpha}]{1},\pi_{2}\big) $$

$$ 1 = \mathrm {K Z G}. \operatorname {V e r i f y} \left(\mathrm {s r s} _ {\mathrm {K Z G}}, [ h _ {2} ] _ {1}, \deg = \bot , X = \alpha , [ h _ {2, \alpha} ] _ {2}, \pi_ {3}\right) $$

$$ 1{\sf Z K}{{\sf N}e}{{\sf N e r i f y}}({\sf s r s}{{\sf N Z G}},[\bar{U}{\alpha}]{1},\ \mathrm{d e g}=n-1,Y=(1,\beta,\beta\sigma),(0,v{2},v_{3}),\pi_{4}) $$

$$ \ {=}\ \mathsf{K Z G.V e r i f y}(\mathsf{s r s}{{\mathsf{K Z G}}},[P]{1},\operatorname{d e g}=n-1,Y=\beta,0,\pi_{5}) $$

Figure 5: Argument for proving that some polynomial u(X) has Nth roots of unity as coecients in the m basis f_j(X)g_j=1.

$$ u(X) $$

$$ {\mu_{j}(X)}_{j=1}^{m} $$

In Game₀ the adversary will return [u]₁= [u(x)] along with a proof. We dene Game₁ identically to Game₀, but after the adversary returns [u]₁and a proof, Game₁ additionally checks whether for u(X); U (X);p(X) the algebraic representations of [u]₁; [U]₁; [P]₁, it is true that u() = v₁, U (1) = 0, U () = v₂, U () = v₃, and p() = 0; and it aborts if one of the conditions does not hold.

$$ [u]_{1}=[u(x)] $$

$$ \mathsf{G a m e_{0}} $$

$$ \mathsf{G a m e_{1}} $$

$$ [u]_{1} $$

$$ u(X),{\bar{U}}_{\alpha}(X),p(X) $$

$$ [u]{1},[\bar{U}{\alpha}]{1},:[P]{1} $$

$$ u(\alpha)=v_{1},\bar{U}_{\alpha}(1)=0. $$

$$ p(\beta)=0 $$

$$ \bar{U}{\alpha}(\beta)=v{2},,\bar{U}{\alpha}(\beta\sigma)=v{3} $$

The redution B₁ takes as input the challenge [y₁]₁;:::;[y_q]₁. It runs the following reduction B_KZG as a subroutine. The B_KZGruns the adversary A against Game₀ over an srs in which [x]₁= [y₁]₁. Whenever A returns an output which wins the Game₀ game, if (f (X); v*;z) for some (f (X);* v*;z) 2 f(u(X);v₁;);* (U (X);(1*;;),(0;v₂;v₃*)); (p(X);; 0)g is such that f (v_i) 6= z_i, then B_KZGcomputes 0 0 f (z) = v⁰ and a valid proof. It outputs ([f (x)]₁; z*;* v*;) and ([f (x)]₁;* z*;v⁰;*) and wins evaluation binding as they are both proofs that verify and open to dierent elements. Then B_qSDHcan extract a qSDH solution from these openings following the proof in Theorem 3 of [22]. Thus

$$ \mathcal{B}_{1} $$

$$ [y_{1}]{1},\dots,[y{q}]_{1} $$

$$ \mathcal{B}_{\mathsf{K Z G}} $$

$$ [x]{1},=,[y{1}]_{1} $$

$$ (f(X),\mathbf{v},\mathbf{z}) $$

$$ (f(X),\mathbf{v},\mathbf{z});\in $$

$$ {(u(X),v_{1},\alpha),(\bar{U_{\alpha}}(X),(1,\beta,\sigma\beta),(0,v_{2},v_{3})),(p(X),\beta,0)} $$

$$ \mathcal{B}_{K Z G} $$

$$ \pi^{\prime} $$

$$ ([f(x)]_{1},\mathbf{z},\mathbf{v},\pi) $$

$$ f(z)=v^{\prime} $$

$$ f(v_{i})\neq z_{i}, $$

$$ ([f(x)]_{1},\mathbf{z},\mathbf{v}^{\prime},\pi^{\prime}) $$

$$ \mathcal{B}_{\mathsf{q S D H}} $$

$$ \operatorname {A d v} _ {\mathcal {A}} ^ {\mathrm {k - s o u n d}} (\lambda) = \operatorname {A d v} _ {\mathcal {A}} ^ {\mathrm {G a m e} _ {0}} (\lambda) \leq \operatorname {A d v} _ {\mathcal {A}} ^ {\mathrm {G a m e} _ {1}} (\lambda) + \operatorname {A d v} _ {\mathcal {B} _ {1}} ^ {\mathrm {q S D H}} (\lambda) $$

Now Game₂ behaves identically as Game₁ but it additionally checks that deg(U) n 1 and deg(h₂) n 1. If it is not the case, it aborts. Suppose A returns either deg(U) = n 1 + d or deg(h₂) = n 1 + d for some d > 0. We argue the advantage of A in Game₁ and Game₂ is the same unless we can build an adversary B₂ that succeeds against qDHE. The B₂ takes as input the challenge [y₁]₁;:::;[y_{q+d 1}]₁and runs the adversary A against Game₁ over an srs in which [x]₁= [y₁]₁. Whenever A returns an output which wins the Game₁ game, if (f (X); v*;*z) for

$$ \mathsf{G a m e_{1}} $$

$$ \deg(\bar{U}_{\alpha}),\leq,n-1 $$

$$ \deg(h_{2}),\leq,n-1 $$

$$ \deg(\bar{U}_{\alpha})=n-1+d $$

$$ d>0 $$

$$ \deg(h_{2})=n-1+d $$

$$ \mathcal{B}_{2} $$

$$ B_{2} $$

$$ [y_{1}]{1},\ldots,[y{q+d-1}]. $$

$$ (f (X), \mathbf {v}, \mathbf {z}) \in \left{\left(\bar {U} _ {\alpha} (X), (1, \beta , \sigma \beta), (0, v _ {2}, v _ {3})\right), \left(p (X), \beta , 0\right) \right} $$

$$ (f(X),\mathbf{v},\mathbf{z}) $$

$$ \mathcal{A} $$

is such that f (X) has degree greater than n 1, then the corresponding proof = [q(x)]1has a Pq 1 i representation q(X) has degree q + 1. Thus B₂ succeeds in returning [_i=0x]₁and

$$ n-1 $$

$$ \pi:=:[q(x)] $$

$$ B{}_{2} $$

$$ [ \pi - \sum_ {i = 0} ^ {q - 1} x ^ {i} ] _ {1} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{q D H E}}(\lambda) $$

We dene Game₃ identically to Game₂, but after the adversary returns [u]₁and a proof, Game₃ additionally checks whether for U (X);h₂(X); U (X);h₂_;(X) the algebraic representations of [U]₁; [U]₁; [h₂]₁; [h₂_;]₁, it is true that X X i j i j U (X) = U X and h₂ (X) = h₂ X

$$ [u]_{1} $$

$$ \bar{U}(X),h_{2}(X),\bar{U}{\alpha}(X),h{2,\alpha}(X) $$

$$ [\bar{U}]{1},[\bar{U}{\alpha}]{1},[h{2}]{1},[h{2,\alpha}]_{1} $$

$$ {\bar{U}}{\alpha}(X)=\sum{i,j}\alpha^{i}{\bar{U}}{n i}X^{j}{\mathrm{a n d}}h{2,\alpha}(X)=\sum_{i,j}\alpha^{i}h_{2,n i}X^{j} $$

and it aborts if one of the conditions does not hold.

The redution B₃ against qSFrac [18] takes as input the challenge [y₁]₁;:::;[y_q]₁and runs the adversary A against Game₂ over an srs in which [x]₁= [y₁]₁. Whenever A returns an output which wins the Game₂ game, if (f (X);V;z) for

$$ Bmathcal{B}_{3} $$

$$ [y_{1}]{1},\ldots,[y{q}] $$

$$ [x]{1}=[y{1}]] $$

$$ (f(X),V,z) $$

$$ (f(X),\phi(X),\mathit z)\in{(U\mathit(X),\mathit U_{\alpha}(X),\mathit\alpha),:(\mathit h_{2}(X),\mathit h_{2,\alpha}(X),\mathit\alpha)} $$

P 0 ⁱ j is such that (X) 6= (X) =i;^jf_niX, then set be the proof for (f (X);(X);z). Then B₃ returns

$$ \phi(X)\neq\phi^{\prime}(X)=\sum_{i,j}\alpha^{i}f_{n i}X^{j} $$

$$ \pi $$

$$ (f(X),\phi(X),z) $$

$$ B{}_{3} $$

$$ \phi(X)-\phi^{\prime}(X),(X^{n}-z),\pi-\left[\frac{f(x)-\phi^{\prime}(x)}{x^{n}-z}\right]_{1} $$

0 n We have that deg( (X) (X)) < deg(X z) because (X) has degree bounded by n 1. Hence this is as a valid solution and Game2 Game3qSFrac Adv () Adv () + Adv ()

$$ \phi(X) $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{3}}(\lambda)+\mathsf{A d v}{\mathcal{B}{3}}^{\mathsf{q S F r a c}}(\lambda) $$

$$ n-1 $$

$$ \deg(\phi(X)-\phi^{\prime}(X))<\deg(X^{n}-z) $$

Lets see that the advantage of A in Game₃ is negligible.

$$ \mathsf{G a m e_{3}} $$

Consider h₁(X);h₂(X;Y) the algebraic representations of [h₁]₁, [h₂]₁. We can use the equations veried by Game₁ and replace the corresponding values in p(X), obtaining

$$ h_{1}(X),h_{2}(X,Y) $$

$$ [h_{1}]{1},,[h{2}]_{1} $$

$$ p(X) $$

$$ \begin{aligned}{p(X)}&{{}=(v_{1}\rho_{1}(\beta)+v_{2})^{2}-h_{1}(X)z_{V_{\alpha}}(\beta)-(v_{3}+\mathsf{i d}(\alpha)\rho_{n}(\beta))-z_{V_{m}}(\alpha)h_{2,\alpha}(X)}\ {}&{{}=(u(\alpha)\rho_{1}(\beta)+\bar{U}{\alpha}(\beta))^{2}-h{1}(X)z_{V_{\alpha}}(\beta)-(\bar{U}{\alpha}(\beta\sigma)+\mathsf{i d}(\alpha)\rho{n}(\beta))-z_{V_{m}}(\alpha)h_{2,\alpha}(X)}\ {}&{{}=\big(u(\alpha)\rho_{1}(\beta)+\bar{U}(\alpha,\beta)\big)^{2}-h_{1}(X)z_{V_{n}}(\beta)-(\bar{U}(\alpha,\beta\sigma)+\mathsf{i d}(\alpha)\rho_{n}(\beta))-z_{V_{m}}(\alpha)h_{2}(\alpha,X)}\ \end{aligned} $$

From the fact that p() = 0 we get that

$$ p(\beta)=0 $$

$$ 0=(u(\alpha)\rho_{1}(\beta)+O(\alpha,\beta))^{2}-(O(\alpha,\beta\sigma)+\mathsf{i d}(\alpha)\rho_{n}(\beta))-z_{V_{n}}(\alpha)h_{2}(\alpha,\beta)-h_{1}(\beta)z_{V_{n}}(\beta) $$

Since [u]₁; [U]₁, [h₁]₁, [h₂]₁have been sent by the prover before it sees challenges, we have that except in the case where (Y =) is a root of the polynomial below, which happens with negligible probability, for all Y,

$$ [u]{1},[\bar{U}]{1},[h_{1}]{1},[h{2}]_{1} $$

$$ \beta, $$

$$ (Y=\beta) $$

$$ 0=\big(u(\alpha)\rho_{1}(Y)+\bar{U}(\alpha,Y)\big)^{2}-(\bar{U}(\alpha,Y\sigma)+\mathsf{i d}(\alpha)\rho_{n}(Y))-z_{V_{m}}(\alpha)h_{2}(\alpha,Y)-h_{1}(Y)z_{V_{n}}(Y) $$

(10)

Thus we have that

$$ \begin{array}{c}{i=0\Rightarrow0=u^{2}(\alpha)-\bar{U}(\alpha,\sigma^{1})-z_{V_{m}}(\alpha)h_{2}(\alpha,\sigma^{1})}\ {1\leq i\leq n-1\Rightarrow0=\bar{U}^{2}(\alpha,\sigma^{i})-\bar{U}(\alpha,\sigma^{i+1})-z_{V_{m}}(\alpha)h_{2}(\alpha,\sigma^{i})}\ {i=n\Rightarrow0=\bar{U}^{2}(\alpha,\sigma^{n-1})-\mathsf{i d}(\alpha)-z_{V_{m}}(\alpha)h_{2}(\alpha,\sigma^{1})}\ \end{array} $$

Since [u]₁; [U]₁, [h₂]₁have been sent by the prover before it sees challenges, we have that except in the case where (X =) is a root of the polynomial below, which happens with negligible probability, for all X,

$$ [u]{1},[\bar{U}]{1},:[h_{2}]_{1} $$

$$ (X=\alpha) $$

$$ X. $$

$$ \begin{array}{c}{i=0\Rightarrow0=u^{2}(X)-\bar{U}(X,\sigma^{1})-z_{V_{m}}(X)h_{2}(X,\sigma^{1})}\ {1\leq i\leq n-1\Rightarrow0=\bar{U}^{2}(X,\sigma^{i})-\bar{U}(X,\sigma^{i+1})-z_{V_{m}}(X)h_{2}(X,\sigma^{i})}\ {i=n\Rightarrow0=\bar{U}^{2}(X,\sigma^{n-1})-\mathsf{i d}(X)-z_{V_{m}}(X)h_{2}(X,\sigma^{1})}\ \end{array} $$

Over 2 V_mwe thus have that

$$ \nu\in V_{m} $$

$$ \begin{array}{c}{{i=0\Rightarrow0=u^{2}(\nu)-\bar{U}(\nu,\sigma^{1})}}\ {{1\leq i\leq n-1\Rightarrow0=\bar{U}^{2}(\nu,\sigma^{i})-\bar{U}(\nu,\sigma^{i+1})}}\ {{i=n\Rightarrow0=\bar{U}^{2}(\nu,\sigma^{n-1})-1}}\end{array} $$

N Together these gives us the desired requirement that u () = 1 for all 2 V_mexcept with negligible probability.

$$ u^{N}(\nu)=1 $$

$$ \nu\in V_{m} $$

Theorem 5. The protocol in Fig.4and5implies position-hiding linkability between the vector commitment schemes of C and cm*, provided that the zk proof for* R⁰_unityis instantiated with a the protocol in Fig.5and that log(N) > 6*.*

$$ \mathsf{R}_{\mathsf{u n i t y}}^{\prime} $$

$$ (N)>6 $$

The proof is in AppendixF.

8 Optimizations

In this section we describe some optimizations we apply to the protocols in Fig.4and5in order to achieve the eciency claimed in Table1.

Opening t polynomials in one point. As noted in [16],[12], whenever we have t openings of dierent polynomials at the same point i.e. for t = 2 this would be of the form

$$ \begin{aligned}{\pi_{1}}&{{}\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s_{K Z G}},f_{1}(X),\operatorname{d e g}=d,\alpha)}\ {\pi_{2}}&{{}\leftarrow\mathsf{K Z G.O p e n}(\mathsf{s r s_{K Z G}},f_{2}(X),\operatorname{d e g}=d,\alpha)}\ \end{aligned} $$

then we can send a single opening proof as opposed to t opening proofs₁;:::;_t.

$$ \pi_{1},\ldots,\pi_{t}. $$

Batching Pairings. We also apply standard techniques to batch pairings that share the same elements in one of the two groups. Namely, we can aggregate the equations

$$ \begin{aligned}{e([a]{1},[b{1}]{2})=e([c{1}]{1},[d]{2})\mathrm{}{{d n}}e([a]{1},[b{2}]{2})=e([c{2}]{1},[d]{2}),}\ {\operatorname{a s}\ e([a]{1},[b{1}+\gamma b_{2}]{2})=e([c{1}+\gamma c_{2}]{1},[d]{2})}\ \end{aligned} $$

for some random eld element sampled by the verier.

$$ \gamma $$

Note that we can adapt KZG openings equations so they can be batched further, namely if we parse the verication pairing as e [F₁]₁s₁ + [Q₁]₁;[1]₂= e [Q₁]₁; [x]₂; then two openings of dierent polynomials at dierent points can be veried by two pairings.

$$ e \left(\left[ F _ {1} \right] _ {1} - s _ {1} + \left[ Q _ {1} \right] _ {1} \alpha , [ 1 ] _ {2}\right) = e \left(\left[ Q _ {1} \right] _ {1}, [ x ] _ {2}\right) $$

Fig.1and3: In Fig.1proofs have the form ([z]₂; [T]₁; [S]₂;_ped;_unity). See that_pedconsists of 1 G₁ and 2F elements. In Fig.3proofs have the form ([F]₁; [H]₁;v₁;v₂;₁;₂) which amounts to 4G₁ and 2F. Thus we have a total of 6G₁, 2G₂ and 4F.

$$ ([z]{2},[T]{1},[S]{2},\pi{\mathsf{p e d}},\pi_{\mathsf{u n i t y}}) $$

$$ \pi_{\mathsf{p e d}} $$

$$ 1,\mathrm{G G_{1}} $$

$$ \left[[F]{1},[H]{1},v_{1},v_{2},\pi_{1},\pi_{2}\right) $$

$$ 4\mathbb{G}_{1} $$

$$ 6\mathbb{G}{1},,2\mathbb{G}{2} $$

For the verier, their rst pairing check in Fig.1uses pairings of the form e(;[1]₂), e(; [z]₂), and e([h]₁;) amounting to 3 pairings. The Pedersen verier uses no pairings. In Fig.3we have a KZG verier which uses pairings of the form e(;[1]₂), e(; [x]₂), and a pairing check that uses pairings of the form e(;[1]₂), e(; [z]₂), and e(; [x]₂). Thus we can batch the pairing checks to get a total of 4 unique pairings over the two constructions.

$$ e([h]_{1},*) $$

$$ e(,[1]_{2}),,e(,[z]_{2}) $$

$$ e(,[1]_{2}),,e(,[x]_{2}) $$

$$ e(,[1]_{2}),:e(,[z]_{2}) $$

$$ e(*,[x]_{2}) $$

Fig.4and5: In Fig.4proofs have the form ([C_I]₁; [z_I]₁; [u]₁; [H₁]₂; [H₂]₁;v₁;v₂;₁;₂;₃;_unity0). Here the₁;₃are both openings at the same and can be batched into one proof. Thus there are 7G₁, 1G₂ and 2F in addition to the_unity0. In3proofs have that form [U]₁; [h₂]₁; [h₁]₁; [U]₁; [h₂_;]₁; 0 0 0 0 0 0 0 ⁰ v₁;v₂;v₃;¹;²;³;⁴;⁵. Here we can send the same verier challenge in both Fig.4and Fig.5 0 0 (assuming we run the protocols in parallel) which allows us to avoid sending v₁;¹in Fig.5. Further, this 0 0 allows us to batch the proofs (₂;₃) with the proof for (₁;₃) because these all use the same. Thus unity0 contributes 7G₁, and 2F Thus we have a total of 14G₁, 1G₂ and 4F.

$$ ([C_{I}]{1},[z{I}]{1},[u]{1},[H_{1}]{2},[H{2}]{1},v{1},v_{2},\pi_{1},\pi_{2},\pi_{3},\pi_{\mathsf{u n i t v}^{\prime}}) $$

$$ \pi_{1},\pi_{3} $$

$$ 7mathbb{G}{1},1\mathbb{G}{2} $$

$$ \pi_{\sf u n i t y^{\prime}} $$

$$ \ [[\bar{U}]{1},[h{2}]{1},[h{1}]{1},[\bar{U}{\alpha}]{1},[h{2,\alpha}]_{1} $$

$$ v_{1}^{\prime},v_{2}^{\prime},v_{3}^{\prime},\pi_{1}^{\prime},\pi_{2}^{\prime},\pi_{3}^{\prime},\pi_{4}^{\prime},\pi_{5}^{\prime}\big) $$

$$ v_{1}^{\prime},\pi_{1}^{\prime} $$

$$ (\pi_{2}^{\prime},\pi_{3}^{\prime}) $$

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

$$ \pi_{\mathsf{u n i t y}^{\prime}} $$

$$ 7mathbb G{{}1_{1}} $$

$$ 14\mathbb{G}{1},,1\mathbb{G}{2} $$

For the verier, their pairing check in Fig.4uses pairings of the form e(;[1]₂) and e([z_I]₁). We also have 3 KZG veriers which use pairings of the form e(;[1]₂), e(; [x]₂). This amounts to 2 batched pairings. In Fig.3we have a 5 KZG veriers. Two use a degree check and thus use pairings of the d n+1 form e(;[1]₂), e(; [x]₂), a^nd e(; [x]₂). The others have the usual pairings as these do not have degree checks. Thus we can batch the pairing checks to get a total of 4 unique pairings over the two constructions.

$$ e(*,[1]_{2}) $$

$$ e([z_{I}]_{1}) $$

$$ e(,[1]_{2}),:e(,[x]_{2}) $$

$$ e(,[1]_{2}),,e(,[x]_{2}) $$

$$ e(*,[x^{d-n+1}]_{2}) $$

9 Implementation

We have implemented our scheme in Rust using the arkworks library [2], and have released the implementation in open source. The code contains a subroutine that computes all KZG openings, which we need for fast proof preprocessing and which can be used in other projects. For all the schemes dierent from Caulk, we used the Legosnark implementation⁴. All the benchmarks included in this section have been obtained by running the corresponding codes in a laptop with CPU i7-8565U and 8GB of RAM; which 22 20 allowed us to run the code for public sets of size up to 2 for the single case and 2 for lookups.

$$ 2^{22} $$

In Table2we compare Caulk’s prover and verier time as well as proof size with its alternatives in the scenario where m = 1 and for dierent values of N. In Figure6, we highlight prover time in the y axis, while N is represented in the x axis on a logarithmic scale. We consider the following schemes:

$$ 2^{20} $$

Caulk: the m = 1 version;

MT-Pos: SNARKed Merkle Poseidon tree with N elements.

MT-SHA: SNARKed Merkle SHA-2 tree with N elements.

Harisa [11]: RSA-2048 accumulator of N elements.

⁴https://github.com/matteocam/libsnark-lego/

We see that Caulk’s prover is almost 100 times as fast as Merkle trees instantiated with a Poseidon Hash and Groth16 zkSNARK on top, and 10 times as fast as the RSA accumulator. Although the latter stays constant while Caulk’s time grows slowly, we claim Caulk will still perform better for all values N that can be consider practical.

Table 2: Comparison Table for individual openings

Figure 6: Comparison for single openings

$$ (\mathbf s $$

$$ m= $$

Table 3: Comparison table for lookups

We compare Caulk’s performance for lookup tables in Table3with its most direct competitors. We consider the following schemes:

20 MT-Pos-20: SNARKed Merkle tree with Poseidon hashes and N = 2 elements.

$$ N=2^{20} $$

8 MT-Pos-8: SNARKed Merkle tree with Poseidon hashes and N = 2 elements.

$$ N=2^{8} $$

8 Caulk-8: Caulk for vectors of size N = 2.

$$ N=2^{8} $$

20 Caulk-20: Caulk for vectors of size N = 2.

$$ N=2^{20} $$

16 Harisa [11]: RSA-2048 accumulator for vectors of size N = 2 elements. The performance of the prover in RSA accumulators is independent on the size of the vector.

$$ N=2^{16} $$

In Figure7, the y axis represent prover time, while the x axis represent the value of m. The size of the vector is dierent for every color line⁵. Caulk is faster than Harisa for all the values of N we were able to compute, but approaches as N grows, and will perform worse for bigger tables. Also, we consider small values for m (up to 50) but we expect that for larger values of m the quadratic component of Caulk’s prover time would make it unpractical. Both constructions are signicantly faster than Merkle-SNARK.

Figure 7: Comparison for lookup tables

$$ \mathbb{G}_{1} $$

For pre-processing the powers of x in G₁ and G₂ as well as the single opening proofs, we use a laptop Dell XPS 17, CPU: Intel Core i9-11900H @2.5 Ghz, 16 GB RAM. The computation was single-core and the times are shown in Table4.

$$ \mathbb{G}_{2} $$

Table 4: Pre-processing times

Acknowledgments

We thank Matteo Campanelli for his help on running the LegoSNARK code.

⁵The values of m have been chosen over the available numbers for RSA accumulators in the Legosnark codebase.

References

[1] M. R. Albrecht, L. Grassi, C. Rechberger, A. Roy, and T. Tiessen. MiMC: Ecient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. In ASIACRYPT 2016, volume 10031 of LNCS, pages 191{219, 2016. [2]arkworks contributors. arkworks zksnark ecosystem, 2022. [3] S. Bayer and J. Groth. Zero-knowledge argument for polynomial evaluation with application to blacklists. In T. Johansson and P. Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 646{663. Springer, 2013. [4] E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18-21, 2014, pages 459{474. IEEE Computer Society, 2014. [5] D. Benarroch, M. Campanelli, D. Fiore, K. Gurkan, and D. Kolonelos. Zero-knowledge proofs for set membership: Ecient, succinct, modular. In N. Borisov and C. Daz, editors, Financial Cryptography and Data Security - 25th International Conference, FC 2021, Virtual Event, March 1-5, 2021, Revised Selected Papers, Part I, volume 12674 of Lecture Notes in Computer Science, pages 393{414. Springer, 2021. [6] D. Boneh and X. Boyen. Short signatures without random oracles. In EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 56{73. Springer, 2004. [7] J. Bootle, A. Cerulli, P. Chaidos, E. Ghada, J. Groth, and C. Petit. Short accountable ring signatures based on DDH. In G. Pernul, P. Y. A. Ryan, and E. R. Weippl, editors, Computer Security - ESORICS 2015 - 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part I, volume 9326 of Lecture Notes in Computer Science, pages 243{265. Springer, 2015. [8] J. Bootle and J. Groth. Ecient batch zero-knowledge arguments for low degree polynomials. In M. Abdalla and R. Dahab, editors, Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part II, volume 10770 of Lecture Notes in Computer Science, pages 561{588. Springer, 2018. [9] J. Camenisch, R. Chaabouni, and A. Shelat. Ecient protocols for set membership and range proofs. In J. Pieprzyk, editor, Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings, volume 5350 of Lecture Notes in Computer Science, pages 234{252. Springer, 2008. [10] J. Camenisch and A. Lysyanskaya. Dynamic accumulators and application to ecient revocation of anonymous credentials. In M. Yung, editor, Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 61{76. Springer, 2002. [11] M. Campanelli, D. Fiore, S. Han, J. Kim, D. Kolonelos, and H. Oh. Succinct zero-knowledge batch proofs for set accumulators. IACR Cryptol. ePrint Arch., page 1672, 2021. [12] A. Chiesa, Y. Hu, M. Maller, P. Mishra, P. Vesely, and N. Ward. Marlin: Preprocessing zksnarks with universal and updatable srs. In A. Canteaut and Y. Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Virtual Conference, May 1-15, 2020, Proceedings, Part I, volume 12105 of Lecture Notes in Computer Science, pages 738{768. Springer, 2020.

[13]D. Feist and D. Khovratovich. Fast amortized kate proofs.

[14]A. Fiat and A. Shamir. How to prove yourself: Practical solu- tions to identication and signature problems. In A. M. Odlyzko, editor, Advances in Cryptology - CRYPTO 1986, volume 263 of Lecture Notes in Computer Science, pages 186{194. Springer, 1987. [15] G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications. In H. Shacham and A. Boldyreva, editors, CRYPTO 2018, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part II, volume 10992 of LNCS, pages 33{62. Springer, 2018. [16] A. Gabizon and Z. J. Williamson. Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. IACR Cryptol. ePrint Arch., page 953, 2019. [17] A. Gabizon and Z. J. Williamson. plookup: A simplied polynomial protocol for lookup tables. IACR Cryptol. ePrint Arch., page 315, 2020. [18] E. Ghada and J. Groth. Towards a classication of non-interactive computational assumptions in cyclic groups. IACR Cryptol. ePrint Arch., page 343, 2017. [19] L. Grassi, D. Khovratovich, A. Roy, C. Rechberger, and M. Schofnegger. Poseidon: A new hash function for zero-knowledge proof systems. Usenix Security 2021, 2021. [20] J. Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT (2), volume 9666 of Lecture Notes in Computer Science, pages 305{326. Springer, 2016. [21] J. Groth and M. Kohlweiss. One-out-of-many proofs: Or how to leak a secret and spend a coin. In E. Oswald and M. Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Soa, Bulgaria, April 26-30, 2015, Proceedings, Part II, volume 9057 of Lecture Notes in Computer Science, pages 253{280. Springer, 2015. [22] A. Kate, G. M. Zaverucha, and I. Goldberg. Constant-size commitments to polynomials and their applications. In ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 177{194. Springer, 2010. [23] M. Kohlweiss, M. Maller, J. Siim, and M. Volkhov. Snarky ceremonies. In ASIACRYPT (3), volume 13092 of Lecture Notes in Computer Science, pages 98{127. Springer, 2021. [24] U. M. Maurer. Unifying zero-knowledge proofs of knowledge. In AFRICACRYPT, volume 5580 of Lecture Notes in Computer Science, pages 272{286. Springer, 2009. [25] I. Miers, C. Garman, M. Green, and A. D. Rubin. Zerocoin: Anonymous distributed e-cash from bitcoin. In 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, May 19-22, 2013, pages 397{411. IEEE Computer Society, 2013. [26] C. Papamanthou, E. Shi, and R. Tamassia. Signatures of correct computation. In TCC, volume 7785 of Lecture Notes in Computer Science, pages 222{242. Springer, 2013. [27] L. Pearson, J. Fitzgerald, H. Masip, M. Belles-Munoz, and J. L. Munoz-Tapia. Plonkup: Reconciling plonk with plookup. IACR Cryptol. ePrint Arch., page 86, 2022. [28] A. Tomescu, I. Abraham, V. Buterin, J. Drake, D. Feist, and D. Khovratovich. Aggregatable subvector commitments for stateless cryptocurrencies. In C. Galdi and V. Kolesnikov, editors, Security and Cryptography for Networks - 12th International Conference, SCN 2020, Amal, Italy, September 14-16, 2020, Proceedings, volume 12238 of Lecture Notes in Computer Science, pages 45{64. Springer, 2020. [29] Tornado cash privacy solution version 1.4, 2021. https://tornado.cash/Tornado.cash_ whitepaper_v1.4.pdf. [30] ZCash protocol specication, 2022, 1st February. https://github.com/zcash/zips/blob/master/ protocol/protocol.pdf. [31] Zksync rollup protocol, 2021. https://github.com/matter-labs/zksync/blob/master/docs/ protocol.md.

A Denitions

Let R be a family of universal relations. Given a relation R 2R and an instance x we call w a witness for x if (x*;w*) 2 R, L(R) = fxj9w : (x*;w*) 2 Rg is the language of all the x that have a witness w in the relation R, while L(R) is the language of all the pairs (x*;*R) such that x 2L(R). We will assume R it is implicit as prover and verier input.

$$ \ {mathsf R\in{\mathcal R R}} $$

$$ \mathrm {x} \text {i f} (\mathrm {x}, w) \in \mathrm {R}, \mathcal {L} (\mathrm {R}) = \left{\mathrm {x} | \exists w: (\mathrm {x}, w) \in \mathrm {R} \right} $$

$$ (\mathsf{X},\mathsf{R}) $$

$$ \mathcal{L}(\mathsf{R}) $$

$$ {\mathsf{X}}\in{\mathcal{L}}({\mathsf{R}}) $$

Denition A.1. A Non-Interactive Zero-Knowledge Argument of Knowledge is a tuple of PPT algorithms (Setup*;Prove;Verify;*Simulate) such that:

(srs*;x*) Setup(R): On input a family of relations R, Setup outputs a structured reference string srs and a trapdoor x;

$$ \ \left(\mathsf{s r s},x\right)\leftarrow\mathsf{S e t u p}(\mathcal{R}) $$

Prove(srs*;(x;w*)): On input a pair (x*;w*) 2 R*, it outputs a proof of the fact that* x 2L(R);

$$ \pi\leftarrow\mathsf{P r o v e}\ \bigl(\mathsf{s r s},\bigl(\mathsf{x},w\bigr)\bigr) $$

$$ ({\mathsf{x}},)\in{\mathsf{R}}_{!} $$

$$ \ \mathsf{X}\in{\mathcal{L}}(\mathsf{R}) $$

1*=0 Verify(srs;* x*;): On input the srs, the instance* x and the proof, it produces a bit expressing acceptance (1), or rejection (0);

$$ 1/0\leftarrow V e r f y(s r s,x,\pi)\colon O0n $$

simSimulate(srs*;x;* x): The simulator has the srs, the trapdoor x and the instance x as inputs and it generates a simulated proof_sim,

$$ \pi_{\mathrm{s i m}}\leftarrow\mathsf{S i n u l a t e}(\mathsf{s r s},\mathsf{x},\mathsf{x}) $$

$$ \pi_{\mathrm{s i m}} $$

and that satises completeness, knowledge soundness and zero-knowledge as dened below.

Completeness: holds if an honest prover will always convince an honest verier. Formally, 8 R 2 R; (x*;w*) 2 R, Verify(srs*;* x*;) = 1 (srs;x*) Setup(R)

$$ \forall\ textsf R inin $$

$$ \mathcal{R},(\ \mathsf x w\) $$

$$ \Pr \left[ \begin{array}{c c} \operatorname {V e r i f y} (\mathrm {s r s}, \mathrm {x}, \pi) = 1 & \left(\mathrm {s r s}, x\right) \leftarrow \operatorname {S e t u p} (\mathcal {R}) \ \pi \leftarrow \operatorname {P r o v e} (\mathrm {s r s}, (\mathrm {x}, w)) \end{array} \right] = 1. $$

Knowledge-Soundness: captures the fact that a cheating prover cannot, except with negligible probability, create a proof accepted by the verication algorithm unless it has a witness w such that (x*;w*) 2 R. Formally, for all PPT adversaries A, there exists a PPT extractor E such that the following probability is negligible in 2 3

$$ (\mathsf{x},w)\in\mathsf{R} $$

$$ \mathcal{E} $$

$$ \Pr \left[ (\mathrm {x}, w) \notin \mathrm {R} \wedge \operatorname {V e r i f y} (\mathrm {s r s}, \mathrm {x}, \pi) = 1 \mid \begin{array}{l l} (\mathrm {s r s}, x) \leftarrow \operatorname {S e t u p} (\mathcal {R}) \ (\mathrm {x}, \pi) \leftarrow \mathcal {A} (\mathrm {s r s}) \ w \leftarrow \mathcal {E} (\mathrm {s r s}, \mathrm {x}, \pi) \end{array} \right] $$

Zero-Knowledge: (Setup*;Prove;Verify;*Simulate) is zero-knowledge if for all R 2R, instances x and PPT adversaries A, 2 3 2 3

$$ \ {mathsf R\in\mathcal{R}} $$

$$ \ \mathcal{A}, $$

$$ \Pr \left[ \mathcal {A} (\mathrm {s r s}, \pi) = 1 \mid \begin{array}{l l} (\mathrm {s r s}, x) \leftarrow \operatorname {S e t u p} (\mathcal {R}) \ \mathrm {x} \leftarrow \mathcal {A} (\mathrm {s r s}) \ \pi \leftarrow \operatorname {P r o v e} (\mathrm {s r s}, (\mathrm {x}, w)) \end{array} \right] \approx \Pr \left[ \mathcal {A} (\mathrm {s r s}, \pi_ {\mathrm {s i m}}) = 1 \mid \begin{array}{l l} (\mathrm {s r s}, x) \leftarrow \operatorname {S e t u p} (\mathcal {R}) \ \mathrm {x} \leftarrow \mathcal {A} (\mathrm {s r s}) \ \pi_ {\mathrm {s i m}} \leftarrow \operatorname {S i m u l a t e} (\mathrm {s r s}, x, \mathrm {x}) \end{array} \right]. $$

Denition A.2 (Vector Commitment Scheme). A Vector Commitment Scheme is a tuple of algorithms Setup*;* Commit*;* Open*;* Verify such that:

(x; srs) Setup par*;d : On input the system parameters and a bound d on the size of the vectors,* it outputs a structured reference string and trapdoor x.

$$ \big(x,\mathsf{s r s}\big)\leftarrow\mathsf{S e t u p}\big(\mathsf{p a r},d\big) $$

C Commit srs*;~v;r : On input the srs, a vector ~v, and randomness r it outputs a commitment* C*.*

$$ C\leftarrow\mathsf{C o m m i t}(\mathsf{s r s},\vec{v},r) $$

(v_i;) Open srs*;~v;r;i : On input the srs, the vector, its size , the commitment randomness, and* a position i 2 [m] it outputs v_i2 F and proof that v_iis the ith element of vector ~v.

$$ (v_{i},\pi)\gets\mathsf{O p e n}\big(\mathsf{s r s},\vec{v},r,i\big) $$

$$ i\in[m] $$

$$ v_{i}\in\mathbb{F} $$

$$ v_{i} $$

1*=0 Verify srs;* C*;i;v*_i; : On input the srs, the commitment, position, claimed value v_i, and the proof, it outputs a bit indicating acceptance or rejection.

$$ 1/0\leftarrow V e r f y y(s r s,C,i,v_{i},\pi) $$

$$ v_{i}, $$

A vector commitment scheme should satisfy the following properties:

Correctness: It captures the fact that an honest prover will always convince an honest verier. Namely, N for all vectors ~v 2 F and i 2 [N] " #

$$ \vec{v}\in\mathbb{F}^{N} $$

$$ i\in[N] $$

$$ \mathsf{P r}\left[\begin{array}{c}{\mathsf{V e v i f y}(\mathsf{s r s},\mathsf{C},i,v_{i},\pi)=1}\ {\begin{array}{c}{\mathsf{s r s}\leftarrow\mathsf{S e t m u p}(\mathsf{p a r},\mathsf{N})}\ {\mathsf{C}\leftarrow\mathsf{C o m m i t}(\mathsf{s r s},\vec{v},r)}\ {(v_{i},\pi)\leftarrow\mathsf{O p e n}(\mathsf{s r s},,r,i)}\ \end{array}}\ \end{array}\right]=1 $$

(Weak) Position Binding: Captures the fact that no PPT adversary A should be able to present for one commitment two valid openings for the same position. Formally: " #

$$ \Pr \left[ \begin{array}{c c} \operatorname {V e r i f y} (\mathrm {s r s}, C, i, y, \pi) = 1, \ \operatorname {V e r i f y} (\mathrm {s r s}, C, i, y ^ {\prime}, \pi^ {\prime}) = 1 \ \text {a n d} y \neq y ^ {\prime} \end{array} \right| \begin{array}{c} \mathrm {s r s} \leftarrow \operatorname {S u p t u p} (\mathrm {p a r}, N) \ (\vec {v}, r, i, y, y ^ {\prime}, \pi , \pi^ {\prime}) \leftarrow \mathcal {A} (\mathrm {s r s}) \ \mathrm {C} \leftarrow \operatorname {C o m m i t} (\mathrm {s r s}, \vec {v}, r) \end{array} ] \approx 0 $$

(Strong) Position Binding: Captures the fact that no PPT adversary A should be able to present for one commitment two valid openings for the same position. Formally: " #

$$ \mathsf{P r}\left[\begin{array}{c}{\mathsf{V e r i f}{\mathsf{Y}}(\mathsf{s r s},\mathsf{C},i,y,\pi)=1,}\ {\mathsf{V e r i f}{\mathsf{F r s}}(\mathsf{s r s},\mathsf{C},i,y^{\prime},\pi^{\prime})=1}\ {\mathsf{a n d}\ y\neq y^{\prime}}\ \end{array}\right]\Bigg|\begin{array}{c}{\mathsf{s r s}\longleftarrow\mathsf{S e t u p}{\mathsf{p a r}}(\mathsf{p r r},N)}\ {(\mathsf{C},i,y,y^{\prime},\pi,\pi^{\prime})\leftarrowleftarrow\mathcal{A}{\mathsf{{s}}}(\mathsf{s r s})}\ \end{array}\Bigg]]approxapprox0 $$

Knowledge Soundness: Captures the fact that whenever the prover provides a valid opening, it knows a valid pair (p(X);p()) 2 F[X] F*, where deg*(p) deg*. Formally, for all PPT adversaries A there* exists an ecient extractor E such that: 2 3

$$ (p(X),p(\alpha))\in\mathbb{F}[X]\times\mathbb{F} $$

$$ \ e g(p)\leq\operatorname{d e g} $$

$$ \Pr \left[ \begin{array}{c c} \operatorname {V e r i f y} (\mathrm {s r s}, \mathrm {C}, i, y, \pi) = 1 \ \wedge v _ {i} \neq y \end{array} \right| \begin{array}{c} \mathrm {s r s} \leftarrow \operatorname {S u p u p} (\mathrm {p a r}, N) \ \mathrm {C} \leftarrow \mathcal {A} (\mathrm {s r s}) \ \vec {v} \leftarrow \mathcal {E} (\mathrm {s r s}, \mathrm {C}, N) \ (i, y, \pi) \leftarrow \mathcal {A} (\mathrm {s r s}, \vec {v}, N, i) \end{array} ] \approx 0 $$

Denition A.3 (Polynomial Commitment Scheme). A Polynomial Commitment Scheme is a tuple of algorithms Setup*;* Commit*;* Open*;* Verify such that:

(x; srs) Setup par*;d : On input the system parameters and a degree bound d, it outputs a* structured reference string and trapdoor x.

$$ \ x,{\mathsf{s r s}},{\gets},\mathsf{S e t u p}\big({\mathsf{p a r}},d\big) $$

C Commit srs*;p*(X);r : On input the srs and a polynomial p(X), and randomness r it outputs a commitment C to p(X).

$$ \left(\mathrm {s r s}, p (X), r\right) $$

$$ p(X) $$

(s;) Open srs*;p*(X);r; : On input the srs, the polynomial, commitment randomness r, a query point 2 F*, it outputs s 2* F and an evaluation proof that s = p().

$$ (s,\pi)\gets\mathsf{O p e n}(\mathsf{s r s},p(X),r,\alpha) $$

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

$$ s\in\mathbb{F} $$

$$ s=p(\alpha) $$

1*=0 Verify srs;* C*;deg;;s; : On input the srs, the commitment, degree bound, query and* evaluation points ;s, and the proof of correct evaluation, it outputs a bit indicating acceptance or rejection.

$$ 1/0\leftarrow\ V e r i f y(s r s,C,d e g,0,s,\pi) $$

A polynomial commitment scheme should satisfy the following properties:

Completeness: It captures the fact that an honest prover will always convince an honest verier. Formally, for any polynomial p(X) such that deg(p) d and query point 2 F the following probability is 1: 2 3 srs Setup par*;d*

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

$$ d e g(p)\leq d $$

$$ p(X) $$

$$ \Pr \left[ \begin{array}{c c} \operatorname {V e r i f y} (\mathrm {s r s}, C, \deg , \alpha , s, \pi) = 1 & \begin{array}{l} \mathrm {s r s} \leftarrow \operatorname {S u p t u p} (\mathrm {p a r}, d) \ \mathrm {C} \leftarrow \operatorname {C o m m i t} (\mathrm {s r s}, p (X), r) \ s = p (\alpha), \deg (p) = \deg \ (s, \pi) \leftarrow \operatorname {O p e n} (\mathrm {s r s}, p (X), r, \alpha) \end{array} \end{array} \right] $$

Soundness: Captures the fact that a cheating prover should not be able to convince the verier of a false opening. Formally, for all stateful PPT adversaries A: 2 3

$$ \Pr \left[ \begin{array}{c c| c} \left(p (\alpha) \neq s \vee d e g (p) > \deg\right) \ \wedge \ \mathrm {V e r i f y} \left(\mathrm {s r s}, \mathrm {C}, \deg , \alpha , s, \pi\right) = 1 \end{array} \right| \begin{array}{c} \mathrm {s r s} \leftarrow \mathrm {S e t u p} \left(\mathrm {p a r}, d\right) \ \left(p (X), \mathrm {C}\right) \leftarrow \mathcal {A} (\mathrm {s r s}) \ \alpha \leftarrow \mathbb {F} \ \left(s, \pi\right) \leftarrow \mathcal {A} (\alpha) \end{array} ] \approx 0 $$

Evaluation Binding: Captures the fact that no PPT adversary A should be able to present two valid openings for dierent values but same evaluation point. Formally: 2 3

$$ \mathsf{P}\left[\begin{array}{c}\\mathsf{{V v e i f y}\big(\mathsf{s r s},\mathsf{C},\mathsf{d e g},\alpha,s,\pi\big)=1,}\ {\mathsf{V e e i i y}\big(\mathsf{s r s},\mathsf{C},\mathsf{d e g},\alpha,s^{\prime},\pi^{\prime}\big)=1}\ {\mathrm{{n d d}~}s\neq s^{\prime}}\ \end{array}\Bigg|\ \begin{array}{c}{\mathsf{s r s}\leftarrow\mathsf{S e t u p}\big(\mathsf{p r r},N\big)}\ {\mathsf{C r s,},\alpha,s^{\prime},\pi,\pi^{\prime}\big)\leftarrow\mathcal{A}\big(\mathsf{s r s}\big)}\ \end{array}\right]\approx0 $$

Extractability: Captures the fact that whenever the prover provides a valid opening, it knows a valid pair (p(X);p()) 2 F[X] F*, where deg*(p) deg*. Formally, for all PPT adversaries A there exists an* ecient extractor E such that: 2 3

$$ (p(X),p(\alpha))\in\mathbb{F}[X]\times\mathbb{F} $$

$$ \ e g(p)\leq\operatorname{d e g} $$

$$ \Pr \left[ \begin{array}{c c} \operatorname {V e r i f y} \left(\mathrm {s r s}, C, \deg , \alpha , s, \pi\right) = 1 \ \wedge \ \left(p (\alpha) \neq s \vee \deg (p) > \deg\right) \ \end{array} \right| \frac {\mathrm {s r s} \leftarrow \operatorname {S u t u p} \left(\mathrm {p a r} , \deg\right)}{\mathrm {C} \leftarrow \mathcal {A} (\mathrm {s r s})} \left. \begin{array}{l} p (X) \leftarrow \mathcal {E} \left(\mathrm {s r s}, C, \deg\right) \ \alpha \leftarrow \mathcal {A} (\mathrm {s r s}, C, \deg) \ (s, \pi) \leftarrow \mathcal {A} \left(\mathrm {s r s}, p (X), \deg , \alpha\right) \end{array} \right] \approx 0 $$

B Proof of Thm1

Proof. We will proceed through a series of games to show that the protocol dened in Fig.1satises the linkability property. Let A be an arbitrary algebraic PPT adversary in the linkability game and let linkability Adv^A() be their advantage. Let Game₀ be dened as in Denition5.1, which is where we want to Gi bound the adversary’s success probability. We dene Game₁*;*Game₂ and denote Adv_Aas the advantage of the adversary A in game i. We also specify reductions B₁; B₂; B₃; B₄ such that

$$ \mathsf{A d v}_{\mathcal{A}}^{\mathsf{l i n k a b i l i t y}}(\lambda) $$

$$ \mathsf{G a m e_{0}} $$

$$ \mathsf{A d v}{\mathcal{A}}^{G{i}} $$

$$ \mathcal{B}{1},\mathcal{B}{2},\mathcal{B}{3},\mathcal{B}{4} $$

$$ \begin{array}{l}{\mathsf{A d v}{\mathcal{A}}^{\mathsf{l n n k b i l i t y}}=\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{0}}\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)+\mathsf{A d v}{\mathsf{B}{1}}^{\mathsf{u n n t y}}(\lambda)}\ {\displaystyle\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{v e d}}(\lambda)+\mathsf{A d v}{\mathcal{B}{1}}^{\mathsf{u n d i y}}(\lambda)}\ {\displaystyle\leq\mathsf{A d v}{\mathcal{B}{1}}^{\mathsf{u n n i y}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{v e d}}(\lambda)+\mathsf{A d v}{\mathcal{B}{3}}^{\mathsf{v e d g}}(\lambda)+\mathsf{A d v}{\mathcal{B}_{4}}^{\mathsf{v S d H}}(\lambda)}\ \end{array} $$

In Game₀ the adversary will return cm along with a proof ([z]₂= [z(x)]₂; [T]₁= [T (x)]₁; [S]₂= [S(x)]₂;_ped;_unity). We dene Game₁ identically to Game₀, but after the adversary returns cm along with N N the proof, Game₁ additionally checks whether there exists a;b such that z(X) = a(X b) with a = b and abort if this is not the case. Note that Game₁ can extract z(X), the algebraic representation of [z]₂, because the adversary A is algebraic .

$$ \mathsf{G a m e_{0}} $$

$$ ([z]{2}:=:[z(x)]{2},[T]{1}:=:[T(x)]{1},[S]_{2}:= $$

$$ [S(x)]{2},\pi{\mathsf{p e d}},\pi_{\mathsf{u n i t y}}) $$

$$ a,b $$

$$ z(X)=a(X-b) $$

$$ a ^ {N} = b ^ {N} $$

$$ z(X) $$

We observe that the adversary’s advantage in Game₀ and Game₁ is identical, unless it manages to break the knowledge soundness of R_unity. Given such an A, we can thus directly get a reduction B₁ against unity the knowledge soundness of R^unityand let the advantage of this adversary be Adv_B. The reduction B₁ 1 simply runs A and returns_unitythat is returned by A. It thus holds that

$$ \mathsf{G a m e_{0}} $$

$$ \mathsf{G a m e_{1}} $$

$$ R_{\mathsf{u n i t y}} $$

$$ {\mathcal A}, $$

$$ \ !{\mathcal{B}}{_{1}} $$

$$ R_{\mathsf{u n i t y}} $$

$$ \mathcal{B}_{1} $$

$$ \mathsf{A d v}{\mathcal{B}{1}}^{\mathsf{u n i t y}} $$

$$ \pi_{\sf u n i t y} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{f i n k a b i l i t y}}(\lambda)=\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{0}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)+\mathsf{A d v}{\mathcal{B}_{1}}^{\mathsf{h n i t y}}(\lambda). $$

Now dene Game₂, which is identical to Game₁, but after the (algebraic) adversary A outputs cm the game Game₂ extracts v and r such that cm = [v + hr]₁. If this extraction fails, meaning that cm is not correctly formed, then Game₂ aborts. We note that the A’s advantage in Game₁ is identical to its advantage in Game₂, unless it manages to break the knowledge soundness of R_ped. Given A, we can construct a reduction B₂ against the knowledge soundness of R_pedanalogously to the reduction above ped and let the advantage of this adversary be Adv_B. We observe that 2

$$ \mathsf{G a m e_{2}} $$

$$ \mathrm {c m} = [ v + \mathrm {h} r ] _ {1} $$

$$ \mathcal {A} ^ {\prime} \mathrm {s} $$

$$ R_{\mathsf{p e d}} $$

$$ \ {{\mathcal{B}}_{2}} $$

$$ R_{\mathsf{p e d}} $$

$$ \mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{p e d}} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{p e d}}(\lambda). $$

Recall that any adversary who successfully wins Game₂ must output a proof that satises the following equation from the verication procedure

$$ \mathsf{G a m e_{2}} $$

$$ \begin{aligned}{C(x)-v-\mathsf{h}r=}&{{}\ T(x)z(x)+\mathsf{h}S(x)\Leftrightarrow}\ {C(x)-v=}&{{}\ T(x)a(x-\omega^{i})+\mathsf{h}(r+S(x)),}\ \end{aligned} $$ while at the same time it must hold that

$$ \mathcal{C}(X)-v\neq\big(X-\omega^{i}\big)a T(X) $$

for any polynomial aT(X), since v is not in the committed vector ~c. Intuitively, the adversary cannot satisfy this equation, since h is unknown to the prover and thus (r + S(X)) is chosen independently of h. More formally, we consider two cases here. If

$$ a T(X) $$

$$ \vec{c}. $$

$$ (r+S(X)) $$

$$ C(x)-v\neq T(x)a\big(x-\omega^{i}\big) $$

then we can construct a reduction B₃ breaking the discrete logarithm problem. Else if

$$ \ {mathcal B}_{3} $$

$$ C(x)-v=T(x)a(x-\omega^{i}) $$

then we can construct a reduction B₄ breaking the qSDH problem.

$$ \mathcal{B}_{4} $$

The reduction B₃ takes as input a challenge [y]₁. It runs the adversary A against Game₂ over an srs in which [h]₁= [y]₁and B₃’s choice of x (where x is the trapdoor information of the KZG commitment). Whenever the adversary returns an output ([z]₂= [z(x)]₂; [T]₁= [T (x)]₁; [S]₂= [S(x)]₂;_ped;_unity) which wins the Game₂ game, then B₃ returns

$$ Bmathcal_{3} $$

$$ \mathcal{A} $$

$$ [y]_{1} $$

$$ [ \mathrm {h} ] _ {1} = [ y ] _ {1} $$

$$ {\mathcal{B}_{3}}^{2} $$

$$ \mathrm{K Z G} $$

$$ ([z]{2}=[z(x)]{2},[T]{1}=[T(x)]{1},[S]{2}=[S(x)]{2},\pi_{\mathsf{p e d}},\pi_{\mathsf{u n i t y}}) $$

$$ \mathsf{G a m e_{2}} $$

$$ \mathsf{h}=\frac{C(x)-v-T(x)z(x)}{r+S(x)}, $$

$$ \ {mathcal B B}_{3} $$

where T (X);r and S(X) are extracted from the outputs of A. The reduction’s success probability is exactly the success probability of the adversary conditioned on (r + S(x)) 6= 0.

$$ T(X),r $$

$$ S(X) $$

$$ (r+S(x))\neq0. $$

The reduction B₄ takes as input the challenge [y₁]₁;:::;[y_q]₁. It runs the following reduction B₄ as a subroutine. The B_KZGruns the adversary A against Game₂ over an srs in which [x]₁= [y₁]₁and B_KZG’s choice of h. Whenever the adversary returns an output ([z]₂= [z(x)]₂; [T]₁= [T (x)]₁; [S]₂= [S(x)]₂;_ped;_unity) which wins the Game₂ game, then B_KZGreturns the KZG openings

$$ \mathcal{B}_{4} $$

$$ \mathcal{B}_{4} $$

$$ [y_{1}]{1},\ldots,[y{q}]_{1} $$

$$ \mathcal {B} _ {\mathrm {K Z G}} $$

$$ [x]{1}=[y{1}] $$

$$ \mathcal {B} _ {\mathrm {K Z G}} $$

$$ ([z]{2}\ \mathrm{}{=}\ [z(x)]{2},[T]{1}\ \hat{\ {=}\ }[\hat{\ }T(x)]{1},\hat{\ }[S]_{2}\ = $$

$$ [S(x)]{2},\pi{\mathsf{p e d}},\pi_{\mathsf{u n i t y}}) $$

$$ \mathsf{G a m e_{2}} $$

$$ \mathcal {B} _ {\mathrm {K Z G}} $$

$$ (v,[a^{-1}T]{1})\ {\operatorname{a n d}}\ (C(\omega^{i}),[\frac{C(x)-C(\omega^{i})}{x-\omega^{i}}]{1}) $$

for v =6 C(x). Then B₄ can extract a qSDH solution from these openings following the proof in Theorem 1 of [22].

$$ v\neq\mathcal{C}(x) $$

$$ \mathcal{B}_{4} $$

$$ q\mathrm{S D H} $$

$$ \ 22 $$

We can thus conclude that

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{h i l a b i l i t y}}(\lambda)\leq\mathsf{A d v}{\mathcal{B}{1}}^{\mathsf{u n i i y}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{p e d}}(\lambda)+\mathsf{A d v}{\mathcal{B}{3}}^{\mathsf{d d d g}}(\lambda)+\mathsf{A d v}{\mathcal{B}_{4}}^{\mathsf{S S G H}}(\lambda). $$

Lastly, we prove the position hiding property of our construction. We dene a simulator Simulate that has access to the trapdoor x of srs that is indistinguishable from an honest prover. First, Simulate 0 calls the simulators of R_pedand R_unityon input the trapdoor x, and gets simulated proofs_pedand ⁰ 1 ^unity. Then, it samples a;r;s F and sets [z⁰]²= [a] , [₂S⁰]²= [s] , [₂T⁰]¹= (C cm [hs] )¹=a, and 0 0 outputs ([z⁰]₂; [T⁰]₁; [S⁰]₂;^ped;^unity). Note that honestly generated [z]²; [S]₂are randomized by a and s, respectively, and thus indistinguishable from [z⁰]₂; [S⁰]₂. Finally, [T⁰]₁is the only element satisfying the verifying equation for given [z⁰]₂; [S⁰]₂and thus indistinguishable from honest [T]₁as well, which concludes the proof.

$$ R_{\mathsf{p e d}} $$

$$ x. $$

$$ R_{\mathsf{u n i t y}} $$

$$ \pi_{\mathsf{p e d}}^{\prime} $$

$$ \pi_{\ i n i t y}^{\prime}. $$

$$ [z^{\prime}]{2}{\ =\ }[a]{2},;[S^{\prime}]{2}{\ =\ }[s]{2},;[T^{\prime}]{1}{\ =\ }(\mathsf{C}\cdot\mathsf{c m}^{-1}-[\mathsf{h}s]{1})\ {//}a, $$

$$ ([z^{\prime}]{2},[T^{\prime}]{1},[S^{\prime}]{2},\pi{\mathsf{p e d}}^{\prime},\pi_{\mathsf{u n i t y}}^{\prime}) $$

$$ s $$

$$ [z]{2},[S]{2} $$

$$ [z^{\prime}]{2},[S^{\prime}]{2} $$

$$ [z^{\prime}]{2},[S^{\prime}]{2} $$

$$ \left[ T ^ {\prime} \right] _ {1} $$

$$ [T]_{1} $$

C Proof of Lemma1

Proof. Because z(X) has degree 1, there exist a;b 2 F such that z(X) = aX b.

$$ a,b\in\mathbb{F} $$

$$ z(X) $$

$$ z(X)=a X-b. $$

From the rst condition, we have f(1) = a(1) = a b; and f () = a() = a b. From items 2 and 3,

$$ f(1)=a(1)=a-b, $$

$$ f(\sigma)=a\ \big(\sigma\big)=a\sigma-b $$

$$ f(\sigma^{2})={\frac{f(1)-f(\sigma)}{1-\sigma}}={\frac{a-a\sigma}{1-\sigma}}=a, $$

$$ f(\sigma^{3})=\sigma f(\sigma^{2})-f(\sigma)=\sigma a-a\sigma+b=b $$

2 3 4 a By substituting f () = a and f () = b into condition 4 we see th^at f () =. Therefore, from b i+1 4+i+1 4+i 2 a 2 item 5 we have that for every i = 0*;:::;* log(N) 1, f () = f () =. In p_art_icular, b log(N) 4+(log(N) 1)+1 a 2 a ^N a f (⁾ = =, th^at equals 1 by the 5th condition, proves that is ^a Nth root b b b of unity as required.

$$ f(\sigma^{2})=a $$

$$ f(\sigma^{3})=b $$

$$ f \left(\sigma^ {4}\right) = \frac {a}{b} $$

$$ i:=:0,\ldots,\operatorname{l o g}(N):-:1,;f(\sigma^{4+i+1}):=:f(\sigma^{4+i})^{2}:=:(\textstyle\frac{a}{b})^{2^{*}:\cdot\cdot\cdot} $$

$$ f(\sigma^{4+(\log(N)-1)+1})=\left(\frac{a}{b}\right)^{2^{\log(N)}}=\left(\frac{a}{b}\right)^{N} $$

$$ \frac{a}{b} $$

D Proof of Thm.2

Proof. We proceed through a series of games to show that the protocol dened in Fig.3satises knowledge soundness. We set Game₀ to be the soundness game as in Def.A.1and consider an algebraic adversary A k-sound against it which has advantage Adv_A. We dene Game₁, Game₂ and specify reductions B₁ and B₂ such that

$$ \mathcal {B} _ {1} $$

$$ \mathsf{A d v}_{\mathcal{A}}^{k mathsf{-s o u n d}} $$

$$ B_{2} $$

$$ \begin{aligned}{\mathsf{A d v}{\mathcal{A}}^{\mathsf{K--s o u n d}}(\lambda)}&{{}=\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{0}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)+\mathsf{A d v}{\mathcal{B}}^{\mathsf{G S B H}}(\lambda)}\ {}&{{}\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)+\mathsf{A d v}{\mathcal{B}}^{\mathsf{G B B H}}(\lambda)+\mathsf{A d v}{\mathcal{B}}^{\mathsf{G B B H}}(\lambda)}\ {}&{{}\leq\mathsf{A d v}{\mathcal{B}}^{\mathsf{S S B H}}(\lambda)+\mathsf{A d v}{\mathcal{B}}^{\mathsf{G B B H}}(\lambda)+\mathsf{n o g}(\lambda).}\ \end{aligned} $$

In Game₀ the adversary will return [z]₂along with a proof ([F]₁= [f (x)]₁; [H]₂= [h(x)];v₁;v₂;₁;₂). We also consider p^(X), the algebraic representation of [P]₁as constructed by the verier. Note that₂is d 1 KZG opening proof for p(X) = p^(X) z(X)(¹() +²() z^Vn()X) opening to 0 at. We dene Game₁ identically to knowledge soundness, but after the adversary returns [z]₂along with the proof, Game₂ additionally checks whether f (₁) = v₁, f (₂) = v₂, p() = 0 and aborts otherwise. Note that Game₁ can extract f (X), h(x) because the adversary A is algebraic, and p(X) is constructed from them.

$$ [z]_{2} $$

$$ ([F]{1}=[f(x)]{1},[H]{2}=[h(x)],v{1},v_{2},\pi_{1},\pi_{2}) $$

$$ {\hat{p}}(X) $$

$$ [ P ]; $$

$$ \pi_{2} $$

$$ p(X)=\hat{p}(X)-z(X)(\rho_{1}(\alpha)+\rho_{2}(\alpha)-z_{V_{n}}(\alpha)X^{d-1}) $$

$$ \alpha $$

$$ [z]_{2} $$

$$ \mathsf{G a m e_{2}} $$

$$ f\big(\alpha_{1}\big)=v_{1},,f\big(\alpha_{2}\big)=v_{2},,p\big(\alpha\big)=0 $$

$$ f(X),,h(x) $$

We show the probability that f (₁) = v₁, f (₂) = v₂, p() = 0 is bounded by qSDH. We construct a reduction B₁ that takes as input a challenge [y]₁;:::;[y_q]₁. It runs the following reduction B_KZGas a subroutine. The B_KZGruns the adversary A against Game₀ over an srs in which [x]₁= [y]₁. Whever the adversary returns an output ([F]₁= [f (x)]₁; [H]₂= [h(x)];v₁;v₂;₁;₂;₃) that wins the Game₀ but not the Game₁ game, then B_KZGreturns the KZG openings

$$ p(X) $$

$$ f\big(\alpha_{1}\big)=v_{1},,f\big(\alpha_{2}\big)=v_{2},,p\big(\alpha\big)=0 $$

$$ \mathcal{B}_{1} $$

$$ [y]{1},\ldots,[y{q}]_{1} $$

$$ \mathcal {B} _ {\mathrm {K Z G}} $$

$$ \mathcal {B} _ {\mathrm {K Z G}} $$

$$ [x]{1}=[y]{1} $$

$$ ([F]{1}=[f(x)]{1},[H]{2}=[h(x)],v{1},v_{2},\pi_{1},\pi_{2},\pi_{3}) $$

$$ \mathcal {B} _ {\mathrm {K Z G}} $$

$$ \begin{array}{l} \left(\left(v _ {1}, [ F ] _ {1}\right) \text {a n d} \left(f \left(\alpha_ {1}\right), \left[ \frac {f (x) - f \left(\alpha_ {1}\right)}{x - \alpha_ {1}} \right]\right)\right), \left(\left(v _ {2}, [ F ] _ {1}\right) \text {a n d} \left(f \left(\alpha_ {2}\right), \left[ \frac {f (x) - f \left(\alpha_ {2}\right)}{x - \alpha_ {2}} \right]\right)\right) \text {o r} \ \left((0, [ P ] _ {1}) \text {a n d} (p (\alpha), \left[ \frac {p (x) - p (\alpha)}{x - \alpha} \right])\right) \ \end{array} $$

for either v₁ 6= f (₁), v₂ =6 f (₂) or p() 6= 0. Then B₁ can extract a q-SDH solution from these openings following the proof of Theorem 3 in [22]. Thus

$$ v_{1}\neq f(\alpha_{1}),v,{{2}}\neq f(\alpha{2}),\ \mathrm{o r},p(\alpha)\neq0 $$

$$ \ !{\cal B}_{1} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{k-s o u n d}}(\lambda)=\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{0}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)+\mathsf{A d v}{\mathcal{B}_{1}}^{\mathsf{G S H H}}(\lambda). $$

We dene Game₂ as Game₁ except that Game₂ additionally checks whether deg(z) 1 for z(X) being the algebraic representation of [z]₂, and aborts otherwise. We show that A’s advantage in both games is the same unless it breaks qDHE. Indeed, assume deg(z) = 2, we construct an adversary B₂ against qDHE. The B₂ takes as input the challenge [y₁]₁;:::;[y_q]₁and runs A against Game₁ over an srs in which [x]₁= [y]₁. When A returns an output ([F]1= [f (x)]1*;* [H]2= [h(x)]*;v₁;v₂;1;*2) that wins the Game₁ but not the Pd+1 s Game₂ game, then B₂ extracts p^(X) =_s=0p^_sX a_s the algebraic representation of [P]₁computed by d 1 the verier. Note that, since₁()₂() z_Vn()X z(X) _does not vanish at X =, we have ^(d+1^(1 d+1 that p^_d+16= 0. Then, B₂ sets P X) = P (X) p^_d+1X an_d outputs [P]₁[P x)]₁= [x]₁, _p^_d+1 wining d-DHE. Thus Game Game qDHE Adv () = Adv () + Adv ():

$$ \deg(z)\leq1,\ \ \mathrm{f o r}\ z(X) $$

$$ \mathsf{G a m e_{2}} $$

$$ \ {cal A A}^{\prime}\mathrm{s} $$

$$ [z]_{\ }2 $$

$$ \deg(z)=2 $$

$$ B{}_{2} $$

$$ \mathcal{B}_{2} $$

$$ [y_{1}]{1},\ldots,[y{q}] $$

$$ [x]{1}=[y]{1} $$

$$ ([F]{1}=[f(x)]{1},[H]{2}=[h(x)],v{1},v_{2},\pi_{1},\pi_{2}) $$

$$ B_{2} $$

$$ [P]_{1} $$

$$ \hat{p}(X)=\sum_{s=0}^{d+1}\hat{p}_{s}X^{s} $$

$$ {((-\ rho{}{1}(\alpha)-\check{\rho}{2}(\alpha)-{}z_{V_{n}}(\alpha)^{{}X^{d-1}}){{}_{}}z(X)} $$

$$ X=\alpha. $$

$$ \hat{p}_{d+1}\neq0 $$

$$ B{}_{2} $$

$$ \big([P]{1}-[\hat{P}(x)]{1}\big)\textstyle{\frac{1}{\hat{p}{d+1}}}=\big[x^{d+1}\big]{1} $$

$$ \hat{P}(X)=P\ X)-\hat{p}_{d+1}X^{d+1} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)=\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{q D H E}}(\lambda). $$

Finally, let us show that

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)\leq\mathsf{n e g l}(\lambda). $$

Consider f (X), h(X) the algebraic representations of [F]₁, [H]₁. The algebraic representation of the element [P]₁that the verier constructs is

$$ [F]{1},,[H]{1} $$

$$ f(X),,h(X) $$

$$ [P]. $$

$$ \begin{array}{l} p (X) = - z _ {V _ {n}} (\alpha) h (X) + \left(\rho_ {1} (\alpha) + \rho_ {2} (\alpha)\right) f (X) + \rho_ {3} (\alpha) \left((1 - \sigma) f (X) + v _ {1} - v _ {2}\right) + \rho_ {4} (\alpha) \left(f (X) + v _ {2} - \sigma v _ {1}\right) \ + \rho_ {5} (\alpha) \left(v _ {1} f (X) - v _ {2}\right) + \rho_ {n} (\alpha) \left(v _ {1} - 1\right) + \prod_ {i \notin [ 5, \dots , 4 + \log (N) ]} \left(\alpha - \sigma^ {i}\right) \left(f (X) - v _ {1} ^ {2}\right) \ \end{array} $$

1 2 Since Game₂ checks that v₁ = f ();v₂ = f (); we can replace these values and see that

$$ v_{1}=f\big(\sigma^{-1}\alpha\big),v_{2}=f\big(\sigma^{-2}\alpha\big) $$

$$ \mathsf{G a m e_{2}} $$

$$ \begin{aligned}{p(X)}&{{}=-z_{V_{\alpha}}(\alpha)h(X)+\big(\rho_{1}(\alpha)+\rho_{2}(\alpha)\big)f(X)+\rho_{3}(\alpha)\big((1-\sigma)f(X)+f(\sigma^{-1}\alpha)-f(\sigma^{-2}\alpha)\big)}\ {}&{{}+\rho_{4}(\alpha)\big(f(X)+f\big(\sigma^{-2}\alpha)-\alpha f(\sigma^{-1}\alpha)\big)+\rho_{5}(\alpha)\big(f(\sigma^{-1}\alpha)f(X)-f(\sigma^{-2}\alpha)\big)}\ {}&{{}+\rho_{n}(\alpha)\big(f(\sigma^{-1}\alpha)-1\big)+\sum_{i\notin[mathbb{S},\ldots,4+\operatorname{l o g}(N)]}(\alpha-\sigma^{i})\big(f(X)-f(\sigma^{-1}\alpha)^{2}\big)}\ \end{aligned} $$

Now, because p() = 0 and has been chosen by the verier after the prover has sent [H]₁; [F]₁, except in the negligible case that is a root of p(X), we have that p(X) 0, i.e,

$$ p(\alpha)=0 $$

$$ p(X) $$

$$ p(X)\equiv0,,\mathrm{i.e.} $$

$$ [H]{1},[F]{1} $$

$$ \begin{array}{l} z _ {V _ {n}} (X) h (X) = - \left(\rho_ {1} (X) + \rho_ {2} (X)\right) f (X) + \rho_ {3} (X) \left((1 - \sigma) f (X) + f \left(\sigma^ {- 1} X\right) - f \left(\sigma^ {- 2} X\right)\right) \ + \rho_ {4} (X) \left(f (X) + f \left(\sigma^ {- 2} X\right) - \sigma f \left(\sigma^ {- 1} X\right)\right) + \rho_ {5} (X) \left(f \left(\sigma^ {- 1} X\right) f (X) - f \left(\sigma^ {- 2} X\right)\right) \ + \rho_ {n} (X) \left(f \left(\sigma^ {- 1} X\right) - 1\right) + \prod_ {i \notin [ 5, \dots , 4 + \log (N) ]} \left(X - \sigma^ {i}\right) \left(f (X) - f \left(\sigma^ {- 1} X\right) ^ {2}\right) \ \end{array} $$

i n z^Vn(X) divides the right side of the equation and thus, the latter vanishes for all the powers f gⁱ₌₀₁. This implies that

$$ z_{V_{n}}(X) $$

$$ {\sigma^{i}}_{i=0}^{n-1} $$

$$ \bullet\ f(1)=a(1),,(f(\sigma)=a(\sigma) $$

$$ \bullet\ f(\sigma^{2})=\frac{v_{2}-v_{1}}{1-\sigma}=\frac{f(\sigma^{2}\sigma^{-2})-f(\sigma^{2}\sigma^{-1})}{1-\sigma}=\frac{f(1)-f(\sigma)}{1-\sigma} $$

$$ \bullet,f\ \bigl(\sigma^{3}\bigr)=r f\bigl(\sigma^{3}\sigma^{-1}\bigr)-f\bigl(\sigma^{3}\sigma^{-2}\bigr)=r f\bigl(\sigma^{2}\bigr)-f\bigl(\sigma\bigr) $$

$$ \operatorname{\bullet\ }f(\sigma^{4})f(\sigma^{4}\sigma^{-1})=f(\sigma^{4}\sigma^{-2}),\operatorname{\operatorname i.e,,}\ f(\sigma^{4})f(\sigma^{3}){\ =\ }f(\sigma^{2}) $$

$$ \bullet,1=f\bigl(\sigma^{5+\log(N)}\sigma^{-1}\bigr)=f\bigl(\sigma^{4+\log(N)}\bigr) $$

$$ \cdot \left(f \left(\sigma^ {4 + i + 1}\right) - f \left(\sigma^ {4 + i + 1} \sigma^ {- 1}\right) f \left(\sigma^ {4 + i + 1} \sigma^ {- 1}\right)\right) \left(\sigma^ {i} - \sigma^ {5 + \log (N)}\right) \prod_ {i = 1} ^ {5} \left(\sigma^ {i} - \sigma^ {j}\right) = 0 \text {f o r a l l} i = 0, \dots , \log (N) - $$

$$ \begin{array}{l l}{\mathrm{1.\ N o t e\ t h a t}:\prod_{j\in[5,\ldots+4\operatorname{l o g}(N)]}(\sigma^{i}{-}\sigma^{j})\neq0:\operatorname{i m p l i s s\ t h a t}:0=f dot\ (\sigma^{4+i+1})-f(\sigma^{4+i+1}\sigma^{-1})f(\sigma^{4+i+1}\sigma^{-1})=}\ {f(\sigma^{4+i+1})-f(\sigma^{4+i})^{2}.}\end{{}}\end{array} $$

a By Lemma1we have that z(X) = aX b where is ^an N-th root of unity. b

$$ \frac{a}{b} $$

$$ z(X)=a X-b $$

For zero-knowledge, we dene a simulator Simulate that has access to the trapdoor of srs and is indistinguishable from an honest prover. The simulator rst chooses s₁;s₂;v₁;v₂ uniformly at random 1 2 and sets [F]¹= [s₁]¹and [H]¹= [s₂]¹. It computes¹=,²=. It then computes 1 x 22 x 11 [w₁]¹= [F]¹v₁₁(x) v₂₂(x₎, for₁⁽x) =,₂(x) =. (^x 1)(x 2) 1 2

$$ s_{1},s_{2},v_{1},v_{2} $$

$$ [F]{1},=,[s{1}]_{1} $$

$$ [H]{1},=,[s{2}]_{1} $$

$$ \alpha_{1},=,\sigma^{-1}\alpha,,\alpha_{2},=,\sigma^{-2}\alpha $$

$$ [w_{1}]{1}=\left([F]{1}-v_{1}\tau_{1}(x)-v_{2}\tau_{2}(x)\right)\frac{1}{(x-\alpha_{1})(x-\alpha_{2})} $$

$$ \tau_{1}\big(x\big)=\frac{x-\alpha_{2}}{\alpha_{1}-\alpha_{2}},,\tau_{2}\big(x\big)=\frac{x-\alpha_{1}}{\alpha_{2}-\alpha_{1}} $$

It sets [P]₁the same as the verier i.e.

$$ [P]_{1} $$

$$ \begin{aligned}{[P]{1}}&{{}=-[H]{1}z_{V_{\alpha}}(\alpha)+[F]{1}\big(\rho{1}(\alpha)+\rho_{2}(\alpha)\big)+\big([F]{1}(1-\sigma)-v{2}+v_{1}\big)\rho_{3}(\alpha)+\big([F]{1}+v{2}-\sigma v_{1}\big)\rho_{4}(\alpha)}\ {}&{{}+\big([F]{1}v{1}-v_{2}\big)\rho_{5}(\alpha)+\big(v_{1}-1\big)\rho_{4}(\alpha)+\big([F]{1}-v{1}^{2}\big)\prod_{i\notin[5,\ ,pm+\operatorname{{l g g}}N N]}(\alpha-\sigma^{i})}\ \end{aligned} $$

d 1 1 and then computes [w₂]¹= ([P]¹(ⁿ() +¹() + z^Vn()x)z), where z = a is the output of x the simulator in the proof of Theorem1. It returns ([F]₁; [H]₁;v₁;v₂;₁= [w₁]₁;₂= [w₂]₂).

$$ [w_{2}]{1}=([P]{1}-(\rho_{n}(\alpha)+\rho_{1}(\alpha)+z_{V_{n}}(\alpha)x^{d-1})z)^{\frac{1}{x-\alpha}} $$

$$ z=a $$

$$ ([F]{1},[H]{1},v_{1},v_{2},\pi_{1}=[w_{1}]{1},\pi{2}=[w_{2}]_{2}) $$

We must argue that the simulators output is distributed identically to the honest provers. Then the provers components are randomised by

$$ \begin{array}{l} F: r _ {0} \rho_ {5 + \log (N)} (x) H: r (x) \ v _ {1}: r \left(\sigma^ {- 1} \alpha\right) z _ {V _ {n}} (\alpha) v _ {2}: r \left(\sigma^ {- 2} \alpha\right) z _ {V _ {n}} (\alpha) \ \end{array} $$

and the elements [w]₁; [w]₂are the unique elements satisfying the veries equations given [F]₁; [H]₁;v₁;v₂.

$$ [w]{1},[w]{2} $$

$$ [F]{1},[H]{1},v_{1},v_{2}. $$

1 2 The probability that the values r₁^6+log(N)(x), r(x), r()z^Vn(), r()z^Vn() are dependent for 1 random is negligible because r(X) is a random degree 2 polynomial and the probability that = x 2 ² or = x is. Where the simulators terms [F]₁; [H]₁;v₁;v₂ are chosen uniformly at random and jFj [w₁]1*;* [w₂]1are the unique terms that satisfy the veries equations, we have that these distributions are identical except with negligible probability.

$$ r_{1}\rho_{6+\operatorname{l o g}(N)}(x),\thinspace r(x),\thinspace r(\sigma^{-1}\alpha)z_{V_{n}}(\alpha),\thinspace r(\sigma^{-2}\alpha)z_{V_{n}}(\alpha) $$

$$ r(X) $$

$$ \sigma^{-1}\alpha=x $$

$$ \sigma^{-2}\alpha=x{\mathrm{i s}}{\frac{2}{|\mathbb{F}|}} $$

$$ [F]{1},[H]{1},v_{1},v_{2} $$

$$ [w_{1}]{1},[w{2}]_{1} $$

E Proof of Thm.3

Proof. We will proceed through a series of games to show that the protocol dened in Fig.4satises linkability as dened in Def.5.1. Let A be an arbitrary PPT adversary in the linkability game with linkability advantage Adv_A(). We dene Game₁, Game₂ and specify reductions B₁ and B₂ such that

$$ \ !{\mathcal{B}}{_{1}} $$

$$ B_{2} $$

$$ \mathsf{A d v}_{\mathcal{A}}^{\mathsf{l i n k a b i l i t y}}(\lambda) $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{l i n k a b i l i t y}}(\lambda)\leq\mathsf{A d v}{\mathcal{B}{1}}^{\mathsf{a S D H}}(\lambda)+\mathsf{A d v}{\mathcal{B}_{2}}^{\mathsf{k}\ \mathsf{s-o u u d}}(\lambda)+\mathsf{n e g l}(\lambda) $$

Let us transition from the linkability game for the protocol of Fig.4to a game Game₁. Game₁ behaves as linkability except that when A returns v₁;v₂, Game₁ checks whether u() = v₁, p₁(v₁) = v₂, and p₂() = 0, for u(X);p₁(X);p₂(X); the algebraic representations of [u]₁; [P₁]₁= [z_I]₁+ [C_I]₁; and [P₂]₁= v₂ cm z_Vm()[H₂]₁. If not then Game₁ aborts. We design B₁ such that

$$ v_{1},v_{2} $$

$$ p_{2}(\alpha)=0 $$

$$ u(\alpha)=v_{1},,p_{1}(v_{1})=v_{2}, $$

$$ u(X),p_{1}(X),p_{2}(X) $$

$$ [P_{2}]{1}=v{2}-\chi\mathsf{c m}-z_{V_{m}}(\alpha)[H_{2}]_{1} $$

$$ \mathcal{B}_{1} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{i n k a b i l i t y}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)+\mathsf{A d v}{\mathcal{B}_{1}}^{\mathsf{g S D H}}(\lambda) $$

Indeed, assume that A succeeds against linkability but not Game₁. Then this corresponds to the case where A returns verifying v₁; v₂; ₁; ₂; ₃but the equality does not hold for some p(X) 2 fu(X);p₁(X);p₂(X)g. Thus B₁ takes as input a challenge [y₁]₁;:::;[y_q]₁and runs the following reduction B_KZGas a subroutine. The B_KZGruns the adversary A against Game₀ over an srs in which [x]₁= [y₁]₁. Whenever the adversary wins the Game₀ but not the Game₁ game, then B_KZGreturns the KZG opening

$$ v_{1},;v_{2},;\pi_{1},;\pi_{2},;\pi_{3} $$

$$ p(X),\in $$

$$ {u(X),p_{1}(X),p_{2}(X)} $$

$$ \mathcal{B}_{1} $$

$$ [y_{1}]{1},\ldots,[y{q}]_{1} $$

$$ \mathcal{B}_{K Z G} $$

$$ \mathcal{B}_{K Z G} $$

$$ [x]{1}=[y{1}]_{1} $$

$$ \mathcal{B}_{K Z G} $$

$$ (\upsilon,\pi)\ \operatorname{a n d}\ (f(\alpha),[(f(x)-f(\alpha))/(x-\alpha)]_{1}) $$

for (v;f(X)) corresponding to either (v₁;u(X)), (v₂;p₁(X)), (v₃;p₂(X)) and the corresponding proof. Then B_qSDHcan extract a solution from these openings following the proof in Theorem 1 in [22].

$$ \mathcal{B}_{\mathsf{q S D H}} $$

$$ (v,f(X)) $$

$$ (v_{1},u(X)),,(v_{2},p_{1}(X)),,(v_{3},p_{2}(X)) $$

Now let us transition to a new game. Game₂ behaves identically except that when A returns [u]₁, j N then Game₂ checks whether its algebraic representation u(X) is such that u() = 1 for all j. If not then Game₂ aborts. We design B₂ such that

$$ [u]_{1} $$

$$ u(X) $$

$$ j $$

$$ u(\nu^{j})^{N}=1 $$

$$ B_{2} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{1}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)+\mathsf{A d v}{\mathcal{B}{2}}^{\mathsf{k-s o u n d}}(\lambda) $$

Assume that A succeeds against Game₁ but not Game₂. Then B₂ chooses [u]₁= [u(x)]₁in its own game and uses it as input to run A. When A returns_unity, B₂ forwards it and wins knowledge-soundness of unitywhenever A succeeds.

$$ \mathcal {B} _ {2} $$

$$ [u]_{1}=[u(x)] $$

$$ \pi_{\sf u n i t y},\mathcal{B}_{2} $$

$$ \Pi_{\mathsf{u n i t y}} $$

Next we transition to a game Game₃ that behaves as Game₂ except that when A returns its proof, Game₃ checks whether C(X) C_I(X) = z_I(X)H₁(X), for C(X);C_I(X);z_I(X);H₁(X) the algebraic representations of [C]₁; [C_I]₁; [H₁]₂; [z_I]₁. If not then Game₃ aborts. We design B₃ such that

$$ \mathcal{C}(X)-\mathcal{C}{I}(X)=z{I}(X)H_{1}(X) $$

$$ \mathcal{C}(X),\mathcal{C}{I}(X),z{I}(X),H_{1}(X) $$

$$ [C]{1},[C{I}]{1},[H{1}]{2},[z{I}]_{1} $$

$$ B{}_{3} $$

$$ \mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{2}}(\lambda)\leq\mathsf{A d v}{\mathcal{A}}^{\mathsf{G a m e}{3}}(\lambda)+\mathsf{A d v}{\mathcal{B}{3}}^{\mathsf{g S D H}}(\lambda) $$

$$ [y_{1}]{1},\ldots,[y{q}]_{1} $$

$$ \mathcal{B}_{3} $$

The B₃ takes as input a challenge [y₁]₁;:::;[y_q]₁and runs the adversary A against Game₂ over an srs in which [x]₁= [y₁]₁. Whenever the adversary wins the Game₂ but not the Game₃ game, then B₃ learns

$$ \mathsf{G a m e_{2}} $$

$$ d(X)=C(X)-C_{I}(X)-z_{I}(X)H_{1}(X) $$

$$ \ {{\mathcal{B}}_{3}} $$

such that d(x) = 0 and d(X) 6= 0. Thus B₃ returns (1*;[1=*(x 1)]₁) as a valid q-SDH solution.

$$ d(X)\neq0 $$

$$ (1,[1/(x-1)]_{1}) $$

$$ B{}_{3} $$

Finally we show that the probability that Game₃ returns 1 but that for some j 2 [m], and for ~c such PN that C(X) =_i=1c_{i i}(X), _j () 62 ~c

$$ j\in[m] $$

$$ C(X)=\sum_{i=1}^{N}c_{i}\lambda_{i}(X) $$

$$ \phi(\nu^{j})\not\in{\vec{c}} $$

is negligible.

$$ p_{2}(\alpha)=v_{2}-\chi\mathsf{c m}-z_{V_{m}}(\alpha)H_{2}(\alpha)=z_{I}(v_{1})+\chi C_{I}(v_{1})-\chi\mathsf{c m}-z_{V_{m}}(\alpha)H_{2}(\alpha)=z_{I}(u(\alpha))+ $$

Recall that p₂() = v₂ cm z^Vm()H₂() = z^I(v₁) +C^I(v₁) cm z^Vm()H₂() = z^I(u()) + C_I(u()) cm z_Vm()H₂() = 0*:* First, because has been sent by the verier after the prover commits to (X);z_I(X);u(X);H₂(X) and C_I(X), we have that

$$ \chi C_{I}(u(\alpha))-\chi\mathsf{c m}-z_{V_{m}}(\alpha)H_{2}(\alpha)\ {=}\ 0 $$

$$ \phi(X),z_{I}(X),u(X),H_{2}(X) $$

$$ C_{I}(X) $$

$$ z_{I}(u(X))+\chi C_{I}(u(X))-\chi\phi(X)-z_{V_{m}}(X)H_{2}(X)=0 $$

for all X except with negligible probability. Further, because has been sent by the verier after the prover commits, we have that there exists H₂_;1(X) and H₂_;2(X) such that

$$ \chi $$

$$ H_{2,1}(X) $$

$$ H_{2,2}(X) $$

$$ 0=z_{I}\big(u(X)\big)-z_{V_{m}}(X)H_{2,1}(X) $$

$$ 0=C_{I}(u(X))-\phi(X)-z_{V_{m}}(X)H_{2,2}(X) $$

except with negligible probability.

Thus,

$$ z_{I}(u(\nu^{j}))=z_{I}(\omega^{i_{j}})=0{\mathrm{f o ra l l~}}j=1,\ldots,m. $$

Q^mQ i_j i and zI(X) =j=1(X!)z^(X) =ⁱ2_I(X!)z^(X), for some polynomⁱal z^(X). From the second equation we also we have that

$$ z _ {I} (X) = \prod_ {j = 1} ^ {m} \left(X - \omega^ {i _ {j}}\right) \hat {z} (X) = \prod_ {i \in I} \left(X - \omega^ {i}\right) \hat {z} (X) $$

$$ \hat{z}(X) $$

$$ C_{I}(u(\nu^{j}))=\phi(\nu^{j})\ \forall\ j\in[m],\operatorname{i.e.,}\ C C_{I}(\omega^{i_{j}})=\phi(\nu^{j}). $$

Using

$$ C\left(u(X)\right)-C_{I}\left(u(X)\right)=z_{I}\left(u(X)\right)H_{1}\left(u(X)\right) $$

we hence gets that

$$ 0=C(u(\nu^{j}))-C_{I}(u(\nu^{j}))=C(\omega^{k})-\phi(\nu^{j}) $$

which concludes the proof.

[ ]

F Proof of Thm.5

Proof. We rst dene a simulator Simulate and then argue that their transcript is indistinguishable from an honest provers transcript. The Simulate subverts the setup algorithm such that it knows the secret x contained in [x]₁; [x²]₁; [x³]₁;:::. It takes as input some instance (C; cm) and aims to generate a verifying transcript.

$$ [x]{1},[x^{2}]{1},[x^{3}]_{1},\ldots $$

$$ (C,\mathsf{c m}) $$

It samples s₁; s₂; s₃; s₄; s₅; s₆;s₇;s₈ F at random and outputs [C_I]₁= [s₁]₁; [z_I]₁= [s₂]₁, [u]₁= [s₃]₁, [H₁]₂= [(C s₁)=s₂]₂and a simulated proof_unitythat we describe in the next paragraph. After receiving it outputs [H₂]₁= [s₄]₁. After receiving it outputs v₁ = s₅, v₂ = s₆. and

$$ \mathfrak{s}{1},\ mathfrak s{}{2},\ \mathfrak{s}{3},\ \mathfrak{s}{4},\ \mathfrak{s}{5},\ \mathfrak{s}{6},\mathfrak{s}{7},\mathfrak{s}{8}\leftarrow\mathbb{P} $$

$$ [\mathcal{C}{I}]{1},=,[s_{1}]{1},[z{I}]{1},=,[s{2}]_{1} $$

$$ \big[u\big]{1}=\big[\mathfrak{s}{3}\big]{1},\big[H{1}\big]{2}=\big[\big(\mathcal{C}-\mathfrak{s}{1}\big)\big/\mathfrak{s}{2}\big]{1} $$

$$ \pi_{\mathsf{u n i t y}} $$

$$ [H_{2}]{1}=[s{4}]_{1} $$

$$ v_{1}=s_{5},,v_{2}=s_{6} $$

$$ \begin{aligned}{\pi_{1}}&{{}=[(u-v_{1})/(x-\alpha)]{1}}\ {\pi{2}}&{{}=[(z_{I}+\chi C_{I})/(x-v_{1})]{1}}\ {\pi{3}}&{{}=[(v_{2}-\chi\mathsf{c m}-z_{V_{m}}(\alpha)H_{2})/(x-\alpha)]}\ \end{aligned} $$

To simulate_unitythe simulate Simulate outputs [U]₁= [s₇]₁, [h₂]₁= [s₈]₁. After receiving it outputs [h₁]₁= [s₉]₁. After receiving it outputs [U]₁= [s₁₀]₁, [h₂_;] = [s₁₁]₁and v₁ = s₁₂, v₂ = s₁₃, v₃ = s₁₄ and

$$ \pi_{\sf u n i t y} $$

$$ [\bar{U}]{1}=[s{7}]{1},[h{2}]{1}=[s{8}]_{1} $$

$$ [h_{1}]{1}=[s{9}]. $$

$$ \beta $$

$$ [\bar{U}{\alpha}]{1}=[s_{10}]{1},,[h{2,\alpha}]=[s_{11}]. $$

$$ v_{1}=s_{12},,v_{2}=s_{13},,v_{3}=s_{14} $$

$$ \pi_{1}=[\big(u-v_{1}\big)/\big(x-\alpha\big)]_{1} $$

$$ \pi_ {2} = \left[ \left(\bar {U} + \bar {U} _ {\alpha}\right) / (x - \alpha) \right] _ {1} $$

$$ \pi_{3}=[\big(h_{2}-h_{2,\alpha}\big)/\big(x-\alpha\big)\big]_{1} $$

$$ \pi_{4}=[x^{\mathsf m{x x_d e g}-n}(\bar{U_{\alpha}}+\ell(x))/(x-1)(x-\beta)(x-\beta\sigma)]_{1} $$

$$ \pi_{5}=[x^{\mathsf{m a x},mathsf d d d-n}big(\big(v_{1}\rho_{1}(\beta)+v_{2}\big)^{2}-h_{1}z_{V_{n}}\big(\beta)-\big(v_{3}+\mathsf{i d}(\alpha)\rho_{n}(\beta)\big)-z_{V_{m}}(\alpha)h_{2,\alpha}\big)/(x-\beta)]_{1} $$

where ‘(x) is the polynomial that interpolates to (0*;v₂;v₃*) at (1*;*).

$$ (0,v_{2},v_{3}) $$

$$ (1,\beta\beta\sigma) $$

$$ \ell(x) $$

We now argue Simulate’s output is indistinguishable from an honest prover’s output.

We consider each of the elements in Fig.4separately and argue they are identically distributed with overwhelming probability.

[C_I]₁is blinded by r₂ for the prover and s₁ for the simulator.

$$ [C_{I}]1 $$

$$ r_{2} $$

[z_I]₁is blinded by r₁ for the prover and s₂ for the simulator.

$$ s_{1} $$

$$ [z_{I}]_{1} $$

$$ r_{1} $$

$$ s_{2} $$

[u]₁is blinded by r₅ for the prover and s₃ for the simulator.

$$ [u]_{1} $$

$$ r_{5} $$

$$ s_{3} $$

[H₁]₂is the unique element satised by the pairing check for both the prover and simulator given [C_I]₁and [z_I]₁.

$$ [H_{1}]_{2} $$

$$ [C_{I}]_{1} $$

$$ [z_{I}]_{1} $$

u(x)zI(u(x)) [H₂]¹is blinded by r₃ for the prover and s₄ for the simulator. Note that r₃ is non-_zero ^zVm^(x) with overwhelming probability.

$$ s_{4} $$

$$ r_{3} $$

$$ [H_{2}]_{1} $$

$$ r_{3}\frac{\chi u(x)z_{I}(u(x))}{z_{V_{m}(x)}} $$

v₁ is blinded by r₆ for the prover and s₅ for the simulator. Note that r₆z_Vm() is non-zero with overwhelming probability.

$$ v_{1} $$

$$ r_{6} $$

$$ s_{5} $$

$$ r_{6}\alpha z_{V_{m}}(\alpha) $$

v₂ is blinded by r₄ for the prover and s₆ for the simulator. Note that r₄u²z_I(u()) is non-zero with overwhelming probability.

$$ v_{2} $$

$$ r_{4} $$

$$ s_{6} $$

$$ r_{4}u^{2}\alpha z_{I}(u(\alpha)) $$

1*;2;*3are the unique element satised by the KZG opening checks for both the prover and the simulator.

$$ \pi_{1},\pi_{2},\pi_{3} $$

Finally we consider each of the elements in Fig.5separately and argue they are identically distributed with overwhelming probability.

[U]₁is blinded by t₁ for the prover and s₇ for the simulator.

$$ [\bar{U}]_{1} $$

$$ t_{1} $$

$$ s_{7} $$

[h₂]₁is blinded by t₂ for the prover and s₈ for the simulator. Note that there exists a₂(x)t₂ term in the provers [h₂]₁which is linearly independent from all other terms and thus not cancelled with overwhelming probability.

$$ [h_{2}]_{1} $$

$$ t_{2} $$

$$ s_{8} $$

$$ \rho_{2}(x)t_{2} $$

$$ [ h _ {2} ] $$

2 2 ² 4(x) ^{4 (x)} [h₁]¹is blinded by t₃ for the prover and s₉ for the simulator. Note that there is a t₃z_V() m zVn(x) term in the provers [h₁]₁which is linearly independent from all other terms.

$$ t_{3} $$

$$ [h_{1}]_{1} $$

$$ s_{9} $$

$$ t_{3}^{2}z_{V_{m}}^{2}(\alpha)\frac{\rho_{4}^{2}(x)-\rho_{4}(x)}{z_{V_{n}}(x)} $$

$$ [h_{1}]_{1} $$

[U]₁is blinded by t₄ for the prover and s₁₀ for the simulator. Note that there is a t₄z_Vm()₅(x) term in the provers [U]₁which is linearly independent from all other terms.

$$ \left\lfloor{\bar{U}_{\alpha}}\right\rfloor. $$

$$ s_{10} $$

$$ t_{4} $$

$$ t_{4}z_{V_{m}}(\alpha)\rho_{5}(x) $$

$$ [\bar{U}{\alpha}]{1} $$

[h₂_;]₁is blinded by t₅ for the prover and s₁₁ for the simulator. Note that there is a₂(x)t₂ term in the provers [h₂_;]₁which is linearly independent from all other terms.

$$ [h_{2,\alpha}]_{1} $$

$$ s_{11} $$

$$ t_{5} $$

$$ \rho_{2}(x)t_{2} $$

$$ [ h _ {2, \alpha} ] _ {1} $$

v₁ is blinded by r₇ for the prover and s₁₂ for the simulator.

$$ v_{1} $$

$$ s_{12} $$

$$ r_{7} $$

v₂ is blinded by t₅ for the prover and s₁₃ for the simulator. Note that there is a t₅z_Vm()₆() term in the provers v₂ which is linearly independent from all other terms.

$$ t_{5}z_{V_{m}}(\alpha)\rho_{6}(\beta) $$

$$ t_{5} $$

$$ v_{2} $$

$$ s_{13} $$

$$ v_{2} $$

v₃ is blinded by t₆ for the prover and s₁₄ for the simulator. Note that there is a t₆z_Vm()₇() term in the provers v₃ which is linearly independent from all other terms.

$$ t_{6}z_{V_{m}}(\alpha)\rho_{7}(\beta) $$

$$ t_{6} $$

$$ v_{3} $$

$$ s_{14} $$

$$ \ _3 $$

1*;2;3;4;*5are the unique elements satised by the KZG opening checks for both the prover and the simulator.

$$ \pi_{1},\pi_{2},\pi_{3},\pi_{4},\pi_{5} $$