## Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

Prastudy Fauzi, Helger Lipmaa and Bingsheng Zhang. Efficient Non-Interactive Zero Knowledge Arguments for Set Operations. In Nicolas Christin and Rei Safavi-Naini, editors, *FC 2014*, volume ? of *Lecture Notes in Computer Science*, pages ?--?, Barbados, March 3--7, 2014. Springer, Heidelberg.

**File:**
[.pdf (453 KB)] __pdf recommended__.

**Abstract**:

We propose a non-interactive zero knowledge \emph{pairwise multiset sum
equality test (PUTME)} argument of knowledge in the common reference string
(CRS) model that allows a prover to show that the given committed multisets
$\mathbf{A}_j$ for $j \in \set{1, 2, 3, 4}$ satisfy $\mathbf{A}_1
\uplus \mathbf{A}_2 = \mathbf{A}_3 \uplus \mathbf{A}_4$, i.e., every
element is contained in $\mathbf{A}_1$ and $\mathbf{A}_2$ exactly as
many times as in $\mathbf{A}_3$ and $\mathbf{A}_4$. As a corollary to
the PUTME 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 two other committed sets. The
new arguments have constant communication and 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.

**Slides:**

**Authors:**

Page by Helger Lipmaa. Send your inqueries to `<helger.lipmaa>gmail.com`.