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

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

<sup>1</sup>
IMDEA Software Institute, Madrid, Spain, ignacio.cascudo@imdea.org

<sup>2</sup>
Aarhus University, Aarhus, Denmark, ivan@cs.au.dk

<sup>3</sup>
IT University of Copenhagen, Copenhagen, Denmark, bernardo@bmdavid.com

<sup>4</sup>
CISPA Helmholtz Center for Information Security, Saarbrucken, Germany, nico.doettling@gmail.com
<sup>5</sup>
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.

<sup>y</sup>
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).

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

<sup>x</sup>
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
<sup>8</sup>
not OT). Notably, however, this commitment scheme does not need to be homomorphic, and in fact it does

<sup>7</sup>
All this holds in an amortized sense, assuming we make enough commitments so that the cost of the setup phase
is dwarfed.

<sup>8</sup>
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*<sub>i;j</sub>for 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*<sub>i;</sub><sub>0</sub>or *s*<sub>i;</sub><sub>1</sub>to 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*<sub>i;</sub><sub>0</sub>or *s*<sub>i;</sub><sub>1</sub>
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,\ }
$$

<sup>9</sup>
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*] = *f*1*;* 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<sub>q</sub>for
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<sup>n</sup> *a b 2* F
a<sup>n</sup>d (*a b*)[*i*] = *a*[*i*]*b*[*i*]. If *A* [*n*], we will use<sub>A</sub>to 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 f*1*;:::;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*<sub>s</sub>*Y*, if for all *z* it holds
that *j* Pr[*D*(*X*<sub>;z</sub>) = 1] Pr[*D*(*Y*<sub>;z</sub>) = 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<sub>c</sub>.

$$
\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<sup>n</sup>ote the Hamming-weight of *x* by *kxk₀* = *jfi 2* [*n*] : *x*[*i*] 6= 0*gj*. Let C F be a
<sup>n</sup>
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<sup>n</sup>d its relative minimum dista<sub>n</sub>ce is.
<sup>n</sup> 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<sup>n</sup>erator matrix of C if C = *f*G*x* : *x 2* F *g*, and we write C(*x*) = G*x*. 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 <sup>m</sup>
C = *f*C *2* F : *8i 2* [*m*] : C[*;i*] *2* C*g*. In other words, C consists of all F <sup>m</sup>atrices 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 <sup>m</sup>atrix E *2* F, *k*E*k₀* is the number of nonzero rows of E, and the code C
<sup>m</sup>
has minimum distance at least *d⁰* if all nonzero C *2* C satisfy *k*C*k₀ 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* an*d 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<sup>m</sup> F to F), and we apply this to
n m n ‘
each of the rows of a matrix X *2* F, obtai<sup>n</sup>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 <sup>n</sup>
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 j*F *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 j*F*j-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 j*F*j 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<sup>s</sup><sup>t</sup>ance 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.
$$

<sup>10</sup>
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 j*F*j-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*<sub>l</sub>*;:::x*<sub>l</sub><sub>+</sub><sub>n</sub>) *is such that the x₁;:::;x*<sub>l</sub>*are independently uniform and x*<sub>l</sub><sub>+1</sub>*;:::;x*<sub>l</sub><sub>+</sub><sub>n</sub>*are*
*independent of x₁;:::;x*<sub>l</sub>*, 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}}
$$

| Functionality $ \mathcal{F}_{\mathrm{COM}} $ is parameterized by commitment length $\lambda$. $ \mathcal{F}_{\mathrm{COM}} $ interacts with a sender $ P $ ,a set of receivers $ V=\left\{V_{1},\ldots,V_{t}\right\} $ and an adversary $ S $ and proceeds as follows： |
| --- |
| -Commit Phase: Upon receiving a message (commit, sid, ssid,P,V,m) from $ P $ where $ m\in\left\{0,1\right\}^{\lambda} $ ，record the tuple(ssid,P,V,m)和 send(receipt,sid,ssid,P,V)to every receiver $ V_{i}\in V $和S. Ignore subsequentcommit messages with the samessid。 |
| -Open Phase: Upon receiving a message (reveal,sid,ssid)from $ P $ ,if a tuple(ssid,P,V,m)was previously recorded，then send(reveal,sid,ssid,P,V,m)to every receiver $ V_{i}\in V $andS. Otherwise，ignore。 |

$$
\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 *F*COM.

$$
\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*<sub>COM</sub>-hybrid model [12,14], where the parties have access to an ideal (non-homomorphic)
commitment functionality (our constructions are described in the *F*<sub>COM</sub>-hybrid model for the sake of clarity,
but they actually only need the underlying commitments to be extractable). Functionality *F*<sub>COM</sub>is described
in Figure 1. Notice that we describe a version of *F*<sub>COM</sub>that operates with a set *V* of multiple receivers
instead of a single receiver. However, *F*<sub>COM</sub>can 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)
$$

| Functionality $ \mathcal{F}_{\mathrm{AHCOM}} $ |  |
| --- | --- |
| $ \mathcal{F}_{\mathrm{AHCOM}} $ interacts with a sender P,a set of receivers $ V=\left\{V_{1},\ldots,V_{t}\right\} $ and an adversary S and proceeds as follows: |  |
| -Commit Phase: | The length of the committed messages $\lambda$ is fixed and known to all parties. |
| -If P is honest, upon receiving a message commit sid,ssid,P,V) from P,sample a random m $ \leftarrow\left\{0,1\right\}^{\lambda} $ record the tuple (ssid,P,V,m), send the message commit sid,ssid,P,V,m) to Pand send the message receive, sid,ssid,P,V) to every receiver $ V_{i}\in V $ and S.Ignore any futurecommit messages with the same ssidfrom Pto V. |  |
| -If P is corrupted, upon receiving a message commit, sid,ssid,P,V,m) from P,where m $ \in\left\{0,1\right\}^{\lambda} $ record the tuple(ssid,P,V,m) and send the message receive, sid,ssid,P,V) to every receiver $ V_{i}\in V $ and S.Ignore any futurecommit messages with the same ssidfrom Pto V. |  |
| -If a message abort, sid,ssid) is received from S,the functionality halts. |  |
| -Addition: Upon receiving a message add, sid,ssid1,ssid2,ssid3,P,V) from P:If tuples(ssid1,P,V,m1)(ssid2,P,V,m2) were previously recorded and ssid3is unused,record(ssid3,P,V,m1+m2)and send the message add, sid,ssid1,ssid2,ssid3,P,V,success) to P,every receiver $ V_{i}\in V $ and S. |  |
| -Open Phase: Upon receiving a message reveal, sid,ssid1,...,ssido) from P,for every ssid $ \in\left\{ssid_{1},\ldots,ssid_{o}\right\} $ if a tuple(ssid,P,V,m) was previously recorded,then send(reveal, sid,ssid,P,V,m) to every receiver $ V_{i}\in V $ and S,if not,send nothing.Finally,halt. |  |

$$
\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 *F*AHCOM

| 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 *F*MHCOM

$$
\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*<sub>AHCOM</sub>, described in Figure 2. Similarly to a functionality of [16], *F*<sub>AHCOM</sub>
augments the standard multiple commitments functionality *F*<sub>MCOM</sub>from [14] by introducing a command
for adding two previously stored commitments and an abort command in the Commit Phase. Moreover,
*F*<sub>AHCOM</sub>gives 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*<sub>AHCOM</sub>lets 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*<sub>MHCOM</sub>(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<sub>AHCOM</sub>realizes *F*<sub>AHCOM</sub>, 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*<sub>AHCOM</sub>is 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<sub>AHCOM</sub>achieves 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<sub>AHCOM</sub>is 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<sub>AHCOM</sub>run 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*<sub>AHCOM</sub>is 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*<sub>AHCOM</sub>is 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 <sup>0</sup>
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<sub>AHCOM</sub>’s security in the *F*<sub>COM</sub>-hybrid model, *i.e.* assuming
access to an ideal functionality for commitments. The proof of security for Protocol<sub>AHCOM</sub>is 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*<sub>COM</sub>instead 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*<sub>COM</sub>before 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<sub>AHCOM</sub>is 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*<sub>AHCOM</sub>*UC-realizes F*<sub>AHCOM</sub>*in the F*<sub>COM</sub>*-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*<sup>AHCOM</sup>*composed with F*<sub>COM</sub>*and A from S composed*
FCOM
*with F*<sub>AHCOM</sub>*. That is,* IDEAL<sub>F</sub><sub>AHCOM</sub><sub>;S;Z</sub> <sub>c</sub>HYBRID<sub>;A;Z</sub>*:*
<sub>AHCOM</sub>

$$
\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*<sub>P</sub>(Figure 12) or an adversary
who corrupts all receivers in *V* by constructing the simulator *S*<sub>V</sub>(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<sub>AHCOM</sub>) 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<sub>AHCOM</sub>. 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}}
$$

| Commitment Phase |  |
| --- | --- |
| 1. On input (commit, sid, ssid1, ..., ssidm, P, V), P proceeds as follows: |  |
| (a) For i ∈ [n] and j ∈ {0, 1}, sample sij←{0, 1}ℓ and send (commit, sid, ssidi,j, P,V,sij) to FCOM. |  |
| (b) Compute Rj[i,·] = PRG(sij,) and set R = R0 + R1 so that R0,R1 forms an additive secret sharing of R. |  |
| (c) Adjust the bottom n-k rows of R so that all columns are codewords in C by constructing a matrix W with dimensions as R and 0s in the top k rows, such that A := R+W ∈ C°m+l (recall that C is systematic). Set A0=R0,A1=R1+W and broadcast (sid,ssid1,...,ssidm,W) (only sending the bottom n-k = O(s) rows). |  |
| 2. Upon receiving all messages (receipt, sid, ssidi,j,P,V) from FCOM and (sid,ssid1,...,ssidm,W) from P, every receiver Vi ∈ V proceeds as follows: |  |
| (a) Sample ri←{0,1}n and ri←{0,1}ℓ and send (commit, sid,ssidVi,V&#x27;,ri) and (commit, sid,ssid&#x27;,Vi,V&#x27;,ri&#x27;) to FCOMa where V&#x27; = P ∪ V\Vi. |  |
| (b) Upon receiving (receipt, sid,ssidVj,V&#x27;) and (receipt, sid,ssid&#x27;,Vj,V&#x27;) from FCOM for all Vj ∈ V\Vi, send (reveal, sid,ssid&#x27;) to FCOM. |  |
| (c) Upon receiving (reveal, sid,ssid&#x27;,Vj,V&#x27;,rj&#x27;) from FCOM for all Vj ∈ V\Vi, set r&#x27; = r1&#x27; ⊕... ⊕rj&#x27;. |  |
| 3. Upon receiving (commit, sid,ssidVi,V&#x27;) and (reveal, sid,ssid&#x27;,Vj,V&#x27;,rj&#x27;) from FCOM for all Vj ∈ V, P proceeds as follows: |  |
| (a) Use r&#x27; = r1&#x27; ⊕... ⊕rj&#x27; as a seed for a random function H ∈ H (note that we identify the function with its matrix and all functions in H are linear). |  |
| (b) Set matrices P, P0 and P1 as the first l columns of A, A0 and A1, respectively, and remove these columns from A, A0 and A1. Renumber the remaining columns of A, A0 and A1 from 1 and associate each ssid(i) (commitment id from step 1) with a different column index in these matrices. Notice that P = P0 + P1. |  |
| (c) For i ∈ {0,1}, compute Ti = AiH + Pi and broadcast (sid,ssid1,...,ssidm,T0,T1). Note that AH + P = A0H + P0 + A1H + P1 = T0 + T1, and AH + P ∈ C°l. |  |

$$
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}
$$

<sup>a</sup>
We abuse notation and assume that each receiver *Vi* in AHCOM has access to an instance of *F*COM that
takes as message with the appropriate length where it acts as sender and where all other receivers plus sender *P*
<u>act as receivers.</u>

$$
\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 2f*0*;* 1*g* 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*<sup>i</sup>= *r*<sup>i</sup>*r*<sup>i0</sup>+ *r*<sup>i</sup>*r*<sup>i0</sup><sup>+1</sup>+ *r*<sup>i0</sup>*r*<sup>i</sup><sup>+1</sup>
(where sums in the indices are modulo 3) and note that all this information is contained in the *i*-th shares
<sup>0i</sup>
*s*<sub>i</sub>*;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
*F*COM and waits for (reveal*;sid;ssid;Vj;V; rj*) from *F*COM 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 *F*COM for all *Vj 2 V*, *P* sets *r* = *r₁ ::: rt*, sends
(reveal*;sid;ssid*i;r[i]) to *F*COM 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;ssid*i;r[i]*;P;V; s*i;r[i<sub>]</sub>) from *F*COM for *i 2* [*n*], every receiver *Vj 2 V* proceeds as
follows:
(a)Compute S[*i;*] = PRG(*s*<sub>i;r</sub><sub>[</sub><sub>i</sub><sub>]</sub>), 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<sub>r</sub><sub>[i]</sub>[*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
<u>(</u><u>sid;ssid</u>*j*<u>; ?</u><u>).</u>

$$
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*))<sub>i</sub>*;*(C(*b*))<sub>i</sub>the verier can determine the *j*-th share (in Add₃) of
2
(C(*a*) C(*b*))<sub>i</sub>, 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*<sub>i</sub>in prodcom(*y*)
as he does for com(*a*)*;*com(*b*)*;*com(*y*) (note that for com that means the additive shares indexed by *r*<sub>i</sub>and
*r*<sub>i</sub>+ 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*<sub>i</sub>-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 *f*0*;* 1*g* a<sup>n</sup>d additive splittings
n e
of them, will concatenate the two vectors and send correction information *z 2f*0*;* 1*g²* 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 2*n 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) <sup>2</sup> <sup>12</sup> <sup>2</sup>
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<sup>s</sup>t 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<sub>MHCOM</sub>is 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<sub>MHCOM</sub>simply sending *c* = *m a*,
where *a* =<sub>[</sub><sub>k</sub><sub>]</sub>(A[*;i*]) is one of the random message that the prover gets in the commit phase of<sub>MHCOM</sub>
(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<sub>MHCOM</sub>we 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}
$$

<sup>11</sup>
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)
$$

<sup>12</sup>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 <sup>k</sup>
(0*;* 0*;* 0*; c⁰*) where *c⁰* 6= 0. I<sup>n</sup>deed ta<sup>k</sup>e (0*; c⁰*) to be the encoding by C of a vector (0 *jjz*) for a nonzero
k0k
*z 2f*0*;* 1*g*

$$
\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 2*n 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 2*n* 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 2*n* bits), and then communicate all shares of a
related commitment with prodcom (the *w*<sub>i</sub>’s in the protocol), which amounts to 3*n* bits. So the communication
2
of this step is 5*n* 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 *f*C<sub>n</sub>*g* with constant rate (of C<sub>n</sub>) and constant relative minimum
2
distance of C<sub>n</sub>exist 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
25*k* bits per *k*-bit message we commit to, and 62*:* 5*k* 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<sub>MHCOM</sub>is similar to that of<sub>AHCOM</sub>. Indeed, the
following Theorem 4 can be proved by adapting the description of simulators *S*<sub>P</sub>and *S*<sub>V</sub>from 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*<sub>COM</sub>; upon receiving (mult*;sid;ssid₁;ssid₂;ssid₃;P;V;* success) from
*F*<sub>MHCOM</sub>, *S*<sub>V</sub>runs the steps of an honest *P* exactly as in<sub>MHCOM</sub>). 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*<sub>MHCOM</sub>*UC realizes F*<sub>MHCOM</sub>*in the F*<sub>COM</sub>*-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*<sup>MHCOM</sup>*composed with F*<sub>COM</sub>*and A from S composed*
FCOM
*with F*<sub>MHCOM</sub>*. That is,* IDEAL<sub>F</sub><sub>MHCOM</sub><sub>;S;Z</sub> <sub>c</sub>HYBRID<sub>;A;Z</sub>*:*
<sub>MHCOM</sub>

$$
\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]

<sup>13</sup>
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 : *f*0*;* 1*g! f*0*;* 1*g*. Let PRG : *f*0*;* 1*g! f*0*;* 1*g* be a
pseudorandom generator. Protocol MHCOM is run by a sender *P* and a set of receivers *V* = *fV₁;:::;Vtg*, who
interact with *F*COM as follows:

| where $\beta = 1 / (\log_{2}3-1)$ and $s$ is the statistical security parameter. Let $\tilde{C}$ be the code defined in (1). Let $\mathcal{H}$ be a family of linear almost universal hash functions $\mathbf{H}: \{0,1\}^{m}\rightarrow \{0,1\}^{l}$. Let PRG: $\{0,1\}^{\ell}\rightarrow \{0,1\}^{m+l}$ be a pseudorandom generator. Protocol $\Pi_{\mathrm{MHCOM}}$ is run by a sender $P$ and a set of receivers $V=\{V_{1},\dots,V_{t}\}$, who interact with $\mathcal{F}_{\mathrm{COM}}$ as follows: |  |
| --- | --- |
| Commitment Phase |  |
| 1. On input(commit,sid,ssid1,...,ssidm,P,V),P proceeds as follows: |  |
| (a) | For $i\in[n]$ and $j\in\{0,1,2\}$, sample $s_{i,j}\leftarrow \{0,1\}^{\ell},\hat{s}_{i,j}\leftarrow \{0,1\}^{\ell}$ and send(commit,sid,ssidij,P,V,si,j),(commit,sid,ssidij,P,V,\hat{s}_{i,j}) to $\mathcal{F}_{\mathrm{COM}}$. |
| (b) | Compute $\mathbf{R}_{j}[i,\cdot]=\mathrm{PRG}(\mathbf{s}_{i,j})$ and $\mathbf{R}_{j}[i,\cdot]=\mathrm{PRG}(\hat{\mathbf{s}}_{i,j})$ and set $\mathbf{R}=\mathbf{R}_{0}+\mathbf{R}_{1}+\mathbf{R}_{2}$ and $\hat{\mathbf{R}}=\hat{\mathbf{R}}_{0}+\hat{\mathbf{R}}_{1}+\hat{\mathbf{R}}_{2}$. |
| (c) | Adjust the bottom $n-k$ rows of $\mathbf{R}$ so that all columns are codewords in C by constructing a matrix W with dimensions as R and 0s in the top k rows, such that A:=R+W\in\mathbb{C}^{\circ m+l}$ (recall that C is systematic). Set A0=R0,A1=R1,A2=R2+W. |
| (d) | Adjust $\hat{\mathbf{R}}$ so that all columns are codewords in C$^{*2}$ and the first $k$ rows are the same as in A by constructing a matrix $\widehat{\mathbf{W}}$ with dimensions as $\widehat{\mathbf{R}}$ such that A:=R+W\in(\mathbb{C}^{*2})^{\circ m+l}$ and A[i,·]=A[i,·] for all i∈[k]. Set A0=R0,A1=R1,A2=R2+W and broadcast(sid,ssid1,...,ssidm,W,\widehat{\mathbf{W}})(sending the bottom n-k rows of W and the entire matrix $\widehat{\mathbf{W}}$). |
| 2. Upon receiving all(receipt,sid,ssidij,P,V) from $\mathcal{F}_{\mathrm{COM}}$ and(sid,ssid1,...,ssidm,W,\widehat{\mathbf{W}}) from P,every V_i\in V$ proceeds as follows: |  |
| (a) | Sample $r_{i}\leftarrow \mathbb{Z}_{3}^{n},r_{i}'\leftarrow \{0,1\}^{\ell}$ and send(commit,sid,ssidVi,V',r_{i})and(commit,sid,ssid'i,V_i,V',r_{i'})$ to $\mathcal{F}_{\mathrm{COM}}$, where V&#x27;=P∪V\setminus V_{i}. |
| (b) | and(c) as is the commit phase of $\Pi_{\mathrm{AHCOM}}$(Figure 4). |
| 3. Upon receiving(commit,sid,ssidVi,V',V') and(reveal,sid,ssid'i,V_j,V',r_{j'})$ from $\mathcal{F}_{\mathrm{COM}}$ for all V_j\in V,P$ proceeds as follows: |  |
| (a) | Use $r&#x27;=r_{1&#x27;}\oplus\cdots\oplus r_{t&#x27;}$ as a seed for a random function H∈H. |
| (b) | Define the matrices $\widetilde{\mathbf{A}}=\begin{pmatrix}\mathbf{A}\\ \mathbf{A}\end{pmatrix}$ and $\widetilde{\mathbf{A}}_{i}=\begin{pmatrix}\mathbf{A}_{i}\\ \mathbf{A}_{i}\end{pmatrix}$ for i∈{0,1,2}.Note that $\widetilde{\mathbf{A}}\in\mathbb{C}^{\circ m+l}$ and $\widetilde{\mathbf{A}}=\widetilde{\mathbf{A}}_{0}+\widetilde{\mathbf{A}}_{1}+\widetilde{\mathbf{A}}_{2}$.Set the matrices $\widetilde{\mathbf{P}}$ and $\widetilde{\mathbf{P}}_{i}$ as the first lcolumns of $\widetilde{\mathbf{A}}$ and $\widetilde{\mathbf{A}}_{i}$,respectively,and remove these columns from $\widetilde{\mathbf{A}},\widetilde{\mathbf{A}}_{i},\mathbf{A},\widetilde{\mathbf{A}}_{i},\widetilde{\mathbf{A}}_{i}$ for i∈{0,1,2}.Renumber the remaining columns from 1 and associate each commitment ssidi(commitment id from step 1)with a different column in these matrices.Notice that $\widetilde{\mathbf{P}}=\widetilde{\mathbf{P}}_{0}+\widetilde{\mathbf{P}}_{1}+\widetilde{\mathbf{P}}_{2}$. |
| (c) | For i∈{0,1,2},compute the matrix $\widetilde{\mathbf{T}}_{i}=\widetilde{\mathbf{A}}_{i}\mathbf{H}+\widetilde{\mathbf{P}}_{i}$ and broadcast(sid,ssid1,...,ssidm,T0,T1,T2).Note that $\widetilde{\mathbf{A}}H+\widetilde{\mathbf{P}}=\widetilde{\mathbf{A}}H+\widetilde{\mathbf{P}}\in\mathbb{C}^{\circ l}$. |

$$
\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

<sup>14</sup>
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 2f*0*;* 1*;* 2*g*, compute *vl*= A*l*[*;i*] A*l*[*;j*]+A*l*[*;i*] A*l*+1[*;j*]+A*l*+1[*;i*] A*l*[*;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 A*i*[*;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 f*1*;:::;kg* the *l*-th component of the newly appended column *i*n 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 *F*COM and waits for (reveal*;sid;ssid;Vj;V; rj*) from *F*COM for all *Vj 2 V n Vi*. *Vi* sets
n 0
*r* = *r₁* + + *rt* (where the sum is in Z3) a<sup>n</sup>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 *F*COM for all *Vj 2 V*, *P* sets *r* = *r₁* + *:::* + *rt*, sends
<u>(reveal</u><u>;sid;ssid</u><u>), (reveal</u><u>;sid;ssid</u><u>) and (reveal</u><u>;sid; ssid</u> <u>d) to</u> <u>F</u> for i = 1<u>;:::;n</u> <u>and halts.</u>
i;r[i] i;r[i]+1 i;r[i] <u>COM</u>

$$
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*<sub>i</sub>, upon which the verier answers with a uniformly random message *v*<sub>i</sub>. We require all the messages
*p*<sub>i</sub>and *v*<sub>i</sub>to be vectors over a eld F. After the conversation is over, the verier evaluates a system of low
degree polynomials *F₁;:::;F*<sub>s</sub>in the *p*<sub>i</sub>and *v*<sub>i</sub>and accepts if all *F*<sub>i</sub>evaluate 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
<sub>x2f</sub><sub>0</sub><sub>;</sub><sub>1</sub><sub>g</sub><sub>n</sub> *P* (*x*) = *L*, where *P 2* F[*X₁;:::;X*<sub>n</sub>] 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.

---

| Protocol $ \varPi_{\mathrm{MHCOM}} $ |  |
| --- | --- |
| Opening(Part 2) |  |
| 4. Upon receiving the messages (reveal, sid, ssid$ _{i,r[i]} $ ,P,V,$ s_{i,r[i]} $ ),(reveal, sid,ssid$ _{i,r[i]} $ +1,P,V,$ s_{i,r[i]} $ +1)and(reveal,sid,ssid$ _{i,r[i]} $ ,P,V,$ \widehat{s}_{i,r[i]} $ )from $ \mathcal{F}_{\mathrm{COM}} $ for $ i\in\{1,\dots,n\} $ every receiver $ V_{j}\in V $ proceeds as follows：(a)Compute $ S[i,\cdot]=\mathrm{PRG}(s_{i,r[i]}),S^{\prime}[i,\cdot]=\mathrm{PRG}(s_{i,r[i]+1}) $ and $ \widehat{S}[i,\cdot]=\pi_{\mu+l}(\mathrm{PRG}(\widehat{s}_{i,r[i]})) $ obtaining matrices $ S,S^{\prime} $ and $ \widehat{S} $ .Note for each $ i $ ，the $ i$-th row of $ S,S^{\prime},\widehat{S} $ will equal the $ i$-th row of $ R_{r[i]},R_{r[i]+1},\widehat{R}_{r[i]} $ respectively.Set $ B=\Delta W+S,B^{\prime}=\Delta^{\prime}W+S^{\prime} $ and $ \widehat{B}=\Delta\widehat{W}+\widehat{S} $ .Define the matrices $ ^{a}Q,Q^{\prime},\widehat{Q} $ as the first $ l $ columns of $ B,B^{\prime},\widehat{B} $ and remove these columns from the latter matrices，renumbering the remaining columns from 1.(b)Notice that $ \widetilde{T}_{0},\widetilde{T}_{1},\widetilde{T}_{2} $ form an additive sharing of $ \widetilde{A H}+\widetilde{P} $ ，and the verifiers know some of the shares，namely the rows of $ BH+Q $ and $ B^{\prime}H+Q^{\prime} $ （shares for the first $ n $ rows of $ \widetilde{A H}+\widetilde{P} $ ）and the rows of |  |
| (b) | Notice that T0,T1,T2form an additive sharing ofAH+P,and the verifiers know some of the shares,namely the rows ofBH+QandB&#x27;H+Q&#x27;(shares for the firstnrows ofAH+P)和the rows ofBH+Q(shares for the lastnrows).Fori∈{0,1,2},parseT_{i}asT_{i}=\begin{array}{c}\mathrm{T}_{i}\\\mathrm{T}_{i}\end{array}.CheckthatBH+Q=\Delta T_{2}+\Delta^{\prime}T_{1}+(1-\Delta-\Delta^{\prime})T_{0},B&#x27;H+Q^{\prime}=\Delta T_{0}+\Delta^{\prime}T_{2}+(1-\Delta-\Delta^{\prime})T_{1}andBH+Q=\Delta \widehat{T}_{2}+\Delta^{\prime}\widehat{T}_{1}+(1-\Delta-\Delta^{\prime})\widehat{T}_{0},and thatT_{0}+T_{1}+T_{2}\in C^{\odot \ell}.If any check fails,abort. |
| (c) | Foreveryadd,sid,ssid1,ssid2,ssid3)receivedfromP,appendB[·a]+B[·b]toB and appendB&#x27;[·a]+B&#x27;[·b]toB&#x27;(a,b)是index corresponding tossid1,ssid2respectively和ssid3isassociatedwiththenewcolumnindex).Foreverymult,sid,ssid1,ssid2,ssid3)receivedfromP:-given(sid,ssid,h,w0,w1,w2),checkthatw0+w1+w2\in C^{*2}andw_{r[i]}=B[·a]*B[·b]+B[·a]*B&#x27;[·b]+B&#x27;[·a]*B[·b]+\widehat{B}[·h];-letu=\pi[k](w0+w1+w2),appendthecolumnsB[·h]+\Delta C(u)andB&#x27;[·h]+\Delta&#x27;C(u)toBandB&#x27;，respectively. |
| B&#x27;，respectively.
Note that the properties detailed in footnotea are maintained. |  |
| (d)For everyj∈J,check thatA0[·,j]+A1[·,j]+A2[·,j]∈Cand that,fori=1,...,n,it holds thatB[i,j]=A r[i][i,j]andB&#x27;(i,j)=A r[i+1][i,j].If all checks succeed,for everyj∈J,output the firstkpositions inA0[·,j]+A1[·,j]+A2[·,j]as the opened string and halts.Otherwise,abort by outputting(sid,ssidj,⊥). |  |
| aNote thatwe haveA=A0+A1+A2,B=ΔA2+Δ&#x27;A1+(1-Δ-Δ&#x27;)A0andB&#x27;=ΔA0+Δ&#x27;A2+(1-Δ-Δ&#x27;)A1This means thatAheldbyPis sharedin the replicated secret sharing schemeRSS3and for each row index,Vknows one share(i.e.,Vknows the corresponding rows from exactly two of the matricesA0,A1,A2).Moreover,A=A0+A1+A2andB=ΔA2+Δ&#x27;A1+(I-Δ-Δ&#x27;)A0i.e.,AheldbyPis sharedin the additive secret sharing schemeAdd3and for each row index,Vknows one share(Vknows the correspondingrowfromexactlyoneofthematricesA0,A1,A2). |  |

$$
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*<sub>s</sub>. The homomorphic property of
the commitments will be used to implement this check eciently. While our protocol<sub>MHCOM</sub>does support
evaluation of low degree polynomials, we will focus on linear/ane verication equations *F₁;:::;F*<sub>s</sub>and will
therefore rely on the additively homomorphic commitment scheme<sub>AHCOM</sub>.

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

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

In our construction, we will use protocol<sub>AHCOM</sub>with 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<sub>AHCOM</sub>.

$$
\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 (10*d*log(*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<sub>AHCOM</sub>as 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 *j*F*j*, 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*<sub>AHCOM</sub>that can be instantiated with Protocol<sub>AHCOM</sub>, 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*<sub>MSAHCOM</sub>*.* 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*<sub>MSAHCOM</sub>, which will let the adversary choose any value to be provided as an opening. *F*<sub>MSAHCOM</sub>will 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*<sub>MSAHCOM</sub>in 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}}
$$

---

| Functionality $F_{\mathrm{MSAHCOM}}$ is parameterized by $n\in\mathbb{N}$. $F_{\mathrm{MSAHCOM}}$ interacts with a set of parties $P=\left\{P_{1},\ldots,P_{t}\right\}$ and an adversary $S$ (who may abort at any time): |  |
| --- | --- |
| -Init | Upon receiving(init, sid)from all parties in P，forward the message to Sand initialize empty lists raw and actual. |
| -Commit | Upon receivingcommit, sid, I)from all parties in PwhereIis a set of unused identifiers，for everyssid∈I，sample a random $x_{ssid} \leftarrow^{\$} \mathbb{F}^{k}$,setraw[ssid]=$x_{ssid}$and sendcommit-recorded,sid,I)to all parties Pand S. |
| -Input | Upon receiving(input, sid, ssid,Pi,y)from $P_{i}\in P$and(input, sid, ssid,Pi)from all other parties in P，if raw[ssid]=$x_{ssid}\neq\bot$,setraw[ssid]=$\bot$,setactual[ssid]=$y$and send(input-recorded,sid,ssid,Pi)to all parties in Pand S. |
| -Random | Upon receiving(random, sid, ssid)from all parties in P，if raw[ssid]=$x_{ssid}\neq\bot$,setactual[ssid]=$x_{ssid}$,setraw[ssid]=$\bot$and send(random-recorded,sid,ssid)to all parties P和S. |
| -Addition | Upon receivinga message(add, sid, ssid1, ssid2, ssid3)from all parties in P：if actual[ssid]=$x_{ssid}\neq\bot$for ssid∈{$ssid_{1},ssid_{2}$}and raw[ssid3]=$\text{actual}[ssid_{3}]=\bot$,setactual[ssid3]=$\text{actual}[ssid_{1}]+\text{actual}[ssid_{2}]$and send the message(add-recorded,sid,ssid1,ssid2,ssid3)to all P和S. |
| -Open | Upon receiving(open, sid, ssid)from all parties P，if actual[ssid]=$x_{ssid}\neq\bot$，send(open, sid, ssid,xssid)to S。If S answers with(open, sid, ssid,x&#x27;ssid)，send(open, sid, ssid,x&#x27;ssid)to all parties in P. |
| -Verify | Upon receivinga message(verify, sid)from all parties in P，let ssid1,...,ssido be the ssids of opened commitments(i.e.for which(open, sid, ssid,x&#x27;ssid)messages were sent)。For ssid∈{$ssid_{1},...,ssid_{o}$}，setb=1 if actual[ssid]=$x&#x27;ssid$or b=0 if not,and send(verify, sid, ssid,b)to every party in P. |

$$
\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*<sub>MSAHCOM</sub>*.* 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*<sub>AHCOM</sub>. We construct a protocol
where every party acts both as sender and receiver of all commitments. In this protocol, each party rst uses
*F*<sub>AHCOM</sub>to 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<sub>i2</sub><sub>[</sub><sub>t</sub><sub>]</sub>raw [*ssid*], where raw [*ssid*] is supposed to be the value obtained by *P*<sub>i</sub>
i j
from *F*<sup>AHCOM</sup>. In the verication procedure, all parties obtain *x*<sup>j</sup>for *j 2* [*t*] directly from *F*<sup>AHCOM</sup>, 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*<sub>j</sub>holding *y* broadcasts *w* = *y*<sub>i2</sub><sub>[</sub><sub>t</sub><sub>]</sub>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*<sub>j</sub>(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*<sub>MSAHCOM</sub>*UC realizes F*<sub>MSAHCOM</sub>*in the F*<sub>AHCOM</sub>*-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<sub>F</sub><sub>MSAHCOM</sub><sub>;S;Z</sub> <sub>s</sub>HYBRID<sub>;A;Z</sub>*:*
<sub>MSAHCOM</sub>

$$
\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}}}
$$

---

| Protocol ΠMSAHCOM |  |
| --- | --- |
| Given a set of parties $P=\{P_{1},\ldots,P_{t}\}$, for each party $P_{i}\in P$, $\Pi_{\mathrm{MSAHCOM}}$ uses an instance of $\mathcal{F}_{\mathrm{AHCOM}}$ denoted as $\mathcal{F}_{\mathrm{AHCOM}}^{i}$ where $P_{i}$ is the sender with a set of receivers $V_{i}=P\backslash P_{i}$. Parties in $P=\{P_{1},\ldots,P_{t}\}$ interact with each other and with $\mathcal{F}_{\mathrm{AHCOM}}^{1},\ldots,\mathcal{F}_{\mathrm{AHCOM}}^{t}$, proceeding as follows: |  |
| 1. | Commit On input (commit, sid, ssid, I) where $I=\{ssid_{1},\ldots,ssid_{y}\}$ each party $P_{i}\in P$, for ssid∈I sends (commit, sid, ssid, $P_{i},V_{i}$) to $\mathcal{F}_{\mathrm{AHCOM}}^{i}$, receiving as answer (receipt, sid, ssid, $P_{i},V_{i},x_{ssid}$) and setting raw$^{i}$[ssid]=$x_{ssid}$ and actual$^{i}$[ssid]=$\bot$. |
| 2. | Input On input (input, sid, ssid, y) for $P_{i}$ and input (input, sid, ssid, $P_{j}$) for every $P_{j}$ for $j\neq i$, parties $P$ proceed as follows: |
| (a) | For every $j\in[t],j\neq i,P_{j}$ aborts if actual$^{j}$[ssid]$\neq\bot$. Otherwise,$P_{j}$ sends (sid, ssid, raw$^{j}$[ssid]) to $P_{i}$. |
| (b) | Upon receiving (sid, ssid, raw$^{j}$[ssid]) from $P_{j}$ for every $j\in[t],j\neq i,P_{i}$ sets $x=\sum_{j\in[t]}\text{raw}^{j}[ssid],w=y-x$, actual$^{i}$[ssid]=$w$ and broadcasts (sid, ssid, $P_{i},w$). |
| (c) | Upon receiving (sid, ssid, $P_{i},w$), every party $P_{j}\in P$ sets actual$^{j}$[ssid]=$w$. |
| 3. | Random On input (random, sid, ssid), if actual$^{i}$[ssid]=$\bot$, each party $P_{i}\in P$ sets actual$^{i}$[ssid]=$0^{k}$. |
| 4. | Addition On input (add, sid, ssid$_{1}$, ssid$_{2}$, ssid$_{3}$), if actual$^{i}$[ssid$_{1}$]$\neq\bot$, actual$^{i}$[ssid$_{2}$]$\neq\bot$ and actual$^{i}$[ssid$_{3}$]=$\bot$, every party $P_{i}\in P$ sets actual$^{i}$[ssid$_{3}$]=$\text{actual}^{i}$[ssid$_{1}$]+actual$^{i}$[ssid$_{2}$]and sends (add, sid, ssid$_{1}$, ssid$_{2}$, ssid$_{3}$, $P_{i},V_{i}$) to $\mathcal{F}_{\mathrm{AHCOM}}^{i}$. All parties proceed after receiving (add, sid, ssid$_{1}$, ssid$_{2}$, ssid$_{3}$, $P_{i},V_{i}$, success) from $\mathcal{F}_{\mathrm{AHCOM}}^{i}$. |
| 5. | Open On input (open, sid, ssid), each $P_{i}\in P$ broadcasts (sid, ssid, raw$^{i}$[ssid]). Upon receiving (sid, ssid, raw$^{j}$[ssid]) for $j\in[t],j\neq i$, each party $P_{i}\in P$ computes $x^{\prime}=\text{actual}^{i}[ssid]+\sum_{j\in[t]}\text{raw}^{j}[ssid]$ and outputs (sid, ssid,$x^{\prime}$). |
| 6. | Verify On input (verify, sid), let ssid$_{1}$,...,ssid$_{o}$ be the ssids of opened commitments (i.e.for which(open, sid, ssid) inputs were received), every $P_{i}\in P$ sends (reveal, sid, ssid$_{1}$,...,ssid$_{o}$) to $\mathcal{F}_{\mathrm{AHCOM}}^{i}$. For every ssid∈{ssid$_{1}$,...,ssid$_{o}$}, upon receiving (reveal, sid, ssid,$P_{j},V_{j},x_{j}$) for $j\in[t],j\neq i$, each party $P_{i}\in P$ sets $x_{i}=\text{real}^{i}[ssid]$ computes $x=\text{actual}^{i}[ssid]+\sum_{j\in[t]}x_{j}$, sets b=1 if $x^{\prime}=x$ (where $x^{\prime}$ is the value previously opened) or b=0 if not, and outputs (verify, sid, ssid,b). |

$$
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<sup>MSAHCOM</sup>only performs operations with random values obtained from *F*<sup>AHCOM</sup>.
Hence, upon learning the opening of any commitment from *F*<sub>MSAHCOM</sub>, the simulator can simply cheat in
i
the openings of random values from the emulated *F*<sup>AHCOM</sup><sup>i</sup>n order to equivocate a commitment. Similarly,
if it needs to extract any commitment done in<sub>MSAHCOM</sub>, 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*<sub>AHCOM</sub>.

$$
\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<sub>MSAHCOM</sub>using *F*<sub>AHCOM</sub>as a black box actually communicates
more bits than necessary. In<sub>MSAHCOM</sub>’s opening phase, all parties broadcast the messages in commitments
generated by *F*<sub>AHCOM</sub>and, later on, verify these openings by opening the commitments through *F*<sub>AHCOM</sub>,
sending the same messages again. If instantiated with<sub>AHCOM</sub>, our construction can be made more ecient
by having the parties broadcast columns A₀[*;j*]*;*A₁[*;j*] (Step 1 of<sub>AHCOM</sub>’s opening phase) during the
opening phase of<sub>MSAHCOM</sub>. Later on, for verication, the parties only need to execute the remaining steps
of the opening phase of<sub>AHCOM</sub>in 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 *F*COM(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*<sub>PVHCOM</sub>is 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<sub>COM</sub>used as a building block is publicly veriable, Protocol<sub>AHCOM</sub>is trivially
publicly veriable when all the messages are posted to an authenticated bulletin board, straightforwardly
realizing functionality *F*<sub>PVHCOM</sub>. The \canonical" random oracle commitment scheme (that realizes *F*<sub>COM</sub>
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<sub>AHCOM</sub>instantiated 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<sub>;A;Z</sub>(*;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*<sub>Z</sub>*;r*<sub>A</sub>*;r*<sub>P</sub><sub>1</sub>*;:::;r*<sub>P</sub><sub>n</sub>), where (*z;r*<sub>Z</sub>), r<sub>A</sub>and *r*<sub>P</sub><sub>i</sub>are respectively related to *Z*, *A* and party *i*. Analogously, we denote by IDEAL<sub>F;S;Z</sub>(*;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*<sub>Z</sub>*;r*<sub>S</sub>*;r*<sub>F</sub>), where (*z;r*<sub>Z</sub>), *r*<sub>S</sub>and *r*<sub>F</sub>are respectively related to *Z*, *S* and *F*. The real world execution and
the ideal executions are respectively represented by the ensembles REAL<sub>;A;Z</sub>= *f*REAL<sub>;A;Z</sub>(*;z; r*)*g*<sub>2</sub><sub>N</sub>and
IDEAL<sub>F;S;Z</sub>= *f*IDEAL<sub>F;S;Z</sub>(*;z; r*)*g*<sub>2</sub><sub>N</sub>with *z 2f*0*;* 1*g* 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<sub>;A;Z</sub>
(dened analogously to REAL<sub>;A;Z</sub>). 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<sub>j</sub><sub>F</sub><sub>j</sub>(*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*<sub>G;</sub>: F*!* F⁰ = <sup>F</sup> *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<sub>d</sub> <sub>1</sub>) *2* F (F)*. Dene the family H by H* = *fH*<sub>G;</sub>: *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*<sub>G;</sub>(x) *is uniformly random for any* (x₁*;:::;*x<sub>d</sub> <sub>1</sub>)
*(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<sub>j</sub><sub>F</sub><sub>j</sub>(*d*)) polylog(s + log<sub>j</sub><sub>F</sub><sub>j</sub>(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<sup>s</sup>t universal. Let
x = (x₀*;:::;*x<sub>d</sub> <sub>1</sub>) 6= 0. Thus there exists an *i 2f*0*;:::;d* 1*g* such that x<sub>i</sub>6= 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<sub>i</sub>) 6= 0, except with probl
ability 1*=j*F*j* = 1*=j*F⁰*j*. Consequently by injectivity of it holds that (*G*(x<sub>i</sub>)) 6= 0. Suppose now that
0d
06= ( (x₀)*;*(*G*(x₁)) *:::;*(*G*(x<sub>d</sub> <sub>1</sub>))) *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)*=j*F⁰*j*. All together, we can conclude that *H*<sub>G;</sub>(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 *j*F *j* = *j*F*j*<sup>j</sup><sup>F</sup><sup>j</sup>.

$$
\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*<sub>G;</sub>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*<sub>G;</sub>can be computed in linear
time in the size of its input x. Computing *G*(x₁)*;:::;G*(x<sub>d</sub>) takes time *O*(*d n*), as computing each *G*(x<sub>i</sub>)
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₀) +<sub>i</sub><sub>=1</sub>(*G*(x<sub>i</sub>))*X* at na<sub>i</sub>vely 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*<sub>G;</sub>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<sub>s</sub>)<sub>s</sub>*of 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<sub>AHCOM</sub>described in Section 3 realizes *F*<sub>AHCOM</sub>, 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*<sub>AHCOM</sub>can
be used to build a protocol for additively homomorphic commitments to arbitrary messages that also achieves
rate-1 and linear time (given that<sub>AHCOM</sub>is used to instantiate *F*<sub>AHCOM</sub>). 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*<sub>AHCOM</sub>, essentially using them as one-time pads. In order
to commit to an arbitrary message *m⁰*, *P* executes the commitment phase of *F*<sub>AHCOM</sub>to 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*<sub>AHCOM</sub>and sets *c₃* = *c₁* +*c₂* = *m⁰*<sub>1</sub>+*m⁰*<sub>2</sub>*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 2f*0*;* 1*g* and set of receivers *V* = *fV₁;:::;Vtg*,
who interact with *F*COM and proceed as follows:
1. Commitment Phase:
0j
(a)On input (commit*;sid;ssid; m*), *P* sends (commit*;sid;ssid;P;V*) to *F*AHCOM. Upon receiving
0j
(commit*;sid;ssid;P;V; mj*) as answer, *P* sets *cj* = *m mj*, and sends (*c*j*;sid;ssid;*) to *V*.
2. Addition:
(a)On input (add*;ssid₁;ssid₂;ssid₃*), *P* sends (add*;sid;ssid₁;ssid₂;ssid₃;P;V*) to *F*AHCOM and sets *c₃* =
*c₁* + *c₂* = *m⁰*<sub>1</sub>+ *m⁰*<sub>2</sub>*m₁ m₂*.
(b)Upon receiving (add*;sid;ssid₁;ssid₂;ssid₃;P;V;* success) from *F*AHCOM, *V* also sets *c₃* = *c₁* + *c₂* =
*m⁰*<sub>1</sub>+ *m⁰*<sub>2</sub>*m₁ m₂*.
3. Opening Phase:
(a)On input (reveal*;ssid₁;:::;ssido*) *P* sends (reveal*;ssid₁;:::;ssido*) to *F*AHCOM and halts.
0j
(b)Upon receiving (reveal*;sid;ssid;P;V; m₁;:::; mo*) from *F*AHCOM, for *j 2f*1*;:::;og V* computes *m* =
<sup>0j</sup>
*cj* +*mj* and outputs *m*. Note that, even if *c* is an addition of two commitments *c₁* and *c₂*, this procedure
<u>is still valid since</u> <u>c₃</u> <u>=</u> <u>c₁</u> <u>+</u> <u>c₂</u> <u>=</u> <u>m⁰</u><sub>1</sub><u>+</u> <u>m⁰</u><sub>2</sub><u>m₁ m₂</u><u>.</u>

$$
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*<sub>AHCOM</sub>, allowing *V* to obtain the intended message by computing *m⁰* = *c*+*m*. We
give the description of Protocol<sub>ARBHCOM</sub>in almost verbatim form [16] in Figure 11. The only dierence
is that Protocol<sub>ARBHCOM</sub>only 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<sub>ARBHCOM</sub>can be trivially observed since the random string from
*F*<sub>AHCOM</sub>acts as a one-time pad hiding all information and binding is guaranteed by *F*<sub>AHCOM</sub>. Hence,
ARBHCOMis statistically secure in the *F*AHCOM-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<sub>ARBHCOM</sub>is instantiated using<sub>AHCOM</sub>to realize *F*<sub>AHCOM</sub>,
0j
the extra communication in relation to<sub>AHCOM</sub>corresponds 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,<sub>ARBHCOM</sub>is 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*<sub>P</sub>*such that for every static*
*adversary A who corrupts P and all but one receivers in V* = *fV₁;:::;V*<sub>t</sub>*g, and any environment Z, the*
*environment cannot distinguish*<sub>AHCOM</sub>*composed with F*<sub>COM</sub>*and A from S*<sub>P</sub>*composed with F*<sub>AHCOM</sub>*.*
*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
<sup>P</sup>
to run an internal copy of with *P*^, extract the messages in commitments performed by *A* and send
AHCOM
them to *F*<sup>AHCOM</sup>. We describe the simulator *S*<sup>P</sup>in Figure 12. The simulator *S*<sub>P</sub>will run protocol<sub>AHCOM</sub>
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*<sub>P</sub>emulates the instances of *F*<sub>COM</sub>used by *A* following the exact instructions of *F*<sub>COM</sub>
but learning *r* and the seeds *s*<sub>i;j</sub>. Using this knowledge, *S*<sub>P</sub>reconstructs 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*<sub>i;r</sub><sub>[1]</sub>for *i* = 1*;:::;n* from *F*<sub>COM</sub>). 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*<sup>COM</sup>: *S*<sup>P</sup> executes exactly the steps of *F*<sup>COM</sup>. *S*<sup>P</sup> stores the vector *r* = *r₁ ::: r*<sup>t</sup> computed
using the vectors *r* rece<sub>i</sub>ved from the receivers *V* (<sub>i</sub>ncluding itself and the receivers controlled by *P*^).
i i
Moreover, it stores the seeds *s* received from *P*^ for *i 2* [*n*] and *j 2f*0*;* 1*g*.
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*<sup>P</sup> executes the steps of the commitment phase of <sup>AHCOM</sup> 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 *F*COM 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*;* 1*g*. Finally, *SP* sends (commit*;sid;ssidj;P;V; mj*) to *F*AHCOM. 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*<sup>AHCOM</sup>.

$$
{\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])) fr*o*m *P*^, *S* executes the exact
o j2J *P*
steps of an honest *V* in <sup>AHCOM</sup>. 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 <sub>o</sub>
<u>to</u> <u>F</u><u>, outputs whatever</u> <u>P</u><u>^ outputs and halts.</u>
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*<sub>P</sub>using 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*<sup>j</sup>sent by *S*<sup>P</sup>to *F*<sup>AHCOM</sup>will 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*<sup>P</sup>succeed, 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 <sub>COM</sub>
for *i 2 f*1*;:::;ng* and *j 2 f*0*;* 1*g*, *S*<sub>P</sub>can reconstruct A by computing R₀[*i;*] = PRG(*s*<sub>i;</sub><sub>0</sub>) and R₁[*i;*] =
PRG(*s*<sup>i;</sup><sup>1</sup>), 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*<sub>P</sub>can 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
<sup>m</sup>
(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*<sub>j</sub>that the simulator will input to *F*<sub>AHCOM</sub>. 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<sub>R</sub>(*c*) = (*c*[*i*])<sub>i2</sub><sub>[</sub><sub>n</sub><sub>]</sub><sub>nR</sub>
be the vector punctured at the indices *i 2 R*. For a matrix M we let M<sub>R</sub>=<sub>R</sub>(M) be the matrix with each
column punctured using<sub>R</sub>and for a set *S* we let *S*<sub>R</sub>= *f*<sub>R</sub>(*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*<sup>i</sup>for *i 2 R* with certainty at this point in the simulation and has no extra information on *b*<sup>i</sup>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
<sub>1</sub> 0
T^ + (I)T^ can be seen to <sub>b</sub>e 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<sub>b</sub><sub>i</sub>[*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*<sup>i</sup>instead of *b*<sup>i</sup>, 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<sub>i</sub> 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 (<sup>jRj</sup>
*b₁;:::;b*<sub>n</sub>prior to sending T<sub>0</sub>and T<sub>1</sub>so P b<sub>i</sub>)<sub>i2R</sub>with probability at most 2. It is easy to see
that the value of the bits *b*<sup>i</sup>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
<sub>R</sub> <sub>Rl</sub> R Rl R Rl
l
and thus X<sup>R</sup>H *2* C<sup>Rl</sup>. 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<sub>R</sub>= C<sub>R</sub>, 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;*]<sup>R</sup>*2* C<sub>R</sub>decode the corresponding
k^.
message *m*<sub>j</sub>*2f*0*;* 1*g*. This is the message that the simulator will input to *F*<sub>AHCOM</sub>on 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*<sup>P</sup>and 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<sup>R</sup>has 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*<sup>i</sup>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*<sub>V</sub>*such that for every static*
*adversary A who corrupts all receivers in V* = *fV₁;:::;V*<sub>t</sub>*g, and any environment Z, the environment cannot*
*distinguish*<sub>AHCOM</sub>*composed with F*<sub>COM</sub>*and A from S*<sub>V</sub>*composed with F*<sub>AHCOM</sub>*. 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 *F*COM: *S*V executes exactly the steps of *F*COM, storing *r* = *r₁ ::: rt* computed using the
random strings *r* rece*i*ved 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 *F*AHCOM, *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 *F*AHCOM, *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 *F*AHCOM 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<u>^, outputs whatever</u> ^
<u>(</u><u>sid;ssid₁;:::;ssid</u><sub>o</sub><u>;</u><u>(A₀ [</u><u>;j</u><u>]</u><u>;</u><u>A₁ [</u><u>;j</u><u>])</u><sub>j2J</sub><u>) to</u> <u>V</u> V <u>outputs and halts.</u>

$$
\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*<sup>V</sup>has to run<sup>AHCOM</sup>with 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*<sub>AHCOM</sub>. In order to achieve this, we construct a *S*<sub>V</sub>that
executes the commitment phase exactly as an honest *P* in<sub>AHCOM</sub>, only deviating in the opening phase.
We describe *S*<sub>V</sub>in 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*<sub>V</sub>can open a commitment to an arbitrary message without being detected.
Note that *S*<sup>V</sup>executes the exact steps of an honest *P* in<sup>AHCOM</sup>except for the opening phase. For each
0 0
commitment associated with index *j* to be opened, *S*<sub>V</sub>sends 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^.
<sub>AHCOM</sub>. However, A<sub>0</sub>[*;j*]*;* A<sub>1</sub>[*;j*], only dier from A<sub>0</sub>[*;j*]*;* A<sub>1</sub>[*;j*] in positions that are unknown by *V*
Hence, the joint distribution of the ideal execution with simulator *S*<sub>V</sub>is computationally indistinguishable
from the real execution of<sub>AHCOM</sub>with 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*<sub>MHCOM</sub>*UC realizes F*<sub>MHCOM</sub>*in the F*<sub>COM</sub>*-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*<sub>MHCOM</sub>*composed with F*<sub>COM</sub>*and A from S composed*
*with F*<sub>MHCOM</sub>*. 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
<sup>P</sup>
<sub>0</sub>b, Q, Q⁰ b, H, T~ ~
analogously as in the proof of Lemma 2 learn the seeds *s*<sub>i;j</sub>, b*s*<sub>i;j</sub>, *r*,,, B, B⁰, B, Q<sub>0</sub>, T<sub>1</sub>,
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*<sup>P</sup>can 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~) <sub>m</sub>
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
<sub>j</sub> 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*<sup>i</sup>= *r*[*i*] the selections of the verier. Since the receiver did not abort, then U<sup>r</sup>i= T<sub>r</sub>i,
U = T, U^ = T^ Fo<sub>r</sub> 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
<sub>i</sub>n *R*^, e<sub>i</sub>the<sub>r</sub> U^ 6= T^ o<sub>r</sub> U^ 6= T^ (o<sub>r</sub> 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* <sub>i</sub>s, for every *i* in *R*^ *n R*. Therefore the probability that the protocol does not abort is
i
<sup>jRj</sup> <sup>jRnRj</sup> <sup>^</sup>^ (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*+*jR*j) 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
<sub>2</sub> ~). 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<sub>R</sub>= A<sub>R</sub>and C<sub>^</sub>= A<sub>^</sub>
b <sub>R</sub> 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<sup>R</sup>means the submatrix of A consisting of all rows except those indexed by *R*). Hence
~ ~) <sub>m</sub>^. 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*<sup>MHCOM</sup>.

$$
\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<sup>s</sup>t 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 <sup>MHCOM</sup>
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.
<sub>R</sub><sub>^</sub> <sub>^2</sub>
R
^ can now choose to announce some arbitrary vectors0l 0r
*P w*. However, if *w*i[*i*] 6= *w*<sub>r</sub>i[*i*], then the protocol
will abort. This is because the verier can compute w [<sub>i</sub>] f<sub>r</sub>om 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. S*i*nce *w*<sub>^</sub>*2* C<sub>^</sub>, 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;bgf*0*;* 1*;* 2*g* such that
^2 s s
*r*<sub>i</sub>*2fa;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<sup>MHCOM</sup>as 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 2f*0*;* 1*;* 2*g* 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
<sub>V</sub>
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*<sub>o</sub>*g* upon receiving *m*<sub>j</sub>from *F*<sub>MHCOM</sub>as opening of the
0r
commitment associated with the index *j*, *S*<sub>V</sub>denes A<sub>[</sub><sub>i</sub><sub>]+2</sub>[*;j*] = C(*m*<sub>j</sub>) A<sub>r</sub><sub>[</sub><sub>i</sub><sub>]+1</sub>[*;j*] A<sub>r</sub><sub>[</sub><sub>i</sub><sub>]</sub>[*;j*] and
<sup>0r</sup>
A<sub>[</sub><sub>i</sub><sub>]+</sub><sub>l</sub>[*;j*] = A<sub>r</sub><sub>[</sub><sub>i</sub><sub>]+</sub><sub>l</sub>[*;j*] for *l 2 f*0*;* 1*g* (where A<sub>i</sub>[*;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*<sub>V</sub>is 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*<sub>PVHCOM</sub>used 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 *F*PVHCOM

---

## 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*<sub>i</sub>, upon which the verier answers with a uniformly random message *v*<sub>i</sub>. We require all the messages
*p*<sub>i</sub>and *v*<sub>i</sub>to be vectors over a eld F. After the conversation is over, the verier evaluates a system of low
degree polynomials *F₁;:::;F*<sub>s</sub>in the *p*<sub>i</sub>and *v*<sub>i</sub>and accepts if all *F*<sub>i</sub>evaluate 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
<sub>x2f</sub><sub>0</sub><sub>;</sub><sub>1</sub><sub>g</sub><sub>n</sub> *P* (*x*) = *L*, where *P 2* F[*X₁;:::;X*<sub>n</sub>] 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*<sub>s</sub>such that the equations *F*<sub>i</sub>(*x;p₁;:::;p*<sub>t</sub>*;v₁;:::;v*<sub>t</sub>) are ane in (*p₁;:::;p*<sub>t</sub>). In our construction,
we will use protocol<sub>AHCOM</sub>with 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<sub>AHCOM</sub>in 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<sub>AHCOM</sub>in 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}}
$$

<sup>15</sup>
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<sub>AHCOM</sub>(Figure 4 and Figure 5) the prover *P* commits
to 2*n* random seeds *s*<sub>i;j</sub>for *i 2* [*f*1*;:::;ng*] and *j 2f*0*;* 1*g* using a UC-commitment *F*<sub>COM</sub>. This is done
to make the commitment scheme<sub>AHCOM</sub>extractable. 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<sub>AHCOM</sub>the verier commits to a challenge *r⁰* using a UCcommitment *F*<sub>COM</sub>. This step in necessary to make the commitment scheme<sub>AHCOM</sub>equivocal. 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<sub>HVZK</sub>is provided in Figure 15. We can also instantiate<sub>HVZK</sub>with the commitment protocol
MHCOM(Section 4) and allow the verication equations *F₁;:::;F*kto be low degree polynomials in the *p*i
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<sub>HVZK</sub>follows 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<sub>HVZK</sub>given that (P*;*V) is sound. First notice that the commitment scheme<sub>AHCOM</sub>is statistically binding, as the underlying commitment scheme Commit is also statistically binding. Therefore, the prover
messages (^*p₁;:::; p*^<sub>t</sub>) commit uniquely to messages (*p₁;:::;p*<sub>t</sub>). Moreover, the proofs for homomorphic relations are also statistically sound. Thus, if the verier accepts, it must hold that *F*<sub>i</sub>(*x;p₁;:::;p*<sub>t</sub>*;v₁;:::;v*<sub>t</sub>) = 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<sub>HVZK</sub>, as the opening phase of<sub>AHCOM</sub>has
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<sub>AHCOM</sub>
becomes equivocal if the prover knows the challenge *r⁰* of the verier before the start of the protocol, see
the construction of simulator *S*<sub>V</sub>in Figure 13 in Appendix D. The simulator for<sub>HVZK</sub>can choose *r⁰* and

$$
r^{\prime}
$$

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

$$
\mathit{\Pi}_{H V Z K}
$$

$$
r^{\prime}
$$ setup<sub>AHCOM</sub>to be equivocal. In the simulated proof it sets the ^*p*<sub>i</sub>fake commitments. During the opening
phase, it opens the commitments to fake values (just as *S*<sub>V</sub>).

$$
\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<sub>AHCOM</sub>.

$$
\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⁰*<sub>2</sub>= com(*r*) and *c⁰*<sub>3</sub>= 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⁰*<sub>3</sub>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*=j*F*j*. 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*<sub>i</sub>= com(*x*<sub>i</sub>) we want
k m k
to show that A *x* = *y*, where *x* = (*x*<sub>i</sub>)<sub>i</sub>and A *2* F and *y 2* F. Consider the following protocol. The
$k
verier chooses a random *v* F and sendsP*v* to the prover. The prover now uses the linear homomorphic
m > >
property of the commitment to prove that<sub>i</sub><sub>=1</sub>*w*<sub>i</sub>co<sup>m</sup>(*x*<sub>i</sub>) 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*=j*F*j*. 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 *c*i= com(*x*i) fo*r* i = 1*;:::;m* where the
Pm
n <sup>></sup>
*x 2* F *ar*e vectors. Now assume the prover wants to conv*i*nce the verier that<sub>i</sub><sub>=1</sub>*a*<sub>i</sub>*x*<sub>i</sub>= *y* where the
<sub>n</sub>
*a*<sub>i</sub>*2* F are ve*c*tors an*d 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}
$$

> 0*i* >
For *i* = 1*;:::;m* the prover computes commitments *d*<sub>i</sub>= com(*a*<sub>i</sub>*x*<sub>i</sub>), *c* = com(*r*<sub>i</sub>) and *c⁰⁰*<sub>i</sub>= com(*a*<sub>i</sub>*r*<sub>i</sub>)
$
and sends them to the verier. The verier responds with random eld element F. For every *i* the
prover now computes *z*<sub>i</sub>= *r*<sub>i</sub>+ *x*<sub>i</sub>, sends *z*<sub>i</sub>to 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*<sub>i</sub>unveils to *zi*

$$
i=1,\ldots,m\;c_{i}^{\prime}+\gamma c_{i}
$$

$$
z_{i}
$$

>
2.For all i = 1*;:::;m c⁰⁰*i+ *d*iunveils to *a*<sub>i</sub>*z*.
P

$$
i=1,\ldots,m\;c_{i}^{\prime\prime}+\gamma d_{i}
$$

$$
a{\}_{i}^{\top}\cdot z}
$$

<sub>m</sub>
3.<sub>i</sub><sub>=1</sub>*d*<sub>i</sub>unveils 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*<sup>i</sup>does not commit to *a*<sup>i</sup>*x*<sub>i</sub>, i.e.
>
assume that *d*<sub>i</sub>commits to *a*<sub>i</sub>*x*<sub>i</sub>+ *t*<sub>i</sub>, where one of the *t*<sub>i</sub>is non-zero. The rst check above ensures that
*z*<sub>i</sub>= *r*<sub>i</sub>+ *x*<sub>i</sub>. Assume that *c⁰⁰*<sub>i</sub>commits to a value *u*<sub>i</sub>. 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*<sub>i</sub>, *u*<sub>i</sub>and *r*<sub>i</sub>are xed before is chosen and therefore independent of. Consequently, if
*t*<sub>i</sub>6= 0 by the Schwartz-Zippel Lemma this check is passed with probability at most 1*=j*F*j* 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*((*d*log(*G*) + *jwj*) *j*F*j* +), 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 *j*F*j*, 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|
$$