Efficient Non-Interactive Zero Knowledge
Arguments for Set Operations?
Prastudy Fauzi1 , Helger Lipmaa1 , and Bingsheng Zhang2
12

University of Tartu, Estonia
National and Kapodistrian University of Athens, Greece

Abstract. We propose a non-interactive zero knowledge pairwise multiset sum equality test (PMSET) argument in the common reference string(CRS) model that allows a prover to show that the given committed multisets Aj for j ∈ {1, 2, 3, 4} satisfy A1 ] A2 = A3 ] A4 , i.e., every element
is contained in A1 and A2 exactly as many times as in A3 and A4 . Asa corollary to the PMSET argument, we present arguments that enable to efficiently verify the correctness of various (multi)set operations,for example, that one committed set is the intersection or union of twoother committed sets. The new arguments have constant communicationand verification complexity (in group elements and group operations,
respectively), whereas the CRS length and the prover’s computational
complexity are both proportional to the cardinality of the (multi)sets.
We show that one can shorten the CRS length at the cost of a small
increase of the communication and the verifier’s computation.
Keywords. Multisets, non-interactive zero knowledge, set operation arguments.

1

Introduction

One of the most common tasks undertaken to achieve active security (i.e., security against malicious participants) in various cryptographic protocols is toconstruct an efficient zero knowledge proof that the committed (or encrypted)
messages sent by various parties belong to correct sets. For example, some of themost efficient e-voting protocols [15,17] and e-auction protocols [38] are secure
only if the voters (resp., bidders) have committed to inputs from a certain range.
Because of such reasons, range proofs — where the prover aims to convince theverifier that the committed message belongs to some public range — have been
widely studied in cryptographic literature. There are many well-known efficient
range proofs, both interactive [9,38,35,10,13] and non-interactive [42,14,21].
However, in many applications it is not sufficient to prove that the inputs
belong to a continuous range, since the valid input set may be an arbitrary(polynomial-size) set of integers. Moreover, often the same party has to commit to related inputs many times, and the whole protocol is secure only if thecommitted input sets satisfy some set-theoretic relations. E.g., in an approval?

First eprint version, January 31, 2014

2

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang
Operation
RO |CRS| Prov comp Ver comp Commzero-knowledge setsyes Θ(k) Θ(k)
Θ(1)
Θ(1)
committed subset of disjoint yes Ω(k)
Ω(k)
Ω(k)
sets
[33]
set intersection, set union yes O(k)
O(k)
O(k)
[31]
set intersection
yes Θ(1) Θ(k)
Θ(k)
Θ(k)
This paper PMSET, committed sub- no Θ(k) Θ(k)
Θ(1)
Θ(1)
set, set intersection, setunion, set difference, zeroknowledge sets, accumulator, . . .
Paper
[32]
[19]

Table 1. Performance comparison of NIZK for set operations

e-voting protocol, one could first to be asked to commit to a set A of all approved
candidates, and in the second round (based on the outcome of the first round)to a certain subset B of A. One could interpret A and B as multisets, where avoter is allowed to distribute a limited number of points between the set of all
candidates. To achieve active security, the voter must prove in particular thatB ⊆ A ⊆ U, where U is the set of all candidates. Moreover, in any concrete
application, it can also be required to lower and upper bound the cardinality ofA and B. For instance, in the case of approval voting, the voter may only have anumber of votes to spend, but may be required to vote at least once. Similarly,
in a combinatorial auction, a bidder may bid up to a certain number items, but
might be required to bid at least once to continue in the next round.
Similar issues arise in many other applications, and thus a lot of work has
been done in constructing efficient zero knowledge proofs for (multi)set-theoretic
operations. However, practically all existing (multi)set-theoretic zero knowledge
proofs [19,33,31] require at least linear communication in the size of the committed sets. This is not acceptable in many applications where the cardinalityof the underlying sets is large. See Table 1 for a brief comparison, and App. A
for a longer comparison. (App. A also compares the current work with [32].)
Moreover, all existing efficient set-theoretic zero-knowledge proofs are interactive, which makes them less useful in practice. While they can be made noninteractive in the random oracle model by using the Fiat-Shamir heuristic [22], itis well-known that such a heuristic is not a proof [12,26]. Thus, a better approachis to build non-interactive zero knowledge (NIZK) proofs in the common reference string (CRS) model. See Sect. 2 for more preliminaries on NIZK proofs andarguments (i.e., computationally sound proofs). For the rest of this introduction,
we recall that sublinear NIZK proofs can only be (a) computationally sound, and(b) cannot be based on standard (falsifiable) assumptions [25]. Thus, following along line of contemporary cryptographic research [28,14,36,24,5,3,21,37], we will
construct NIZK arguments that are sound under some knowledge assumptions.

Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

3

Our Contibutions. We tackle the task of constructing efficient (multi)settheoretic NIZK arguments in a modular way. First, we design an efficient pairingbased NIZK argument for a certain multiset relation. Second, we show that the
proposed argument can be used to construct efficient NIZK arguments for aplethora of other (multi)set relations.
More precisely, recall that if A is a multiset, then every element a of theuniverse U belongs to A with some multiplicity 1A (a) ≥ 0. (Multiplicity 0 meansthat a does not belong to A.) In particular, A1 ]A2 is a multiset that has as many
copies of any element a as A1 and A2 put together, 1A1 ]A2 (a) = 1A1 (a) + 1A2 (a)for each a ∈ U. See Sect. 2 for more preliminaries on multisets.
We propose a non-interactive pairwise multiset sum equality test (PMSET)
argument, where the prover has committed to four multisets A1 , A2 , A3 and A4 ,and aims to prove in zero knowledge that A1 ] A2 = A3 ] A4 . That is, for alla ∈ U, 1A1 (a) + 1A2 (a) = 1A3 (a) + 1A4 (a). Moreover, for some public constants
kj , this argument guarantees the verifier that |Aj | ≤ kj .
Briefly, the intuition behind our new PMSET argument is as follows. The
prover first commits to a succinct encoding
Q of each Aj . More precisely, Aj ⊂ Zp
is encoded as χAj (σ), where χAj (X) := a∈Aj (X − a) (with correct multiplicities), and σ is a secret key. The prover commits to χAj (σ) for j ∈ {1, 2, 3, 4}.
After that, the prover creates a succinct NIZK argument that χA1 (σ)χA2 (σ) =χA3 (σ)χA4 (σ), where χAj (X) is a degree ≤ kj polynomial. The real argument ismore complicated, since it has to include several extra values to allow for boththe soundness and the zero knowledge part of the security proof to go through:(i) to achieve computational soundness, every group element in the argument
is accompanied by a knowledge component,(ii) to achieve zero knowledge, the argument contains independent random
commitments Dj to all 4 multisets Aj . In the simulation, the simulator
sets Dj to be equal to random group elements, and simulates the NIZK
arguments that Dj commit to the original sets Aj .
(See Sect. 4 for details.) The argument can be verified by using a small numberof computations of a bilinear map.
By relying on suitable cryptographic hardness assumptions, from a successful
verification it follows that χA1 (X)χA2 (X) = χA3 (X)χA4 (X), and thus the twopolynomials χA1 (X)χA2 (X) and χA3 (X)χA4 (X) have the same set of roots withthe same multiplicities. Thus, if the PMSET argument verifies, then the verifier
is convinced that the prover knows multisets Aj , such that A1 ] A2 = A3 ] A4 .
Moreover, since χAj (X) is a degree ≤ kj polynomial, the verifier is also convincedthat |Aj | ≤ kj .
We actually work in a relaxation of the described model, by allowing χAj (X)to be any polynomial that has Aj as its null set (again, with correct multiplicities). This somewhat simplifies the argument. Moreover, it allows us to specify
parameters kj such that the prover can additionally convince the verifier that the
cardinality of Aj is not larger than kj . Thus, we automatically achieve the sizehiding property, required (in particular) in the case of zero-knowledge sets [39].
On the other hand, we can use the upper bound on |Aj | to guarantee, for exam-

4

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang

ple, that a voter has approved at most kj candidates. Without the mentioned
relaxation, it seems that the cardinality of Aj would have to be exactly equal tokj , where kj is fixed during the CRS generation.
The length of the new argument is Θ(1) group elements, while the verifier’s computation is dominated by Θ(1) cryptographic pairings. As a drawback,the CRS length is Θ(k ∗ ), where k ∗ = maxj kj , and the prover’s computational
complexity is dominated by several k ∗ -wide bilinear-group multiexponentiations.
Although multiexponentiations can be optimized by using the algorithms ofStraus [43] and Pippenger [41], they are still costly.
We also provide a version of the PMSET argument that has a smaller CRS
length but larger communication and verifier’s√computation. In the balanced
version, all these parameters have complexity Θ( k). (The prover’s computationis still linear in k — this seems, although we are not claiming it, to be necessary
unless Aj have a specific structure that one can exploit.)
Applications. We finish the paper by showing how to use the PMSET argument
to prove the correct execution of several (multi)set operations. Many applications
are possible since any of the multisets Aj can be either public (e.g., in some
applications we can choose Aj = ∅ to be public) or committed to, and that
we are given flexibility of choosing the values kj for committed multisets. For
example, we obtain arguments for A1 ⊆ A2 , A1 = A2 \ A3 , A1 = A2 ∪ A3 ,A1 = A2 ∩ A3 , etc.
As another example, we can prove that A1 is a multiset obtained from A2 by
increasing or decreasing the multiplicity of exactly one (public or committed)
element by one. If that element is public, we obtain a dynamic accumulator [11].
Finally, we mention that one can construct a zap (two-message witnessindistinguishable argument, where the verifier’s first message can be shared between many protocol executions, [20]) from the new NIZK argument by using
standard techniques: basically, the verifier creates the CRS, and the prover thenreplies with the NIZK argument. Such a zap is secure in the standard model,
without assuming the existence of a trusted third party who creates the CRS.

2

Preliminaries

Notation. Sets are denoted by blackboard bold uppercase letters as in A. Bydeg(f ), we denote the degree of the polynomial f . If h = g x in a group G,
then we write x = logg h. For a group G, we utilize the fact that G2 = G × G
is a group and thus aggressively use notation like (g, h)a or (g1 , h1 ) · (g2 , h2 ).
Let NUPPT stand for non-uniform probabilistic polynomial time. A positive
function ε(·) is negligible in its parameter if it decreases faster than the inverseof any polynomial, i.e., ε(n) = n−ω(1) . By κ, we denote the security parameter.
Sets And Multisets. Formally, a multiset is a 2-tuple (A, µA ) where A is some
set and µA : A → N≥1 is a function from A to the set N≥1 = {1, 2, 3, . . . } of

Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

5

positive natural numbers. The set A is called the underlying set of elements. For
each a in A the multiplicity of a is the number µA (a). If A ⊆ U for some larger
set U, then one can extend µA to U, by defining µA (a) = 0 for a 6∈ A. We denote
this extended multiplicity function by 1A , and assume its existence implicitly,
talking about a multiset A instead of a multiset (A, 1A ).
If A and B are sets, then 1A (a) = 1 if a ∈ A and 1A (a) = 0 if x 6∈ A. If A and B
are sets, then 1A∩B (a) = min {1A (a), 1B (a)} and 1A∪B (a) = max {1A (a), 1B (a)}.
We have that
P A ⊆ B iff ∀a, 1A (a) ≤ 1B (a). The cardinality of a finite (multi)set
A is |A| = a∈U 1A (a).
Now, assume that A and B are multisets. The multiset sum A ] B is definedso that 1A]B (i) = 1A (i) + 1B (i) for all i, and the multiset difference A \ B isdefined so that 1A\B (i) = max(0, 1A (i) − 1B (i)) for all i. In most of the cases,
we just use common set-theoretic operations with multisets. For example, a ∈ Ameans that 1A (a) ≥ 1.
Bilinear Groups. Let Gbp (1κ ) be a bilinear group generator that outputs
a description of a bilinear group parm := (p, G1 , G2 , GT , ê) ← Gbp (1κ ), s.t. p
is a κ-bit prime, G1 , G2 and GT are multiplicative cyclic groups of order p,ê : G1 × G2 → GT is a bilinear map (pairing), s.t. ∀a, b ∈ Zp and gz ∈ Gz ,ê(g1a , g2b ) = ê(g1 , g2 )ab . If gz generates Gz for z ∈ {1, 2}, then ê(g1 , g2 ) generates
GT . Deciding the membership in G1 , G2 and GT , group operations, the pairing ê,and sampling the generators are efficient, and the descriptions of the groups andgroup elements are O(κ)-bit long each. A cryptographic pairing is also required
to satisfy some hardness assumptions (see later in this section).
Well-chosen asymmetric pairings (with no efficient isomorphism between G1and G2 ) are much more efficient than symmetric pairings (where G1 = G2 ).
For κ = 128, the current recommendation is to use an optimal (asymmetric)Ate pairing [30] over a subclass of Barreto-Naehrig curves [2,40]. In that case,at security level of κ = 128, an element of G1 /G2 /GT can be represented in
respectively 512/256/3072 bits.
(Λ, u) Trapdoor Commitment Scheme. A trapdoor commitment scheme isa randomized cryptographic primitive (in the common reference string model [8])that takes a message and outputs a commitment and a trapdoor. It is required
to have the following three security properties.
Computational binding: without access to the trapdoor, it is intractable toopen the same commitment to two different messages.
Perfect hiding: the commitments of any two messages have the same distribution.
Trapdoor: given an access to the original message, the randomizer and the
trapdoor, one can open the commitment to an arbitrary message.
Let z ∈ {1, 2}. Assume that k > 0 and u 6∈ [0, k] are public parameters. LetΨk,u := [0, k] ∪ {u}. We use the following ([0, k], u) trapdoor commitment schemefrom [21]. For parm ← Gbp (1κ ), gz ←r Gz \ {1} and the trapdoor (σ, α) ← Z2p

6

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhangi(with σ 6= 0), let the common reference string be ck = (gz , gzα )σ. Thei∈Ψk,ucommmon reference string ck is made public, while the trapdoor(σ, α) is only
Qk 
i ai
3
used in security proofs. Define comck ((a0 , . . . , ak ); r) := i=0 (gz , gzα )σ
·

u Pk
i
α σu rα rσ + i=0 ai σ
(gz , gz )= (gz , gz ). The computation of com can be sped up
by using efficient multi-exponentiations algorithms [43,41]. Groth [28] and Lipmaa [36] used a similar trapdoor commitment scheme, but with u = 0. (Seealso [27].) In our arguments, the case of an arbitrary u is more suitable, though
we can also modify them to work in the case u = 0.
Let Λ ⊆ Zp . A bilinear group generator Gbp is Λ-PSDL (power symmetricdiscrete logarithm) secure [36], if for any NUPPT adversary A, the following
probability is negligible in κ:"#parm := (p, G1 , G2 , GT , ê) ← Gbp (1κ ), g1 ←r G1 \ {1} ,Pr.
iig2 ←r G2 \ {1} , σ ←r Zp : A(parm; (g1σ , g2σ )i∈Λ ) = σ
For algorithms A and XA , we write (y; yX ) ← (A||XA )(σ) if A on input σ
outputs y, and XA on the same input (including the random tape of A) outputs
yX . Let z ∈ {1, 2}. Let Λ ⊂ Zp . Gbp is Λ-PKE (power knowledge of exponent)
secure [28,36] in Gz if for any NUPPT A there exists an NUPPT extractor XA ,such that the following probability is negligible in κ:parm := (p, G1 , G2 , GT , ê) ← Gbp (1κ ), gz ←r Gz \ {1} , (α, σ) ←r Z2p , crs ← parm; ((gz , g α )σi )i∈Λ , (c, ĉ; (ai )i∈Λ ) ← (A||XA )(crs) :

z
 .
Pr 


Y


α
ai σ iĉ = c ∧ c 6=gzi∈ΛLet z = 1. Consider a CRS ck that in particular specifies g2 , ĝ2 ∈ G2 . A
commitment (C, Ĉ) ∈ G21 is valid, if ê(C, ĝ2 ) = ê(Ĉ, g2 ). The case z = 2 is dual.
As shown in [21], the ([0, k], u) trapdoor commitment scheme is perfectly hiding, and computationally binding under the Ψk,u -PSDL assumption. Moreover,
if the Ψk,u -PKE assumption holds, then for any NUPPT A that outputs a valid
commitment C, there exists a NUPPT extractor that, given A’s input together
with A’s random coins, extracts a valid opening of C.
Non-Interactive Zero Knowledge (NIZK). NIZK proofs [8] allow theprover to convince the verifier that some input x belongs to some NP language L in the manner that nothing else expect the truth of the statement isrevealed. It is well-known that NIZK proofs do not exist without trusted setups
unless P = NP. There are two popular approaches to deal with this. The first
approach, the use of random oracle model, results often in very efficient protocols. It is well known [12,26] that some protocols that are secure in the random
3

Here and in what follows, elements of the form (g, g α )x , where α is a secret random
key, can be thought of as a linear-only encoding of x, see [5] for a discussion

Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

7

oracle model are non-instantiable in the standard model, and thus the random
oracle model is a heuristic at its best.
A better approach is to construct NIZK proofs in the common reference
string (CRS) model [8]. Many verifiers can then later independently verify theproof, by having access to the same CRS. The proof has to be complete, soundand satisfy the zero-knowledge property. In practice, one is interested in proofs
where both the proof length and verification time are sublinear in the statement
size. Such succinct proofs cannot be statistically sound, and their soundness
cannot be proven under falsifiable assumptions [25]. The latter means that one
has to employ knowledge assumptions [16]. A computationally sound proof isalso known as an argument. Succinct NIZK arguments have been proposed for
languages like Circuit-SAT [28,36,24,3,37], Range [14,21], Set Partition,
Subset Sum and Decision Knapsack [21]. While several of these arguments
are efficient, they are all highly technical, and based on a careful combination of
already complex basic arguments.
More formally, an NIZK argument for a language L consists of three algorithms, Gencrs , Pro and Ver. The CRS generation algorithm Gencrs takes as input
1κ (and possibly some other, public, language-dependent information) and outputs the prover’s CRS crsp , the verifier’s CRS crsv , and the trapdoor td. (Thedistinction between crsp and crsv is not important for security, but in many applications crsv is much shorter.) The prover’s algorithm Pro takes as an input
crsp together with a statement x and a witness w, and outputs an argument π.
The verifier’s algorithm Ver takes as an input crsv together with a statement x
and an argument π, and either accepts or rejects.
We expect the argument to be (i) perfectly complete (the honest verifier
always accepts the honest prover), (ii) perfectly zero knowledge (there exists
an efficient simulator who can, given x, crsp and td, output an argument thatcomes from the same distribution as the argument produced by the prover), and(iii) computationally sound (if x 6∈ L, then an arbitrary NUPPT prover has only
a negligible success in creating a satisfying argument). We refer to say [28,36]
for formal definitions.

3

New Succinct Trapdoor Multiset Commitment Scheme

To succinctly commit to a multiset A, we represent A as a null set
Q (with multiplicities) of a polynomial. For a multiset A ⊂ Zp , let χA (X) := a∈A (X − a),where every a has been counted with its multiplicity. For example, χ{1,1,2} (X) =(X − 1)2 (X − 2).
Let z ∈ {1, 2}, and let k = |A| (recall that |A| includes the multiplicities of all elements) and u 6∈ [0, k] be again public parameters. To commit to a multiset A, we use the ([0, k], u) trapdoor commitment schemefrom [21]. Again, we first choose parm ← Gbp (1κ ) and α, σ ←r Zp , and theniset ck ← (parm, ((gz , gzα )σ )i∈Ψk,u ) to be the common reference string. We
then define comck (A; r) := comck (χA (σ); r). More precisely, the committer asPkisumes that χA (X) =i=0 si X for some coefficients si , and then computes

8

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang

comck (A; r) :=

Qk

i=0



(gz , gzα )σisi· (gz , gzα )σur

for r ←r Zp . The trapdoor isequal to td ← (α, σ).
Theorem 1. Suppose z ∈ {1, 2}. The described trapdoor multiset commitment
scheme is hiding and, under the Ψk,u -PSDL assumption, computationally binding. If the Ψk,u -PKE assumption holds in Gz , then one can also extract thecontents of the commitment.
Proof. The proof follows [21]. Perfect Hiding: follows from the fact that if r
χ (σ)+rσ u
is uniformly random in Zp , then gz A
is a uniformly random element ofGz and thus does not depend on A. Computational Binding: assume that anadversary can efficiently produce (s1 , . . . , sk ; r) and (s01 , . . . , s0k ; r0 ) with si 6= s0i
Pk
Pk
i
u
0 i
0 u
=
for some i, such that loggz c =i=0 si σ + rσ
i=0 si σ + r σ . Then
Pk
P
k
i
u
0
0 i
0 u
f (X) =
are two different
i=0 si X + rX and f (X) =i=0 si X + r X
polynomials. Thus, d(X) = f (X) − f 0 (X) is a non-zero polynomial such thatd(σ) = 0. By using efficient polynomial factorization [34], we can find all possibleroots of d, and then find σ by comparing for each root x the value gzx with thegiven gzσ in ck.
Trapdoor: given td, ck, (A, r), (C, C 0 ) = comck (A; r) and A0 , one can compute r0 such that (C, C 0 ) = comck (A0 ; r0 ) by using the fact that loggz C =P
P 0 i
si σ i + rσ u =si σ + r0 σ u .
Extraction: follows straightforwardly from the Ψk,u -PKE assumption. tu

4

New Pairwise Multiset Sum Equality Test Argument

In a pairwise multiset sum equality test (PMSET) argument, the prover aims toconvince the prover, that he knows how to open given four commitments Cj tofour multisets Aj , for j ∈ {1, 2, 3, 4}, such that A1 ] A2 = A3 ] A4 , where inboth sides, the multiplicities of all elements are summed up. That is, we have
1A1 (i) + 1A2 (i) = 1A3 (i) + 1A4 (i) for all i ∈ Zp . In addition to that, one can also
upperbound |Aj | by some public value kj .
The intuition of the new PMSET argument is as follows. The prover commits
to Aj , for j ∈ {1, 2, 3, 4}, by using the multiset commitment scheme of Sect. 3.
After that, the prover creates a short NIZK argument to show that
χA1 (σ)χA2 (σ) = χA3 (σ)χA4 (σ) .

(1)

If one does not randomize the commitments, the use of the trapdoor commitment
scheme from [21] makes the corresponding NIZK argument relatively (but notcompletely) straightforward. To take into account the fact that the commitment
scheme is randomized, we let the prover also to create a crib E that enables theverifier to verify Eq. (1) on committed elements.
Moreover, due to technical reasons, the prover also has to add extra elements(Dj , ∆j ), j ∈ {1, 2, 3, 4}, to the argument. These elements make it possible
for the simulator to simulate the NIZK argument, and are necessary since theEfficient Non-Interactive Zero Knowledge Arguments for Set Operations

9commitments Cj are a part of the statement (i.e., the input of the prover) andnot a part of the NIZK argument. Here, Dj is basically an alternative random
commitment to Aj , while ∆j is an element that makes it possible to verify that
Dj was created correctly. In the simulation, Dj are chosen uniformly and at
random, and ∆j will be set so that the verification still accepts. Such a design
also increases the compatibility of our argument; namely the four multisets tobe proven can be arbitrarily committed in either G1 or G2 . This allows theprover to freely compose our arguments for some complex (multi)set relations.
Without loss of generality, in the remaining of this section, we assume that all
the commitments in the statement are in G1 .
Thus, in the new argument, the prover creates new random commitments Dj
to Aj for j ∈ {1, 2, 3, 4}, together with ∆j and the crib E. Since we will use aknowledge assumption, all elements have an accompanying knowledge component.
By relying on suitable assumptions, from Eq. (1) we obtain that
χA1 (X)χA2 (X) = χA3 (X)χA4 (X), and thus in particular χA1 (X)χA2 (X) andχA3 (X)χA4 (X) have the same roots with the same multiplicities. Therefore, theverifier is convinced that A1 ] A2 = A3 ] A4 (and due to the use of a knowledge
assumption, that the prover actually knows all four multisets).
We relax the multiset commitment scheme of Sect. 3 slightly, by allowingχAj (X) to be any polynomial that has Aj as its null set (with correct multiplicities). This relaxation allows us to achieve the following property. Recall that
P the cardinality of a multiset counts the multiplicities of its elements,|A| = a 1A (a) = deg χA (X). In the new PMSET argument, one sets an upper bound kj to the cardinality of the multiset Aj , |Aj | ≤ kj , before creating
Pkj
the CRS. Hence, χAj (X) = i=0
sji X i for some coefficients sji . As we will see
later, setting different kj to related values makes it possible to design interesting
variations of the PMSET argument.
We do not know how to achieve such flexibility without the relaxation of theprevious paragraph: without it, the committed polynomial χAj has to be monic,
and thus in the committed subset argument one has to check that a specificcoefficient of χAj is equal to 1. This would mean that the cardinality of Aj has
to be known before even creating the CRS. In our case, one just has an upperbound on |Aj |, and thus our arguments are size-hiding which allows to build
zero-knowledge sets [39].
We note that we have another complication. We divide the commitment scheme into two partial commitment schemes as follows(com1ck (A; r), com2ck (A; r)) ← comck (A; r). (Thus, com2 is the knowledge
component of the commitment scheme.) Only com1ck (Aj ; rj ) is given as a partof the statement. To obtain soundness, it is necessary that the prover generates
com2ck (Aj ; rj ) as a part of the argument.
We now give a formal definition of the new PMSET argument(Gencrs , Pro, Ver). Here, the statement is (Cj )4j=1 where Cj = com1ck (Aj ; rj )4j=1 .
On the other hand, the witness is (Aj , rj )4j=1 . Note that most of the elements gijthat are used by the prover or the verifier include a secret component in their

10

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang

exponent and thus they are computed based on the elements that are a partof the CRS. To avoid filling the variable namespace, we will not assign special
variable names for all those elements.
CRS generation Gencrs (1κ , k1 , k2 , k3 , k4 ):Set parm := (p, G1 , G2 , GT , ê) ←r Gbp (1κ ); Set g1 ←r G1 \ {1} andg2 ←r G2 \ {1}; Set σ, α, β1 , β2 , β3 , β4 , η, γ ←r Zp with σ 6= 0; Setk ∗ ← max(k1 , k2 , k3 , k4 ); Set u ← k ∗ + 1;
For j ∈ {1, 2, 3, 4}: Let z = 1 if j ∈ {1, 3} and z = 2 if j ∈ {2, 4}; Setiiβckj ← (((gz , gz j )σ )i∈Ψkj ,u ); Set ck ← ((g1 , g1α )σ )i∈Ψk∗ ,u ;Output


i+u
∗
2u
,
crsp ← parm, ck, ck1 , ck2 , ck3 , ck4 , ((g2 , g2η )σ )ki=0 , (g2 , g2η )σucrsv ← parm, g1 , g2γ , g2σ , g1β1 , g1β3 , g2 , g2β2 , g2β4 , g2η ,td ←(σ, α, β1 , β2 , β3 , β4 , η, γ) .
Prover Pro(crsp ; (Cj )4j=1 ; (Aj , rj )4j=1 ):For j ∈ {1, 2, 3, 4}:Pkj(i) Write χAj (X) = i=0
sji X i ;02(ii) Set Cj ← comck (Aj ; rj );(iii) Set rj0 ←r Zp ;(iv) Set (Dj , Dj0 ) ← comckj (Aj ; rj0 );0(v) Set (∆j , ∆0j ) ← (g1 , g1γ )rj −rj ;Set(E, E 0 ) ←k1 Y(g2 , g2η )σ

i+u

k2 
r20 s1i Y
0
i+u r1 s2i·(g2 , g2η )σ
·

i=0
k3 
Y

i=0
k4 
 0
 0
Y
i+u −r4 s3i
i+u −r3 s4i(g2 , g2η )σ·(g2 , g2η )σ
·

i=0



2u
(g2 , g2η )σi=0

r10 r20 −r30 r40;


Output π ← (Cj0 , ∆j , ∆0j , Dj , Dj0 )4j=1 , E, E 0 ;Verifier Ver(crsv ; (Cj )4j=1 ; π): Accept if(a) Verify knowledge components:– For j ∈ {1, 2, 3, 4}, ê(∆0j , g2 ) =? ê(∆j , g2γ ),– For j ∈ {1, 2, 3, 4}, ê(Cj0 , g2 ) =? ê(Cj , g2α ),– ê(D10 , g2 ) =? ê(D1 , g2β1 ), ê(g1 , D20 ) =? ê(g1β2 , D2 ), ê(D30 , g2 ) =?
ê(D3 , g2β3 ), ê(g1 , D40 ) =? ê(g1β4 , D4 ),– ê(g1 , E 0 ) =? ê(g1η , E),(b) Verify that Cj and Dj commit to the same multisets:u– For j ∈ {1, 3}, ê(Cj /Dj , g2 ) =? ê(∆j , g2σ );u?
– For j ∈ {2, 4}, ê(Cj , g2 )/ê(g1 , Dj ) = ê(∆j , g2σ );Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

11(c) Verify that A1 ] A2 =? A3 ] A4 : ê(g1 , E) =? ê(D1 , D2 )/ê(D3 , D4 ).
Otherwise, reject.
Theorem 2. The argument of the current subsection is a perfectly complete andperfectly zero-knowledge argument that the prover knows how to open Cj as amultiset Aj for j ∈ {1, 2, 3, 4}, such that A1 ] A2 = A3 ] A4 and |Aj | ≤ kj for
j ∈ {1, 2, 3, 4}. Let Ψk∗ ,u,2u := [0, k ∗ ] ∪ [u, k ∗ + u] ∪ {2u}. Moreover:– If the Ψk∗ ,u,2u -PSDL, the Ψk1 ,u -PKE and Ψk3 ,u -PKE assumption in G1 , theΨk2 ,u -PKE and the Ψk4 ,u -PKE and the ([u, u + k ∗ ] ∪ {2u})-PKE assumption
in G2 hold, then it is computationally sound.
– If the Ψk1 ,u -PKE assumption and the Ψk3 ,u -PKE assumption hold in G1 andthe Ψk2 ,u -PKE assumption and the Ψk4 ,u -PKE assumption hold in G2 , thenit is an argument of knowledge.
We remark that to simplify the claim, one can combine the the different PKE
assumptions into one (stronger than necessary) PKE assumption, but we preferred to state precise assumptions. For example, (Ψ1 ∪ Ψ2 )-PKE implies bothΨ1 -PKE and Ψ2 -PKE, but the opposite direction does not necessarily hold.
Proof. Let h = ê(g1 , g2 ). Completeness: It is easy to see that if the prover ishonest, then all the equations
but P
the last one hold.
Pk1
Q For the veryQlast equak2
tion, note that since ( i=0s1i σ i )( i=0s2i σ i ) =(σ −i∈A1 (σ − i) ·
2
Q
Q
P
Pki∈A
k3
4
i) = i∈A1 ]A2 (σ − i) = i∈A3 ]A4 (σ − i) = · · · = ( i=0s3i σ i )( i=0s4i σ i ),
 Pk

Pk2
1 s σ i +r 0 σ u
s σ i +r20 σ u
1we get logh ê(D1 , D2 ) = logh ê g1 i=0 1i, g2 i=0 2i
=
P
 P

Pk1 0
k1
k2
i
0 u
i
0 u
= χA1 ]A2 (σ) + i=0
r2 s1i σ i+u +i=0 s1i σ + r1 σi=0 s2i σ + r2 σ
Pk2 0
r1 s2i σ i+u + r10 r20 σ 2u , and analogously logh ê(D3 , D4 ) = χA3 ]A4 (σ) +
Pi=0
Pk4 0
k3
0
i+u
0 0 2u+ i=0
r3 s4i σ i+u +r. Thus, logh (ê(D1 , D2 )/ê(D3 , D4)) =i=0 r4 s3i σ
P
3 r4 σP
P
Pk4 0
k1
k
k3
2
0
i+u
0
i+u
0
i+u
i+u
r
s
σ
+
r
s
σ
r
−
s
σ
+
r
s
σ
+
i=0 2 1ii=0 1 2ii=0 4 3ii=0 3 4i(r10 r20 − r30 r40 ) σ 2u = logh E.
Zero-Knowledge: In the real execution, the variables Cj , Dj , ∆j , and E
are distributed randomly, modulo the last verification equation. Moreover, Cj0 ,Dj0 , ∆0j , and E 0 are such that the verification equations on line (a) hold.
The simulator, who knows td but does not know the witness, will simulate
the proof as follows.
β∗
β∗
β∗
β∗
1. Let D1 ← g1 1 , D2 ← g2 2 , D3 ← g1 3 , D4 ← g2 4 for β1∗ , β2∗ , β3∗ , β4∗ ←r Zp .
 u
−β ∗ 1/σ. It is obvious that
2. For j ∈ {1, 2, 3, 4}, set ∆j ←Cj g1 j


∗

u
−β
for j ∈ {1, 3} andê(Cj /Dj , g2 ) = ê Cj g1 j , g2
= ê ∆j , g2σ


∗
u
−βj∗
ê(Cj , g2 )/ê(g1 , Dj ) = ê Cj g1 , g2 ê(g1 , g2 )βj /ê(g1 , Dj ) = ê ∆j , g2σ forj ∈ {2, 4}.
3. Choose E so that the last verification equation holds, that is, E ←∗ ∗∗ ∗β ∗ β ∗ −β ∗ β ∗g2 1 2 3 4 . Clearly, ê(D1 , D2 )/ê(D3 , D4 ) = ê(g1 , g2 )β1 β2 −β3 β4 = ê(g1 , E).

12

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang
β4. Now, set Cj0 ← Cjα , ∆0j ← ∆γj , Dj0 ← Dj j for j ∈ {1, 2, 3, 4}, and E 0 ← E η .
Such a choice satisfies the verification equations on line (a).
5. Finally, let π ← ((Cj0 , ∆j , ∆0j , Dj , Dj0 )4j=1 , E, E 0 ).
Since all verifications are satisfied and π comes from the correct distribution, then the simulation has been successful and the argument is perfect zeroknowledge.
Computational soundness: Assume that an adversary A can break thesoundness assumption. We construct another adversary Apsdl that breaks theΨk∗ ,u,2u -PSDL assumption as follows.
Assume that all the required knowledge assumptions hold. Therefore, we canextract the following values:– For j ∈ {1, 2, 3, 4}, by the Ψkj ,u -PKE assumption in G1 , from (Cj , Cj0 ) the
Pkj
adversary obtains a polynomial fj (X) = i=0
sji X i +rj X u , such that Cj =fj (σ)
g1.
– For j ∈ {1, 2, 3, 4}, by the {0}-PKE assumption in G2 , from (∆j , ∆0j ) theδ

adversary obtains δj such that ∆j = g1j . (Note that the {0}-PKE assumption
follows from the Ψkj ,u -PKE assumption.)– For j ∈ {1, 2, 3, 4}: let z = 1 for j ∈ {1, 3} and z = 2 for j ∈ {2, 4}. By
the Ψkj ,u -PKE assumption in Gz , from (Dj , Dj0 ) the adversary obtains a
Pkj 0 if 0 (σ)polynomial fj0 (X) = i=0
sji X + rj0 X u , such that Dj = gz j .
– By the ([u, u+k ∗ ]∪{2u})-PKE assumption in G2 , from (E, E 0 ) the adversary
Pk∗
fˆ(σ)
obtains a polynomial fˆ(X) = i=0 ŝi X u+i + r̂X 2u , such that E = g2 .
If any extraction does not succeed, then Apsdl aborts (this happens with a negligible probability). Assume now that Apsdl does not abort.
uSince for j ∈ {1, 3}, ê(Cj /Dj , g2 ) = ê(∆j , g2σ ) holds, we have fj (σ)−fj0 (σ) =δj σ u . Therefore, if for some i, j, sji 6= s0ji or δj 6= tj − rj we have a non-zeropolynomial d(X) := fj (X) − fj0 (X) − δj X u , such that d(σ) = 0. Note that σ 6= 0,
so Apsdl uses an efficient polynomial factorization algorithm [34] to find all rootsof d(X), and then tests for which root x it holds that (say) g1x = g1σ . Thus,
Apsdl has found σ and broken the Ψk∗ ,u -PSDL assumption (and thus also theΨk∗ ,u,2u -PSDL assumption).
Analogously, Apsdl can break the Ψk∗ ,u -PSDL assumption if for some i, sji 6=
s0ji or δj 6= tj − rj in the case j ∈ {2, 4}.
Assuming that the adversary did not already break the Ψk∗ ,u -PSDL assumption, we now have that for all j ∈ {1, 2, 3, 4}, (Dj , Dj0 ) and (Cj , Cj0 ) commit to
the same set, let it be Aj .
Finally, due to the last verification equation, we have fˆ(σ) = f10 (σ)f20 (σ) −0f3 (σ)f40 (σ). This means that, defining d(X) := f10 (X)f20 (X) − f30 (X)f40 (X) −P 0 i P 0 iP 0 i  P 0 i  Pk∗
fˆ(X) =s1i X
s2i X −s3i X
s4i X + i=0 ci X i+u + c0 X 2u
0
for some coefficients ci and c , we have d(σ) = 0.
Since A succeeded in cheating, it must be the case that d(X) is a nonzero polynomial. But in this case, Apsdl has obtained a non-zero polynomial
d(X) where d(σ) = 0 for some unknown σ. Apsdl uses an efficient polynomial
factorization algorithm [34] to find all roots of d(X), and then tests for whichEfficient Non-Interactive Zero Knowledge Arguments for Set Operations

13

root x it holds that (say) g1x = g1σ . Thus, Apsdl has found σ and broken theΨk∗ ,u,2u -PSDL assumption.
Thus, (Dj , Dj0 ) commit to the sets Aj such that A1 ] A2 = A3 ] A4 . We
have already established before that (Cj , Cj0 ) and (Dj , Dj0 ) commit to the samevalues. The claim follows.
Argument of knowledge: follows from the last claim of Thm. 1.
tu
Clearly, the communication complexity of this argument is Θ(1) group elements and the verifier’s computational complexity is dominated by Θ(1) pairings. The verifier’s CRS length contains the parameters parm and Θ(1) groupelements. On the other hand, the prover’s CRS length, the CRS computation,and the prover’s computation are Θ(k) group elements or operations respectively. Once again, the computation can be sped up by using efficient multiexponentiation algorithms [43,41].

Balancing. One can design a balanced version of the new √subset argument asfollows. Let k = |A1 ] A2 |. Partition
both A1 and A2 into ≈ k subsets A1i and√
A2i , so that |A1i ] A2i | ≈ k. Partition A3 and A4 in a similar way, so that
A1i ] A2i = A3i ] A4i . Now, the√PMSET argument that A1 ] A2 = A3 ] A4 is justequal to the concatenation of k PMSET arguments that A1i ] A2i = A3i ] A4i .
Clearly, in this balanced version,√ the CRS length, the verifier’s computation,and the communication are Θ( k), that is, sublinear in k. On the other hand,the prover’s computational complexity is still Θ(k). However, Θ(k) total work isclearly a lower bound for arbitrary sets Aj .

5

Applications

Next, we show how to apply the new PMSET argument to construct arguments
for standard (multi)set operations, such as intersections, unions, and complements. In such arguments, the prover wants to convince the verifier that its
three committed (multi)sets A, B, C satisfy relations like A ⊆ B, A = B ∩ C,
A = B ∪ C or A = B \ C. We first note that one can clearly modify the PMSET
argument so that to allow any subset of {A, B, C, D} to be publicly known sets
(e.g., C = ∅). This just means that canonical commitments of the public sets
are included to the CRS. One has to obviously take care about including only
the correct knowledge components to the CRS, but we omit further discussion
because of the lack of space.
In what follows, let U be some publicly known universal set. For efficiency
reasons, it is required that U is not too large; this is usually not a too restrictive
assumption. In fact, in many cases U has been fixed by the application and one
has to verify among other things that all sets belong to U. E.g., in the case of
e-voting, U can be the set of all candidates, and in the case of e-auctions, U canbe the set of bids (or in combinatorial auctions, the set of all auctioned goods).

14

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang

Is-a-Sub(multi)set argument. Clearly, A ⊆ B (i.e., 1A (a) ≤ 1B (a) for all a ∈ U)
iff A ] C = ∅ ] B, for some (committed) multiset C. Thus, the prover simply
provides a commitment to C as a part of the is-a-subset argument, and thendirectly utilizes the PMSET argument.
Is-a-Set argument. A committed multiset A is a set (i.e., 1A (a) ≤ 1 for all a) if
A ⊆ U. Thus, for example to show that A ⊆ B where A and B are both sets, one
has to show that A ⊆ B and B ⊆ U by using the argument from the previous
paragraph. Note that having an upper bound on |C| effectively enforces an lower
bound on |A|.
Multiset-Sum argument. Multiset sum is trivial, as C = A ] B iff A ] B = C ] ∅.
Set-Intersection-And-Union argument. Set intersection and union are closely
related. Suppose the prover wants to show that the given four committed sets
A, B, C, D ⊆ U satisfy C = A ∩ B and D = A ∪ B. For this it is sufficient toshow that A ] B = C ] D, C ⊆ A, C ⊆ B and that A, B and D are sets.
Really, if A, B and D are sets, and C ⊆ A then also C is a set. Thus, for alla, 1A (a), 1B (a), 1C (a), 1D (a) ∈ {0, 1}. If 1A (a) = 1B (a) = 0, then also 1C (a) =1D (a) = 0. If 1A (a) = 1B (a) = 1, then 1C (a) + 1D (a) = 2. But since C and D
are sets, then 1C (a) = 1D (a) = 1. If 1A (a) = 0 and 1B (a) = 1 (the opposite caseis similar), then 1C (a) + 1D (a) = 1. But since C ⊆ A, 1C (a) = 0 and 1D (a) = 1.
Thus, C = A ∩ B and D = A ∪ B.
Set-Difference argument. To show that committed sets A, B, C ⊆ U satisfy A =B\C (i.e., 1A (a) = max(0, 1B (a)−1C (a)) for all a), the prover shows (by using the
set-intersection-and-union argument from the previous paragraph) that A∩C = ∅and A ∪ C = B ∪ C. Since ∅ is not committed to, one can somewhat simplify the
resulting argument (e.g., one does not have to verify that ∅ ⊆ A).
Accumulators. We can extend the applications to the case of cryptographic
accumulators [4], where given committed S and a public k, one has to present a
short proof of either k ∈ S or k 6∈ S. In this case, one is traditionally not interested
in privacy, but the proofs should be sound. More precisely, given k ∈ S, we cangive a PMSET argument that {k} ∪ S0 = S for some committed multiset S0 .
Similarly, given k 6∈ S, we can give a PMSET argument that {k} ∪ S00 = U \ S forsome committed multiset S00 . In both cases, one can additionally use an is-a-set
argument to show that S (or S00 , in the k 6∈ S case) is a set. This also means that
we can implement a dynamic accumulator [11], by first showing that k ∈ S (ork 6∈ S) and then using commitment to S0 as the accumulator for S \ {k} (resp.,
commitment to S ∪ {k} as the accumulator for S ∪ {k}).
Acknowledgments. The first two authors were supported by the Estonian
Research Council, and European Union through the European Regional Development Fund. The third author was supported by Project FINER, Greek
Secretariat of Research and Technology, and by ERC project CODAMODA.

Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

15

References
1. Abe, M. (ed.): ASIACRYPT 2010, LNCS, vol. 6477. Springer, Heidelberg
2. Barreto, P.S.L.M., Naehrig, M.: Pairing-Friendly Elliptic Curves of Prime Order.
In: Preneel, B., Tavares, S.E. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331.
Springer, Heidelberg
3. Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C:
Verifying Program Executions Succinctly and in Zero Knowledge. In: Canetti, R.,
Garay, J. (eds.) CRYPTO (2) 2013. LNCS, vol. 8043, pp. 90–108. Springer, Heidelberg
4. Benaloh, J., de Mare, M.: One-Way Accumulators: A Decentralized Alternative to
Digital Signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp.
274–285. Springer, Heidelberg
5. Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct Noninteractive Arguments via Linear Interactive Proofs. In: Sahai, A. (ed.) TCC 2013.
LNCS, vol. 7785, pp. 315–333. Springer, Heidelberg
6. Blanton, M., Aguiar, E.: Private and oblivious set and multiset operations. In:
Youm, H.Y., Won, Y. (eds.) ASIACCS 2012. pp. 40–41. ACM
7. Blaze, M. (ed.): FC 2002, LNCS, vol. 2357. Springer, Heidelberg
8. Blum, M., Feldman, P., Micali, S.: Non-Interactive Zero-Knowledge and Its Applications. In: STOC 1988. pp. 103–112. ACM Press (May 2–4, 1988)
9. Boudot, F.: Efficient Proofs That a Committed Number Lies in an Interval. In:
Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer,
Heidelberg
10. Camenisch, J., Chaabouni, R., shelat, a.: Efficient Protocols for Set Membershipand Range Proofs. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp.
234–252. Springer, Heidelberg
11. Camenisch, J., Lysyanskaya, A.: Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In: Yung, M. (ed.) CRYPTO 2002.
LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg
12. Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited.
In: Vitter, J.S. (ed.) STOC 1998. pp. 209–218
13. Chaabouni, R., Lipmaa, H., shelat, a.: Additive Combinatorics and Discrete Logarithm Based Range Protocols. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010.
LNCS, vol. 6168, pp. 336–351. Springer, Heidelberg
14. Chaabouni, R., Lipmaa, H., Zhang, B.: A Non-Interactive Range Proof with Constant Communication. In: Keromytis, A. (ed.) FC 2012. LNCS, vol. 7397, pp.
179–199. Springer, Heidelberg
15. Cramer, R., Gennaro, R., Schoenmakers, B.: A Secure and Optimally EfficientMulti-Authority Election Scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS,
vol. 1233, pp. 103–118. Springer, Heidelberg
16. Damgård, I.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp.
445–456. Springer, Heidelberg
17. Damgård, I., Jurik, M.: A Generalisation, a Simplification and Some Applicationsof Paillier’s Probabilistic Public-Key System. In: Kim, K. (ed.) PKC 2001. LNCS,
vol. 1992, pp. 119–136. Springer, Heidelberg
18. D’Arco, P., Gonzalez Vasco, M.I., Pérez del Pozo, A.L., Soriente, C.: Size-Hiding in
Private Set Intersection: Existential Results and Constructions. In: Mitrokotsa, A.,
Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 378–394. Springer,
Heidelberg

16

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang

19. Dimitriou, T., Foteinakis, D.: A Zero Knowledge Proof for Subset Selection froma Family of Sets with Applications to Multiparty/Multicandidate Electronic Elections. LNCS, vol. 3416, pp. 100–111. Springer, Heildeberg
20. Dwork, C., Naor, M.: Zaps and Their Applications. In: FOCS 2000. pp. 283–293.
IEEE Computer Society Press
21. Fauzi, P., Lipmaa, H., Zhang, B.: Efficient Modular NIZK Arguments from Shiftand Product. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds.) CANS 2013.
LNCS, vol. 8257, pp. 92–121. Springer, Heidelberg
22. Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identificationand Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263,
pp. 186–194. Springer, Heidelberg
23. Freedman, M.J., Nissim, K., Pinkas, B.: Efficient Private Matching and Set Intersection. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027,
pp. 1–19. Springer, Heidelberg
24. Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic Span Programs and
NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013.
LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg
25. Gentry, C., Wichs, D.: Separating Succinct Non-Interactive Arguments from All
Falsifiable Assumptions. In: Vadhan, S. (ed.) STOC 2011. pp. 99–108. ACM Press
26. Goldwasser, S., Kalai, Y.T.: On the (In)security of the Fiat-Shamir Paradigm. In:
FOCS 2003. pp. 102–113. IEEE, IEEE Computer Society Press
27. Golle, P., Jarecki, S., Mironov, I.: Cryptographic Primitives Enforcing Communication and Storage Complexity. In: Blaze [7], pp. 120–135
28. Groth, J.: Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In:
Abe [1], pp. 321–340
29. Henry, R., Goldberg, I.: All-but-k Mercurial Commitments and their Applications.
Tech. Rep. 26, Centre for Applied Cryptographic Research (Dec 2012), available
at http://cacr.uwaterloo.ca/techreports/2012/cacr2012-26.pdf
30. Hess, F., Smart, N.P., Vercauteren, F.: The Eta Pairing Revisited. IEEE Transactions on Information Theory 52(10), 4595–4602 (2006)
31. Jarecki, S., Liu, X.: Efficient Oblivious Pseudorandom Function with Applications
to Adaptive OT and Secure Computation of Set Intersection. In: Reingold, O. (ed.)
TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg
32. Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-Size Commitments to Polynomials and Their Applications. In: Abe [1], pp. 177–194
33. Kissner, L., Song, D.: Privacy-Preserving Set Operations. In: Shoup, V. (ed.)
CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg
34. Lenstra, A.K., Lenstra, Jr., H.W., Lovász, L.: Factoring Polynomials with Rational
Coefficients. Mathematische Annalen 261, 513–534 (1982)
35. Lipmaa, H.: On Diophantine Complexity and Statistical Zero-Knowledge Arguments. In: Laih, C.S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 398–415.
Springer, Heidelberg
36. Lipmaa, H.: Progression-Free Sets and Sublinear Pairing-Based Non-Interactive
Zero-Knowledge Arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp.
169–189. Springer, Heidelberg
37. Lipmaa, H.: Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013 (1). LNCS, vol. 8269, pp. 41–60. Springer, Heidelberg
38. Lipmaa, H., Asokan, N., Niemi, V.: Secure Vickrey Auctions without Threshold
Trust. In: Blaze [7], pp. 87–101

Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

17

39. Micali, S., Rabin, M.O., Kilian, J.: Zero-Knowledge Sets. In: FOCS 2003. pp. 80–
91. IEEE, IEEE Computer Society Press
40. Pereira Geovandro, C.C.F., Simplı́cio Jr., M.A., Naehrig, M., Barreto, P.S.L.M.:
A Family of Implementation-Friendly BN Elliptic Curves. Journal of Systems andSoftware 84(8), 1319–1326 (2011)41. Pippenger, N.: On the Evaluation of Powers and Monomials. SIAM J. Comput.
9(2), 230–250 (1980)
42. Rial, A., Kohlweiss, M., Preneel, B.: Universally Composable Adaptive Priced
Oblivious Transfer. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol.
5671, pp. 231–247. Springer, Heidelberg
43. Straus, E.G.: Addition Chains of Vectors. American Mathematical Monthly 70,
806–808 (1964)

A

Related Work

Our multiset commitment scheme is a modification of the (what we call a FLZ)
commitment scheme [21], which in turn is related to the polynomial commitment
scheme of [32]. In [32], the authors proposed a commitment scheme for polynomials f , where instead of committing to the coefficients of f separately, one
commits to f (σ), where σ is a random key. Their commitment scheme is basedon the fact that for any polynomial f , x − i divides f (x) − f (i). Our commitment
scheme is somewhat more efficient than the one from [32], since [32] required therandomness r also to be a polynomial. Thus, one needs to generate deg(f ) times
more randomness, and the opening of the commitment is also more burdensome.
While the need for a new commitment scheme was motivated by the applications
considered in [32], it is not necessary in our distinctively different applications.
Also, based on their commitment scheme, [32] proposed an NIZK proof thata specific public element belongs to the committed subset, which they named
zero knowledge sets. Henry and Goldberg [29] showed that this argument was
insecure, and provided a secure improvement. However, both these constructions
were interactive, and would either require a random oracle, or be less efficient to
get non-interactiveness. We provide a non-interactive implementation without
random oracles in our accumulator argument, which is as efficient as both [32]and [29].
The balanced version of our multiset commitment scheme is somewhat similar
to the setting in the electronic voting protocol of Dimitriou and Foteinakis [19],which had K disjoint but same size sets V1 , · · · VK with total cardinality C =K · |V1 |, and a prover commits to S such that√S ⊆ Vi for some i ∈ [1, K]. We candirectly compare when either K = 1 or K = C = |V1 |. But in both cases Dimitriou and Foteinakis require a separate zero-knowledge proof for each candidate,hence the prover’s computation, communication and verification
are all ω(C),√whereaswe
haveeitherΘ(C)prover’s
computation,Θ(C)
communicationand√Θ( C) verification (in the balanced version) or Θ(C) prover’s computation, constant communication and constant verification (in the non-balanced version).
In terms of set operations, there is a lot of related research in the literature.
We denote k to be an upper bound for the size of the client’s and server’s sets (or18Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang

the maximum of the two, if an upper bound is not required). Freedman, Nissim
and Pinkas presented a two-party private matching and set intersection protocol [23], where the client inputs a private set C, and the server inputs a private
set S; if si ∈ S ∩ C, the client learns si , otherwise it learns a uniformly random
value. The proposed 2-round protocol requires oblivious pseudorandom functions(OPRF) and is provably secure in the random oracle model, but requires O(k)communication. Jarecki and Lim [31] improved upon this and used OPRF to
get a 1-round protocol secure in the random oracle model, and a 2-round protocol secure in the CRS model, both cases having O(k) communication. Both
protocols reveal the size of the server’s set.
Kissner and Song [33] proposed different privacy-preserving set operation
protocols that employed the concept of multi-sets. For example, the set union
operation is seen as simply the product of the polynomial representations of thetwo sets. They implement secure set intersection with a fixed and equal sizefor the client and server sets, using the fact that for random polynomials r, s,
χA r + χB s = χA∩B t with t having no roots from the universal set U, except fora negligible probability. However, their protocols have O(k) proof size, prover’s
computation and verification, with the overhead being a proof of correct polynomial multiplication. Moreover, they also have several operations on encrypted
polynomials, such as derivatives to reduce duplicated elements of a multiset.
These operations are costly, and we choose not to implement them as they will
require a product argument as in [21].
There are several other results on private set intersections that are not directly comparable to ours. For example, Blanton and Aguiar [6] had more efficient set operations than the work stated above based on efficient parallelized
multi-party operations, but it requires n > 2 parties while we focus on two-party
protocols. D’Arco et al. [18] showed that unconditionally secure size-hiding set
intersection is possible with the help of a trusted third party (TTP), given thatthe client and server have set cardinality at most k. However, the TTP sends
output to the client and server based on their specific sets. This means that evenfor a fixed server set V, the TTP is required for each new client set. Moreover,their 2-round, O(k)-communication protocol was only secure in the semi-honest
model. Extending it to become a protocol secure against malicious adversaries,
the proof size (that is dominated by proof of correct encryption for each of k
Paillier ciphertexts) will also become O(k).
We summarize in Table 1. Note that we only include results that either have
non-interactive zero knowledge proofs, or can be made non-interactive using theFiat-Shamir heuristic. None of the work discussed has 1 round (non-interactive),
does not require a random oracle and has proof size sublinear in the set cardinality, whereas our set operations have constant-size proof and is secure in the
CRS model.