Ecient UC Commitment Extension with Homomorphism for Free (and Applications)

y z Ignacio Cascudo¹, Ivan Damgard², Bernardo David³, Nico Dottling⁴, y x Rafael Dowsle^y⁵, and Irene Giacomelli⁶

¹ IMDEA Software Institute, Madrid, Spain, ignacio.cascudo@imdea.org

² Aarhus University, Aarhus, Denmark, ivan@cs.au.dk

³ IT University of Copenhagen, Copenhagen, Denmark, bernardo@bmdavid.com

⁴ CISPA Helmholtz Center for Information Security, Saarbrucken, Germany, nico.doettling@gmail.com ⁵ Bar Ilan University, Tel Aviv, Israel, rafael@dowsley.net 6

Protocol Labs, Inc., Basel, Switzerland, irene@protocol.ai

Abstract. Homomorphic universally composable (UC) commitments allow for the sender to reveal the result of additions and multiplications of values contained in commitments without revealing the values themselves while assuring the receiver of the correctness of such computation on committed values. In this work, we construct essentially optimal additively homomorphic UC commitments from any (not necessarily UC or homomorphic) extractable commitment. We obtain amortized linear computational complexity in the length of the input messages and rate 1. Next, we show how to extend our scheme to also obtain multiplicative homomorphism at the cost of asymptotic optimality but retaining low concrete complexity for practical parameters. While the previously best constructions use UC oblivious transfer as the main building block, our constructions only require extractable commitments and PRGs, achieving better concrete eciency and oering new insights into the sucient conditions for obtaining homomorphic UC commitments. Moreover, our techniques yield public coin protocols, which are compatible with the Fiat-Shamir heuristic. These results come at the cost of realizing a restricted version of the homomorphic commitment functionality where the sender is allowed to perform any number of commitments and operations on committed messages but is only allowed to perform a single batch opening of a number of commitments. Although this functionality seems restrictive, we show that it can be used as a building block for more ecient instantiations of recent protocols for secure multiparty computation and zero knowledge non-interactive arguments of knowledge.

1 Introduction

A commitment scheme is the digital equivalent of a locked box containing a committed message chosen by a prover. Once the prover gives away the box to a verier, the content cannot be changed, the commitment is binding. On the other hand, the verier cannot look into the box so the message is hidden until the prover gives away the key to the box. Commitments are perhaps the most fundamental building block in cryptographic protocols and despite the conceptual simplicity of the primitive, it has far-reaching consequences and many applications, e.g., to coin-ipping, zero-knowledge proofs and many other things.

The simplest form of commitment that only have the basic binding and hiding properties follow from oneway functions. On the other hand, one may wish for many other properties, such as non-malleability, security under composition etc. The strongest form of commitments, namely UC secure commitments, has all these properties, but on the other hand can only be implemented under setup assumptions, such as the common

This work was done while Ignacio Cascudo was with Department of Mathematics, Aalborg University, Denmark.

^y This project has received funding from the European Research Council (ERC) under the European Unions’ Horizon 2020 research and innovation programme under grant agreement No 669255 (MPCPRO).

^z This work was partially supported by DFF grant number 9040-00399B (TrA²C).

^x This work was done while Irene Giacomelli was with the ISI Foundation (Turin, Italy) and supported by Intesa Sanapolo Innovation Center.

reference string model. In this model, UC commitments imply secure key exchange, so since some sort of public-key technology seems to be required, it was believed for a long time that even if UC commitments are the gold standard for security, they must be much less ecient than the weaker type that only requires symmetric primitives.

However, in [18] and independently in [24,9], this was shown to be false: one can push the use of publickey technology into a preprocessing phase that is only needed once and for all and the cost of which does not depend on the number of commitments to be done later. Notably, the actual commitment and opening protocols only requires simple nite eld algebra and a pseudorandom generator. After this, a long line of research optimized this approach [17,22], culminating in [16] where it was shown that after doing O(k + s) string OTs in the setup phase (where s is the statistical security parameter and k is the message length) one can commit at rate approaching 1, that is, the communication required is k + o(1) bits, furthermore the computational complexity is linear in k⁷. Finally, the commitments are additively homomorphic, i.e., k one commits to vectors over a nite eld F, and if a; b 2 F have been committed, prover and verier can compute a commitment to a + b which, if opened, would reveal only the sum.

$$ O(k+s) $$

$$ k^{7} $$

$$ a,b\in\mathbb{R}^{k} $$

The rst construction from this line of work [18] had also a multiplicatively homomorphic property, namely the prover can send the verier a single message, and this allows the verier to compute a commitment to a b, the coordinate-wise (Schur) product of the vectors. However, subsequent constructions did not have this property.

So, while this line of research has resulted in constructions that are optimal in several respects, it still leaves some important and natural questions unanswered:

$$ a*b $$

Is it overkill to use OT in the setup phase? All ecient earlier schemes [18,24,17,22,16] use OT in the preprocessing phase, but this is in general a stronger primitive than commitment. Even UC commitments do not always imply OT, this depends on the setup assumption. It is therefore natural to ask if we can make do with only commitment in the preprocessing, thus obtaining a proper \commitment extension" result.

Can we make an ecient multi-verier scheme? The commitments from [16], and in fact all constructions from this line of work, can only work with one verier because security against a corrupt prover depends on the verier’s private choice of selections bits in the initial OT’s. Thus, if a prover needs to commit towards several veriers, the only known solution is to run many instances of the scheme, one for each verier and then on top of this have the prover convince the veriers that (s)he committed to the same message. This seems quite far from an ideal solution.

Can we also get multiplicatively homomorphic schemes? The most ecient constructions are not multiplicative, but one earlier scheme was in fact \fully homomorphic" [18]. So it is natural to ask if we can solve the above problems and also get multiplication at the same time.

1.1 Our contributions

In this paper, we come up with positive answers to all of the above questions. We present a protocol for UC secure commitments that has the well known structure consisting of a preprocessing phase and a phase where the actual commitments are built, computed on and opened. In addition to achieving the same asymptotic eciency as the former best scheme [16] in the single-verier additive case, our protocol supports multiple veriers and multiplicative homomorphism.

In contrast to previous work, however, the preprocessing only makes use of a commitment scheme (and ⁸ not OT). Notably, however, this commitment scheme does not need to be homomorphic, and in fact it does

⁷ All this holds in an amortized sense, assuming we make enough commitments so that the cost of the setup phase is dwarfed.

⁸ The scheme of [9] can be constructed from an extractable commitment and an equivocal commitment. However, it is intrinsically incompatible with homomorphic operations.

not even need to be UC secure. It just needs to be extractable and hiding - here, extractable means that the simulator can extract the committed value from a corrupt prover. For UC full security one usually needs also equivocation (when the prover is honest, the simulator can fake a commitment and later open it to any value). The commitment scheme we build uses only a PRG and nite eld arithmetic after the preprocessing. It has rate 1, it is additively homomorphic, and linear time. Security does not depend on any secret choices of the verier, so the scheme easily extends to multiple veriers with no essential loss of security. Finally, we show how to make the scheme multiplicative, the scheme is then only quasilinear, and we get constant rate instead of rate 1.

All these results come at the cost that what we implement is a slightly weaker commitment functionality than the standard one. Namely, it allows opening of committed values only in a nal stage and after this the functionality stops working. Equivalently, one can think of this as a functionality one can use exactly as the standard one, except that when opening a value the prover simply tells the verier what the committed value is. Of course a corrupt prover can lie, but there is a nal verication stage where the prover will be caught if he lied.

We show that despite this limitation there are a wide range of applications for the scheme. While we describe these in more detail below, it is already intuitively clear that our functionality is sucient for ZK proofs, for instance: the verier needs to decide to accept or reject only at the end of the protocol so it is sucient that a cheating prover is caught at that point. As a simple example of the power of our construction, consider that UC secure commitments are easy to implement in the (global) random oracle model [11]: one simply inputs the message concatenated with some randomness to the oracle and uses the output as the commitment. Of course, a random oracle based scheme has no homomorphic properties: a random oracle \by denition" has no such structure. But nevertheless, we can use it as commitment scheme in our preprocessing and get a homomorphic scheme. In general, one can think of our protocol as a \commitment extension" result. It is similar to the well known OT extension protocols, but incomparable because we get extra homomorphic properties (and perhaps UC security) for free, but we realize a slightly weaker functionality.

Techniques. On the technical side, our approach is best described by referring to previous work such as [16]: the main idea there was that the prover commits to a vector a by encoding it using a linear code C. He then additively secret shares each coordinate in the codeword C(a) to get two shares for each position. Using the OT’s from the preprocessing, the verier will learn one out of the two shares for each position, however, the prover does not know which shares the verier has. To open, the prover must reveal C(a) and all shares, and the verier can now check that the prover sent a codeword and that the shares are consistent with C(a) and with the shares the verier knows.

Intuitively, since the verier has only one share of each coordinate, C(a) is unknown to him at commit time. On the other hand, if the prover wants to open a dierent value, he must change to a dierent codeword. However, if C has large minimum distance, this means the prover must change many coordinates and therefore must lie about many of the shares. Since he does not know which shares he can change without being detected, this can only be done with negligible success probability⁹.

In order to avoid having to do an OT for each codeword position and each commitment, instead the prover chooses seeds s_i;jfor a PRG, where i points to a codeword position and j = 0*;*1. The shares for all the commitments are then constructed by running the PRG on all these seeds and for each i an OT is done that transfers either s_i;0or s_i;1to the verier.

$$ s_{i,j} $$

$$ s_{i,0} $$

$$ s_{i,1} $$

Our key observation now is that it is actually sucient if the prover simply commits to the seeds in the preprocessing phase, if we are careful later. Namely, we run the same protocol as we would have done had the OTs been used, but at the end of the protocol, the verier will ask the prover to reveal either s_i;0or s_i;1 for each i. Note that, as long as a corrupt prover cannot predict which seeds he will be asked for, he is in

$$ s_{i,0} $$

$$ s_{i,\ } $$

⁹ This argument works, even if the prover did not choose a codeword at commit time. If we also want to have additive homomorphism, we need to check that the prover chose something that it at least close to a codeword. This can be done using, e.g., the interactive proximity testing from [16].

the exactly same position as in the original protocol. The verier will receive the same information as before, but cannot verify it until the end, so hence openings can only be done, or at least can only be veried, at the end. A corrupt verier clearly has no advantage compared to the OT based protocol: he learns the same information, only later.

A very nice \side eect" of this is that we can now easily have several veriers. They just need to receive the prover’s initial commitments (assuming, of course that the initial commitments support this). Then at the end, they can decide, e.g., by coin ipping which seeds to ask for.

We also extend the commitment scheme to allow for proving multiplicative relations on committed values. 2 For this purpose, we require the code C to have the property that its square C is also a good code, 2 with large minimum distance. Here C is dened to be the span of all pairwise Schur-products of words from C. Moreover, we replace the 2-party additive secret sharing by 3-party linear secret sharing which is multiplicative: the Schur-product of sets of shares of u;v 2 F is (essentially) an additive secret sharing of uv. The eect of all this is that if we multiply two commitments to a; b by multiplying corresponding components of them, we obtain a commitment to a b of essentially the same form as in the original protocol, except 2 that underlying code is now C. See more details within. The new demands we place on C imply that we can only get constant rate and not rate 1 and also that complexity will be quasilinear rather than linear. The main motivation for this construction is that we get the multiplicative property and at the same time have multiple veriers and use only commitment for preprocessing. An earlier scheme that achieves multiplicative homomorphism was constructed in [18] via building rst an elaborate VSS (veriable secret sharing) scheme. Our construction obtains similar asymptotic complexity, but it requires less conditions on the underlying linear code. Indeed, our multiplicatively homomorphic scheme can be constructed from any linear code whose minimum distance and squares minimum distance are large enough. In contrast, [18] requires in addition a code whose duals minimum distance is large enough (i.e., equivalent to multiplicative secret sharing scheme). Thanks to this, for xed security parameters we can give an explicit bound for the rate of our multiplicative commitment based on recent results on squares of cyclic codes (details in Section 4.1).

$$ \mathbb{C}^{*2} $$

$$ \mathbb{C}^{*2} $$

$$ u,v\in\mathbb{E} $$

$$ a*b $$

$$ \mathbb{C}^{*2} $$

1.2 Applications

Ecient Zero-Knowledge Arguments. A recent line of research is concerned with the construction of practically ecient succinct non-interactive zero-knownledge arguments of knowledge (e.g. [1,10,32]) with a particular focus on optimizing the eciency of the prover while keeping verication complexity sub-linear.

One such approach, originally dating back to [5], compiles a public coins interactive proof system for a language L into a zero-knowledge proof system for the same language. This transformation is conceptually simple: Instead of sending its messages to the verier in the clear, the prover provides only commitments of his messages to the verier. At the end of the protocol, the prover provides a zero-knowledge proof to the verier which asserts that the verier of the original proof system would accept the committed transcript. This transformation has received renewed interest in the light of ecient P-delegation schemes [25,30].

Wahby et al. [32] observed that this approach can be implemented in a particularly ecient way if the verier of the interactive proof system is algebraic: In this case the zero-knowledge proof in the transformation of [5] can be implemented very eciently via homomorphic commitments.

We show that using our homomorphic commitment scheme, this transformation can be performed at a very low overhead, i.e. we can convert any public coin interactive proof system with algebraic verier into an honest-verier zero-knowledge proof system such that the communication complexity of the protocol grows only by a small factor and both prover and verier incur only a small constant factor overhead. Using the Fiat Shamir transform [20], we can convert such a proof system into a succinct non-interactive zero-knowledge argument.

Committed MPC. The so called \Committed MPC" protocol [21] requires a multiparty additively homomorphic commitment protocol that supports additions of commitments generated by dierent senders. While a generic approach for constructing such schemes from any two-party additively homomoprhic commitments was proposed in [21], their generic construction for t parties requires t² calls to the underlying commitment scheme. If instantiated with the previously best two-party additively homomorphic commitment protocol of [16] using a [n;k;s] code, this construction would require nt² OTs plus extra communication in the order of O(nmt²) to commit to m messages of length k. We provide a new generic construction from multi-receiver additively homomorphic commitments which can be instantiated with our new protocols, requiring only nt non-homomorphic commitments (e.g. random oracle commitments) plus extra communication in the order of O(smt) to achieve the same.

$$ t^{2} $$

$$ [n,k,s] $$

$$ n t ^ {2} $$

$$ O(n m t^{2}) $$

Insured MPC. The topic of MPC with nancial penalties has attracted increasing attention recently [2,6,27,7,4]. The main idea is to combine MPC techniques with cryptocurrencies in order to provide monetary incentives for the participants to act honestly during the protocol execution. Insured MPC [4], the most ecient solution to date, uses a publicly veriable additively homomorphic multi-receiver commitment as an important component to build the protocol. However, the employed commitment scheme is a bottleneck in that construction as its complexity grows quadratically in the number of participants. Using our new techniques together with an authenticated bulletin board (which is also used in the previous construction), it is possible to dramatically improve the performance of publicly veriable additively homomorphic multi-receiver commitment. We can obtain extremely ecient instantiations, for instance, by using the canonical random oracle commitment scheme. The improvement in computational and communication complexity achieved for this application is very similar to that of the Committed MPC case, since the previously best protocol for publicly veriable additively homomorphic multi-receiver commitments [4] has a very similar structure to the multi-sender protocol of [21]. Thus, we basically go from quadratic to linear in the number of players.

2 Preliminaries

In this section we establish notation and introduce notions that will be used throughout the paper. We borrow much of the notation from [16].

2.1 Notation

The set of the n rst positive integers is denoted [n] = f1*;* 2*;:::;ng*. Given a nite set D, sampling a uniformly $ random element from D is denoted r D. Vectors of elements of some eld are denoted by bold lower-case letters, while matrices are denoted by bold upper-case letters. We denote nite elds by F and write F_qfor k the nite eld of size q. For z 2 F, z[i] denotes the i’th entry of the vector, where z[1] is the rst element n n of z. The coordinate-wise (Schur) product of two vectors is denoted by, i.e. if a; b 2 F, theⁿ a b 2 F aⁿd (a b)[i] = a[i]b[i]. If A [n], we will use_Ato denote the projection that outputs the coordinates n k with index in A of a vector. For a matrix M 2 F, we let M[;j] denote the j’th column of M and M[i;] denote the i’th row. The row support of M is the set of indices I f1*;:::;ng* such that M[i;] 6= 0.

$$ [n]={1,2,\ldots,n} $$

$$ D, $$

$$ r \leftarrow^ {$} D $$

$$ \mathbb{F} $$

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

$$ z[1] $$

$$ \ *b\in\mathbb{F}^{n} $$

$$ a,b\in\mathbb{F}^{n} $$

$$ (a*b)[i]=a[i]b[i] $$

$$ A\subseteq[n] $$

$$ \pi_{A} $$

$$ \mathrm{M}\in\mathbb{R}^{n\times k} $$

$$ \mathbf{M}[\cdot,j] $$

$$ \mathbf{M}[i,\cdot] $$

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

$$ \mathbf{M}[i,\cdot]\neq\mathbf{0} $$

We say that a function is negligible in n if for every positive polynomial p there exists a constant c 1 such that (n) < when n > c. Two ensembles X = fX;zg2N;z2f0;1gand Y = fY;zg2N;z2f0;1gof p(n) binary random variables are said to be statistically indistinguishable, denoted by X_sY, if for all z it holds that j Pr[D(X_;z) = 1] Pr[D(Y_;z) = 1] j is negligible in for every probabilistic algorithm (distinguisher) D. In case this only holds for computationally bounded (non-uniform probabilistic polynomial-time (PPT)) distinguishers we say that X and Y are computationally indistinguishable and denote it by_c.

$$ \epsilon (n) < \frac {1}{p (n)} $$

$$ n>c. $$

$$ X={X_{\kappa,z}}_{\kappa\in\mathbb{N},z\in{0,1}^{*}} $$

$$ Y={Y_{\kappa,z}}_{\kappa\in\mathbb{N},z\in{0,1}^{*}} $$

$$ X\approx_{s}Y $$

$$ \mid\operatorname*{P r}[\mathcal{D}(X_{\kappa,z}){\ =\ }1]-\operatorname*{P r}[\mathcal{D}(Y_{\kappa,z}){\ =\ }1] $$

$$ \approx_{c} $$

2.2 Coding Theory

n n For a vector x 2 F, we deⁿote the Hamming-weight of x by kxk₀ = jfi 2 [n] : x[i] 6= 0gj. Let C F be a ⁿ linear subspace of F. We say that C is an F-linear [n;k;d] code, if C has dimension k and it holds for every

$$ \boldsymbol{x}\in\mathbb{F}^{n} $$

$$ |\ \ x{\big|}_{0}=\left|\left{i\in[n]:x[i]\neq0\right}\right. $$

$$ \mathsf{C}\subset\mathbb{F}^{n} $$

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

$$ [n,k,d] $$ nonzero x 2 C that kxk₀ d, i.e., the minimum distance of C, denoted dist(C), is at least d. The distance n dist(C*; x*) between C and a vector x 2 F is the minimum of kc xk₀ when c 2 C. The rate of an F-linear k d [n;k;d] code is aⁿd its relative minimum dista_nce is. ⁿ n

$$ x\in\mathbb{C} $$

$$ |x|_{0}\geq d, $$

$$ \mathsf{d i s t(C)} $$

$$ C, $$

$$ \boldsymbol{x}\in\mathbb{F}^{n} $$

$$ |c-x|_{0} $$

$$ c\in\mathbb{C} $$

$$ \mathsf{t}(\mathsf{C},\mathfrak{x}) $$

$$ [n,k,d] $$

$$ \frac{d}{m} $$

$$ \frac{k}{n} $$

n k k A matrix G 2 F is a geⁿerator matrix of C if C = fGx : x 2 F g, and we write C(x) = Gx. The code C is systematic if it has a generator matrix G such that the submatrix given by the top k rows of G is the k k identity matrix I 2 F.

$$ \overset{\cdot}{\mathbb{G}}\in\mathbb{F}^{n\times k} $$

$$ {\mathsf{C}}({\pmb x{}})=={\mathbf{G}}{\pmb{x}} $$

$$ \acute{\mathsf{C}}=\left{\mathbf{G}x:x\in\mathbb{F}^{k}\right} $$

$$ \mathbf{I}\in\mathbb{F}^{k\times k} $$

m For an F-linear [n;k;d] code C, we denote by C the m-interleaved product of C, which is dened by m n m m n ^m C = fC 2 F : 8i 2 [m] : C[;i] 2 Cg. In other words, C consists of all F ^matrices for which m m all columns are in C. We can think of C as a linear code with symbol alphabet F, where we obtain codewords by taking m arbitrary codewords of C and bundling together the components of these codewords m n m m into symbols from F. For a ^matrix E 2 F, kEk₀ is the number of nonzero rows of E, and the code C ^m has minimum distance at least d⁰ if all nonzero C 2 C satisfy kCk₀ d⁰. With this denition, it is easy m to see that dist(C) = dist(C)

$$ [n,k,d] $$

$$ \mathsf{C}^{\odot m} $$

$$ C, $$

$$ \mathrm {C} ^ {\odot m} = \left{\mathbf {C} \in \mathbb {F} ^ {n \times m}: \forall i \in [ m ]: \mathbf {C} [ \cdot , i ] \in \mathrm {C} \right} $$

$$ \mathsf{C}^{\odot m} $$

$$ \mathbb{F}^{n\times m} $$

$$ \mathsf{C}^{\odot m} $$

$$ \mathbb{F}^{m} $$

$$ \mathbb{F}^{m} $$

$$ \mathbf{E}\in\mathbb{F}^{n\times m},,|\mathbf{E}|_{0} $$

$$ {\bf E}, $$

$$ \mathsf{C}^{\odot m} $$

$$ |\mathbf{C}|_{0}\geq d^{\prime} $$

$$ \mathbf {C} \in \mathrm {C} ^ {\odot m} $$

$$ {mathsf{d i s t}}(\mathsf{C}^{\odot m})={\mathsf{d i s t}}(\mathsf{C}) $$

$$ d^{\prime} $$

2 For an F-linear [n;k;d] code C, we denote by C the Schur square of C, which is dened as the linear n ^ ^] code subspace of F generated by all the possible vectors of the form v w with v; w 2 C. This is an [n; k;d where k^ k and d^ d.

$$ [n,k,d] $$

$$ \mathbb{C}^{*2} $$

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

$$ [n,\hat{k},\hat{d}] $$

$$ v,w\in\mathbb{C} $$

$$ \hat{d}\leq d $$

$$ \hat{k}\geq k $$

2.3 Interactive Proximity Testing and Linear Time Building Blocks

We will use the interactive proximity testing technique and corresponding linear time building blocks introduced in [16]. As stated in [16], this technique consists in the following argument: suppose we sample a m ‘ function H from an almost universal family of linear hash functions (fro^m F to F), and we apply this to n m n ‘ each of the rows of a matrix X 2 F, obtaiⁿing another matrix X⁰ 2 F; because of linearity, if X m ‘ belonged to an interleaved code C, then X⁰ belongs to the interleaved code C. Theorem 1 states that m ‘ we can test whether X is close to C by testing instead if X⁰ is close to C (with high probability over the choice of the hash function) and moreover, if these elements are close to the respective codes, the set of rows that have to be modied in each of the matrices in order to correct them to codewords are the same.

$$ \bar{\mathbb{F}^{m}}\mathbin{\ t_{0}}\mathbb{F}^{\ell}) $$

$$ \mathbf{X},\in,\mathbb{F}^{n\times m} $$

$$ \mathbf{X}^{\prime},\in,\mathbb{F}^{n\times\ell}; $$

$$ \mathsf{C}^{\odot m} $$

$$ \mathbf{X}^{\prime} $$

$$ C^{\odot\ell}. $$

$$ \mathsf{C}^{\odot m} $$

$$ \mathbf{X}^{\prime} $$

$$ \mathbb{C}^{\odot\ell} $$

Denition 1(Almost Universal Linear Hashing [16]). We say that a family H of linear functions n s ⁿ F*!* F is-almost universal, if it holds for every non-zero x 2 F that

$$ W e $$

$$ \mathbb{F}^{n}\to\mathbb{F}^{s} $$

$$ \mathbf{x}\in\mathbb{R}^{n} $$

$$ \operatorname*{P r}_{\mathbf{H}\stackrel{s}{\leftarrow}\mathcal{H}}[\mathbf{H}(\mathbf{x})=0]\leq\epsilon, $$

s where H is chosen uniformly at random from the family H. We say that H is universal, if it is jF j-almost universal. We will identify functions H 2H with their transformation matrix and write H(x) = H x*.*

$$ \mathbb{F}^{-s} $$

$$ H\in{\mathcal{H}} $$

$$ \mathbf{H}(\mathbf{x})=\mathbf{H}\cdot\mathbf{x} $$

m 2s+t 2s Theorem 1(Theorem 1 in [16]). Let H : F*!* F be a family of jFj-almost universal F*-linear hash* n m functions. Further let C be an F*-linear* [n;k;s] code. Then for every X 2 F at least one of the following s $ statements holds, except with probability jFj over the choice of H H :

$$ \mathcal{H}:\mathbb{F}^{m}\rightarrow\mathbb{F}^{2s+t} $$

$$ \left\vert\mathbb{F}\right\vert^{-2s} $$

$$ [n,k,s] $$

$$ \mathbb{X}\in\mathbb{F}^{n\times m} $$

$$ |\mathbb{F}|^{-s} $$

$$ \mathbf {H} \leftarrow^ {$} \mathcal {H}: $$

(2s+t) 1. XH has distance at least s from C

$$ \mathbf{X}\mathbf{H}^{\top} $$

$$ \mathsf{C}^{\odot(2s+t)} $$

(2s+t) m > 2.For every C⁰ 2 C there exists a C 2 C such that XH C⁰ and X C have the same row support

$$ \mathbf{C}^{\prime}\in\mathsf{C}^{\odot(2s+t)} $$

$$ \iota\ \mathbf{C}\in\mathsf{C}^{\odot m} $$

$$ \mathbf{X}\mathbf{H}^{\top}-\mathbf{C}^{\prime} $$

$$ \mathrm{X}C-\mathrm{C} $$

Remark 1([16]). If the rst item in the statement of the Theorem does not hold, the second one must hold. Then we can eciently recover a codeword C with distance at most s 1 from X using erasure correction, (2s+t) > given a codeword C⁰ 2 C with di^stance at most s 1 from XH. More specically, we compute the row

support of XH C⁰, erase the corresponding rows of X and recover C from X using erasure correction¹⁰. The last step is possible as the distance between X and C is at most s 1.

$$ 1\ (\ !6) $$

$$ \mathbf{C}^{\prime}\in\mathsf{C}^{\odot(2s+t)} $$

$$ s-1 $$

$$ \mathbf{X}\mathbf{H}^{\top} $$

$$ \mathbf{X}\mathbf{H}^{\top}-\mathbf{C}^{\prime} $$

$$ s-1. $$

¹⁰ Recall that erasure correction for linear codes can be performed eciently via gaussian elimination.

In order to achieve linear time and optimal rate (i.e., rate-1) in our constructions, we will need to instantiate interactive proximity testing with a family of linear time almost universal linear hash functions and a linear time encodable error correcting code that achieves rate 1. Theorems 3 and 6 from [16] guarantee that explicit constructions of such building blocks exist.

$$ ({..e.,,{mathrm\ r r a t e{1}}}) $$

The following theorem is a strengthening of Theorem 3 of [16] in that the output of the hash functions is guaranteed to be uniformly random given that its rst l inputs are uniformly random. The full proof is given in Supplementary Material Appendix B.

Theorem 2. Fix a nite eld F of constant size, let s 2 N be a statistical security parameter, let n 2 N and l+n l s let l = s + O(log(n)). Then there exists an explicit family H : F*!* F of jFj-universal hash functions that can be represented by O(s²) bits and computed in time O(n). Moreover, it holds for any function H 2H that if x = (x₁;:::;x_l;:::x_l+n) is such that the x₁;:::;x_lare independently uniform and x_l+1;:::;x_l+nare independent of x₁;:::;x_l, then H(x) is distributed uniformly random.

$$ s\in\mathbb{N} $$

$$ n\in\mathbb{N} $$

$$ l=s+O(\log(n)) $$

$$ \mathcal{H}:\mathbb{F}^{l+n}\rightarrow\mathbb{F}^{l} $$

$$ |\mathbb{F}|^{-s} $$

$$ O(s^{2}) $$

$$ H\in{\mathcal{H}} $$

$$ i!,\mathtt f,mathtt=left(x_{1},\dots,x_{l},\dots x_{l+n}) $$

$$ x_{1},\ldots,x_{l} $$

$$ x_{l+1},\ldots,x_{l+n} $$

$$ x_{1},\ldots,x_{l} $$

2.4 Universal Composability

The protocols presented in this paper are proven secure in the Universal Composability (UC) framework introduced by Canetti in [12]. We refer the reader to the Supplementary Material Appendix A and [12] for further details.

Adversarial Model: Our protocols will be proven secure against static and active adversaries. In other words, the adversary may deviate from the protocol in any arbitrary way and can only corrupt parties before the protocol execution starts.

Functionality FCOM

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ P, $$

$$ V\ = $$

$$ {V_{1},\ldots,V_{t}} $$

$$ P,V,m) $$

$$ m\in\left{0,1\right}^{\lambda} $$

$$ V_{i}\in V $$

$$ s i d,s s i d) $$

$$ P, $$

$$ (s s i d,P,V,m) $$

$$ V_{i}\in V $$

Fig. 1. Functionality FCOM.

$$ \mathcal{F}_{\mathrm{C O M}}. $$

Setup Assumption: Since UC commitment protocols cannot be obtained in the plain model [13], they need a setup assumption, i.e., a resource available to all parties before the protocol starts. In this work, our goal is to prove security in the F_COM-hybrid model [12,14], where the parties have access to an ideal (non-homomorphic) commitment functionality (our constructions are described in the F_COM-hybrid model for the sake of clarity, but they actually only need the underlying commitments to be extractable). Functionality F_COMis described in Figure 1. Notice that we describe a version of F_COMthat operates with a set V of multiple receivers instead of a single receiver. However, F_COMcan operate as a standard two-party commitment functionality with a single receiver by setting V = fV₁g, in which case it can be realized in the CRS model under dierent assumptions with security against static malicious adversaries by a number of protocols such as [13,28,8].

$$ i.e. $$

$$ \mathcal{F}_{\mathrm{C O M}\ \mathrm{h y b r i}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V=\left{V_{1}\right} $$

A recent result by Camenisch et al. [11] shows that the \canonical" random oracle commitment realizes this functionality in the Global Random Oracle model without extra computational assumptions achieving security against static malicious adversaries. We observe that the protocol in [11] supports multiple receivers. In this protocol, the sender commits to a message m with randomness r by sending to the receiver the output c of the global random oracle when queried on (r; m) and opens by revealing (r; m), which allows the receiver to verify by querying the global random oracle with the pair (r; m) received as opening and checking that the response is equal to c. Given that the random oracle functionality in this model is global, any number of receivers who have received the commitment and the opening can trivially obtain the same result in the verication.

$$ (r,m) $$

$$ (r,m) $$

$$ (r,m) $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{S} $$

$$ V,=,{V_{1},\ldots,V_{t}} $$

$$ s i d,s s i d,P,V) $$

$$ \imath\gets{0,1}^{\lambda}, $$

$$ P,V) $$

$$ V_{i}\in V $$

$$ P, $$

$$ m,\in,{0,1}^{\lambda}. $$

$$ V_{i}\in V $$

$$ \left(\mathfrak{a d d},\mathfrak{s i d},\mathfrak{s s i d}{1},\mathfrak{s s i d}{2},\mathfrak{s s i d}_{3},P,V\right) $$

$$ P: $$

$$ (s s i d_{2},P,V,m_{2}) $$

$$ (s s i d_{1},P,V,m_{1}) $$

$$ \ (s s i d_{3},P,V,m_{1}+m_{2}) $$

$$ (\mathsf{a d d},\mathsf{s i d},\mathsf{s s i d}{1},\mathsf{s s i d}{2},\mathsf{s s i d}_{3},P,V, $$

$$ P, $$

$$ V_{i}\in V $$

$$ s i d, s s i d _ {1}, \dots , s s i d _ {o}) $$

$$ {s s i d_{1},\ldots,s s i d_{o}} $$

$$ P,V,m) $$

$$ V_{i}\in V $$

$$ P,V,m) $$

Fig. 2. Functionality FAHCOM

| Augment the functionality $ \mathcal{F}_{\mathrm{AHCOM}} $ (Figure 2) with the step：

• Multiplication：Upon receiving a message（mult，sid，ssid1，ssid2，ssid3，P,V）from P：If tuples(ssid1,P,V,m1)，(ssid2,P,V,m2) were previously recorded and ssid3 is unused，record(ssid3,P,V,m1*m2)和 send the message（mult，sid，ssid1，ssid2，ssid3,P,V,success)to P，every receiver $ V_{i}\in V $and S。

$$ P: $$

$$ (s i s{}{3},P,V,m{1}\ *m_{2}) $$

$$ P, $$

$$ V_{i}\in V $$

Fig. 3. Functionality FMHCOM

$$ \mathcal{F}_{\mathrm{M H C O M}} $$

Ideal Functionalities: In Section 3, we construct an additively homomorphic string commitment protocol that UC-realizes functionality F_AHCOM, described in Figure 2. Similarly to a functionality of [16], F_AHCOM augments the standard multiple commitments functionality F_MCOMfrom [14] by introducing a command for adding two previously stored commitments and an abort command in the Commit Phase. Moreover, F_AHCOMgives an honest sender commitments to random messages instead of letting it submit a message as input, which can be straightforwardly used to commit to arbitrary messages with additive homomorphism as shown in [16] and discussed in Appendix C. In order to model corruptions, functionality F_AHCOMlets a corrupted sender choose the messages it wants to commit to. The abort is necessary to deal with inconsistent commitments that could be sent by a corrupted party. However, dierently from [16] or [14], this functionality can operate with a set V of multiple receivers but only allows for a single opening of a batch of commitments, after which it halts, not allowing further commitments, additions or openings. Notice that this functionality can operate as a two-party commitment functionality with a single receiver by setting V = fV₁g. Section 4 shows how to modify the construction of Section 3 to obtain a protocol that UC-realizes the augmented functionality F_MHCOM(Figure 3), which also allows for multiplication of committed values.

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{M C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ V=\left{V_{1}\right} $$

3 Rate-1 Linear Time Additively Homomorphic Commitments

In this section, we construct a linear time additively homomorphic commitment protocol that achieves amortized rate-1 and linear time in the length of committed messages assuming an extractable (not homomorphic) commitment and a PRG as building blocks. Protocol_AHCOMrealizes F_AHCOM, which only allows for commitments to random messages. Interestingly, in this case we can achieve sublinear communication complexity in the commitment phase while maintaining rate-1 in the opening phase. Even though committing to random messages is useful for a number of applications (e.g. [23]) that F_AHCOMis sucient for building a protocol ARBHCOMthat commits to arbitrary messages achieving rate-1 and running in linear time as discussed in [16] and Appendix C. Essentially, Protocol_AHCOMachieves the same asymptotic eciency as the former best UC commitment scheme [16], while supporting multiple veriers and without requiring OT in the preprocessing phase, resulting in better concrete eciency.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \Pi_ {\mathrm {A R B H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

The main idea is to use a \delayed watchlist" mechanism where the sender rst commits to seeds that will be stretched by a PRG to instantiate the watchlist but only allows the receivers to learn the watch bits in a later point, at which the receivers choose a random subset of the seed commitments to be opened. Basically, the watchlist is viewed as a matrix R = R₀ + R₁ such that, for each row of R, the receiver learns only a row from either R₀ or R₁ without revealing to the sender which one. Instead of using a number of 1-out-of-2 random OTs to obtain seeds that are stretched to generate each line of R₀ or R₁ in the beginning of the protocol as in previous works, the receiver relies on simple commitments to each seed sent by the sender. This scheme achieves rate-1 using similar techniques as [16]: rst having the sender adjust the bottom bits of the watchlist matrix R so that its columns are codewords of random strings (in the top bits of R) and then using interactive proximity testing to convince the receiver that these columns are indeed \very close" to codewords. In order to \open" a commitment, the sender reveals the columns from both R₀ and R₁ corresponding to that commitment, allowing a receiver who knows rows from each of these matrices to check that the revealed column vector corresponds to the watchlist with high probability. However, in our new scheme, the receiver only chooses which commitments to seeds will be revealed after the sender has sent this opening information. Otherwise, the sender would learn which rows of R₀ or R₁ the receiver would check, being able to open commitments to arbitrary messages. Protocol_AHCOMis described in Figures 4 and 5.

$$ \mathbf{R}=\mathbf{R}{0}+\mathbf{R}{1} $$

$$ \mathbf{R}_{0} $$

$$ \mathbf{R}_{1} $$

$$ \mathbf{R}_{0} $$

$$ \mathbf{R}_{1} $$

$$ \mathbf{R}_{0} $$

$$ \mathbf{R}_{1} $$

$$ \mathbf{R}_{0} $$

$$ \mathbf{R}_{1} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

In comparison to the protocol of [16], our scheme realizes a functionality with a caveat that only one opening of a batch of commitments is allowed (after which it terminates). However, this limited functionality is sucient for a number of applications that we discuss in later sections. Moreover, our protocol has two important properties that the scheme of [16] lacks: it is public coin and supports multiple receivers. Notice that the watch bits of the receiver (represented by a row from either R₀ or R₁) are chosen at random but in public by the receiver. Hence, given an underlying commitment that support multiple receivers (e.g., the canonical random oracle commitment scheme), it is sucient to have the receivers run a simple commit-thenopen coin tossing protocol to choose the watch bits they will learn, then have the sender publicly open his seed commitments. Interestingly, having the receivers broadcast their coin tossing commitments at the beginning of the protocol (before the sender broadcasts opening information), allows the simulator to both equivocate and extract commitments solely by extracting the underlying commitments. Notice that the simulator can equivocate a commitment by knowing in advance the watch bits to be learned by the receivers and extract a commitment by learning the whole watchlist, which are xed in the sender’s seed commitments. In order to eliminate interaction with the receivers, the random watch bits to be opened can be selected with the help of a random oracle following the Fiat-Shamir heuristic.

$$ \mathbf{R}_{0} $$

$$ {\mathbf{R}}_{1}) $$

$$ (e,g. $$

Eciency. We achieve the same asymptotic complexity as [16] but with a preprocessing phase that can be instantiated with lower concrete complexity since it only requires extractable commitments. All phases of the_AHCOMrun in linear time (requiring a constant number of operations per committed bit) when we use a linear time PRG (i.e., with a constant number of operations per generated bit [31]) a linear time encodable code C (e.g. the one from [16]) and a linear time linear almost universal hash function H (e.g. the one from [16]). The cost of the calls to F_AHCOMis amortized over the number of commitments, which

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ (i,e. $$

$$ \textit{C}(e.g. $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$ does not need to be very large if F_AHCOMis instantiated with cheap random oracle based commitments. The commitment phase achieves sublinear communication complexity when committing to random messages, since a rate-1 [n;k;s]-code C is used and only W*;T₀;T₁ (of size O(1)) are exchanged. Even if the trick from [16] (described in Appendix C) is used to commit to arbitrary messages, only k extra bits need to be sent per message. In this case, our protocol achieves rate-1, meaning that the amortized overhead per committed bit is o(1) for a suciently large number of commitments. The opening phase as described in Figure 5 does not achieve rate-1, since the sender has to send both A₀[;j*] A₁[;j]. However, it can be modied to achieve rate- 1 using the same technique from [16], where a batch of commitments are opened by performing interactive proximity testing on a matrix A⁰ containing the columns of A corresponding to the commitments to be opened. The receivers can use another coin-tossing to select a hash function H, then the sender sends A⁰, 0 0 0 0 0 ⁰ T₀ = A₀ H and T₁ = A₁ H. The receivers check that A⁰H=T₀ +T₁, that all columns in A⁰ are in C and 0 0 that T₀ + (I)T₁ = B⁰H, where B⁰ contains the columns from B corresponding to the commitments being checked. This technique can be proven secure with the same techniques used for the case of a corrupt sender.

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ [n,k,s] $$

$$ \bf{W},{bf_{0}},{\bf{T_{1}}} $$

$$ O(1)_{\ }^{\top} $$

$$ o(1) $$

$$ \mathbf{A_{0}}[\cdot,j];\mathbf{A_{1}}[\cdot,j] $$

$$ \ \mathbf{A}^{\prime} $$

$$ {\bf{H}}, $$

$$ \ \mathbf{A}^{\prime} $$

$$ {\mathrm{T_{0}}}^{\prime}={\mathrm{A_{0}}}^{\prime} $$

$$ \mathbf{T_{1}}^{\prime}=\mathbf{A_{1}}^{\prime}\mathbf{H} $$

$$ \mathbf{A}^{\prime}\mathbf{H}=\mathbf{T_{0}}^{\prime}{+}\mathbf{T_{1}}^{\prime} $$

$$ \ \mathbf{A}^{\prime} $$

$$ \Delta \mathbf {T} _ {0} ^ {\prime} + (\mathbf {I} - \Delta) \mathbf {T} _ {1} ^ {\prime} = \mathbf {B} ^ {\prime} \mathbf {H} $$

$$ \mathbf{B}{}^{\prime} $$

3.1 Security Analysis

For the sake of clarity, we will prove Protocol_AHCOM’s security in the F_COM-hybrid model, i.e. assuming access to an ideal functionality for commitments. The proof of security for Protocol_AHCOMis very similar to that of the scheme of [16], with the exception that all information the simulator needs to extract and equivocate commitments will be obtained from F_COMinstead of an OT functionality. However, our simulator will only rely on the fact that it can extract the messages sent by the adversary to F_COMbefore it opens its commitments. Essentially, our simulators only need an underlying commitment scheme that is extractable, not a full blown UC commitment scheme (which would also allow the simulator to open the underlying commitments to arbitrary messages). The security of Protocol_AHCOMis formally stated in Theorem 3.

$$ \mathit{\Pi}_{\mathrm{A H C O M}}^{\prime}\mathit{\mathbf{s}}} $$

$$ \mathcal{F}_{\mathrm{C O M}\ \mathrm{h y b l}} $$

$$ i.e. $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

Theorem 3. Protocol_AHCOMUC-realizes F_AHCOMin the F_COM-hybrid model with computational security against a static adversary. Formally, there exists a simulator S such that for every static adversary A, and any environment Z, the environment cannot distinguish^AHCOMcomposed with F_COMand A from S composed FCOM with F_AHCOM. That is, IDEAL_{FAHCOM;S;Z c}HYBRID_;A;Z: _AHCOM

$$ \mathcal{F}_{\mathrm{C O M}}\ \ y b $$

$$ \mathit{\Pi}_{\underline{{A H}O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathsf{i s},;\mathsf{I D E A L}{\mathcal{F}{\mathbf{A H C O M}},\mathcal{S},\mathcal{Z}}\approx_{c}\mathsf{H Y B R I D}{\mathcal{H}{\mathbf{A H I C O M}},\mathcal{A},\mathcal{Z}}^{\mathcal{r}_{\mathbf{C O M}}} $$

Proof. Constructing a simulator for the case where all parties are honest is trivial. Hence, the theorem follows straightforwardly from Lemma 2 and Lemma 3 (Appendix D), which establish security against an adversary that corrupts P and all but one receiver in V by constructing the simulator S_P(Figure 12) or an adversary who corrupts all receivers in V by constructing the simulator S_V(Figure 13), respectively.

$$ \ {mathcal S P_{{}\ }} $$

$$ \mathcal{S}_{V} $$

4 Achieving Multiplicative Homomorphism

In this section, we modify our additively homomorphic commitment protocol described Section 3 (protocol_AHCOM) so that it is also homomorphic for (coordinatewise) multiplication of messages. That is, if we denote the scheme from Section 3 by com, our goal is that given commitments com(a), com(b) the prover can construct a commitment com(a b). In order to do this we need to introduce a second auxiliary commitment scheme prodcom, also described below.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ (a*b) $$

Both com and prodcom can be obtained by changing the instantiation of two of the building blocks of protocol_AHCOM. Namely, at the core of the construction of the commitment scheme in Section 3 (as well as in the ones from [16,17,22]) there is a linear error correcting code C, which is used to encode the message and which needs to have a large enough minimum distance; and there is the 2-out-of-2 additive secret sharing scheme Add₂, which is applied to each coordinate of the encoding. Our modications are as follows: rst, we 2 need a linear code C such that also its (Schur) square C has a large enough minimum distance. We will use

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathsf{A d d}_{2}. $$

$$ \mathbb{C}^{*2} $$

Protocol AHCOM

$$ [n,k,s] $$

$$ \Pi_{\mathrm{A}} $$

$$ k+O(s) $$

$$ \mathsf{P R G}:{0,1}^{\ell}\to{0,1}^{m+\ell} $$

$$ \mathbf{I}:{0,1}^{m}\to{0,1}^{l} $$

$$ \Pi_{\mathrm{A}}] $$

$$ V={V_{1},\ldots,V_{t}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \ i d,s s i d_{1},\ldots,s s i d_{m},P,V), $$

$$ i\in[n] $$

$$ j\in{0,1} $$

$$ \boldsymbol {s} _ {i, j} \leftarrow^ {$} {0, 1 } ^ {\ell} $$

$$ s i d,s s i d_{i,j},P,V,\mathfrak{s}_{i,j}\big) $$

$$ \mathbf{R}=\mathbf{R_{0}}+\mathbf{R_{1}} $$

$$ \mathcal{F}_{\mathrm{C O M}}. $$

$$ {\bf R}{0},{\bf R}{1} $$

$$ \mathbf{R}{\mathbf{j}}[i,\cdot]=\mathsf{P R G}(\mathbf{s}{i,j}) $$

$$ n-k $$

$$ \mathsf{A}:=\mathsf{R}+\mathsf{W}\in\mathsf{C}^{\odot m+l} $$

$$ \ {tt A A}{0}={\tt R}{0},{\tt A}{1}={\tt R}{1}+{\tt W} $$

$$ (s i d,s s i d_{1},\ldots,s s i d_{m},\mathtt{W}) $$

$$ n-k=O(s) $$

$$ (s i d,s s i d_{1},\ldots,s s i d_{m},\mathtt{W}) $$

$$ V_{i}\in V $$

$$ s i d,s s i d_{i,j},P,V) $$

$$ P, $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \ _{i}\stackrel{\ast}{\longleftarrow}{0,1}^{n} $$

$$ \boldsymbol {r} _ {i} ^ {\prime} \leftarrow^ {$} {0, 1 } ^ {\ell}, $$

$$ V_{i},V^{\prime},{\ {r_{i}}^{\prime}}) $$

$$ \mathcal{F}_{\mathrm{C O M}}^{a}. $$

$$ V^{\prime}=P\cup V\setminus V_{i} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V_{j},V^{\prime}) $$

$$ V_{j},\in,V,\setminus,V_{i}, $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \left(\mathsf{r e v e a l},s i d,s s i d^{\prime},V_{j},V^{\prime},{r_{j}}^{\prime}\right) $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V_{j}\in V\setminus V_{i}, $$

$$ r r^{\prime}={r_{1}}^{\prime}\oplus\ldots\oplus{r_{t}}^{\prime}. $$

$$ s i d,s s i d,V_{i},V^{\prime}) $$

$$ ,V_{j},V^{\prime},{\mathbf{r}_{j}}^{\prime}) $$

$$ V_{j};\in;V,\ P $$

$$ {r^{\prime}}={r_{1}}^{\prime}\oplus\ldots\oplus{r_{t}}^{\prime} $$

$$ \mathbf{H}\in{\mathcal{H}} $$

$$ \mathcal{H} $$

$$ \mathbf{P},,\mathbf{P_{0}} $$

$$ {\bf P}_{1} $$

$$ \mathbf{A_{1}} $$

$$ \mathbf{A},,\mathbf{A}_{0} $$

$$ \mathbf{A_{1}} $$

$$ \mathbf{A},,\mathbf{A}_{0} $$

$$ \mathbf{A_{1}} $$

$$ \mathbf{P}=\mathbf{P_{0}}+\mathbf{P_{1}} $$

$$ i\in{0,1} $$

$$ \mathbf{T}{i}=\mathbf{A}{i}\mathbf{H}+\mathbf{P}_{i} $$

$$ \mathbf{A H+} $$

$$ s s i d_{1},\ldots,s s i d_{m},\mathbf{T_{0}},\mathbf{T_{1}}\big) $$

$$ \mathbf {P} = \mathbf {A} _ {0} \mathbf {H} + \mathbf {P} _ {0} + \mathbf {A} _ {1} \mathbf {H} + \mathbf {P} _ {1} = \mathbf {T} _ {0} + \mathbf {T} _ {1}, \text {a n d} \mathbf {A H} + \mathbf {P} \in C ^ {\odot l} $$

^a We abuse notation and assume that each receiver Vi in AHCOM has access to an instance of FCOM that takes as message with the appropriate length where it acts as sender and where all other receivers plus sender P act as receivers.

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V_{i} $$

Fig. 4. Commit phase for the protocol AHCOM.

$$ \mathit{\Pi}_{\mathrm{A H C O M}}. $$

2 C as the linear code in com and C as the linear code in prodcom (with a certain caveat described below). As for the secret sharing schemes, we will use the replicated secret sharing scheme RSS₃ (described below) for com and the additive 3-out-of-3 Add₃ secret sharing scheme for prodcom. RSS₃ is the secret sharing scheme where the secret s 2f0*;* 1g is additively split into three parts, i.e., s = r₀ +r₁ +r₂ where r₀;r₁ are uniformly random and independent, and the shares are dened to be the pairs s₀ = (r₀;r₁), s₁ = (r₁;r₂), s₂ = (r₂;r₀). RSS₃ is a multiplicative secret sharing scheme, which means that shares of s;s⁰ can locally be transformed into shares by Add₃ of the product s s⁰. More precisely, s s⁰ = t₀ +t₁ +t₂, where tⁱ= rⁱrⁱ⁰+ rⁱrⁱ⁰⁺¹+ rⁱ⁰rⁱ⁺¹ (where sums in the indices are modulo 3) and note that all this information is contained in the i-th shares ⁰ⁱ s_i;s of s and s⁰.

$$ \mathbb{C}^{*2} $$

$$ {\mathsf R S S}_{3} $$

$$ {\mathsf S S}{\mathsf S}_{3} $$

$$ \ {tt A A d}_{3} $$

$$ s\in{0,1} $$

$$ s=r_{0}+r_{1}+r_{2} $$

$$ r_{0},r_{1} $$

$$ {mathsf R S S}_{3} $$

$$ s_{0}=(r_{0},r_{1}) $$

$$ s_{1}=\ r_{1},r_{2}),,s_{2}=\ r_{2},r_{0}, $$

$$ \mathsf{A d d}_{3} $$

$$ s,s^{\prime} $$

$$ s\cdot s^{\prime}=t_{0}+t_{1}+t_{2} $$

$$ s\cdot s^{\prime} $$

$$ t_{i}=r_{i}r_{i}^{\prime}+r_{i}r_{i+1}^{\prime}+r_{i}^{\prime}r_{i+1} $$

$$ s_{i},s_{i}^{\prime} $$

$$ s^{\prime} $$

The rationale for the choices of codes and secret sharing schemes is then that from the watchlists of com(a)*;*com(b) a verier can compute a watchlist to a commitment prodcom(a b). Indeed, given the j-th

Protocol AHCOM

Addition of Commitments

1.On input (add*;sid;ssid₁;ssid₂;ssid₃;P;V*), P nds indexes i and j corresponding to ssid₁ and ssid₂ respectively and check that ssid₃ is unused. P appends the column A[;i]+ A[;j] to A, likewise appends to A₀ and A₁ the sum of their i-th and j-th columns, and associates ssid₃ with the new column index. P broadcasts m0 (add*;sid;ssid₁;ssid₂;ssid₃*). Note that this maintains the properties A = A₀ + A₁ and A 2 C, where m⁰ is the current number of columns (after appending columns for addition results).

$$ s s i d_{2} $$

$$ j $$

$$ ,mathfrak s i i,s s i d_{1},s s i d_{2},s s i d_{3},P,V) $$

$$ s s i d_{1} $$

$$ \mathbf{A}[\cdot,i]+!\mathbf{A}[\cdot,j] $$

$$ \mathbf{A_{1}} $$

$$ \mathbf{A}_{0} $$

$$ \ i d,s s i d_{1},s s i d_{2},s s i d_{3}\big) $$

$$ m^{\prime} $$

$$ \mathbf{A}=\mathbf{A_{0}}+\mathbf{A_{1}} $$

$$ \mathbf {A} \in \mathrm {C} ^ {\odot m ^ {\prime}} $$

2.Upon receiving (add*;sid;ssid₁;ssid₂;ssid₃*), every receiver Vi 2 V stores the message.

$$ V_{i}\in V $$

Opening

1.On input (reveal*;sid;ssid₁;:::;ssido*), P nds the set J = fj₁;:::;jog of indexes associated to ssid₁;:::;ssido and broadcasts (sid;ssid₁;:::;ssido;(A₀[;j];A₁[;j])j2J).

$$ s i d,s s i d_{1},\ldots,s s i d_{o} $$

$$ J={j_{1},\ldots,j_{o}} $$

$$ s s i d_{1},\ldots,s s i d_{o} $$

2.Upon receiving message (sid;ssid₁;:::;ssido;(A₀[;j];A₁[;j])j2J), every Vi 2 V sends (reveal*;sid;ssid*) to 0 FCOM and waits for (reveal*;sid;ssid;Vj;V; rj*) from FCOM for all Vj 2 V n Vi. Vi sets r = r₁ rt and sets the diagonal matrix such that it contains r[1];:::; r[n] in the diagonal.

$$ (s i d,s s i d_{1},\ldots,s s i d_{o},(\mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j])_{j\in J}). $$

$$ V_{i}\in V $$

$$ \mathcal{F}_{\mathrm{C O N}} $$

$$ (\mathsf{r e v e a l},s i d,s s i d) $$

$$ V _ {j}, V ^ {\prime}, \boldsymbol {r} _ {j}) $$

$$ V_{j}\in V\setminus V_{i}.\ V_{i} $$

$$ r=r_{1}\oplus\cdots\oplus r_{t} $$

$$ \mathfrak{r}[1],\ldots,\mathfrak{r}[n] $$

$$ V _ {j}, V ^ {\prime}, \boldsymbol {r} _ {j}) $$

0 3.Upon receiving (reveal*;sid;ssid;Vj;V; rj*) from FCOM for all Vj 2 V, P sets r = r₁ ::: rt, sends (reveal*;sid;ssid*i;r[i]) to FCOM for i 2 [n] and halts.

$$ V_{j}\ \in\ V $$

$$ r,=,r_{1}\oplus\ldots\oplus r_{t} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V_{j};\in;V $$

$$ i\in[n] $$

4.Upon receiving (reveal*;sid;ssidi;r[i];P;V; s*i;r[i_]) from FCOM for i 2 [n], every receiver Vj 2 V proceeds as follows: (a)Compute S[i;] = PRG(s_i;r[i]), obtaining a matrix S. Note that each row of S is a row from either R₀ or R₁, which form an additive secret sharing of R held by P. Set B = W + S. Dene the matrix Q as the rst l columns of B and remove these columns from B, renumbering the remaining columns from m

1. Note that, for A from the commitment phase, A = A₀ + A₁*;* B=A₁ + (I)A₀*;* A 2 C*;* i.e., A initially held by P is additively shared and for each row index, V knows either a row from A₀ or from A₁.

$$ \mathsf{S}[i,\cdot]=\mathsf{P R G}(\mathfrak{s}_{i,r[i]}) $$

$$ \mathbf{R_{0}} $$

$$ \mathbf{R_{1}}, $$

$$ \mathbf{B}=\mathbf{\Delta W}+\mathbf{S} $$

$$ \mathbf{A}{\mathrm{}{=}}\ \mathbf{A}{\mathrm{}{{0}}}+\mathbf{A}{\mathrm{}{{1}}},\ \mathbf{B}{\mathrm{}{=}}\ \mathbf{\Delta}\mathbf{A}{\mathrm{}{{1}}}+(\mathbf{I}-\mathbf{\Delta})\mathbf{A}{\mathrm{}{{0}}},\ \mathbf{A}{\mathrm{}{\ }}\mathbf{\in{}}\ mathbf C{{}}^{odot{m}} $$

$$ \mathbf{A}_{0} $$

l (b)Check that T₁ + (I)T₀ = BH + Q and that T₀ + T₁ 2 C. If any check fails, abort. Notice that T₀*;*T₁ form an additive sharing of AH + P, where V knows some of the shares, namely the rows of BH + Q.

$$ \ mathrm A{}_{1} $$

$$ \Delta\mathbb{T}{1}+(\mathrm{I}-\Delta)\mathbb{T}{0}=\mathrm{B H}+\mathbb{Q} $$

$$ \mathbf{T_{0}}+\mathbf{T_{1}}\in\mathsf{C}^{\odot l} $$

$$ \mathbf{A H}+\mathbf{P}. $$

(c)For every message (add*;sid;ssid₁;ssid₂;ssid₃*) received from P, append B[;j] + B[;i] to B, where i and j are the index corresponding to ssid₁ and ssid₂ respectively and associate ssid₃ with the new column index. Note that this maintains the property B = A₁ + (I)A₀.

$$ \mathrm{B H}Q $$

$$ \left(\mathrm {a d d}, s i d, s s i d _ {1}, s s i d _ {2}, s s i d _ {3}\right) $$

$$ P, $$

$$ \mathbf{B}[\cdot,j]+\mathbf{B}[\cdot,i] $$

$$ \mathbf {B} = \Delta \mathbf {A} _ {1} + (\mathbf {I} - \Delta) \mathbf {A} _ {0}. $$

(d)For every j 2 J, check that A₀[;j] + A₁[;j] 2 C and that, for i 2 [n], it holds that B[i;j] = A_r[i][i;j] (recall that r[i] is the i-th entry on the diagonal of). If all checks succeed, for every j 2 J, output the rst k positions in A₀[;j] + A₁[;j] as the opened string and halt. Otherwise, abort by outputting (sid;ssidj; ?).

$$ j\in J $$

$$ \mathbf{A_{0}}[\cdot,j]+\mathbf{A_{1}}[\cdot,j]\in\mathsf{C} $$

$$ \mathbf{B}[i,j]=\mathbf{A}_{r[\mathbf{i}]}[i,j] $$

$$ r[i] $$

$$ i\in[n] $$

$$ \Delta) $$

$$ j\in J, $$

$$ \mathbf{A_{0}}[\cdot,j]\dot{+}\mathbf{A_{1}}[\cdot,j] $$

$$ (s i d,s s i d_{j},\bot) $$

Fig. 5. Addition of commitments and opening phase for the protocol AHCOM.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

share (in RSS₃) of the i-th coordinates (C(a))_i;(C(b))_ithe verier can determine the j-th share (in Add₃) of 2 (C(a) C(b))_i, and note C(a) C(b) is a codeword in C having a b as the vector of its rst k coordinates.

$$ {\mathsf S S{\ S}}_{3}) $$

$$ (\mathsf{C}(\mathbf{\mathit{a}})){i},(\mathsf{C}(\mathbf{\mathit{b}})){i} $$

$$ j-\mathrm{t h} $$

$$ (\mathrm{i n},{\mathsf{A d}}_{3}) $$

$$ (\mathsf{C}(\mathsf{a})*\mathsf{C}(b))_{i} $$

$$ \mathbb{C}^{*2} $$

$$ {\mathsf{C}}(a)*{\mathsf{C}}(b) $$

$$ a*b $$

But our goal is to construct com(a b) rather than prodcom(a b). We do that as follows: the prover constructs commitments com(y), prodcom(y) of a random vector y with both commitment schemes, where for every coordinate i, the verier will later request to open the share with the same index r_iin prodcom(y) as he does for com(a)*;com(b);com(y) (note that for com that means the additive shares indexed by r_iand r_i+ 1). The sender needs to prove that com(y), prodcom(y) are indeed commitments to the same vector, which will be detailed later. From com(a);com(b) the prover constructs all the shares in prodcom(a b) as mentioned above, and then announces all three additive shares of a b y. For each coordinate i, the receiver will be able to determine the r_i-th share of this vector from the watchlists of com(a);com(b);*prodcom(y)

$$ (a*b) $$

$$ \mathrm{c o m}(y) $$

$$ (a*b) $$

$$ r_{i} $$

$$ r_{i}+1) $$

$$ r_{i} $$

$$ {\tt{c o m}}(a),{\tt{c o m}}(b),{\tt{c o m}}(y) $$

$$ \mathrm{c o m}(y) $$

$$ (a*b) $$

$$ a{*}b{-}y. $$

$$ r_{i}\mathrm{{-t h} $$

$$ {\tt c o m}(a),{\tt c o m}(b),{\tt p r o d c o m}(y) $$ and contrast this with the information that the prover opens. Now assuming the verier does not abort, the 11 prover and verier can simply construct com(a b) by adding a b y to com(y).

We need to address however some small technical details: commitments with prodcom are to messages 2 of length k⁰ (the dimension of C) rather than messages of length k and in general it can happen that k⁰ > k, so when we say prodcom(y) we mean that the commitment is to a vector yjjz where z is of length k⁰ k. Moreover, initially we cannot choose the random vectors we commit to since these are generated pseudorandomly from the seeds, so the prover will need to send some correction information in order to commit to the same value in the two schemes. In order to do that, and simultaneously prepare to prove that com(y) and prodcom(y) are commitments to the same vector y, we dene the linear code Ce dened as the 2 concatenation of C and C. More precisely,

$$ a*b-y $$

$$ ((a*b) $$

$$ \mathtt{c o m}(y) $$

$$ \mathbb{C}^{*} $$

$$ k^{\prime}>k $$

$$ k^{\prime}-k $$

$$ y||z $$

$$ \mathbb{C}^{*2} $$

$$ \widetilde{\mathsf{C}}={(y,c,y,c^{\prime}):(y,c)\in\mathsf{C},(y,c^{\prime})\in\mathsf{C}^{*2}}. $$

(1)

n The prover, having used the PRGs to construct pairs of random vectors r; r⁰ in f0*;* 1g aⁿd additive splittings n e of them, will concatenate the two vectors and send correction information z 2f0*;* 1g² so that (rjjr⁰) z 2 C (as before, the rst k bits of z can be taken to be 0, so the prover needs to send only 2n k bits). Now given a batch of supposed codewords of this form the interactive proximity testing technique is applied so that the sender proves they are indeed codewords in Ce, and therefore they are associated to commitments (com(y)*;*prodcom(y)).

$$ r,r^{\prime} $$

$$ {0,1}^{n} $$

$$ z\in{0,1}^{2n} $$

$$ (\boldsymbol{r}||\boldsymbol{r}^{\prime})-\boldsymbol{}\boldsymbol{z}\in\widetilde{\mathsf{C}} $$

$$ 2n-k $$

$$ \tilde{\mathbb C} $$

Note that since the rst n coordinates of the codewords in Ce are codewords in C, this test also guarantees all properties of the interactive proximity test for the additive case, so we do not need to perform that one separately.

$$ \widetilde{C} $$

e = dist(Ce) ^{2 12 2} We note that d dist(C), so in this case we will need a lower bound on dist(C) to obtain the same guarantees as in the additive case. Furthermore, a dierence with the proof for the additive-only commitment scheme is that now the verier sees 2 out of 3 additive shares of the rst n coordinates and 1 out of 3 coordinates of the last n, which aects the cheating probabilities of a corrupt prover: we will show that 2 it is enough to assume that dist(C) > s, where = 1*=(log₂ 3 1) = 1:* 709*:::* (which satises (2*=3) = 1=*2), s in order to guarantee that the cheating prover can succeed with probability at mo^st 2.

$$ \cdot(\mathbb{C}^{*2}) $$

$$ \widetilde{d}=\mathsf{d i s t}(\widetilde{\mathsf{C}})\geq\mathsf{d i s t}(\mathsf{C}^{*2}), $$

$$ n. $$

$$ \mathsf{J i s t}(\mathsf{C}^{*2})>\beta s $$

$$ \beta!=!1/(\log_{2}3!-!1)!=!1.709. $$

$$ (2/3)^{\beta}=1/2) $$

$$ 2^{-s} $$

Protocol_MHCOMis described in Figures 6, 7 and 8. Notice that for consistency with the notation of Section 3, we describe our fully homomorphic commitment protocol for random messages. However, a commitment to chosen messages m can be created using the protocol_MHCOMsimply sending c = m a, where a =_[k](A[;i]) is one of the random message that the prover gets in the commit phase of_MHCOM (same technique used in Appendix C). Now, in order to allow multiplication of commitments to chosen messages it is enough that all the players locally adjust the shares of the random messages used as OTP keys 0 (e.g., the prover P adds C(c) to A₂[;i] and every receiver in V adds C(c) and C(c) to B[;i] and B⁰[;i], respectively) and then execute the multiplication step as detailed in Figure 7.

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ c=m-a. $$

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ \ =\pi_{[k]}(\mathbf{A}[\cdot,i]) $$

$$ \mathit{\Pi}_{\mathrm{M H}} $$

$$ \mathrm {C} (\boldsymbol {c}) $$

$$ \mathbf{A}_{2}[\cdot,i] $$

$$ \Delta\mathsf{C}(\mathbf{c}) $$

$$ \mathsf{\Delta}^{\prime}\mathsf{C}(\mathbf{c}) $$

$$ \mathbf{B}[\cdot,i] $$

$$ \mathbf{B}^{\prime}[\cdot,i] $$

Finally notice that for the sake of simplicity, in the commit phase of Protocol_MHCOMwe use the same notation and the same construction both for random messages that are actually input to commitments (or used to construct a commitment to a chosen message as explained above) and for the auxiliary random messages that are needed in the multiplication step (i.e., y in the notation used in the introduction of this section), so that all those messages are encoded in columns of the big matrix A~. However, committing with prodcom,

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ (i.e,,y $$

$$ \tilde{\bf A} $$

¹¹ More precisely, the last share of each coordinate of C(y) is added with the corresponding (now public) coordinate of C(a b y).

$$ Cmathsf(y) $$

$$ C \left(a * b - y\right) $$

¹²e)2 One could be tempted to think that the tighter lower bound dist(C dist(C) + dist(C) holds, but this is 2 not necessarily true if the dimension k⁰ of C is larger than k, as in that case there will be codewords of the form k n k k n k k 2 ^k (0*;* 0*;* 0*; c⁰*) where c⁰ 6= 0. Iⁿdeed ta^ke (0*; c⁰*) to be the encoding by C of a vector (0 jjz) for a nonzero k0k z 2f0*;* 1g

$$ \sf{d i s t}(\tilde{C})\geq\sf{d i s t}(C)+\sf{d i s t}(C^{*2}) $$

$$ k^{\prime} $$

$$ (\mathbf{0}^{k},\mathbf{0}^{n-k},\mathbf{0}^{k},\mathbf{c}^{\prime}) $$

$$ C^{*} $$

$$ k, $$

$$ c^{\prime}\neq0^{n-k} $$

$$ (\mathbf{0}^{k},\mathbf{c}^{\prime}) $$

$$ \ ^{*} $$

$$ (\mathbf{0}^{k}||z) $$

$$ z\in{0,1}^{k^{\prime}-k} $$ and hence creating and manipulating the last n rows of the matrix A~ (what we call A^), is only necessary for the random messages used in the multiplication step, and could be saved for the remaining random messages. On the other hand, the current structure of the commit phase, where we do not distinguish between the two roles for the random messages, allows us to use only a single interactive proximity test instead of two (i.e., one for C as in protocol to guarantee the additive property and another one for Ce and the auxiliary AHCOM 2 random messages to guarantee that the same value y is encoded using C and C).

$$ \tilde{\mathbf A} $$

$$ \hat{\mathbf{A}}) $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathbb{C}^{*2} $$

$$ \tilde{C} $$

4.1 Eciency

Since we choose to commit to every random message with both com and prodcom, the total length of the commitment will be 2n k + o(k) bits per message of k bits. For chosen messages we need to add an extra k bits per message for a total of 2n bits. If C has rate R, our commitments have then rate R=2. Moreover, for multiplying two commitments the prover needs to have created an additional commitment of a random message with both com and prodcom (hence communicating 2n bits), and then communicate all shares of a related commitment with prodcom (the w_i’s in the protocol), which amounts to 3n bits. So the communication 2 of this step is 5n bits. The question is then what rates we can have under our new requirements on dist(C).

$$ 2n-k+o(k) $$

$$ 2n $$

$$ R/2 $$

$$ \ {boldsymbol w_{i}} $$

Asymptotical families of binary codes fC_ng with constant rate (of C_n) and constant relative minimum 2 distance of C_nexist based on algebraic geometry [29]. For xed values of the security parameter s, the families of cyclic codes constructed in [15], while not asymptotically good, give better rates. As an example, 2 for s = 60, where our protocol needs dist(C) 103, Table 2 in [15] gives a [4095*;338] cyclic code with 2 13 dist(C) 135, which has rate around 0:* 08. Hence the commitments will have rate 0*:* 04. We need to send 25k bits per k-bit message we commit to, and 62*:* 5k bits to construct a commitment to the product of two messages.

$$ \mathsf{d i s t}(\mathsf{C}^{*2}) $$

$$ \left{\mathsf{C}_{n}\right} $$

$$ \mathbb{C}_{n}^{*2} $$

$$ \mathbb{C}_{n}) $$

$$ s, $$

$$ s,6,=,60 $$

$$ \mathsf{t}(\mathsf{C}^{*2}),\geq,103 $$

$$ \mathsf{d i s t}(\mathsf{C}^{*2})\geq135 $$

Security Analysis. The proof of security for Protocol_MHCOMis similar to that of_AHCOM. Indeed, the following Theorem 4 can be proved by adapting the description of simulators S_Pand S_Vfrom Appendix D (resp. Figure 12 and Figure 13) to the new watchlist setting (i.e., three additive shares instead of two, of which the verier knows either two - in the base commitment given by matrix A - or one - in the product commitment given by Ab) and adding to both simulators the step to simulate the multiplication command (i.e., upon receiving (mult*;sid;ssid₁;ssid₂;ssid₃*) from P^, S executes the steps of for multiplication P MHCOM and commits to a new unused ssid via F_COM; upon receiving (mult*;sid;ssid₁;ssid₂;ssid₃;P;V;* success) from F_MHCOM, S_Vruns the steps of an honest P exactly as in_MHCOM). More details are given in Appendix E.

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \ {\mathcal{S}}_{P} $$

$$ \mathcal{S}_{V} $$

$$ (i.e. $$

$$ (i,e., $$

$$ \widehat{\mathbf{A}}) $$

$$ s i d,s s i d_{1},s s i d_{2},s s i d_{3}) $$

$$ {\hat{P}},,{\mathcal{S}}_{P} $$

$$ \mathcal{F}_{\mathrm{C O M}}; $$

$$ \ i d d_{1} $$

$$ \mathcal{F}{\operatorname{M H C O M}},:\mathcal{S}{V} $$

$$ P $$

$$ \varPi_ {\mathrm {M H C O M}}) $$

Theorem 4. Protocol_MHCOMUC realizes F_MHCOMin the F_COM-hybrid model with computational security against a static adversary. Formally, there exists a simulator S such that for every static adversary A, and any environment Z, the environment cannot distinguish^MHCOMcomposed with F_COMand A from S composed FCOM with F_MHCOM. That is, IDEAL_{FMHCOM;S;Z c}HYBRID_;A;Z: _MHCOM

$$ \mathit{\Pi}_{\mathrm{M H C O N}} $$

$$ \mathcal{F}_{\mathrm{M H C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}}_h y b r i d $$

$$ \mathcal{F}_{\mathrm{M H C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathsf{s},\ \mathsf{I D E A L}{\mathcal{F}{\mathbf{M H C O M}},\mathcal{S},\mathcal{Z}}\approx_{c}\mathsf{H Y B R I D}{H{\mathbf{M H C O M}},\mathcal{A},\mathcal{Z}}^{\mathcal{F}_{\mathbf{C O M}}} $$

5 Applications to Ecient Zero-Knowledge Arguments

In this section, we outline how to use a variant of the homomorphic commitments constructed in Section 3 and 4 to compile a certain class of public coin interactive proof system into public coin honest-verier zero-knowledge proof systems. Using the Fiat-Shamir heuristic, we can convert such a zero-knowledge proof system into a non-interactive zero-knowledge proof system. As an application, we can improve a recent construction of zkSNARKs [32] in a certain parameter regime. Specically, the zkSNARK construction of [32]

¹³ And naturally from this one can also obtain a [4095 ‘; 338 ‘]-code with the same minimum distance of its square, by simply applying the [4095*;*338] to each block of 338 bits of the message.

Protocol MHCOM

2 2 Let C be a systematic binary linear [n;k] code, such that C is also systematic and satises dist(C) s, where = 1*=(log₂ 3 1) and s is the statistical security parameter. Let Ce be the code dened in (1). Let H be m l ‘ m+l a family of linear almost universal hash functions H : f0;* 1g! f0*;* 1g. Let PRG : f0*;* 1g! f0*;* 1g be a pseudorandom generator. Protocol MHCOM is run by a sender P and a set of receivers V = fV₁;:::;Vtg, who interact with FCOM as follows:

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ (\mathsf{C}^{*2}),\geq,\beta s. $$

$$ \beta=1/(\log_{2}3-1) $$

$$ \ ^{*2} $$

$$ [n,k] $$

$$ \tilde{}C\ {} $$

$$ \mathbf{H}:{0,1}^{m}\to{0,1}^{l} $$

$$ \mathsf{P R G}:{0,1}^{\ell}\to\dot{{0,1}^{m+l}} $$

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ V={V_{1},\ldots,V_{t}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ s i d, s s i d _ {1}, \dots , s s i d _ {m}, P, V), P $$

$$ i\in[n] $$

$$ j\in{0,1,2} $$

$$ \mathfrak{s}{i,j}\overset{\S}{\leftarrow}{0,1}^{\ell},,\widehat{\mathfrak{s}}{i,j}\overset{\S}{\leftarrow}{0,1}^{\ell} $$

$$ s i d, s s i d _ {i, j}, P, V, \boldsymbol {s} _ {i, j}), $$

$$ s i d,\hat{s s i d}{i,j},P,V,\widehat{s}{i,j}\big) $$

$$ \mathbf{R}{\mathbf{j}}[i,\cdot]=\mathsf{P R G}(\mathbf{s}{i,j}) $$

$$ \hat{\mathbf{R}}{\mathbf{j}}[i,\cdot]=\mathsf{P R G}(\hat{\mathbf{s}}{i,j}) $$

$$ \mathbf{R}=\mathbf{R}{0}!+!\mathbf{R}{1}!+!\mathbf{R}_{2} $$

$$ n-k $$

$$ \widehat{\bf R}=\widehat{\bf R}{0}!+!\widehat{\bf R}{1}!+!\widehat{\bf R}_{2} $$

$$ \mathbf{A}:=\mathbf{R}+\mathbf{W}\dot{\in\mathsf{C}^{\odot m+l}} $$

$$ \mathrm{A}{0},=,\mathrm{R}{0},\mathrm{A}{1},=,\mathrm{R}{1},\mathrm{A}{2},=,\mathrm{R}{2}+,\mathrm{W}. $$

$$ C^{*} $$

$$ :\widehat{\mathbf{A}}:=\widehat{\mathbf{R}}+\widehat{\mathbf{W}}\in(\mathsf{C}^{*2})^{\odot m+l}\mathrm{}{a n d}\widehat{\mathbf{A}}[i,\cdot]=\mathbf{A}[i,\cdot] $$

$$ i,\in,[k] $$

$$ \hat{\mathrm{A}}{0}=\hat{\mathrm{R}}{0},\hat{\mathrm{A}}{1}=\hat{\mathrm{R}}{1},\hat{\mathrm{A}}{2}=\hat{\mathrm{R}}{2}+\hat{\mathrm{W}} $$

$$ \big(\mathrm{{i i d}},\mathrm{}{s s i d}{1},\ldots,\mathrm{}{s s s i d}{m},\mathbf{W},\widehat{\mathbf{W}}\big) $$

$$ (\mathsf{r e c e i p t},s i d,s s i d_{i,j},P,V) $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \left(s\ d,s s i d_{1},\ldots,s s i d_{m},\mathbf{W},\widehat{\mathbf{W}}\right) $$

$$ V_{i}\in V $$

$$ P, $$

$$ ,V_{i},V^{\prime},r_{i}) $$

$$ \mathcal{F}_{\mathrm{C O M}}, $$

$$ V_{i},V^{\prime},{\ \ r_{i}}^{\prime}) $$

$$ V^{\prime}=P\cup V\setminus V_{i} $$

$$ \ {\mathit{\Pi}}_{\mathrm{A H C O O}};(\mathrm{F i g u r e~,4}) $$

$$ s i d,s s i d,V_{i},V^{\prime}) $$

$$ \left(\mathsf{r e v e a l},s i d,s s i d^{\prime},V_{j},V^{\prime},{r_{j}}^{\prime}\right) $$

$$ V_{j}\ in V\mathrm $$

$$ r r^{\prime}={r_{1}}^{\prime}\oplus\ldots\oplus{r_{t}}^{\prime} $$

$$ \mathbf{H}\in\mathcal{H}. $$

$$ \widetilde{\mathbf{A}},=,\left(\begin{matrix}{\mathbf{A}}\ {\widehat{\mathbf{A}}}\end{matrix}\right) $$

$$ \widetilde{\bf{A}}{\bf{i}},=,\left(\begin{matrix}{{\bf{A}{}{\bf{i}}}}\ {{\widehat{\bf{A}}{}_{\bf{i}}}}\end{matrix}\right) $$

$$ i;\in;{0,1,2} $$

$$ \tilde{\bf{A}}=,, $$

$$ \mathbf{\widetilde{A}{0}+\widetilde{A}{1}+\widetilde{A}_{2}} $$

$$ \ \tilde{\mathbf{P}}_{i} $$

$$ \tilde{\mathbf A{}} $$

$$ \mathbf{\widetilde{A}},\mathbf{\widetilde{A}}{i},\mathbf{A},\mathbf{A}{i},\mathbf{\widehat{A}},\mathbf{\widehat{A}}, $$

$$ \ {widetilde\mathbf{A}}_{i}. $$

$$ i\in{0,1,2} $$

$$ \widetilde{\mathbf{P}}=\widetilde{\mathbf{P}}{0}+\widetilde{\mathbf{P}}{1}+\widetilde{\mathbf{P}}_{2} $$

$$ \widetilde{\mathbf{T}}{i}=\widetilde{\mathbf{A}}{i}\mathbf{H}+\widetilde{\mathbf{P}}, $$

$$ i \in {0, 1, 2 } $$

$$ \left(\mathit{s i d},\mathit{s s i d}{1},\dots,\mathit{s s i d}{m},\mathbf{\tilde{T}{0}},\mathbf{\tilde{T}{1}},\mathbf{\tilde{T}_{2}}\right) $$

$$ \widetilde{\mathbf{A}}\mathbf{H}+\widetilde{\mathbf{P}}\in\widetilde{\mathsf{C}}^{\odot l} $$

$$ \widetilde{\mathbf{A}}\mathbf{H}+\widetilde{\mathbf{P}}=\widetilde{\mathbf{T}}{0}+\widetilde{\mathbf{T}}{1}+\widetilde{\mathbf{T}}_{2}. $$

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

Fig. 6. Commit phase for the protocol MHCOM.

uses additively homomorphic vector commitments¹⁴ to transform a public coin interactive proof system into a zero-knowledge protocol. The commitments in [32] are instantiated using number-theoretic assumptions. The construction of [32] is general enough that it can be instantiated with homomorphic commitment schemes with some additional properties. We remark though that [32] utilizes an additional optimization which relies on compressing homomorphic commitments, which is not available in our setting.

Our main observation is that for this application the unveil of the commitments in the protocol of [32] can be delayed until the very end of the protocol, which makes this protocol compatible with our commitment scheme.

The notion of interactive proof system we focus on will be resettably sound public coin interactive proofs with algebraic verier. Such a proof system proceeds in t rounds, where in each round i the prover sends a

¹⁴ In [32] they are referred to as multi-commitments

Protocol MHCOM

Addition of Commitments

1.On input (add*;sid;ssid₁;ssid₂;ssid₃;P;V*), P nds indexes i and j corresponding to ssid₁ and ssid₂ respectively and check that ssid₃ is unused. P appends the column A[;i] + A[;j] to A, likewise appends to A₀, A₁, A₂ the sum of their i-th and j-th columns, and associates ssid₃ with the new column index. P broadcasts (add*;sid;ssid₁;ssid₂;ssid₃*) to V.

$$ j $$

$$ smathrm i d_{2} $$

$$ s s i d_{1} $$

$$ (\mathsf{a d d},\mathsf{s i d},\mathsf{s s i d}{1},\mathsf{s s i d}{2},\mathsf{s s i d}_{3},P,V),\textit{I} $$

$$ \mathbf{A}[\cdot,i]+\mathbf{A}[\cdot,j] $$

$$ \mathbf{A_{0}},;\mathbf{A_{1}},;\mathbf{A_{2}} $$

$$ V. $$

$$ s i d,s s i d_{1},s s i d_{2},s s i d_{3}\big) $$

2.Upon receiving (add*;sid;ssid₁;ssid₂;ssid₃*), every Vi 2 V stores the message.

$$ \left\langle\mathsf{a d d},\mathrm{}{s i d},\mathrm{}{s s i d}{1},\mathrm{}{s s i d}{2},\mathrm{}{s s i d}_{3}\right\rangle $$

$$ V_{i}\in V $$

Multiplication of Commitments

1.On input (mult*;sid;ssid₁;ssid₂;ssid₃;P;V*), P nds indexes i and j corresponding to ssid₁ and ssid₂ respectively and check that ssid₃ is unused. Then, P proceeds as follows:

$$ \ i d,s s i d_{1},s s i d_{2},s s i d_{3},P,V) $$

$$ s s i d_{1} $$

$$ j $$

(a)For l 2f0*;* 1*;* 2g, compute vl= Al[;i] Al[;j]+Al[;i] Al+1[;j]+Al+1[;i] Al[;j]. Note that v₀; v₁; v₂ are shares of A[;i] A[;j] in the scheme Add₃ and known to P only. Let h be the index of the rst unused column from A and Ab, compute w = v Ab [;h] for l = 0*;* 1*;2 and broadcast (sid;ssid;h; w₀; w₁; w₂) l l l to V. Note that w₀; w₁; w₂ are shares of A[;i*] A[;j] Ab [;h] in the scheme Add₃ and are known to P [ V.

$$ smathrm i d_{2} $$

$$ l\in{0,1,2} $$

$$ v_{l}=\underset{}{\mathbf{A}{l}[\cdot,i]}{\ }\mathbf{A}{l}[\cdot,j]{+}\underset{}{\mathbf{A}{l}[\cdot,i]}{\ }\mathbf{A}{l+1}[\cdot,j]{+}\underset{}{\mathbf{A}{l+1}[\cdot,i]}{\ }\mathbf{A}{l}[\cdot,j] $$

$$ \mathbf{v_{0}},\mathbf{v_{1}},\mathbf{v_{2}} $$

$$ \underset{}{\mathbf{A}[\cdot,i]}{*}\mathbf{A}[\cdot,j] $$

$$ \mathbf{\dot{A}}; $$

$$ \ {l}=\boldsymbol{v}{l}-\widehat{\mathbf{A}}_{l}[\cdot,h] $$

$$ l=0,1,2 $$

$$ (s i d,s s i d,h,w_{0},w_{1},w_{2}) $$

$$ \mathbf{A}[\cdot,i]*\mathbf{A}[\cdot,j]-\widehat{\mathbf{A}}[\cdot,h] $$

$$ w_{0},w_{1},w_{2} $$

$$ \mathsf{A d d_{3}} $$

$$ P\cup V. $$

(b)Let u = (w₀+w₁+w₂) (i.e., u consists of the rst k components of A[;i] A[;j] Ab [;h]), append [k] the columns A[;h] + C(u) and A₂[;h] + C(u) to A and A₂, respectively. Append the column Ai[;h] to A for i = 0;1 and associate ssid₃ with the new column index. Note that since (Ab [;h])+ (A[;h]), i [k] [k] for l 2 f1*;:::;kg* the l-th component of the newly appended column in A is equal to A[l;i] A[l;j]. Broadcast (add*;sid;ssid₁;ssid₂;ssid₃*) to V.

$$ u=\pi_{[k]}(w_{0}!+!w_{1}!+!w_{2})\left(i.e.\right) $$

$$ \mathsf{A}[\cdot,i],*,mathsf A![\cdot,j],-,\widehat{\mathsf{A}}[\cdot,h]\bigr) $$

$$ \mathbf{A}|\cdot,h|\ +,{\mathsf{C}}(\mathbf{u}) $$

$$ \mathbf{A_{2}}[\cdot,h]+\mathsf{C}(\boldsymbol{u}) $$

$$ \mathbf{A}_{i}|\cdot,h| $$

$$ i=0, $$

$$ \pi_{|k|}\bigl(\widehat{\mathbf{A}}[\cdot,h]\bigr)!+!\pi_{|k|}\bigl(\mathbf{A}[\cdot,h]\bigr) $$

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

$$ \mathbf{A}[l,i]*\mathbf{A}[l,j] $$

$$ V $$

$$ \left(\mathrm {a d d}, s i d, s s i d _ {1}, s s i d _ {2}, s s i d _ {3}\right) $$

2.Upon receiving (mult*;sid;ssid₁;ssid₂;ssid₃*), every Vi 2 V stores the message.

$$ (\mathsf{m u l t},\mathfrak{s i d},\mathfrak{s s i d}{1},\mathfrak{s s i d}{2},\mathfrak{s s i d}_{3}) $$

$$ V_{i}\in V $$

m00 Note that this maintains the properties A = A₀ + A₁ + A₂ and A 2 C, where m is the current number of columns.

$$ \mathbf{A}=\mathbf{A_{0}}+\mathbf{A_{1}}+\mathbf{A_{2}} $$

$$ \mathbf {A} \in \mathrm {C} ^ {\odot m ^ {\prime}} $$

$$ m^{\prime} $$

Opening (Part 1)

1.On input (reveal*;sid;ssid₁;:::;ssido*), P nds the set J = fj₁;:::;jog of indexes associated to ssid₁;:::;ssido and broadcasts (sid;ssid₁;:::;ssido;(A₀[;j];A₁[;j];A₂[;j])j2J).

$$ s i d,s s i d_{1},\ldots,s s i d_{o} $$

$$ J={j_{1},\ldots,j_{o}} $$

$$ s s i d_{1},\ldots,s s i d_{o} $$

$$ (s i d,s s i d_{1},\ldots,s s i d_{o},(\mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j],\mathbf{A_{2}}[\cdot,j])_{j\in J}). $$

2.Upon receiving message (sid;ssid₁;:::;ssido;(A₀[;j];A₁[;j];A₂[;j])j2J), every receiver Vi 2 V sends 0 (reveal*;sid;ssid*) to FCOM and waits for (reveal*;sid;ssid;Vj;V; rj*) from FCOM for all Vj 2 V n Vi. Vi sets n 0 r = r₁ + + rt (where the sum is in Z3) aⁿd sets the diagonal matrices*;* such that the i-th element 0 in (resp.) is 1 if r[i] = 2 (resp. r[i] = 1) and 0 otherwise.

$$ (s i d,s s i d_{1},\ldots,s s i d_{o},(\mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j],\mathbf{A_{2}}[\cdot,j])_{j\in J}) $$

$$ V_{i}\ \in\ V $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V_{j},V^{\prime},r_{j}) $$

$$ r=r_{1}+\cdots+r_{t} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V_{j}\in V\setminus V_{i}.\ V_{i} $$

$$ \mathbb{Z}_{3}^{n} $$

$$ \Delta,\Delta^{\prime} $$

$$ \mathbf{\Delta}\ (\mathrm{r e s p.}\ \mathbf{\Delta}^{\prime}) $$

$$ r[i]=2 $$

$$ r[i]=1) $$

0 3.Upon receiving (reveal*;sid;ssid;Vj;V; rj*) from FCOM for all Vj 2 V, P sets r = r₁ + ::: + rt, sends (reveal;sid;ssid), (reveal;sid;ssid) and (reveal;sid; ssid d) to F for i = 1;:::;n and halts. i;r[i] i;r[i]+1 i;r[i] COM

$$ V_{j},V^{\prime},r_{j}) $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ V_{j};\in;V, $$

$$ r,=,r_{1}+\ldots+r_{t} $$

$$ \ {(\mathsf{r e v e a l},s i d,s s i d_{i,\mathsf{r}[i]})},\ {\mathsf(r\mathsf{r e v e a l},s i d,s s i{d_{i,\mathsf{r}[i]+1}})} $$

$$ s s i d _ {i, r [ i ]}) $$

$$ i=1,\ldots,n $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

Fig. 7. Addition and multiplication steps, and opening phase for the protocol MHCOM.

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

message p_i, upon which the verier answers with a uniformly random message v_i. We require all the messages p_iand v_ito be vectors over a eld F. After the conversation is over, the verier evaluates a system of low degree polynomials F₁;:::;F_sin the p_iand v_iand accepts if all F_ievaluate to 0, otherwise it rejects. At the heart of this kind of protocol is the sum-check protocol, which lets a prover prove statements of the form P _x2f0;1gn P (x) = L, where P 2 F[X₁;:::;X_n] is a low-degree polynomial and L 2 F.

$$ p_{i} $$

$$ p_{i} $$

$$ v_{i} $$

$$ \upsilon_{i} $$

$$ F_{1},\ldots,F_{s} $$

$$ v_{i} $$

$$ p_{i} $$

$$ F_{i} $$

$$ P\in\mathbb{F}[X_{1},\ldots,X_{n}] $$

$$ \textstyle{\sum_{x\in{0,1}^{n}}P(x)=L} $$

$$ L\in\mathbb{F} $$

While it can be shown that any constant round proof system can be immediately compiled into a noninteractive argument system via the Fiat-Shamir heuristic [20], super-constant round protocols need to full a stronger soundness property called resettable soundness for the Fiat-Shamir transform to result in a sound protocol.

We will now outline how to compile any resettable sound public coin interactive proof system into an honest-verier zero-knowledge proof systems in a way that only slightly increases the communication complexity and only aects the eciency of prover and verier by a small constant factor.

$$ s i d,s s i d_{i,r[i]},P,V,s_{i,r[i]} $$

$$ \ s i d_{i,r[i]+1},P,V,\mathfrak{s}_{i,r[i]+1}) $$

$$ ,\widehat{s s i d}{i,r[i]},P,V,\widehat{s}{i,r[i]}\big) $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

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

$$ V_{j}\in V $$

$$ \mathbf{S}[i,\cdot]=\mathsf{P R G}(s_{i,[i]}),:\mathbf{S}^{\prime}[i,\cdot]=\mathsf{P R G}(s_{i,\mathfrak{r}[i]+1}) $$

$$ \widehat{\mathsf{S}}[i,\cdot]=\pi_{\mu+l}\big(\mathsf{P R G}\big(\widehat{\mathfrak{s}}_{i,r[i]}\big)\big) $$

$$ \mathbf{s},,\mathbf{s}^{\prime},,\widehat{\mathbf{s}} $$

$$ \mathbf{R}{r[\mathbf{i}]},:\mathbf{R}{r[\mathbf{i}]+\mathbf{1}},:\widehat{\mathbf{R}}_{r[\mathbf{i}]} $$

$$ \ {tt B B}=\Delta{\tt W}+{\tt S},,{\tt B}^{\prime}=\Delta^{\prime}{\tt W}+{\tt S}^{\prime} $$

$$ \widehat{\mathbf{B}}=\mathbf{\Delta}\widehat{\mathbf{W}}+\widehat{\mathbf{S}} $$

$$ \mathbf{\widetilde{T}{0}}\mathbf{,\widetilde{T}{1}},\mathbf{\widetilde{T}_{2}} $$

$$ \widetilde{\mathbf{A}}\mathbf{H}+\widetilde{\mathbf{P}}. $$

$$ \mathtt{B}{}^{\prime}\mathtt{H}+\mathtt{Q}{}^{\prime} $$

$$ \tilde{\mathbf{A}}\mathbf{H}+\tilde{\mathbf{P}}) $$

$$ \hat{\mathbf{B}}\mathbf{H}+\hat{\mathbf{Q}} $$

$$ i\in{0,1,2} $$

$$ \widetilde{\mathbf{T}}_{i} $$

$$ \mathrm{B H+Q=} $$

$$ \widetilde{\mathbf{T}}{i}=\left(\begin{matrix}{\mathbf{T}{i}}\ {\widehat{\mathbf{T}}_{i}}\ \end{matrix}\right) $$

$$ \Delta \mathbf {T} _ {2} + \Delta^ {\prime} \mathbf {T} _ {1} + \left(1 - \Delta - \Delta^ {\prime}\right) \mathbf {T} _ {0}, \mathbf {B} ^ {\prime} \mathbf {H} + \mathbf {Q} ^ {\prime} = \Delta \mathbf {T} _ {0} + \Delta^ {\prime} \mathbf {T} _ {2} + \left(1 - \Delta - \Delta^ {\prime}\right) \mathbf {T} _ {1} $$

$$ \widehat{\mathbf{B}}\mathbf{H}+\widehat{\mathbf{Q}},= $$

$$ \Delta\hat{\mathrm{T}}{2}+\Delta^{\prime}\hat{\mathrm{T}}{1}+\big(1-\Delta-\Delta^{\prime}\big)\hat{\mathrm{T}}_{0}. $$

$$ \mathrm{T_{0}+T_{1}+T_{2}\in\ {sf C}^{\odot\ell}} $$

$$ s i d,s s i d_{1},s s i d_{2},s s i d_{3}\big) $$

$$ \mathbf{B}[\cdot,a]+\mathbf{B}[\cdot,b] $$

$$ \mathbf{B}^{\prime}[\cdot,a]+ $$

$$ \mathbf{B}^{\prime}[\cdot,b] $$

$$ s s i d_{1},\thinspace s s i d_{2} $$

$$ P\cdot $$

$$ \mathtt{n}\left(s i d,s s i d,h,w_{0},w_{1},w_{2}\right. $$

$$ w_{0}!+!w_{1}!+!w_{2}\in\mathsf{C}^{*2} $$

$$ w_{r[i]}=\mathrm{B}[\cdot,a],\mathrm{*B}[\cdot,b],+,\mathrm{B}[\cdot,a],\ast $$

$$ \mathbf {B} ^ {\prime} [ \cdot , b ] + \mathbf {B} ^ {\prime} [ \cdot , a ] * \mathbf {B} [ \cdot , b ] + \widehat {\mathbf {B}} [ \cdot , h ]; $$

$$ u=\pi_{|k|}\big(w_{0}+w_{1}+w_{2}\big) $$

$$ \mathbf{B}[\cdot,h]+\mathbf\Delta\mathsf{C}(u) $$

$$ \mathbf {B} ^ {\prime} [ \cdot , h ] + \Delta^ {\prime} \mathrm {C} (\boldsymbol {u}) $$

$$ \mathbf{B}^{\prime} $$

$$ j\in J, $$

$$ i,=,1,\ldots,n_{\ .} $$

$$ \ {bf A_{{0}}}[\cdot,j]+{\bf A_{{1}}}[\cdot,j]+{\bf A_{{2}}}[\cdot,j]\in\mathsf{C} $$

$$ \mathbf{B}[i,j]=\mathbf{A}_{r[\mathbf{i}]}[i,j] $$

$$ \mathbf{B^{\prime}}[i,j]=\mathbf{A_{r[i]+1}}[i,j] $$

$$ j\in J. $$

$$ \mathsf{A}{\ }{0}[\cdot,j]+\mathsf{A}{{\ }}{1}[\cdot,j]+\mathsf{A}{{\ }}_{2}[\cdot,j] $$

$$ (s i d,s s i d_{j},\bot) $$

$$ \mathbf{A}=\mathbf{A_{0}}+\mathbf{A_{1}}+\mathbf{A_{2}},:\mathbf{B}=\mathbf{\Delta_{{2}}}+\mathbf{\Delta^{\prime}}\mathbf{A_{1}}+(1-\mathbf{\Delta}-\mathbf{\Delta^{\prime}})\mathbf{A_{0}} $$

$$ \mathbf{B}^{\prime}=\mathbf{\Delta A}{0}+\mathbf{\Delta }^{\prime}\mathbf{A}{2}+ $$

$$ (1-\mathbf{\Delta}-\mathbf{\Delta}^{\prime})\mathbf{A_{1}} $$

$$ {\mathsf S S}{\mathsf S}_{3} $$

$$ \mathbf{A}_{0}. $$

$$ \widehat{\mathbf{A}}=\widehat{\mathbf{A}}{0}+\widehat{\mathbf{A}}{1}+\widehat{\mathbf{A}}_{2} $$

$$ \mathrm{A_{1},A_{2})} $$

$$ \mathbf{\widehat{B}}=\mathbf{\Delta}\mathbf{\widehat{A}{2}}+\mathbf{\Delta}^{\prime}\mathbf{\widehat{A}{1}}+(\mathbf{I}-\mathbf{\Delta}-\mathbf{\Delta}^{\prime})\mathbf{\widehat{A}_{0}}\mathbf\ {\mathit{i.e}} $$

$$ \mathbf{\widehat{A}{0},:\widehat{A}{1},:\widehat{A}_{2})} $$

Fig. 8. Opening phase (continued) for the protocol MHCOM.

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

The basic idea of the transformation is simple and follows the paradigm of committed conversations [5]. The prover and verier run the interactive proof system with the modication that instead of sending its messages in the plain, the prover sends commitments to its messages. After the protocol is over the prover convinces the verier that the commitment values pass the verication equations F₁;:::;F_s. The homomorphic property of the commitments will be used to implement this check eciently. While our protocol_MHCOMdoes support evaluation of low degree polynomials, we will focus on linear/ane verication equations F₁;:::;F_sand will therefore rely on the additively homomorphic commitment scheme_AHCOM.

$$ F_{1},\ldots,F_{s} $$

$$ F_{1},\ldots,F_{s} $$

In our construction, we will use protocol_AHCOMwith several modications which are discussed in Appendix G.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

Instantiation We will now discuss instantiating the hyrax protocol of [32] with the modied version of the commitment scheme_AHCOM.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

To prove satisability of an algebraic circuit of depth d, width G and input/witness size jwj, the hyrax p protocol has proof size (10dlog(G) + jwj) assuming that a group element in a DLOG-hard group G has p size. The verier runtime is O( jwj + d log(G)) whereas the prover runtime is linear in the size of the circuit C.

$$ d, $$

$$ \left(10d\log(G)+\sqrt{|w|}\right) $$

$$ \kappa. $$

$$ O!({\sqrt{|w|}}+d\cdot\log(G))! $$

Replacing the DLOG-based homomorphic commitment in the hyrax protocol with our commitment protocol_AHCOMas outlined above, the main optimization which is not available is compression of the witness w. Consequently, in our instantiation proof size will depend linearly on the size of the witness jwj.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ |w| $$

One of the key ideas in the hyrax protocol is to reduce all algebraic relations between commitments to linear relations between vector commitments, an idea also used in bulletproofs [10]. In this way, general algebraic relations can be proven using a protocol which just supports linear relations between vectors. This transformation only incurs a small constant factor additional overhead. Omitting details, there are three main steps. In the rst step reduce multiplicative relations to linear relations, in the second step show that many linear relations can be compressed into a single linear relation, and in. the third step step reduce linear relations between commitments to linear relations between vector commitments. All three steps are implemented using a Schnorr-style protocol. In [32] these transformations are provided for the concrete case of DLOG-based commitments, but these ideas can be implemented using arbitrary homomorphic vector commitments.

The main improvement of our protocol over [32] is that we only rely on simple private key primitives. On the turn side, our vector-commitments are not compressing, which leads to the proof-size to depend p linearly on the witness-size jwj instead of jwj. However, the proof size does not depend multiplicatively on the computational security parameter, but rather on jFj, which is a statistical security parameter an can therefore be chosen much smaller. Consequently, we get an advantage in terms of proof-size whenever the proof-size is dominated by d rather than jwj.

$$ \sqrt{|w|} $$

$$ \kappa, $$

$$ \left\vert\mathbb{F}\right\vert $$

6 Applications to Secure Multiparty Computation

6.1 Committed MPC

A recent work by Frederiksen et al. [21] has shown that additively homomorphic commitments can be leveraged to construct ecient preprocessed MPC. However, their \Committed MPC" protocol requires a multiparty commitment functionality that allows for multiple senders and for computing linear combinations between commitments generated by dierent senders. We will show a generic construction of such a protocol from functionality F_AHCOMthat can be instantiated with Protocol_AHCOM, achieving signicantly better eciency than the construction of [21].

$$ \mathrm{M P C} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

Functionality F_MSAHCOM. Our protocol will realize the multiparty additively homomorphic commitment functionality from [21] with the dierence that it will only allow for a single batch verication of opened commitments. While it allows for openings before verication, the validity of those will not be ensured by F_MSAHCOM, which will let the adversary choose any value to be provided as an opening. F_MSAHCOMwill allow for a single verication phase where all parties check whether the openings they have received are valid, after which the functionality halts. This functionality is sucient for realizing the \Committed MPC" protocol of [21], since the parties can use the intermediate (non-veried) openings to compute the protocol and in the end verify that the result is correct. Other small dierences is that we omit the Partial Open interface used to open a commitment to a single receiver and provide an interface for single addition operations. Notice that our procedures for opening a commitment for all receivers can be trivially adapted to opening towards a specic receiver by sending the corresponding messages only to that receiver and that single additions of commitments can be trivially used for computing linear combinations as in the functionality of [21]. We present Functionality F_MSAHCOMin Figure 9.

$$ \mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ \mathrm{M P C} $$

$$ \mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ P,=,{P_{1},\ldots,P_{t}} $$

$$ n,\in,\mathbb{N}.,,\mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ P, $$

$$ \mathcal{S} $$

$$ \in\mathcal{I}, $$

$$ \ {mathfrak x}_{s s i d}{\xleftarrow{\mathfrak S}}\ {mathbb F F}^{k} $$

$$ P $$

$$ \mathsf{r a w}[s s i d]=x_{s s i d} $$

$$ \mathcal{S} $$

$$ P_{i},y) $$

$$ P_{i}\in P $$

$$ =\mathtt{x}_{s s i d}\neq\bot $$

$$ P, $$

$$ \mathsf{r a w}[s s i d]=\bot. $$

$$ S, $$

$$ P, $$

$$ x_{\mathrm{}{s s i d}}, $$

$$ \mathsf{a w}[s s i d]=\bot $$

$$ \mathsf{v}[s s i d]=x_{s s i d}\neq\bot. $$

$$ \bar{P} $$

$$ {\mathcal{S}}. $$

$$ (\mathsf{a d d},s\mathsf{i d d},s\mathsf{s d d}{1},s\mathsf{s d d}{2},s\mathsf{s d d}_{3}) $$

$$ \left[s s i d\right],= $$

$$ \ \ \ _{s s i d}\ \ \ \bot\ $$

$$ \in \left{s s i d _ {1}, s s i d _ {2} \right} $$

$$ {\mathsf{r a w}}[{\mathfrak{s s i d}}{3}]={\mathsf{a c t u d}}[{\mathfrak{s s i d}}{3}]=\bot $$

$$ P $$

$$ \big(\mathsf{o p e n},s i d,s s i d,x_{s s i d}\big) $$

$$ x_{s s i d}^{\prime} $$

$$ \left(\mathrm {o p e n}, s i d, s s i d, \boldsymbol {x} _ {s s i d} ^ {\prime}\right) $$

$$ P. $$

$$ (\mathsf{v e r i f y},s i d) $$

$$ \ s{i d d}{1},\ldots,s s i{d}{o} $$

$$ P, $$

$$ \left(\mathrm {o p e n}, s i d, s s i d, \boldsymbol {x} _ {s s i d} ^ {\prime}\right) $$

$$ \in \left{s s i d _ {1}, \dots , s s i d _ {o} \right} $$

$$ \ d d]=x_{s s i d}^{\prime} $$

$$ b=0\ \mathrm{i l} $$

$$ P. $$

Fig. 9. Functionality for additively homomorphic commitments with multiple senders.

Protocol_MSAHCOM. While a generic construction of such a protocol from any two-party additively homomorphic commitment scheme is presented in [21], we can signicantly simplify and improve the eciency of this construction departing from a multi-receiver scheme as dened in F_AHCOM. We construct a protocol where every party acts both as sender and receiver of all commitments. In this protocol, each party rst uses F_AHCOMto commit to random values towards the others. A joint random commitment in the new multisender protocol is dened as the commitment to the sum of all random messages contained in the individual commitments by each party. Linear combinations between joint commitments can be computed by having each party (acting as a sender in the underlying multi-receiver commitment scheme) compute the same linear combination on its own \shares" of the joint commitment. Opening a joint commitment works by having each party open their individual commitments, allowing everybody to compute the joint commitment as the sum of the opened messages. Using standard tricks, these joint random commitments can be easily turned into commitments to arbitrary messages.

$$ \pi_ {\mathrm {M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

Security Analysis: To verify correctness, notice thatMSAHCOMcomputes a random commitment identied P i i by ssid as a commitment to_i2[t]raw [ssid], where raw [ssid] is supposed to be the value obtained by P_i i j from F^AHCOM. In the verication procedure, all parties obtain x^jfor j 2 [t] directly from F^AHCOM, being able to verify that the previously opened commitments are indeed valid. If a commitment identied by ssid is set P i to an arbitrary message y, the sender P_jholding y broadcasts w = y_i2[t]raw [ssid], which also allows i all parties to retrieve y when values raw [ssid] are released and to verify the correctness of this opening j when x_j(corresponding to raw [ssid]) are revealed. Notice that addition are simply computed by adding i the actual [ssid] vectors and, since all of these vectors are linear combinations of themselves, opening and verication of a result addition works the same way as for the other commitments.

$$ \Pi_ {\mathrm {M S A H C O M}} $$

$$ \textstyle\sum_{i\in[t]}\mathsf{r a w}^{i}[\mathrm{}{s s i d}] $$

$$ [s s i d] $$

$$ P_{i} $$

$$ \mathcal{F}_{\mathrm{A H C O M}}^{i} $$

$$ x_{j} $$

$$ j\in[t] $$

$$ \mathcal{F}_{\mathrm{A H C O M}}^{j} $$

$$ w=y-\sum_{i\in[t]}\mathsf{r a w}^{i}[s s i d] $$

$$ P_{j} $$

$$ y $$

$$ {\mathfrak{r w w}}^{j[\mathfrak{s s i d}]} $$

$$ x_{j} $$

$$ {\mathsf{r a w}}^{i}[s s i d] $$

Theorem 5. Protocol_MSAHCOMUC realizes F_MSAHCOMin the F_AHCOM-hybrid model with statistical se- curity against a static adversary. Formally, there exists a simulator S such that for every static adversary FAHCOM A, and any environment Z the following holds: IDEAL_{FMSAHCOM;S;Z s}HYBRID_;A;Z: _MSAHCOM

$$ \mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}},{\it h y b r i d} $$

$$ \mathcal{S} $$

$$ \mathcal{A}_{\downarrow} $$

$$ \mathsf{I D E A L}{\mathcal{F}{\mathrm{}{M S A H C M}},\mathcal{S},\mathcal{Z}}\approx_{s}\mathsf{H Y B R D D}{\mathcal{H}{\mathrm{}{M S A H C O M}},\mathcal{A},Z}^{\mathcal{F}_{\mathrm{}{M H C O M}}} $$

$$ P={P_{1},\ldots,P_{t}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ P_{i}\in P. $$

$$ P={P_{1},\ldots,P_{t}} $$

$$ V_{i}=P\setminus P_{i} $$

$$ \mathcal{F}_{\mathrm{A H C O M}}^{i} $$

$$ P_{i} $$

$$ \mathcal{F}{\mathrm{A H C O M}}^{1},\ldots,\mathcal{F}{\mathrm{A H C O M}}^{t}, $$

$$ P_{i},\in,P, $$

$$ s s i d:\in:\mathcal{I}, $$

$$ \mathcal {I} = \left{s s i d _ {1}, \dots , s s i d _ {\gamma} \right} $$

$$ P_{i},V_{i}) $$

$$ \mathcal{F}_{\mathrm{A H C O M}}^{i} $$

$$ P_{i},V_{i},\ {tt x x}_{s s i d}) $$

$$ \left(\mathsf{i n p u t},s i d,s s i d,P_{j}\right) $$

$$ P_{i} $$

$$ \mathsf{r a w}^{i}[s s i d]=x_{s s i d} $$

$$ P_{j} $$

$$ j\neq i, $$

$$ j\in[t],j\neq i,,P_{j} $$

$$ \neq\bot $$

$$ (s i d,s s i d,\mathsf{r a w}^{j}[s s i d]) $$

$$ P_{j} $$

$$ (s i d,s s i d,\mathsf{r a w}^{j}[s s i d]) $$

$$ P i_{i} $$

$$ P_{j} $$

$$ j,\in,[t],j,\neq,i,,P_{i} $$

$$ \textstyle{\b{{x}},=,\sum_{j\in[t]}\mathsf{r a w}^{j}[s s i d].} $$

$$ P_{j}\in P $$

$$ (\mathrm{{i s d}},\mathrm{}{s s i d},P_{i},w) $$

$$ {\mathsf{a c t u a l}}^{j}|s s i d|=w. $$

$$ \ s s i d\ =\bot $$

$$ P_{i}\in P $$

$$ {i\ !s i s!}=0^{k} $$

$$ (\mathsf{a d d},\mathrm{{i s d}},\mathrm{}{s s i d}{1},\mathrm{}{s i{d}}{2},\mathrm{}{s i i}_{3}) $$

$$ \begin{array}{r l}{\mathsf{a c t u a l}^{i}[s s i d_{1}]}&{{}\neq\bot}\ \end{array} $$

$$ \mathsf{t u a l}^{i}[\check{s{i s}}\ {{i i d}}{_22}]\quad\neq\bot $$

$$ P _ {i} \quad \in P $$

$$ ^i s s s d{}_{2}] $$

$$ s i d, s s i d _ {1}, s s i d _ {2}, s s i d _ {3}, P _ {i}, V _ {i} $$

$$ \mathcal{F}_{\hat{A}}^{i}} $$

$$ \begin{array}{r c l}{P_{i}}&{\in}&{P}\ \end{array} $$

$$ (s i d,s s i d,\mathsf{r a w}^{i}[s s i d]) $$

$$ j,\in,[t],j,\neq,i, $$

$$ P_{i};\in;P $$

$$ x^{\prime}=\mathsf{a c t a d}^{i}\dot[\ \ {mathfrak s s i d}]+\sum_{i\in[t]}\mathsf{r a w}^{j}[\ {\mathfrak s}s i d $$

$$ (s i d, s s i d, \boldsymbol {x} ^ {\prime}) $$

$$ s s i d_{1},\ldots,s s i d_{o} $$

$$ (i,e. $$

$$ P_{i}\in P $$

$$ s s i d_{1},\ldots,s s i d_{o}) $$

$$ \in{\mathrm{}{s s i d}{1},\ldots,\mathrm{}{s s i d}{o}} $$

$$ \mathcal{F}_{\mathrm{A}}^{i} $$

$$ P_{j},V_{j},x_{j}) $$

$$ x_{i}=\mathsf{r a w}^{i}[s s i d] $$

$$ j\in[t],j\neq i, $$

$$ P_{i}\in P $$

$$ \textstyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\ \ \ mathsf a c c u a^{i}\ s i d^{i} $$

$$ b=1{\mathrm{i f}}x^{\prime}=x $$

$$ a^{\prime} $$

Fig. 10. Protocol MSAHCOM

i Proof(Sketch). Notice that^MSAHCOMonly performs operations with random values obtained from F^AHCOM. Hence, upon learning the opening of any commitment from F_MSAHCOM, the simulator can simply cheat in i the openings of random values from the emulated F^AHCOMin order to equivocate a commitment. Similarly, if it needs to extract any commitment done in_MSAHCOM, the simulator can compute it from the messages i sent by the adversary in the protocol and the messages the adversary obtains from the emulated F_AHCOM.

$$ \mathcal{F}_{\mathrm{A H C O M}}^{i}. $$

$$ \mathcal{F}_{\mathrm{M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}}^{i} $$

$$ \mathit{Pi}_{\ \mathrm{M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}}^{i}\cdot $$

Eciency: Notice that our construction of_MSAHCOMusing F_AHCOMas a black box actually communicates more bits than necessary. In_MSAHCOM’s opening phase, all parties broadcast the messages in commitments generated by F_AHCOMand, later on, verify these openings by opening the commitments through F_AHCOM, sending the same messages again. If instantiated with_AHCOM, our construction can be made more ecient by having the parties broadcast columns A₀[;j];A₁[;j] (Step 1 of_AHCOM’s opening phase) during the opening phase of_MSAHCOM. Later on, for verication, the parties only need to execute the remaining steps of the opening phase of_AHCOMin order to verify that the columns they have previously obtained are actually valid. In a setting with t parties, our protocol only requires t individual multi-receiver commitments, where the construction of [21] requires t² two-party commitments. Their constructions also require extra communication in the order of O(skt²) for generating a batch of m commitments, where s is the security parameter and k is the message length. Moreover, instantiating the construction of [21] with the previously best two-party additively homomorphic commitments [16] implies a high cost of nt² OTs for the setup phase (with an underlying [n;k;s] code) and extra communication in the order of O(nmt²) bits for generating a batch of m commitments to random messages. On the other hand, our construction instantiated with protocol AHCOMcan do the same with nt calls to FCOM(which can be instantiated much cheaper than an OT by calling a random oracle and sending its output) and extra communication in the order of O(smt) bits. In

$$ \pi_ {\mathrm {M S A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \Pi_ {\mathrm {M S A H C O M}} ^ {\prime \prime} \mathrm {s} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}}, $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathbf{A}{0}[\cdot,j],\mathbf{A}{1}[\cdot,j] $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}}^{'}\mathrm{}! $$

$$ \mathit{Pi}_{mathrm\ M{S H H C M M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \bar{O(s k t^{2})} $$

$$ t^{2} $$

$$ n!^{2} $$

$$ O(n m t^{2}) $$

$$ [n,k,s] $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ O(s m t) $$ the opening phase, the construction of [21] requires communication in the order of O(nt²) bits, while our construction only requires communication in the order of O(nt) bits, assuming broadcast channels.

$$ O(n t^{2}) $$

$$ O(n t) $$

6.2 Insured MPC

Recently, Andrychowicz et al. [2] started a line of work [6,27,7,4] that deals with the problem of fairness in multiparty computation by combining MPC protocols with cryptocurrencies. The main idea is to provide nancial incentives for the parties to act honestly. In a nutshell, each party provides a security deposit before the protocol execution or right before the outputs are revealed. After that, the protocol is executed and if no problem happens, then the security deposits are reimbursed. On the other hand, if some problem happens, the security deposit of the parties who misbehaved/aborted is used to compensate the remaining parties. This combination of MPC and cryptocurrency techniques also allows to have both inputs and outputs consisting of both data and monetary assets and distribute the funds according to the output of the computation.

The most ecient solution to date, due to Baum et al. [4], uses a publicly veriable additively homomorphic multi-receiver commitment scheme as a central building block. By combining such commitment scheme with a smart contract, an authenticated bulletin board, and a MPC scheme that output veriably secret shared outputs, they obtained an ecient MPC protocol with public detection of cheating behavior that nancially punishes misbehaving parties. Nevertheless, the main bottleneck of their protocol is the multi-party commitment scheme, as its complexity grows quadratically in the number of parties. With our techniques it is possible to greatly improve the performance of publicly veriable additively homomorphic multi-receiver commitments.

The functionality for publicly veriable additively homomorphic commitment F_PVHCOMis described in the Appendix F and the set of external veriers U is allowed to be dynamic by adding procedures for registering and deregistering parties following the approach of Badertscher et al. [3]. Assuming that the underlying commitment protocol_COMused as a building block is publicly veriable, Protocol_AHCOMis trivially publicly veriable when all the messages are posted to an authenticated bulletin board, straightforwardly realizing functionality F_PVHCOM. The \canonical" random oracle commitment scheme (that realizes F_COM in the programmable Global Random Oracle model without extra computational assumptions according to a recent result by Camenisch et al. [11]) is a clear example of a scheme that is publicly veriable when the messages are posted to an authenticated bulletin board, and_AHCOMinstantiated using that commitment scheme can be used to remarkably improve the performance of publicly veriable additively homomorphic commitments and consequently of the Insured MPC protocol of Baum et al. [4]. The eciency improvements achieved in this application are similar to those of the Committed MPC case, since the previously best publicly veriable multi-receiver additively homomorphic commitment protocol of [4] has a very similar structure to the commitment protocol of [21].

$$ \mathcal{F}_{\mathrm{P V H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{P V H C O M}} $$

$$ \mathcal{F}_{\mathrm{C O N}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

References

1.Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 17, pages 2087{2104. ACM Press, October / November 2017. 2.Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, and Lukasz Mazurek. Secure multiparty computations on bitcoin. In 2014 IEEE Symposium on Security and Privacy, pages 443{458. IEEE Computer Society Press, May 2014. 3.Christian Badertscher, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. Bitcoin as a transaction ledger: A composable treatment. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 324{356. Springer, Heidelberg, August 2017. 4.Carsten Baum, Bernardo David, and Rafael Dowsley. Insured mpc: Ecient secure multiparty computation with punishable abort. Cryptology ePrint Archive, Report 2018/942, 2018. https://eprint.iacr.org/2018/942.

5.Michael Ben-Or, Oded Goldreich, Sha Goldwasser, Johan Hastad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In Sha Goldwasser, editor, CRYPTO’88, volume 403 of LNCS, pages 37{56. Springer, Heidelberg, August 1990. 6.Iddo Bentov and Ranjit Kumaresan. How to use bitcoin to design fair protocols. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II, volume 8617 of LNCS, pages 421{439. Springer, Heidelberg, August 2014. 7.Iddo Bentov, Ranjit Kumaresan, and Andrew Miller. Instantaneous decentralized poker. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, pages 410{440. Springer, Heidelberg, December 2017. 8.Olivier Blazy, Celine Chevalier, David Pointcheval, and Damien Vergnaud. Analysis and improvement of Lindell’s UC-secure commitment schemes. In Michael J. Jacobson Jr., Michael E. Locasto, Payman Mohassel, and Reihaneh Safavi-Naini, editors, ACNS 13, volume 7954 of LNCS, pages 534{551. Springer, Heidelberg, June 2013. 9.Lus T. A. N. Brand~ao. Very-ecient simulatable ipping of many coins into a well - (and a new universallycomposable commitment scheme). In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, PKC 2016, Part II, volume 9615 of LNCS, pages 297{326. Springer, Heidelberg, March 2016. 10.Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for condential transactions and more. In 2018 IEEE Symposium on Security and Privacy, pages 315{334. IEEE Computer Society Press, May 2018. 11.Jan Camenisch, Manu Drijvers, Tommaso Gagliardoni, Anja Lehmann, and Gregory Neven. The wonderful world of global random oracles. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 280{312. Springer, Heidelberg, April / May 2018. 12.Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136{145. IEEE Computer Society Press, October 2001. 13.Ran Canetti and Marc Fischlin. Universally composable commitments. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 19{40. Springer, Heidelberg, August 2001. 14.Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. Universally composable two-party and multiparty secure computation. In 34th ACM STOC, pages 494{503. ACM Press, May 2002. 15.Ignacio Cascudo. On squares of cyclic codes. IEEE Transactions on Information Theory, 65(2):1034{1047, 2019. 16.Ignacio Cascudo, Ivan Damgard, Bernardo David, Nico Dottling, and Jesper Buus Nielsen. Rate-1, linear time and additively homomorphic UC commitments. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 179{207. Springer, Heidelberg, August 2016. 17.Ignacio Cascudo, Ivan Damgard, Bernardo Machado David, Irene Giacomelli, Jesper Buus Nielsen, and Roberto Triletti. Additively homomorphic UC commitments with optimal amortized overhead. In Jonathan Katz, editor, PKC 2015, volume 9020 of LNCS, pages 495{515. Springer, Heidelberg, March / April 2015. 18.Ivan Damgard, Bernardo Machado David, Irene Giacomelli, and Jesper Buus Nielsen. Compact VSS and ecient homomorphic UC commitments. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part II, volume 8874 of LNCS, pages 213{232. Springer, Heidelberg, December 2014. 19.Erez Druk and Yuval Ishai. Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications. In Moni Naor, editor, ITCS 2014, pages 169{182. ACM, January 2014. 20.Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identication and signature problems. In Andrew M. Odlyzko, editor, CRYPTO’86, volume 263 of LNCS, pages 186{194. Springer, Heidelberg, August 1987. 21.Tore K. Frederiksen, Benny Pinkas, and Avishay Yanai. Committed MPC - maliciously secure multiparty computation from homomorphic commitments. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part I, volume 10769 of LNCS, pages 587{619. Springer, Heidelberg, March 2018. 22.Tore Kasper Frederiksen, Thomas P. Jakobsen, Jesper Buus Nielsen, and Roberto Triletti. On the complexity of additively homomorphic UC commitments. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part I, volume 9562 of LNCS, pages 542{565. Springer, Heidelberg, January 2016. 23.Tore Kasper Frederiksen, Thomas Pelle Jakobsen, Jesper Buus Nielsen, Peter Sebastian Nordholt, and Claudio Orlandi. MiniLEGO: Ecient secure two-party computation from general assumptions. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 537{556. Springer, Heidelberg, May 2013. 24.Juan A. Garay, Yuval Ishai, Ranjit Kumaresan, and Hoeteck Wee. On the complexity of UC commitments. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 677{694. Springer, Heidelberg, May 2014.

25.Sha Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 113{122. ACM Press, May 2008. 26.Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 433{442. ACM Press, May 2008. 27.Aggelos Kiayias, Hong-Sheng Zhou, and Vassilis Zikas. Fair and robust multi-party computation using a global transaction ledger. In Marc Fischlin and Jean-Sebastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 705{734. Springer, Heidelberg, May 2016. 28.Yehuda Lindell. Highly-ecient universally-composable commitments based on the DDH assumption. In Kenneth G. Paterson, editor, EUROCRYPT 2011, volume 6632 of LNCS, pages 446{466. Springer, Heidelberg, May 2011. 29.Hugues Randriambololona. Asymptotically good binary linear codes with asymptotically good self-intersection spans. IEEE Trans. Information Theory, 59(5):3038{3045, 2013. 30.Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 49{62. ACM Press, June 2016. 31.Salil P. Vadhan and Colin Jia Zheng. Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In Howard J. Karlo and Toniann Pitassi, editors, 44th ACM STOC, pages 817{836. ACM Press, May 2012. 32.Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walsh. Doubly-ecient zkSNARKs without trusted setup. In 2018 IEEE Symposium on Security and Privacy, pages 926{943. IEEE Computer Society Press, May 2018.

Appendix A Universal Composability

We adopt the description of the Universal Composability (UC) framework given in [17]. In this framework, protocol security is analyzed under the real-world/ideal-world paradigm, i.e. by comparing the real world execution of a protocol with an ideal world interaction with the primitive that it implements. The model has a composition theorem, that basically states that UC secure protocols can be arbitrarily composed with each other without any security compromises. This desirable property not only allows UC secure protocols to eectively serve as building blocks for complex applications but also guarantees security in practical environments where several protocols (or individual instances of protocols) are executed in parallel, such as the Internet.

In the UC framework, the entities involved in both the real and ideal world executions are modeled as probabilistic polynomial-time Interactive Turing Machines (ITM) that receive and deliver messages through their input and output tapes, respectively. In the ideal world execution, dummy parties (possibly controlled by an ideal adversary S referred to as the simulator) interact directly with the ideal functionality F, which works as a trusted third party that computes the desired primitive. In the real world execution, several parties (possibly corrupted by a real world adversary A) interact with each other by means of a protocol that realizes the ideal functionality. The real and ideal executions are controlled by the environment Z, an entity that delivers inputs and reads the outputs of the individual parties, the adversary A and the simulator S. After a real or ideal execution, Z outputs a bit, which is considered as the output of the execution. The rationale behind this framework lies in showing that the environment Z (that represents all the things that happen outside of the protocol execution) is not able to eciently distinguish between the real and ideal executions, thus implying that the real world protocol is as secure as the ideal functionality.

We denote by REAL_;A;Z(;z; r) the output of the environment Z in the real-world execution of protocol between n parties with an adversary A under security parameter, input z and randomness r = (r_Z;r_A;r_P1;:::;r_Pn), where (z;r_Z), r_Aand r_Piare respectively related to Z, A and party i. Analogously, we denote by IDEAL_F;S;Z(;z; r) the output of the environment in the ideal interaction between the simulator S and the ideal functionality F under security parameter, input z and randomness r =

$$ \mathsf{R E A L}_{\pi,\mathcal{A},\mathcal{Z}}\ (\kappa,z,\bar{r}) $$

$$ \scriptstyle $$

$$ \vec{r},=,(r_{\mathcal{Z}},r_{\mathcal{A}},r_{P_{1}},\ldots,r_{P_{n}}) $$

$$ (z,r_{\mathcal{Z}}),;{r_{\mathcal{A}}} $$

$$ r_{P_{i}} $$

$$ \mathsf{I D E A L}_{\mathcal{F},\mathcal{S},\mathcal{Z}}(\kappa,z,\bar{r}) $$

$$ S $$

$$ \kappa, $$

$$ \mathcal{F} $$

$$ \bar{r}\ == $$

(r_Z;r_S;r_F), where (z;r_Z), r_Sand r_Fare respectively related to Z, S and F. The real world execution and the ideal executions are respectively represented by the ensembles REAL_;A;Z= fREAL_;A;Z(;z; r)g_2Nand IDEAL_F;S;Z= fIDEAL_F;S;Z(;z; r)g_2Nwith z 2f0*;* 1g and a uniformly chosen r.

$$ (r_{\mathcal{Z}},r_{\mathcal{S}},r_{\mathcal{F}}) $$

$$ r\mathcal{F} $$

$$ (z,r_{\mathcal{Z}}),r_{\mathcal{S}} $$

$$ \mathcal{F} $$

$$ \mathcal{Z},\mathcal{S} $$

$$ \mathsf{R E A L}{\pi,\mathcal{A},\mathcal{Z}}={\mathsf{R E A L}{\pi,\mathcal{A},\mathcal{Z}}(\kappa,z,\bar{r})}_{\kappa\in\mathbb{N}} $$

$$ \overline{{r}} $$

$$ \mathsf{I D E A L}{\mathcal{F},\mathcal{S},\mathcal{Z}}={\mathsf{I D E A L}{\mathcal{F},\mathcal{S},\mathcal{Z}}(\kappa,z,\bar{r})}_{\kappa\in\mathbb{N}} $$

$$ z\in\left{0,1\right}^{*} $$

In addition to these two models of computation, the UC framework also considers the G-hybrid world, where the computation proceeds as in the real-world with the additional assumption that the parties have access to an auxiliary ideal functionality G. In this model, honest parties do not communicate with the ideal functionality directly, but instead the adversary delivers all the messages to and from the ideal functionality. We consider the communication channels to be ideally authenticated, so that the adversary may read but not modify these messages. Unlike messages exchanged between parties, which can be read by the adversary, the messages exchanged between parties and the ideal functionality are divided into a public header and a private header. The public header can be read by the adversary and contains non-sensitive information (such as session identiers, type of message, sender and receiver). On the other hand, the private header cannot be read by the adversary and contains information such as the parties’ private inputs. We denote the ensemble G of environment outputs that represents the execution of a protocol in a G-hybrid model as HYBRID_;A;Z (dened analogously to REAL_;A;Z). UC security is then formally dened as:

$$ {mathcal\mathcal G{}}. $$

$$ \ {\sf{R E A L}}_{\pi,\ {\mathcal{A}},{\mathcal{Z}}}) $$

$$ \pi $$

$$ {sf H H Y R D}_{\pi,\mathcal{A},\mathcal{Z}}^{\mathcal{G}} $$

Denition 2. A n-party (n 2 N*) protocol is said to UC-realize an ideal functionality F in the G-hybrid* model if, for every adversary A, there exists a simulator S such that, for every environment Z, the following relation holds: G IDEAL HYBRID :

$$ (n\in\mathbb{N}) $$

$$ \mathcal{F} $$

$$ \sf{I D E A L}{\mathcal{F},\mathcal{S},\mathcal{Z}}\approx\sf{H Y B R I D}{\pi,\mathcal{A},\mathcal{Z}}^{\mathcal{G}} $$

We say that the protocol is statistically secure if the same holds for all Z with unbounded computing power.

Appendix B Interactive Proximity Testing

To prove Theorem 2 we rely on the Theorem 6 from [26,19] and the following Lemma 1.

Theorem 6([26,19]). Fix a nite eld F of constant size. For all integers n;m with m n there exists n m a family of linear universal hash functions G : F*!* F such that each function G 2G can be described by O(n) bits and computed in time O(n).

$$ \mathbb{F} $$

$$ m\leq n $$

$$ \mathcal{G}:\mathbb{F}^{n}\rightarrow\mathbb{F}^{m} $$

$$ G\in{\mathcal{G}} $$

$$ O(n) $$

$$ O(n) $$

Lemma 1. Let d = d(s) be a positive integer. Let F be a nite eld of constant size and F⁰ be an extension eld of F of degree l = ds + log_jFj(d)e. Let n = n(s;d) be such that a multiplication in F⁰ can be performed in n l time O(n). Let G : F*!* F be a family of F*-linear universal hash functions which can be computed in time* l l O(n) and has seed length O(n). Let : F*!* F⁰ be a linear embedding of F into F⁰*. For a function G 2G* l+d n s+logjFj(d) and an element 2 F⁰*, dene the function H*_G;: F*!* F⁰ = ^F by

$$ \mathbb{F}^{\prime} $$

$$ d=d(s) $$

$$ \mathbb{F} $$

$$ l=\left\lceil s+\log_{|\mathbb{F}|}(d)\right\rceil $$

$$ \mathbb{F}^{\prime} $$

$$ n=n(s,d) $$

$$ O(n) $$

$$ \mathcal{G}:\mathbb{F}^{n}\to\mathbb{F}^{l} $$

$$ O(n) $$

$$ \mathbb{F}^{l} $$

$$ \phi:\mathbb{F}^{l}\to\mathbb{F}^{\prime} $$

$$ O(n) $$

$$ \mathbb{F}^{\prime} $$

$$ G\in{\mathcal{G}} $$

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

$$ H_{G,\alpha}:\mathbb{F}^{l+d\cdot n}\to\mathbb{F}^{l}\cong\mathbb{F}^{s+\mathring{\mathrm{l o g}}_{|\vec{\mathbb{F}}|}(d)} $$

$$ H_{G,\alpha}(\mathbf{x})=\phi(\mathbf{x}{0})+\sum{i=1}^{d-1}\phi(G(\mathbf{x}_{i}))\alpha^{i}, $$

l n d where x = (x₀*;x₁;:::;x_{d 1}) 2 F (F). Dene the family H by H* = fH_G;: G 2 G; 2 F⁰g. Then s the family H is 2*-almost universal, has sub-linear seed-length O*(n) and can be computed in linear time O(d n). Moreover, if x₀ is uniformly random, then H_G;(x) is uniformly random for any (x₁*;:::;x_{d 1}) (xed or independent of x₀).*

$$ \mathbf{x}:=:(\mathbf{x}{0},\mathbf{x}{1},\ldots,\mathbf{x}_{d-1}):\in:\mathbb{F}^{l}\ \times:(\mathbb{F}^{n})^{d} $$

$$ \mathcal{H}=\left{H_{G,\alpha}:G\in\mathcal{G},\alpha\in\mathbb{F}^{\prime}\right} $$

$$ 2^{-s} $$

$$ O(d\cdot n) $$

$$ O(n) $$

$$ \mathbf{x}_{0} $$

$$ H_{G,\alpha}(\mathtt{X}) $$

$$ \left(\mathbf {x} _ {1}, \dots , \mathbf {x} _ {d - 1}\right) $$

$$ \mathbf{x}_{0}) $$

Instantiating the family G in Lemma 1 with the family provided in Theorem 6 we obtain Theorem 2.

Remark 2. We can choose the function n(s;d) as small as O((s + log_jFj(d)) polylog(s + log_jFj(d))), if a fast multiplication algorithm for F⁰ is used.

$$ n(s,d) $$

$$ O((s+\operatorname{l o g}{|\mathbb{F}|}(d))\cdot{\sf p o l y l o g}(s+\operatorname{l o g}{|\mathbb{F}|}(d)) $$

$$ \mathbb{F}^{\prime} $$ s Proof. The uniformity property follows immediately. We will show that H is 2 almo^st universal. Let x = (x₀*;:::;x_{d 1}) 6= 0. Thus there exists an i 2f0;:::;d* 1g such that x_i6= 0. If i = 0 then (x₀) 6= 0 $ as is injective. If i > 0 then it holds for a randomly chosen G G that G(x_i) 6= 0, except with probl ability 1*=jFj* = 1*=jF⁰j*. Consequently by injectivity of it holds that (G(x_i)) 6= 0. Suppose now that 0d 06= ( (x₀);(G(x₁)) :::;(G(x_{d 1}))) 2 F. Then

$$ \mathtt{X}=\left(\mathtt{X}{0},\dots,\mathtt{X}{d-1}\right)\neq0 $$

$$ 2^{-s} $$

$$ i\in{0,\ldots,d-1} $$

$$ \mathbf{x}_{i}\neq0 $$

$$ i=0 $$

$$ \phi(\mathbf{x}_{0})\neq,{0} $$

$$ i,>,0 $$

$$ G\xleftarrow{\mathfrak{S}}\ {mathcal G G} $$

$$ G(\mathbf{x}_{i}):\neq:0. $$

$$ 1/|\mathbb{F}|^{l},=,1/|\mathbb{F}^{\prime}| $$

$$ \phi $$

$$ \phi(G(\mathbf{x}_{i}));\neq;0 $$

$$ 0\neq(\phi(\mathbf{x}{0}),\phi(G(\mathbf{x}{1}))\ldots,\phi(G(\mathbf{x}_{d-1})))\in{\mathbb{F}^{\prime}}^{d} $$

$$ P(X)=\phi(\mathbf{x}{0})+\sum{i=1}^{d-1}\phi(G(\mathbf{x}_{i}))X^{i} $$

is a non-zero polynomial of degree at most d 1, and consequently P (X) has at most d 1 zeros. It follows $0 that for a random F that

$$ d-1 $$

$$ P(X) $$

$$ H_{G,\alpha}(\mathbf{x})=\phi(\mathbf{x}{0})+\sum{i=1}^{d-1}\phi(G(\mathbf{x}_{i}))\alpha^{i}=P(\alpha)\neq0, $$

except with probability (d 1)=jF⁰j. All together, we can conclude that H_G;(x) 6= 0, except with probability

$$ {\ (!!{d}!-!1)}/{|\ {mathbb R^{\prime}}|} $$

$$ H_{G,\alpha}(\mathbf{x})\neq0 $$

$$ \ 1/|\mathbb{F}^{\prime}|+(d-1)/|\mathbb{F}^{\prime}|=d/|\mathbb{F}|^{l}=|\mathbb{F}|^{-s} $$

$ $0 0 s+log (d) over the choice of G G and F, as jF j = jFj^jFj.

$$ \iota\xleftarrow{\S}\mathbb{F}^{\prime} $$

$$ G\xleftarrow{\mathfrak{S}}{mathcal G} $$

$$ \ \vert|\mathbb{F}^{\prime}\vert=\vert\mathbb{F}\vert^{s+\log_{\vert\mathbb{F}\vert}(d)} $$

Notice that the seed size of H_G;is

$$ H_{G,\alpha} $$

$$ |G|+\operatorname{l o g}(|\mathbb{F}^{\prime}|)=O(n)+(s+\operatorname{l o g}_{|\mathbb{F}|}(d))\operatorname{l o g}(|\mathbb{F}|)=O(n). $$

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

$$ H_{G,\alpha} $$

We will nally show that for any choice of G 2G and 2 F⁰ the function H_G;can be computed in linear time in the size of its input x. Computing G(x₁);:::;G(x_d) takes time O(d n), as computing each G(x_i) takes time O(n). By choosing the representation of the eld F⁰ appropriately computing the embedding is Pd 1 i esssentially free. Next, evaluating the polynomial P (X) = (x₀) +_i=1(G(x_i))X at na_ively costs d 1 additions and 2(d 1) multiplications. Since both additions and multiplications in F⁰ can be performed in time O(n), the overall cost of evaluating P (X) at can be bounded by O(l + d n). All together, we can compute H_G;in time O(l + d n), which is linear in the size of the input.

$$ G\in{\mathcal{G}} $$

$$ G(\mathbf{x}{1}),\ldots,G(\mathbf{x}{d}) $$

$$ O(d\cdot n) $$

$$ O(n) $$

$$ G(\mathbf{x}_{i}) $$

$$ \mathbb{F}^{\prime} $$

$$ \begin{array}{r}{P(X\boldsymbol X\big)=\phi\big(\mathtt x_{0}\big)+\sum_{i=1}^{d-1}\phi\big(\hat G\big(\mathtt x_{i}\big)\big)\boldsymbol X^{i}}\end{array} $$

$$ d-1 $$

$$ 2(d-1) $$

$$ \mathbb{F}^{\prime} $$

$$ O(n) $$

$$ P(X) $$

$$ O(l+d\cdot n) $$

$$ H_{G,\alpha} $$

$$ O(l+d\cdot n) $$

Theorem 7(Theorem 6 in [16]). Fix a nite eld F of constant size. There exists a constant > 0 and an explicit family of F*-linear codes* (C_s)_sof length O(s²), minimum distance s and rate 1 s, which approaches 1. Moreover, C has an encoding algorithm Enc that runs in time O(s²), which is linear in the codeword length.

$$ \mathbb{F} $$

$$ \gamma>0 $$

$$ O(s^{2}) $$

$$ \left(\mathsf{C}_{s}\right) $$

$$ 1-s^{-\gamma} $$

$$ O(s^{2}) $$

Appendix C Committing to Arbitrary Messages withAHCOM

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

Protocol_AHCOMdescribed in Section 3 realizes F_AHCOM, which only allows for commitments to random messages. While committing to random messages can be useful for a number of applications (e.g. [23]), in many scenarios it is necessary to commit to arbitrary messages. It has been shown in [16] that F_AHCOMcan be used to build a protocol for additively homomorphic commitments to arbitrary messages that also achieves rate-1 and linear time (given that_AHCOMis used to instantiate F_AHCOM). The basic idea consists in having the sender provide the receiver with the dierence between the arbitrary message it wants to commit to and one of the random messages provided by F_AHCOM, essentially using them as one-time pads. In order to commit to an arbitrary message m⁰, P executes the commitment phase of F_AHCOMto obtain a random message m, then it computes c = m⁰ m and broadcasts c. In order to add two commitments, P issues the addition command to F_AHCOMand sets c₃ = c₁ +c₂ = m⁰₁+m⁰₂m₁ m₂. In the opening phase, P issues

$$ \ mathit\Pi{}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ (e. g. [ 2 3 ]) $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ m^{\prime},P $$

$$ m, $$

$$ c=m^{\prime}-m $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ c_{3}=c_{1}+c_{2}=m_{1}^{\prime}+m_{2}^{\prime}-m_{1}-m_{2} $$

Protocol ARBHCOM 0m k Protocol ARBHCOM is run by a sender P with inputs m⁰1*;:::; m 2f0;* 1g and set of receivers V = fV₁;:::;Vtg, who interact with FCOM and proceed as follows:

1. Commitment Phase: 0j (a)On input (commit*;sid;ssid; m*), P sends (commit*;sid;ssid;P;V*) to FAHCOM. Upon receiving 0j (commit*;sid;ssid;P;V; mj*) as answer, P sets cj = m mj, and sends (cj*;sid;ssid;*) to V.
2. Addition: (a)On input (add*;ssid₁;ssid₂;ssid₃*), P sends (add*;sid;ssid₁;ssid₂;ssid₃;P;V*) to FAHCOM and sets c₃ = c₁ + c₂ = m⁰₁+ m⁰₂m₁ m₂. (b)Upon receiving (add*;sid;ssid₁;ssid₂;ssid₃;P;V;* success) from FAHCOM, V also sets c₃ = c₁ + c₂ = m⁰₁+ m⁰₂m₁ m₂.
3. Opening Phase: (a)On input (reveal*;ssid₁;:::;ssido*) P sends (reveal*;ssid₁;:::;ssido*) to FAHCOM and halts. 0j (b)Upon receiving (reveal*;sid;ssid;P;V; m₁;:::; mo*) from FAHCOM, for j 2f1*;:::;og V* computes m = ^0j cj +mj and outputs m. Note that, even if c is an addition of two commitments c₁ and c₂, this procedure is still valid since c₃ = c₁ + c₂ = m⁰₁+ m⁰₂m₁ m₂.

$$ m_{1}^{\prime},\ldots,m_{m}^{\prime}\in{0,1}^{k} $$

$$ V={V_{1},\ldots,V_{t}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ ,s i d,s s i d,P,V,m_{j}) $$

$$ c_{j}=m_{j}^{\prime}-m_{j} $$

$$ {_c{c3}}= $$

$$ c_{1}+c_{2}=m_{1}^{\prime}+m_{2}^{\prime}-m_{1}-m_{2} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ c_{3},=,c_{1}+c_{2},= $$

$$ m_{1}^{\prime}+m_{2}^{\prime}-m_{1}-m_{2}. $$

$$ s s i d_{1},\ldots,s s i d_{o})\ . $$

$$ s i d_{1},\ldots,s s i d_{o}) $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ i d,P,V,m_{1},\dots,m_{o}\big) $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

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

$$ m_{j}^{\prime}= $$

$$ m_{j}^{\prime} $$

$$ \ \ c_{j}+m m_j $$

$$ c_{1} $$

$$ c,, $$

$$ c_{3}=c_{1}+c_{2}=m_{1}^{'}+m_{2}^{'}-m_{1}-m_{2} $$

Fig. 11. Protocol ARBHCOM: Using AHCOM to commit to arbitrary messages.

the opening command to F_AHCOM, allowing V to obtain the intended message by computing m⁰ = c+m. We give the description of Protocol_ARBHCOMin almost verbatim form [16] in Figure 11. The only dierence is that Protocol_ARBHCOMonly allows for a single batch opening.

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ m^{\prime}=c+m $$

$$ \Pi_{\mathrm{A}} $$

$$ \Pi_ {\mathrm {A R B H C O M}} $$

As stated in [16], the security of_ARBHCOMcan be trivially observed since the random string from F_AHCOMacts as a one-time pad hiding all information and binding is guaranteed by F_AHCOM. Hence, ARBHCOMis statistically secure in the FAHCOM-hybrid model (which is realized byHCOM). Notice that ARBHCOMinstantiated withAHCOMalso achieves rate-1, since the commitment phase ofAHCOMonly sends the n k bottom rows of W and T₀*;*T₁, which only depend on the security parameter and are amortized over many commitments. When_ARBHCOMis instantiated using_AHCOMto realize F_AHCOM, 0j the extra communication in relation to_AHCOMcorresponds to the remaining k bits that dene each m. Moreover, it is possible to embed the dierence c in W so that no extra rounds are required. Hence, in this case,_ARBHCOMis rate-1 and linear time.

$$ \Pi_{\mathrm{A I}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M^h y}} $$

$$ \ mathit\Pi_{\mathrm{H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A R B I}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ n-k $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathbf {T} _ {0}, \mathbf {T} _ {1} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ m_{j}^{\prime}. $$

Appendix D Security Proofs forAHCOM

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

Lemma 2(Security Against a Corrupt P). There exists a simulator S_Psuch that for every static adversary A who corrupts P and all but one receivers in V = fV₁;:::;V_tg, and any environment Z, the environment cannot distinguish_AHCOMcomposed with F_COMand A from S_Pcomposed with F_AHCOM. That is, we have FCOM IDEAL HYBRID :

$$ \ {\mathcal{S}}_{P} $$

$$ V,=,{V_{1},\ldots,V_{t}} $$

$$ \mathcal{Z} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{S}_{P} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathsf{I D E A L}{\mathcal{F}{\operatorname{A H C O M}},\mathcal{S}{P},\mathcal{Z}}\approx{c}\mathsf{H T B R D}{\varPi{\operatorname{A H C O M}},\mathcal{A},Z}^{\mathcal{F}_{\operatorname{C O M}}}\ . $$

Proof. In case the adversary P^ corrupts the sender P and all but one receivers in V, the simulator S has ^P to run an internal copy of with P^, extract the messages in commitments performed by A and send AHCOM them to F^AHCOM. We describe the simulator S^Pin Figure 12. The simulator S_Pwill run protocol_AHCOM with an internal copy of P^ exactly as an honest V would.

$$ \hat{P} $$

$$ {hat\bar P}, $$

$$ \mathcal {S} _ {P} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{S}_{P} $$

$$ \mathcal{S}_{P} $$

$$ \Pi_{\mathrm{A I}} $$

Notice that S_Pemulates the instances of F_COMused by A following the exact instructions of F_COM but learning r and the seeds s_i;j. Using this knowledge, S_Preconstructs matrices*;* Q*;B following the instructions of an honest V in the opening phase. With the reconstructed;* Q*;B and matrices H;T₀;T₁ learned in the course of the execution with P^, S has exactly the same view as an honest V will have in the P opening phase (when it learns r and s_i;r[1]for i = 1;:::;n* from F_COM). Hence, if the checks of an honest V

$$ \hat{P} $$

$$ \ {\mathcal{S}}_{P} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ s_{i,j} $$

$$ \mathcal{S}_{P} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \Delta,\mathbb{Q},\mathbb{B} $$

$$ \mathbf{\Delta},\mathbf{Q},\mathbf{B} $$

$$ \mathrm{H}T_{0},T_{1} $$

$$ {\hat{P}},{\mathcal{S}}_{P} $$

$$ s_{i,r[1]} $$

$$ i=1,\ldots,n $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ {\mathcal{S}}_{P} $$

Simulator SP

Simulator S interacts with environment Z, functionality F and an internal copy of the adversary P^. P AHCOM Upon being activated by Z, SV proceeds as follows:

$$ {\mathcal{S}}_{P} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ {mathcal{Z}}, $$

$$ \hat {P}. $$

$$ \mathcal{Z},\mathcal{S}_{V} $$

1. Emulating F^COM: S^P executes exactly the steps of F^COM. S^P stores the vector r = r₁ ::: r^t computed using the vectors r rece_ived from the receivers V (_including itself and the receivers controlled by P^). i i Moreover, it stores the seeds s received from P^ for i 2 [n] and j 2f0*;* 1g. i;j

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \ {\mathcal{S}}_{P} $$

$$ \mathcal{S}_{P} $$

$$ r r r r r_{1}\oplus\ldots\oplus r_{t} $$

$$ V_{i} $$

$$ \hat{P} $$

$$ r_{i} $$

$$ \hat{P}) $$

$$ i\in[n] $$

2. Commitment Phase: S^P executes the steps of the commitment phase of ^AHCOM exactly like an honest V would do. After completing the commitment phase with P^, S learns W*;T₀;T₁ from P^ and H from r⁰ P (which in turn is obtained from FCOM during the execution). SP uses its knowledge of si;j to reconstruct R₀;R₁;R and then obtain A given W. Next, SP uses W and its knowledge of the seeds si;j and r to reconstruct, Q and B as honest receivers would in Step 4(a) of the opening phase. SP executes the tests of an honest verier in Step 4(b) using H;T₀;T₁ obtained in the execution with P^ and;* Q*;B reconstructed previously. If the checks succeed, for j 2 [m], SP decodes column A[;j*] obtaining message mj. Otherwise, it k samples mj f 0*;* 1g. Finally, SP sends (commit*;sid;ssidj;P;V; mj*) to FAHCOM. We will show that if the checks of an honest verier’s steps in AHCOM fail, then SP will abort in the Opening Phase (as an honest verier would). Otherwise, the remaining m columns of A can indeed be decoded to their corresponding committed messages except with negligible probability. ^,

$$ j\in{0,1} $$

$$ s_{i,j} $$

$$ {\mathcal{S}}_{P} $$

$$ \Pi_{\mathrm{A l}} $$

$$ \mathbf{W},\mathbf{T_{0}},\mathbf{T_{1}} $$

$$ {\dot{P}},{\cal S}_{P} $$

$$ \hat{P} $$

$$ r^{\prime} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ s_{i,j} $$

$$ {\mathcal{S}}_{P} $$

$$ \mathrm{R_{0},R_{1},R} $$

$$ {\mathcal{S}}_{P} $$

$$ s_{i,j} $$

$$ \Delta , \mathrm {Q} $$

$$ r $$

$$ 4(\mathbf{a}) $$

$$ {\mathcal{S}}_{P} $$

$$ \mathrm{H}T_{0},_{\ } $$

$$ \hat{P} $$

$$ 4(\mathrm{b}) $$

$$ \mathbf{\Delta},\mathbf{Q},\mathbf{B} $$

$$ j\in[m] $$

$$ \mathbf{A}[\cdot,j] $$

$$ \ {\mathcal{S}}_{P} $$

$$ m_{j} $$

$$ m_{j}\leftarrow{0,1}^{k} $$

$$ {\mathcal{S}}_{P} $$

$$ s i d,s s i d_{j},P,V,m_{j}) $$

$$ \mathcal{F}_{A} $$

$$ {\mathcal{S}}P $$

3. Addition: Upon receiving (add*;sid;ssid₁;ssid₂*) from P SP execute the steps of AHCOM for addition, chooses an unused ssid ssid₃ and sends (add*;sid;ssid₁;ssid₂;ssid₃;P;V*) to F^AHCOM.

$$ {\hat{P}},,{\mathcal{S}}_{P} $$

$$ smathrm i d{}{{}}\mathrm{}{s i d}{3} $$

$$ \left(\mathsf{a d d},\mathsf{s i d},\mathsf{s s i d}{1},\mathsf{s s i d}{2},\mathsf{s s i d}_{3},P,V\right) $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

4. Opening Phase: Upon receiving (sid;ssid₁;:::;ssid;(A₀[;j];A₁[;j])) from P^, S executes the exact o j2J P steps of an honest V in ^AHCOM. If any of the checks fails (meaning one of the (A₀[;j];A₁[;j]) is not a consistent opening),, S outputs whatever P^ outputs and aborts. Otherwise S sends (reveal*;sid;ssid₁;:::;ssid*) P P _o to F, outputs whatever P^ outputs and halts. AHCOM

$$ \mathcal{F}_{\mathrm{A H C O M}}. $$

$$ (s i d,s s i d_{1},\ldots,s s i d_{o},(\mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j])_{j\in J}) $$

$$ \ddot {P}, \mathcal {S} _ {P} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ {\mathcal{S}}P $$

$$ \hat{P} $$

$$ (\mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j]) $$

$$ \ {\mathcal{S}}P $$

$$ (\mathrm {r e v e a l}, s i d, s s i d _ {1}, \dots , s s i d _ {o}) $$

$$ \hat{P} $$

Fig. 12. Simulator SP

$$ {\mathcal{S}}P $$

performed by S_Pusing this view of H*;T₀;T₁;;* Q*;*B fail, it will abort in the opening phase with probability 1 (as an honest V would). In this case, the random messages m^jsent by S^Pto F^AHCOMwill never be opened, and the joint distribution of ideal execution with S is indistinguishable from the real execution with P^. P

$$ \mathcal{S}_{P} $$

$$ \mathrm{H,T_{0},T_{1},\Delta,Q} $$

$$ m_{j} $$

$$ \mathcal{S}_{P} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{S}_{P} $$

$$ \hat{P} $$

In case the checks of an honest V performed by S^Psucceed, it is necessary to extract the messages contained in A. By using W received from P^ in the execution and the seeds s received from P^ by F i;j _COM for i 2 f1*;:::;ng* and j 2 f0*;* 1g, S_Pcan reconstruct A by computing R₀[i;] = PRG(s_i;0) and R₁[i;] = PRG(s^i;1), for i = 1*;:::;n*, and setting A₀ = R₀, A₁ = R₁ + W and A = A₀ + A₁. However, it might be m^ is malicious. It remains to prove that the case that A 62 C because P S_Pcan decode the columns of A m and obtain the committed messages with high probability, even though it might be the case that A 62 C ^m (but close enough to C). As an intermediate hybrid, we assume that matrices R₀*;R₁ are uniformly random. Notice that this hybrid is computationally indistinguishable from the actual simulation since the rows of R₀;*R₁ are generated by stretching uniformly random seeds with PRG, so distinguishing them from uniformly random matrices of same size breaks the pseudorandomness of PRG. The remainder of this proof uses the same technique of [16, Lemma 8], which we reproduce in almost verbatim form below:

$$ \mathcal{S}_{P} $$

$$ \hat{P} $$

$$ \hat{P} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

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

$$ s_{i,j} $$

$$ j\in{0,1} $$

$$ \ {\mathcal{S}}_{P} $$

$$ \mathsf{R}{0}[i,\cdot]=\mathsf{P R G}(\mathfrak{s}{i,0}) $$

$$ \mathsf{P R G}(s_{i,1}) $$

$$ i=1,\ldots,n. $$

$$ \mathrm{,},,\mathbf{A}{0}=\mathbf{R}{0},,\mathbf{A}{1}=\mathbf{R}{1}+\mathbf{W} $$

$$ \mathbf{A}=\mathbf{A}{0}+\mathbf{A}{1} $$

$$ \mathsf{A}\not\in\mathsf{C}^{\complement}m $$

$$ \hat{P} $$

$$ \mathcal{S}_{P} $$

$$ \mathsf{A}\notin\mathbb{C}^{\complement}m $$

$$ \mathbb{C}^{\odot m}] $$

$$ {\bf R}{0},{\bf R}{1} $$

$$ {\bf R}{0},{\bf R}{1} $$

m The simulator will identify < s rows such that A is in C except for the identied rows. As the code has minimum distance s, this allows to erasure decode each column j of A to C and the corresponding decoded message will be the extracted message m_jthat the simulator will input to F_AHCOM. We now give the details.

$$ \mathbb{C}^{\odot m} $$

$$ s, $$

$$ m_{j} $$

$$ \mathsf{C} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

n Let R [n] be a set of indices specifying rows of A. For a column vector c 2 F we let_R(c) = (c[i])_i2[n]nR be the vector punctured at the indices i 2 R. For a matrix M we let M_R=_R(M) be the matrix with each column punctured using_Rand for a set S we let S_R= f_R(s)js 2 Sg. The simulator will need to nd R [n] with jRj < s such that

$$ R\subset[n] $$

$$ \boldsymbol{c}\in\mathbb{F}^{n} $$

$$ \pi_{R}(c)=(c[i])_{i\in[n]\setminus R} $$

$$ i\in R $$

$$ \mathbf{M}{R}=\pi{R}(\mathbf{M}) $$

$$ R\subset[n] $$

$$ S_{R}={{\pi}_{R}(s)|s\in S} $$

$$ \pi_{R} $$

$$ |R|<s $$

$$ \mathsf{A}{R}\in\mathsf{C}{R}^{\complement},, $$

(2)

It should furthermore hold that

(3)

$$ \mathbb{H}{\infty}\big((b{i})_{i\in R}|\hat{P}\big)=0 $$

$$ \mathbb{H}{\infty}\bigl((b{i})_{i\in[n]\setminus R}\bigl|\hat{P}\bigr)=n-\bigl|R\bigr| $$

(4)

where P^ here denotes the view of P^ in the simulator so far, i.e., the adversary can guess R and each choice bit bⁱfor i 2 R with certainty at this point in the simulation and has no extra information on bⁱfor i 62 R.

$$ \hat{P} $$

$$ \hat{P} $$

$$ b_{i} $$

$$ i\in R $$

Dene T := AH. Let T^ and T^ be the values sent by P and let T^ = T^ + T^. Let T₀ = R₀H and 0 1 0 1 T₁ = (R₁ + W)H be the values that P^ should have sent. Let T = T₀ + T₁. Let R be the smallest set such that T^ = T. We claim that this set fullls (2), (3) and (4). R R

$$ b_{i} $$

$$ i\not\in R $$

$$ \hat{P} $$

$$ \mathbf{T}:=\mathbf{A}\mathbf{H} $$

$$ \hat{\mathbf{T}}_{0} $$

$$ \mathbf{\dot{T}}_{1} $$

$$ \hat{\mathbf{T}}=\hat{\mathbf{T}}{0}+\hat{\mathbf{T}}{1} $$

$$ \mathbf{T}{1}=(\mathbf{R}{1}+\mathbf{W})\mathbf{I} $$

$$ \mathbf{T}{0}=\mathbf{R}{0}\mathbf{H} $$

$$ \mathbf{T}=\mathbf{T}{0}+\mathbf{T}{1} $$

$$ \hat{\mathbf{T}}{R}=\mathbf{T}{R} $$

We know that the receiver did not abort, which implies that T^ + (I)T^ = BH. The i’th row of ₁ 0 T^ + (I)T^ can be seen to _be T^ [i;]. The i’th row of B can be seen to be b W[i;] + R, so the i’th 1 0 bi i bi row of BH is T_bi[i;]. We thus have for all i that

$$ \Delta\mathring{\mathrm{T}}{1}+(\mathrm{I}-\Delta)\mathring{\mathrm{T}}{0}=\mathrm{B H} $$

$$ \Delta\hat{\mathbf{T}}{1}+(\mathbf{I}-\Delta)\hat{\mathbf{T}}{0} $$

$$ \hat{\mathbf{T}}{b{i}}[i,\cdot] $$

$$ \ {\mathbf{T}{b}}{i}[i,\cdot] $$

$$ b_{i}\ \mathbf{W}[i,\cdot]+\mathbf{R}{b{i}} $$

$$ \hat{\mathrm{T}}{b{i}}[i,\cdot]=\mathrm{T}{b{i}}[i,\cdot];. $$

For each i 2 R we have that T^ [i;] 6= T[i;], so we must therefore have for all i 2 R that

$$ i\in R $$

$$ \hat{\mathbf{T}}[i,\cdot]\neq\mathbf{T}[i,\cdot] $$

$$ i\in R $$

$$ \hat{\mathbf{T}}{1-b{i}}[i,\cdot]\neq\mathbf{T}{1-b{i}}[i,\cdot];. $$

It follows that if V for position i had chosen the choice bit 1 bⁱinstead of bⁱ, then the protocol would have aborted. Since P^ can compute the correct values T [i;] and T₁ [i;] it also knows which value of b b_i bi i will make the test pass. By assumption the protocol did not abort. This proves (3). It also proves that the jRj^ has no information on probability of the protocol not aborting and R having size jRj is at most 2 as P ^ ^ ^ can guess (^jRj b₁;:::;b_nprior to sending T₀and T₁so P b_i)_i2Rwith probability at most 2. It is easy to see that the value of the bits bⁱfor i 62 R do not aect whether or not the test succeeds. Therefore these bits are still uniform in the view of P^ at this point.

$$ 1-b_{i} $$

$$ \hat{P} $$

$$ b_{i} $$

$$ \mathbf{T}{b{i}}[i,\cdot] $$

$$ \mathbf{T}{1-b{i}}[\dot{i},\cdot] $$

$$ b_{i} $$

$$ (3) $$

$$ |R| $$

$$ \hat {\mathbf {T}} _ {0} $$

$$ \ ^{-}|R| $$

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

$$ \hat{\mathbf{T}}_{1} $$

$$ \hat{P} $$

$$ \hat{P} $$

$$ (b_{i})_{i\in R}} $$

$$ 2^{-|R|} $$

$$ b_{i} $$

$$ i\not\in R $$

$$ \dot{P} $$

In particular, we can therefore continue under the assumption that jRj < s. We can then apply Theorem m 1 where we set X = A. From jRj < s it follows that XH has distance less than s to C, so we must be ^l in case 2 in Theorem 1. Now, since the receiver checks that T 2 C and the protocol did not abort, we in particular have that T^ 2 C from which it follows that T 2 C, which in turn implies that A H 2 C _{R Rl} R Rl R Rl l and thus X^RH 2 C^Rl. We can therefore pick a codeword C⁰ 2 C such that the row support of XH C⁰ is m R. From Theorem 1 we then get that there exists C 2 C such that the row support of A C is R. From this it follows that A_R= C_R, which implies (2).

$$ |R|<s $$

$$ |R|<s $$

$$ \mathbf{X}=\mathbf{A} $$

$$ \mathsf{C}^{\odot m} $$

$$ \hat{\mathbf{T}}\in\mathbb{C}^{\odot l} $$

$$ \hat{\mathbf{T}}{R}\in\mathbb{C}{R}^{\odot l} $$

$$ \mathbf{T}{R}\in\mathsf{C}{R}^{\odot l} $$

$$ \mathbf{A}{R}\mathbf{H}\in\mathsf{C}{R}^{\odot l} $$

$$ \mathbf{X}{R}\mathbf{H}\in\mathsf{C}{R}^{\odot l} $$

$$ \mathbf {C} ^ {\prime} \in \mathrm {C} ^ {\odot l} $$

$$ \mathrm{X H-C^{\prime}} $$

$$ \mathsf{C}\in\mathsf{C}^{\complement}m $$

$$ \mathbf{A}C- $$

$$ \mathbf{A}{R}=\mathbf{C}{R}. $$

Now notice that since C has minimum distance s and jRj < s the punctured code CRwill have minimum distance at least 1. Therefore the simulator can from each column A[i;]^R2 C_Rdecode the corresponding k^. message m_j2f0*;* 1g. This is the message that the simulator will input to F_AHCOMon behalf of P

$$ |R|<s $$

$$ C!{{_it R}} $$

$$ m_{j}\in{0,1}^{k} $$

$$ \mathbf{A}[i,\cdot]{R}\in\mathsf{C}{R} $$

$$ \dot{P} $$

$$ \mathcal{S}_{P} $$

In order to fool S^Pand open a commitment to a dierent message than the one that has been extracted from A[;j], P^ would have to provide A⁰ [;j];A⁰ [;j] such that A⁰[;j] = A⁰ [;j]+ A⁰ [;j] is a valid codeword 0 1 0 1 of C corresponding to a dierent message m⁰. However, notice that since C^Rhas minimum distance s jRj, that would require P^ to modify an additional s jRj positions of A that are not contained in R so that it does not get caught in the checks performed by a honest V in the opening phase. That means that P^ would have to guess s jRj of the choice bits bⁱfor i 62 R. It follows from (4) that this will succeed with probability jRjs^ suceeded in passing the previous checks without at most 2. Taken in combination with the fact that P jRj^ is 2jRj jRjs s the protocol aborting with probability 2, the total probability of success for P 2 = 2.

$$ \mathcal{F}_{\mathrm{A H C O h}} $$

$$ \mathbf{A}[\cdot,j],\hat{P} $$

$$ \mathbf{A}{0}^{\prime}[\cdot,j],\mathbf{A}{1}^{\prime}[\cdot,j] $$

$$ \mathbf{A}^{\prime}[\cdot,j]=\mathbf{A}{0}^{\prime}[\cdot,j]!+!\mathbf{A}{1}^{\prime}[\cdot,j] $$

$$ m^{\prime} $$

$$ s-|R| $$

$$ \mathbb{C}_{R} $$

$$ \hat{P} $$

$$ s-|R| $$

$$ s-|R| $$

$$ b_{i} $$

$$ \hat{P} $$

$$ 2^{|R|-s} $$

$$ i\not\in R $$

$$ \hat{P} $$

$$ 2^{-|R|} $$

$$ 2^{-|R|}\cdot2^{|R|-s}=2^{-s} $$

$$ \hat{P} $$

Lemma 3(Security Against a Corrupt V). There exists a simulator S_Vsuch that for every static adversary A who corrupts all receivers in V = fV₁;:::;V_tg, and any environment Z, the environment cannot distinguish_AHCOMcomposed with F_COMand A from S_Vcomposed with F_AHCOM. That is, we have

$$ \mathcal{S}_{V} $$

$$ V={V_{1},\ldots,V_{t}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \mathcal{S}_{V} $$

$$ \mathsf{I D E A L}{\mathcal{F}{\operatorname{A H C O M}},\mathcal{S}{V},\mathcal{Z}}\approx{c}\mathsf{H Y B R D}{\varPi{\operatorname{A H C O M}},\mathcal{A},Z}^{\mathcal{F}_{\operatorname{C O M}}}. $$

$$ \mathcal{S}_{V} $$

Simulator SV

Simulator S interacts with environment Z, functionality F and an internal copy of adversary V^. Upon V AHCOM being activated by Z, SV proceeds as follows:

$$ \mathcal{S}_{V} $$

$$ \hat{V}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ \preceq $$

$$ \mathcal{Z},,\mathcal{S}_{V} $$

1. Emulating FCOM: SV executes exactly the steps of FCOM, storing r = r₁ ::: rt computed using the random strings r received from V for i 2 [t] (controlled by V^). i i

$$ \mathcal{S}_{V} $$

$$ \mathcal{F}_{\mathrm{C O M}}. $$

$$ r=r_{1}\oplus\ldots\oplus r_{t} $$

2. Commitment Phase: Upon receiving (receipt*;sid;ssid₁;:::;ssidm;P;V*) from FAHCOM, SV runs the steps of an honest P in the commitment phase exactly as in AHCOM.

$$ V_{i} $$

$$ i\in[t] $$

$$ r_{i} $$

$$ \hat{V}) $$

$$ \ *{i}d{}{1},\ldots,{{s s}i d d{m}},P,V{} $$

$$ \mathcal{F}{\operatorname{A H C O M}},:\mathcal{S}{V} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}}. $$

3. Addition: Upon receiving (add*;sid;ssid₁;ssid₂;ssid₃;P;V;* success) from FAHCOM, SV runs the steps of an honest P exactly as in AHCOM (using indexes i and j associated to ssid₁;ssid₂).
4. Opening Phase: Let J = fj₁;:::;jog be the set of indexes associated with ssid of the opening phase, ssid₁;:::;ssido. Upon receiving (reveal*;sid;ssid;P;V; mj*) from FAHCOM for j 2 J, SV uses its knowledge of 0 0 0 0 r[1];:::; r[n] to compute alternative columns A₀ [;j];A₁ [;j] such that A⁰[;j] = A₀ [;j]+A₁ [;j] is a valid commitment to m that can opened without being caught by V^ even though m is dierent from the messages j j 0 0 committed to in the commitment phase. Namely, SV initially sets A₀ [;j] = A₀[;j];A₁ [;j] = A₁[;j] and 0 0 then sets A⁰1 r[i][;j] = C(mj) Ar[i][;j]. Note that matrices A₀ [;j];A₁ [;j] only dier from matrices A₀[;j];A₁[;j] obtained in the commitment phase in positions that are not known by V^. Finally, S sends V 0 0^, outputs whatever ^ (sid;ssid₁;:::;ssid_o;(A₀ [;j];A₁ [;j])_j2J) to V V outputs and halts.

$$ \mathcal{F}{\operatorname{A H C O M}},:\mathcal{S}{V} $$

$$ s s i d_{1},s s i d_{2}) $$

$$ j $$

$$ J,=,{j_{1},\ldots,j_{o}} $$

$$ P,V,m_{i}) $$

$$ smathrm{}{s s i}{1},\ldots,\mathrm{}{s s i}{o} $$

$$ {\mathcal{F}}_{\mathrm{A}} $$

$$ j\in J,,\mathcal{S}_{V} $$

$$ \mathfrak{r}[1],\ldots,\mathfrak{r}[n] $$

$$ \mathbf{A_{0}}^{\prime}[\cdot,j],\mathbf{A_{1}}^{\prime}[\cdot,j] $$

$$ \mathbf{A^{\prime}[\cdot,j]}=\mathbf{A_{0}}^{\prime}[\cdot,j]{+}\mathbf{A_{1}}^{\prime}[\cdot,j] $$

$$ m_{j} $$

$$ \hat{V} $$

$$ m_{j} $$

$$ \mathcal{S}_{V} $$

$$ {\bf{A}}{0}{'}[\cdot,j]={\bf{A}}{0}[\cdot,j],{\bf{A}}{1}{'}[\cdot,j]={\bf{A}}{1}[\cdot,j] $$

$$ \mathsf{A}{1-r[i]}^{\prime}[\cdot,j]=\ {mathsf C\bigl(}m{j}{\bigr)}-\mathsf{A}_{r[i]}[\cdot,j] $$

$$ \mathbf{A_{0}}^{\prime}[\cdot,j],\mathbf{A_{1}}^{\prime}[\cdot,j] $$

$$ \mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j] $$

$$ \mathcal{S}_{V} $$

$$ \hat{V} $$

Fig. 13. Simulator SV

$$ \hat{V} $$

$$ {,}{s s}{i d}{1},\ldots,{s s}{i d}{o},(\mathbf{A_{0}}^{\prime}[\cdot,j],\mathbf{A_{1}}^{\prime}[\cdot,j])_{j\in J}) $$

$$ \mathcal{S}_{V} $$

Proof. In case the adversary corrupts all receivers in V, the simulator S^Vhas to run^AHCOMwith an internal copy of V^, commit to a random string and then equivocate this commitment (i.e., open it to an arbitrary message) when it receives the actual message from F_AHCOM. In order to achieve this, we construct a S_Vthat executes the commitment phase exactly as an honest P in_AHCOM, only deviating in the opening phase. We describe S_Vin Figure 13.

$$ V $$

$$ \hat{V} $$

$$ \mathcal{S}_{V} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{A H C O M}} $$

$$ (i.e. $$

$$ \mathcal{S}_{V} $$

$$ P $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{S}_{V} $$

Again we use an intermediate hybrid, where we assume that matrices R₀*;R₁ are uniformly random. Notice that this hybrid is computationally indistinguishable from the actual simulation since the rows of R₀;*R₁ are generated by stretching uniformly random seeds with PRG, so distinguishing them from uniformly random matrices of same size breaks the pseudorandomness of PRG.

$$ {\bf R}{0},{\bf R}{1} $$

$$ {\bf R}{0},{\bf R}{1} $$

Notice that V^ has no information at all about the committed strings after the commitment phase. This is true because each row of B is one additive share of A (either a row from R₀ or a row from R₁ adjusted by W) that trivially contains no information. Moreover, matrix P is never revealed and Q has the same structure as B (containing no information about P). Hence, matrices T₀*;*T₁ seen by V^ in the commitment phase contain no information about the message encoded in A.

$$ \mathbf{R}_{0} $$

$$ \mathbf{R_{1}} $$

$$ \mathbf{T}{0},\mathbf{T}{1} $$

$$ \hat{V} $$

Notice that S learns vector r by observing vectors r sent to F by V^ and that the inverses of V i COM bits r[1];:::; r[n] represent the positions of the matrices that are unknown to V^ (i.e., unknown to V in the real world). In this scenario, S_Vcan open a commitment to an arbitrary message without being detected. Note that S^Vexecutes the exact steps of an honest P in^AHCOMexcept for the opening phase. For each 0 0 commitment associated with index j to be opened, S_Vsends A₀ [;j];A₁ [;j], which are dierent from the vector A₀[;j];A₁[;j] computed in the commitment phase and that would be sent in a real execution of 0 0^. _AHCOM. However, A₀[;j]; A₁[;j], only dier from A₀[;j]; A₁[;j] in positions that are unknown by V Hence, the joint distribution of the ideal execution with simulator S_Vis computationally indistinguishable from the real execution of_AHCOMwith corrupted receivers.

$$ \mathcal{S}_{V} $$

$$ r_{i} $$

$$ r[1],\ldots,r[n] $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \hat{V} $$

$$ \mathcal{S}_{V} $$

$$ \mathcal{S}_{V} $$

$$ {\hat{V}}\ (i,e). $$

$$ P $$

$$ \mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j] $$

$$ \mathcal{S}_{V} $$

$$ j $$

$$ \mathbf{A_{0}}^{\prime}[\cdot,j],\mathbf{A_{1}}^{\prime}[\cdot,j] $$

$$ \Pi_{\mathrm{A}} $$

$$ \mathbf{A_{0}}^{\prime}[\cdot,j],\mathbf{A_{1}}^{\prime}[\cdot,j] $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathbf{A_{0}}[\cdot,j],\mathbf{A_{1}}[\cdot,j] $$

$$ \hat{V} $$

Appendix E Security Proofs forMHCOM

$$ \mathcal{S}_{V} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

Theorem 4. Protocol_MHCOMUC realizes F_MHCOMin the F_COM-hybrid model with computational security against a static adversary. Formally, there exists a simulator S such that for every static adversary A, and any

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

environment Z, the environment cannot distinguish_MHCOMcomposed with F_COMand A from S composed with F_MHCOM. That is, we have

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{F}_{\mathrm{M H C O M}} $$

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ \mathsf{I D E A L}{\mathcal{F}{\operatorname{M H C O M}},\mathcal{S},\mathcal{Z}}\approx_{c}\mathsf{H V B R D D}{\varPi{\operatorname{M H C O M}},\mathcal{A},Z}^{\mathcal{F}_{\operatorname{C O M}}}\ . $$

Proof. If the adversary P^ corrupts the sender P and all but one receivers in V, the simulator S will ^P ₀b, Q, Q⁰ b, H, T~ ~ analogously as in the proof of Lemma 2 learn the seeds s_i;j, bs_i;j, r,,, B, B⁰, B, Q₀, T₁, T. Then it will do all checks that the honest verier will do in the step 4(b). If the checks fail, it will abort 2 A as an honest V would. Assume then that the checks succeed. Now S reconstructs A = and we need to Pb A ~ ) m prove that S^Pcan extract the committed messages with high probability even in the case where A 2= (C. In order to do that, the simulator S will nd sets of rows R, R^ of rows (where R is a subset of the rows in P ^ is a subset of the rows in Ab) such that ^ are small and such that A would be in (C) _m A and R R, R except ~ ~) m in the remaining rows). for those rows (i.e. there exists C 2 (C which equals A

$$ \hat{P} $$

$$ V, $$

$$ \mathcal{S}_{P} $$

$$ \ {i,j},:\widehat{s}{i,j},:\mathbf{r},:\mathbf{\Delta},:\mathbf{\Delta}^\prime,:\mathbf{B},:\mathbf{B}^{\prime},:\mathbf{B},:\mathbf{Q},:\mathbf{Q}^{\prime},:\widehat{\mathbf{Q}} $$

$$ \tilde{\mathbf{T}}{0},\tilde{\mathbf{T}}{1} $$

$$ \tilde{\bf{T}}_{2} $$

$$ \mathcal{S}_{P} $$

$$ \tilde {\mathbf {A}} = \left( \begin{array}{c} \mathbf {A} \ \widehat {\mathbf {A}} \end{array} \right) $$

$$ \ {\mathcal{S}}_{P} $$

$$ \mathcal{S}_{P} $$

$$ \tilde{\mathsf{A}}\notin(\tilde{\mathsf{C}})^{\complement}m $$

$$ \tilde{\mathbf A{}} $$

$$ R,,{\hat{R}} $$

$$ (tilde\tilde{\mathsf{C}})^{\odot m} $$

For j = 0*;* 1*;*2, let U, U^, be matrices sent by the corrupt prover in place of the values T, T^ that _j j j j it should have sent. Let U = U₀ + U₁ + U₂ and dene U^ , T, T^ analogously. The simulator denes R (respectively R^) to be the set of rows in which T and U (respectively T^ and U^) dier.

$$ j,=,0,1,2 $$

$$ \tilde {\mathbf {C}} \in (\tilde {\mathrm {C}}) ^ {\odot m} $$

$$ \tilde{\bf A} $$

$$ \mathbf{T}{j},,\hat{\mathbf{T}}{j} $$

$$ \mathbf{U},{=},\mathbf{U}{0}+\mathbf{U}{1}+\mathbf{U}_{2} $$

$$ \mathbf{U}{j},\hat{\mathbf{U}}{j} $$

$$ \hat{\mathbf{U}},,\hat{\mathbf{T}} $$

$$ \mathbf{T} $$

$$ \hat{\mathbf{T}} $$

$$ r_{i},=,r|i| $$

Now call rⁱ= r[i] the selections of the verier. Since the receiver did not abort, then U^ri= T_ri, U = T, U^ = T^ Fo_r every position in R, it must hold that U 6= T, while for every position ri+1 ri+1 ri ri ri+2 ri+2 _in R^, e_ithe_r U^ 6= T^ o_r U^ 6= T^ (o_r both). The probability that the protocol does not abort ri+1 ri+1 ri+2 ri+2 equals the probability that P^ guesses r exactly for every i in R and guesses a subset of two (out of three) i elements in which r _is, for every i in R^ n R. Therefore the probability that the protocol does not abort is i ^{jRj jRnRj ^}^ (indeed this is in ^’s advantage: if ^ changes a share for the (1*=3) (2=3). We can assume R R P P i-th row of T successfully, then it is because it guessed r exactly, but then it can change the i-th row T^ i \for free"). Nevertheless, the maximum number of total coordinates that P^ can change (the maximum of ^s jRj+jRj) such that the probability that the protocol does not abort is at least 2 is achieved for R =;* and jR^j = s where = 1*=*(log₂ 3 1). Therefore assume that P^ can change at most s coordinates, and recall ₂ ~). We are then in case 2 of Theorem 1 when applied to X = A^ that by assumption s < dist(C) dist(C C ~ = ~) mb b and C as linear code. Thus we eventually nd a matrix C 2 (C with C_R= A_Rand C_^= A_^ b _R R

$$ \mathrm{U}{r{i}+1}=\mathrm{T}{r{i}+1},\hat{\mathrm{U}}{r{i}}=\hat{\mathrm{T}}{r{i}} $$

$$ {bf U}{r{i}};=;{\bf}{\bf T}{r{i}} $$

$$ \mathbf{U}{r{i}+2}\neq\mathbf{T}{r{i}+2} $$

$$ {\dot{R}},{\dot{}} $$

$$ \mathbf{\hat{U}}{r{i}+1}\neq\mathbf{\hat{T}}{r{i}+1} $$

$$ \mathbf{\hat{U}}{r{i}+2}\neq\mathbf{\hat{T}}{r{i}+2} $$

$$ \hat{P} $$

$$ r_{i} $$

$$ r_{i} $$

$$ {hat R}\setminus $$

$$ (1/3)^{|R|}(2/3)^{|\hat{R}\backslash R|} $$

$$ \hat{P}^{'}\mathrm{s} $$

$$ \hat{P} $$

$$ R\subseteq\hat{R} $$

$$ \mathrm{f{e e e}}) $$

$$ \hat{\mathbf{T}} $$

$$ r_{i} $$

$$ \hat{P} $$

$$ \ R|+|\hat{R}|)big, $$

$$ 2^{-s} $$

$$ R=\emptyset $$

$$ |\ddot{R}|=\beta s $$

$$ \beta=1/(\log_{2}3-1, $$

$$ \hat{P} $$

$$ \beta s $$

$$ \beta s<\mathsf{d i s t}(\mathsf{C}^{*2})\leq\mathsf{d i s t}(\tilde{\mathsf{C}}) $$

$$ \mathbf{X}=\hat{\mathbf{A}} $$

C (where the notation A^Rmeans the submatrix of A consisting of all rows except those indexed by R). Hence ~ ) _m^. Since these are in total less than dist(C) coordinates, A belongs to (C except for the rows in R and R the simulator can now erasure-correct each column and input that as messages to F^MHCOM.

$$ \mathrm{C}{R}=\mathrm{A}{R} $$

$$ \mathbf{\tilde{C}}=\left(\begin{matrix}{\mathbf{C}}\ {\mathbf{\tilde{C}}}\end{matrix}\right),\in,(\mathbf{\tilde{C}})^{\odot m} $$

$$ \hat{\mathbf{C}}{\hat{R}}=\hat{\mathbf{A}}{\hat{R}} $$

$$ \mathbf{A}_{R} $$

$$ (\tilde{\mathsf{C}})^{\odot m} $$

$$ \mathcal{F}_{\mathrm{M H C O M}} $$

In order to open a commitment to a dierent message and avoid that the verier aborts, P^ would need to modify additional positions Q and Q^, respectively in the matrices A and A^ where Q is disjoint with R and Q^ is disjoint with Q^ so that in total jRj + jQj + jR^j + jQ^j dist(C) = s since P^ needs to reveal a codeword in C. P^ can guess correctly the selections of the choices of the verier in the new sets with probability jQj jQnQj ^ (1*=3) (2=*3). Under these conditions, and similarly to what is mentioned above the probability that s the protocol does not abort either because of the choices of the R’s or of the Q’s is at mo^st 2.

$$ \hat{P} $$

$$ Q $$

$$ \hat{\mathbf A} $$

$$ \hat{Q} $$

$$ Q $$

$$ \hat{Q} $$

$$ \hat{\mathfrak Q{}} $$

$$ | R | + | Q | + | \hat {R} | + | \hat {Q} | \geq \operatorname {d i s t} (\tilde {\mathrm {C}}) = \beta s $$

$$ \hat{P} $$

$$ \tilde{c},\ \hat{P} $$

$$ (1/3)^{|Q|}(2/3)^{|\hat{Q}\setminus Q|} $$

$$ 2^{-s} $$

$$ Q^{\prime}\mathrm{S} $$

Finally we need to prove that, given two committed values (indexed by i, j), P^ cannot fool S by creating P a third commitment that it claims to contain the product of the two committed values, but which it can open to a dierent message.

$$ \ {\mathcal{S}}_{P} $$

Let w, l = 0*;* 1*;2, be the vectors created from the matrices A and A^ as in the Protocol. l l l ^MHCOM Remember that P^ may have cheated in positions R, R^ of the matrices A and A^ respectively and that we were assuming that R R^ (since this is in P^’s advantage). Let w = w₀ + w₁ + w₂. Note that w 2 C. _{R^ ^2} R ^ can now choose to announce some arbitrary vectors0l 0r P w. However, if wi[i] 6= w_ri[i], then the protocol will abort. This is because the verier can compute w [_i] f_rom A, A, A^. Let M the set of positions ri ri ri+1 ri ^ where2 2 outside R w 6= w⁰. The verier will abort if w⁰ 2= C. Si*nce w_^2 C_^, if the verier does not abort R R

$$ w_{l},,l=0,1,2 $$

$$ \hat{\mathbf{A}}_{l} $$

$$ \mathbf{A}_{l} $$

$$ \mathit{\Pi}_{\mathrm{M H C O M}} $$

$$ R\subseteq\hat{R} $$

$$ w=w_{0}+w_{1}+w_{2} $$

$$ \hat{P}^{\ }\mathrm{s} $$

$$ \hat{P} $$

$$ w_{\hat{R}}\in\mathsf{C}_{\hat{R}}^{*2} $$

$$ w^{\prime}l $$

$$ \boldsymbol {w} ^ {\prime} _ {r _ {i}} [ i ] \neq \boldsymbol {w} _ {r _ {i}} [ i ] $$

$$ w w_{r_{i}}[i] $$

$$ \mathbf {A} _ {r _ {i}}, \mathbf {A} _ {r _ {i + 1}}, \hat {\mathbf {A}} _ {r _ {i}} $$

$$ \hat{R} $$

$$ w\neq w^{\prime} $$

$$ w^{\prime}\notin\mathbb{C}^{*2} $$

$$ \ {\hat{R}}\in\hat{\mathbb{C}}^{*2}{}{\hat{R}} $$

^ ^ has not cheated) or ^2 either jR [ M j = 0 (i.e. P jR [ M j dist(C) > s. So the protocol has not aborted at this point if P^ has been able to guess, for every i 2 R^ [ M, a pair of indices fa;bgf0*;* 1*;* 2g such that ^2 s s r_i2fa;bg and jR [ M j dist(C). This occurs with probability smaller than (2*=*3) = 2.

$$ \big|\hat{R}\cup M\big|\geq\sf{s i s t}(C^{*2})>\beta s. $$

$$ |\hat{R}\cup M|=0;(\mathrm{i.e.};\hat{P} $$

$$ \hat{P} $$

$$ i\in\dot{R}\cup M $$

$$ {a,b}\subseteq{0,1,2} $$

$$ r_{i}\in\left{a,b\right} $$

$$ |\hat{R}\cup M|\geq\mathsf{d i s t}(\mathsf{C}^{*2}) $$

$$ (2/3)^{\beta s}=2^{-s} $$

In case the adversary V^ corrupts all receivers in V, the simulator S rst runs the commit phase and the V computation steps of^MHCOMas an honest P and then equivocates these commitments when it receives the actual messages from F. This is possible for two reasons, rst V^ has no information at all about the MHCOM committed messages before the opening phase. This is true because: 1) the matrices W and W c broadcasted during the commit phase (if adjusted by R₂ and Rb₂, respectively) represent one out of three additive shares of the components of the codewords encoding the committed messages and therefore they trivially contains no information, 2) the matrix P~ and the columns of A~ used in the multiplication steps are never revealed; hence the matrices T~ for i 2f0*;* 1*;* 2g from the commit phase and the triples from the multiplication step i (i.e. one triple (w₀; w₁; w₂) for each multiplication) contains no information (i.e., they are additive share of values that don’t contain information).

$$ \hat{V} $$

$$ \mathcal{S}_{V} $$

$$ \mathcal{F}_{\mathrm{M H C O M}} $$

$$ \mathbf{R}_{2} $$

$$ {\hat{\bf R}}_{2} $$

$$ \tilde{\mathbf P} $$

$$ \tilde{\mathbf{T}}_{i} $$

$$ \tilde{\mathbf A} $$

$$ i,\in,0,1,2} $$

$$ (w_{0},w_{1},w_{2}) $$

Second, V^ learns the vector r by emulating F and therefore it knows the index of the shares that COM are checked by V^ in the opening phase. This implies that in order to equivocate a commitment, S simply _V needs to modify the share not checked by V^ before broadcasting them at the beginning of the opening phase. In more detail, for any j 2 fssid₁;:::;ssid_og upon receiving m_jfrom F_MHCOMas opening of the 0r commitment associated with the index j, S_Vdenes A_[i]+2[;j] = C(m_j) A_r[i]+1[;j] A_r[i][;j] and ^0r A_[i]+l[;j] = A_r[i]+l[;j] for l 2 f0*;* 1g (where A_i[;j] are the ones constructed for the commit phases executed by V^). Now, V^ broadcasts (sid;ssid; A⁰ [;j];A⁰ [;j];A⁰ [;j]) and outputs the same value as V^. 0 1 2 This guarantees that the joint distribution of the ideal execution with simulator S_Vis computationally indistinguishable from the real execution of with receivers controlled by V^. AHCOM

$$ \hat{V} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathcal{S}_{V} $$

$$ j\in{s s i d_{1},\ldots,s s i d_{o}} $$

$$ m_{j} $$

$$ \mathcal{F}_{\mathrm{M}} $$

$$ \mathbf{A^{\prime}}{\mathbf{r}[i]+2}[\cdot,j]:=:\mathbf{\hat{C}(m mathbf{}mathit{m}{j})}-\mathbf{A}{\mathbf{r}[i]+1}[\cdot,j]:\-{\mathbf{A}{\mathbf{r}[i]}}[\cdot,j] $$

$$ j,,S_{V} $$

$$ {\bf{A}}^{\prime}{}{r[i]+l}[\cdot,j],=,{\bf{A}}{r[i]+l}[\cdot,j] $$

$$ l\ \in\ {0,1} $$

$$ \mathbf{A}_{i}[\cdot,j] $$

$$ \hat{V} $$

$$ \hat {V}. $$

$$ \mathsf{A_{0}^{\prime}}[\cdot,j],\mathsf{A_{1}^{\prime}}[\cdot,j],\mathsf{A_{2}^{\prime}}[\cdot,j]) $$

$$ \mathcal{S}_{V} $$

$$ \mathit{\Pi}_{\mathrm{A H C O N}} $$

$$ \hat{V} $$

Appendix F Publicly Veriable Multi-Receiver Additively Homomorphic Commitments

The functionality for publicly veriable additively homomorphic commitments F_PVHCOMused in the Insured MPC protocol of Baum et al. [4] is described in Figure 14.

$$ \mathcal{F}_{\mathrm{P V H C O M}} $$

| Functionality $ \mathcal{F}{\mathrm{PVHCOM}} $ interacts with a sender $ P $ ,a set of receivers $ V=\left{V{1},\ldots,V_{m}\right} $ ,a set of external verifiers $ U $ ,and an adversary $ S $ and proceeds as follows:

• Commit Phase: As in $ \mathcal{F}_{\mathrm{AHCOM}} $
• Addition: As in $ \mathcal{F}_{\mathrm{AHCOM}} $
• Open Phase: As in $ \mathcal{F}_{\mathrm{AHCOM}} $
• Public Verification: Upon receiving a message (verify, sid, ssid,P,V,m) from $ U_{i}\in U $ ,if a tuple(ssid,P,V,m) was previously recorded and revealed,then send (verified,sid,ssid,P,V,m) to $ U_{i} $
• Register External Verifier: Upon receiving (register) from $ U_{i} $ ,set $ U=U\cup U_{i} $ and return (registered) to $ U_{i} $
• Deregister External Verifier: Upon receiving (deregister) from $ U_{i} $ ,set $ U=U\backslash U_{i} $ and return (deregistered) to $ U_{i} $
• Check Registration: Upon receiving(is-registered)from $ U_{i} $ ,return(is-registered,b)to $ U_{i} $ ,where b=1 if $ U_{i}\in U $ and b=0 otherwise.

• Get Registred: Upon receiving(get-registered)from the ideal adversary $ S $ ,the functionality returns(get-registered,U)to $ S $ .

$$ P, $$

$$ V=\left{V_{1},\ldots,V_{m}\right} $$

$$ U_{i}\ \in\ U $$

$$ (s s i d,P,V,m) $$

$$ {\cal{U}}_{i}. $$

$$ U _ {i}, $$

$$ U=U\cup U_{i} $$

$$ {\cal{U}}_{i}. $$

$$ U_{i}, $$

$$ {\cal{U}}_{i}. $$

$$ U=U\backslash U_{i} $$

$$ U_{i}\in U $$

$$ (\mathsf{i s-r e g i s t e r e d}) $$

$$ U\mathrm,.. $$

$$ \ {cal U_{{i}}}, $$

$$ {\cal{S}}, $$

Fig. 14. Functionality FPVHCOM

Appendix G Applications to Ecient Zero-Knowledge Arguments

In this section, we show how to use a variant of the homomorphic commitments constructed in Section 3 and 4 to compile a certain class of public coin interactive proof system into public coin honest-verier zero-knowledge proof systems. Using the Fiat-Shamir heuristic, we can convert such a zero-knowledge proof system into a non-interactive zero-knowledge proof system. As an application, we can improve a recent construction of zkSNARKs [32] in a certain parameter regime. Specically, the zkSNARK construction of [32] uses additively homomorphic vector commitments¹⁵ to transform a public coin interactive proof system into a zero-knowledge protocol. The commitments in [32] are instantiated using number-theoretic assumptions. The construction of [32] is general enough that it can be instantiated with homomorphic commitment schemes with some additional properties. We remark though that [32] utilizes an additional optimization which relies on compressing homomorphic commitments, which is not available in our setting.

The notion of interactive proof system we focus on will be resettably sound public coin interactive proofs with algebraic verier. Such a proof system proceeds in t rounds, where in each round i the prover sends a message p_i, upon which the verier answers with a uniformly random message v_i. We require all the messages p_iand v_ito be vectors over a eld F. After the conversation is over, the verier evaluates a system of low degree polynomials F₁;:::;F_sin the p_iand v_iand accepts if all F_ievaluate to 0, otherwise it rejects. At the heart of this kind of protocol is the sum-check protocol, which lets a prover prove statements of the form P _x2f0;1gn P (x) = L, where P 2 F[X₁;:::;X_n] is a low-degree polynomial and L 2 F.

$$ p_{i} $$

$$ v{}i $$

$$ p_{i} $$

$$ \mathbb{F} $$

$$ v_{i} $$

$$ F_{1},\ldots,F_{s} $$

$$ p_{i} $$

$$ v_{i} $$

$$ F_{i} $$

$$ 0{,} $$

$$ \textstyle{\sum_{x\in{0,1}^{n}}P(x)=L} $$

$$ L\in\mathbb{F} $$

$$ P\in\mathbb{F}[X_{1},\ldots,X_{n}] $$

$$ F_{1},\ldots,F_{s} $$

$$ F_{1},\ldots,F_{s} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

Let (P*;V) be a t-round public coins interactive proof system for a language L with verication equations F₁;:::;F_ssuch that the equations F_i(x;p₁;:::;p_t;v₁;:::;v*_t) are ane in (p₁;:::;p_t). In our construction, we will use protocol_AHCOMwith several modications.

$$ (\mathsf{P},\mathsf{V}) $$

$$ \mathcal{C} $$

$$ F_{1},\ldots,F_{s} $$

$$ F_{i}(x,p_{1},\ldots,p_{t},v_{1},\ldots,v_{t}) $$

$$ (p_{1},\ldots,p_{t}) $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

{ We will only consider a single verier V

{ While the scheme_AHCOMin section 3 supports to committing to vectors over F₂ and supports additions (i.e. F₂-linear operations), we can modify the scheme such that we can commit to vectors over F for a large nite eld F while supporting F-linear operations. The resulting scheme does not have linear complexity but still achieves quasi-linear complexity and rate 1.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathbb{F}_{2}^{\lambda} $$

$$ \mathbb{F}_{2^{-}}\mathrm{l i n e a r} $$

$$ \mathbb{F}^{\lambda} $$

$$ \mathbb{F} $$

$$ \mathbb{F}- $$

{ Moreover, the commitment scheme_AHCOMin section 3 produces commitments to random vectors. Given such a commitment to a random vector, we can derandomize the components of the vector sequentially. I.e. we treat a commitment to a vector of random elements as a vector of commitments to random elements.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

¹⁵ In [32] they are referred to as multi-commitments

Thus each component of the vector can serve as an individual commitment which can individually be changed to a commitment of a concrete value.

{ In step 1 of the commitment phase of Protocol_AHCOM(Figure 4 and Figure 5) the prover P commits to 2n random seeds s_i;jfor i 2 [f1*;:::;ng*] and j 2f0*;* 1g using a UC-commitment F_COM. This is done to make the commitment scheme_AHCOMextractable. For the context of the current application, it is sucient to downgrade this to a non-interactive commitment scheme Commit which is perfectly binding and computationally hiding. Such a commitment scheme can be constructed e.g. from an injective one-way function.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ s_{i,j} $$

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

$$ j \in {0, 1 } $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

{ In step 2 of the commitment phase of_AHCOMthe verier commits to a challenge r⁰ using a UCcommitment F_COM. This step in necessary to make the commitment scheme_AHCOMequivocal. In the context of the current application, we only need to achieve honest-verier ZK in order to apply the Fiat- Shamir heuristic. Consequently, we can drop this commitment step and have the verier send r⁰ in the clear after the end of the commitment phase.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ r^{\prime} $$

$$ \mathcal{F}_{\mathrm{C O M}} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ r^{\prime} $$

The protocol_HVZKis provided in Figure 15. We can also instantiate_HVZKwith the commitment protocol MHCOM(Section 4) and allow the verication equations F₁;:::;Fkto be low degree polynomials in the pi rather than just linear, which however comes at the expense of a worse rate (i.e. constant rate instead of rate 1).

$$ \ mathit Pi!{{}}_{H V Z K} $$

$$ \ mathit Pi!{!{}}_{H V Z K} $$

$$ F_{1},\ldots,F_{k} $$

Protocol HVZK

$$ p_{i} $$

1. Prover P: On input a statement x and a witness w, let m be a polynomial upper bound on the number of eld elements in F that P sends in the interaction with V upon input (x;w). P runs the setup step of the commitment protocol AHCOM to pre-compute for m F-vector commitments of length n. We assume that component-commitments are used in such that verication equations waste a minimal number of commitments.

$$ \mathbb{F} $$

$$ (x,w) $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

2.Prover P and Verier V run the following interaction for i = 1*;:::;t*:

$$ i=1,\ldots,t\colon $$

{ P computes pi P(x;w;i;v₁;:::;vi 1) and computes a commitment p^i on pi using the modied AHCOM.

$$ p_{i},\leftarrow,{\sf P}(x,w,i,v_{1},\ldots,v_{i-1}) $$

$$ \hat{p}_{i} $$

$$ p_{i} $$

{ Upon receiving ^pi, the verier V chooses a uniformly random value vi and sends it to P.

$$ v_{i} $$

$$ \hat{p}_{i} $$

3. P now provides a proof to V that the verication equations Fi(x; p^1*;:::; p*^t;v₁;:::;vt) = 0 for i = 1*;:::;s* hold using the additively homomorphic property of AHCOM.

$$ i=1,\ldots,s $$

$$ F_{i}(x,{\hat{p}}{1},\ldots,{\hat{p}}{t},v_{1},\ldots,v_{t})=0 $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

4. P and V now run the consistency check/opening phase of AHCOM. As described above, for this consistency check V uses fresh random coins. If the consistency check passes, V outputs 1, otherwise 0.

Fig. 15. Protocol HVZK

Completeness of the protocol_HVZKfollows immediately from the completeness of (P*;V). We will briey argue why the protocol is sound and honest-verier zero-knowledge. First, we will sketch how we can establish soundness of_HVZKgiven that (P;V) is sound. First notice that the commitment scheme_AHCOMis statistically binding, as the underlying commitment scheme Commit is also statistically binding. Therefore, the prover messages (^p₁;:::; p^_t) commit uniquely to messages (p₁;:::;p_t). Moreover, the proofs for homomorphic relations are also statistically sound. Thus, if the verier accepts, it must hold that F_i(x;p₁;:::;p_t;v₁;:::;v*_t) = 0 for i = 1*;:::;s*. But by the soundness of (P*;*V) this means that x is in the language L, except with negligible probability over the random coins of V.

$$ \mathit{\Pi}_{H V Z K} $$

$$ (\mathsf{P},\mathsf{V}) $$

$$ \ mathit Pi $$

$$ (\mathsf{P},\mathsf{V}) $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ (p_{1},\ldots,p_{t}) $$

$$ (\hat{p}{1},\ldots,\hat{p}{t}) $$

$$ F_{i}(x,p_{1},\ldots,p_{t},v_{1},\ldots,v_{t})=0 $$

$$ i=1,\ldots,s $$

Notice further that if (P*;*V) is resettably sound, then so is_HVZK, as the opening phase of_AHCOMhas only a negligible soundness error.

$$ \mathit{\Pi}_{H V Z K} $$

$$ (\mathsf{P},\mathsf{V}) $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

To see why the protocol is honest-verier zero-knowledge, notice that the commitment scheme_AHCOM becomes equivocal if the prover knows the challenge r⁰ of the verier before the start of the protocol, see the construction of simulator S_Vin Figure 13 in Appendix D. The simulator for_HVZKcan choose r⁰ and

$$ r^{\prime} $$

$$ \mathcal{S}_{V} $$

$$ \mathit{\Pi}_{H V Z K} $$

$$ r^{\prime} $$ setup_AHCOMto be equivocal. In the simulated proof it sets the ^p_ifake commitments. During the opening phase, it opens the commitments to fake values (just as S_V).

$$ \hat{p}_{i} $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ \ _{V}) $$

Instantiation We will now discuss instantiating the hyrax protocol of [32] with the modied version of the commitment scheme_AHCOM.

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

$$ d, $$

$$ (G) + \sqrt {| w |}) $$

$$ O!({\sqrt{|w|}}+d\cdot\log(G))! $$

$$ \mathit{\Pi}_{\mathrm{A H C O M}} $$

One of the key ideas in the hyrax protocol is to reduce all algebraic relations between commitments to linear relations between vector commitments. In this way, general algebraic relations can be proven using a protocol which just supports linear relations between vectors. This transformation only incurs a small constant factor additional overhead. Omitting details, there are three main steps. In the rst step reduce multiplicative relations to linear relations, in the second step show that many linear relations can be compressed into a single linear relation, and in. the third step step reduce linear relations between commitments to linear relations between vector commitments. All three steps are implemented using a Schnorr-style protocol. In [32] these transformations are provided for the concrete case of DLOG-based commitments, but these ideas can be implemented using arbitrary homomorphic vector commitments. We will briey outline the main ideas.

From quadratic relations to linear relations Assume that given 3 commitments c₁ = com(x), c₂ = com(y) and c₃ = com(x y) the prover wants to convince the verier that c₃ commits to the product of the values committed to in c₁ and c₂. This can be achieved via the following protocol. First the prover computes 2 new commitments c⁰₂= com(r) and c⁰₃= com(r x) and sends the commitments to the verier. The verier $ responds with a uniformly random eld element F. In the last step, the prover send a value z = r + y to the verier and proves the following 2 relations using the homomorphic property of the commitment scheme.

$$ c_{3}={\mathsf{c o m}}(x\cdot y) $$

$$ c _ {1} = \operatorname {c o m} (x), c _ {2} = \operatorname {c o m} (y) $$

$$ c_{2} $$

$$ c_{3} $$

$$ c_{1} $$

$$ c_{2}^{\prime}=\mathsf{c o m}(r) $$

$$ c_{3}^{\prime}={\mathsf{c o m}}(r\cdot x) $$

$$ z=r!+!\gamma!\cdot!y $$

$$ \gamma\stackrel{\mathfrak{S}}{\longleftarrow}\mathbb{F} $$

$$ c_{2}^{\prime}+\gamma\cdot c_{2} $$

$$ 2.\ c_{3}^{l}+\gamma\cdot c_{3}-z\cdot c_{1}\ \mathrm{p e n s\ t0}\ 0 $$

Correctness of the protocol follows routinely and and honest-verier ZK can be established using equivocality of the commitments. To see that the protocol is sound, assume that c₃ commits to a value dierent from x y, say x y + t for a t 6= 0 and that c⁰₃contains a value r⁰. Note that the rst check enforces that z = r + y. Now the second check passes if and only if

$$ x\cdot y $$

$$ c_{3} $$

$$ x\cdot y+t $$

$$ t\neq0 $$

$$ c_{3}^{\prime} $$

$$ r^{\prime} $$

$$ z=r+\gamma y. $$

$$ \begin{aligned}{}&{{}r^{\prime}+\gamma(x y+t)-(r+\gamma y)\cdot x=0}\ {\Leftrightarrow}&{{}r^{\prime}-r\cdot x+\gamma t=0.}\ \end{aligned} $$

Noting that r⁰;r;x;t were xed before and is uniformly random in F, we get that since t 6= 0 it holds by the Schwartz-Zippel Lemma that this check is passed with probability at most 1*=jFj*. Consequently the protocol is sound.

$$ r^{\prime},r,x,t $$

$$ \mathbb{F}, $$

$$ t\neq0 $$

$$ \gamma $$

$$ 1/|\mathbb{F}| $$

From many linear relations to a single linear relation Assume that for m commitments c_i= com(x_i) we want k m k to show that A x = y, where x = (x_i)_iand A 2 F and y 2 F. Consider the following protocol. The $k verier chooses a random v F and sendsPv to the prover. The prover now uses the linear homomorphic m > > property of the commitment to prove that_i=1w_ico^m(x_i) opens to z, where w = v A and z = v y.

$$ c_{i}=\mathsf{c o m}(x_{i}) $$

$$ \mathbf{A}\cdot\pmb{{}}\pm{b}x=\pmb{y}. $$

$$ \mathbf{A}\in\mathbb{R}^{k\times m} $$

$$ x=(x_{i}). $$

$$ \ boldsymbol y inin\mathbb{F}^{k} $$

$$ \boldsymbol{v}\xleftarrow{\mathfrak{S}}\mathbb{F}^{k} $$

$$ \textstyle\sum_{i=1}^{m}w_{i}\cdot\mathsf{c o m}(x_{i}) $$

$$ z $$

$$ \pm\ b{v}^\top\cdot\mathbf{A} $$

$$ z=\ \ {pm{pm v v}}\cdot{\pmb y}. $$

Correctness and honest verier ZK follow immediately. To show soundness, note that if y = A x + t for a t 6= 0, then it holds that

$$ \ {boldsymbol y=\mathbf{A}\cdot\ pm{\boldsymbol{x}}+t} $$

$$ t\neq0 $$

$$ \begin{array}{r l}&{^{v}\cdot\mathbf{A}\cdot x=v^{\top}\cdot(\mathbf{A}\cdot x+t)}\ {\Leftrightarrow}&{v^{\top}t=0}\end{array} $$

but by the Schwarz-Zippel Lemma this check is passed with probability at most 1*=jFj*. Consequently the protocol is sound.

$$ 1/|\mathbb{F}| $$

From linear relations to linear relations for vectors We will nally outline how to eciently prove a linear relation across all components for a set of vector commitments. Let ci= com(xi) for i = 1*;:::;m* where the Pm n ^> x 2 F are vectors. Now assume the prover wants to convince the verier that_i=1a_ix_i= y where the _n a_i2 F are vectors and y 2 F.

$$ c_{i}=\mathsf{c o m}(x_{i}) $$

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

$$ \ \boldsymbol{x}\in\mathbb{F}^{n} $$

$$ \textstyle{\sum_{i=1}^{m}a_{i}^{\top}x_{i}=y} $$

$$ \boldsymbol{a}_{i}\in\mathbb{F}^{n} $$

$$ y\in\mathbb{F} $$

0i > For i = 1*;:::;m* the prover computes commitments d_i= com(a_ix_i), c = com(r_i) and c⁰⁰_i= com(a_ir_i) $ and sends them to the verier. The verier responds with random eld element F. For every i the prover now computes z_i= r_i+ x_i, sends z_ito the verier and proves the following 3 relations using the homomorphic property of the commitment scheme.

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

$$ d_{i}={\mathfrak{c o m}}(a_{i}^{\top}x_{i}),c_i{{}}{\ =\mathfrak{c o m}}(r_{i}) $$

$$ c_{i}^{\prime\prime}={\mathsf{c o m}}(a_{i}^{\top}r_{i}) $$

$$ z_{i}=r_{i}+\gamma\cdot x_{i} $$

$$ \gamma \leftarrow^ {$} \mathbb {F} $$

$$ z_{i} $$

0i 1.For all i = 1*;:::;m c* + c_iunveils to zi

$$ i=1,\ldots,m;c_{i}^{\prime}+\gamma c_{i} $$

$$ z_{i} $$

2.For all i = 1*;:::;m c⁰⁰*i+ diunveils to a_iz. P

$$ i=1,\ldots,m;c_{i}^{\prime\prime}+\gamma d_{i} $$

$$ a{}_{i}^{\top}\cdot z} $$

_m 3._i=1d_iunveils to y

$$ \textstyle\sum_{i=1}^{m}d_{i} $$

Again, correctness of the protocol follows routinely and and honest-verier ZK can be established using equivocality of the commitments.

To see that the protocol is sound, assume that for some i it holds that dⁱdoes not commit to aⁱx_i, i.e.

assume that d_icommits to a_ix_i+ t_i, where one of the t_iis non-zero. The rst check above ensures that z_i= r_i+ x_i. Assume that c⁰⁰_icommits to a value u_i. Now the second check passes if and only if

$$ d_{i} $$

$$ a{{i}^{\top}x}{{i}} $$

$$ a_{i}^{\ |}\ {\bf x}{i}+t{i}. $$

$$ t_{i} $$

$$ z_{i}=r_{i}+\gamma\cdot x_{i} $$

$$ c_{i}^{\prime\prime} $$

$$ u_{i} $$

$$ \begin{aligned}{}&{{}u_{i}+\gamma\cdot(\mathbf{a}{i}^{\top}\mathbf{x}{i}+t_{i})=\mathbf{a}{i}^{\top}(\mathbf{r}{i}+\gamma\cdot\mathbf{x}{i})}\ {\Leftrightarrow}&{{}\gamma\cdot t{i}+u_{i}-\mathbf{a}{i}^{\top}\mathbf{r}{i}=0.}\ \end{aligned} $$

Note again that t_i, u_iand r_iare xed before is chosen and therefore independent of. Consequently, if t_i6= 0 by the Schwartz-Zippel Lemma this check is passed with probability at most 1*=jFj* and we conclude that the protocol is sound.

$$ t_{i},\ u_{i} $$

$$ r_{i} $$

$$ \gamma $$

$$ t_{i}\neq0 $$

$$ \gamma $$

$$ 1/|\mathbb{F}| $$

As before these protocols can be made non-interactive via the Fiat-Shamir transform. Moreover, both protocols only need a small constant number of additional commitments. Consequently, when instantiating the protocol of [32] with our commitment scheme accounting for these modications we get a scheme with proof size O((dlog(G) + jwj) jFj +), where the additive overhead of is due to the setup. The verier runtime is O(jwj + d log(G)) whereas the prover runtime is still linear in the size of the circuit C.

$$ O((d\log(G)+|w|)\cdot|\mathbb{F}|+\kappa) $$

$$ O(|w|+d\cdot\log(G)) $$

As mentioned before, the main improvement of our protocol over [32] is that we only rely on simple private key primitives. On the turn side, our vector-commitments are not compressing, which leads to the p proof-size to depend linearly on the witness-size jwj instead of jwj. However, the proof size does not depend multiplicatively on the computational security parameter, but rather on jFj, which is a statistical security parameter an can therefore be chosen much smaller. Consequently, we get an advantage in terms of proof-size whenever the proof-size is dominated by d rather than jwj.

$$ C. $$

$$ \sqrt{|w|} $$

$$ \ \kappa $$

$$ |\mathrm{F}| $$

$$ |w| $$