Paper 2014/006

Efficient Non-Interactive Zero Knowledge Arguments for Set Operations

Prastudy Fauzi, Helger Lipmaa, and Bingsheng Zhang

Abstract

We propose a non-interactive zero knowledge \emph{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 $\AAA_j$ for $j \in \set{1, 2, 3, 4}$ satisfy $\AAA_1 \uplus \AAA_2 = \AAA_3 \uplus \AAA_4$, i.e., every element is contained in $\AAA_1$ and $\AAA_2$ exactly as many times as in $\AAA_3$ and $\AAA_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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. FC 2014
Keywords
Multisetsnon-interactive zero knowledgeset operation arguments
Contact author(s)
helger lipmaa @ gmail com
History
2014-01-06: revised
2014-01-05: received
See all versions
Short URL
https://ia.cr/2014/006
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/006,
      author = {Prastudy Fauzi and Helger Lipmaa and Bingsheng Zhang},
      title = {Efficient Non-Interactive Zero Knowledge Arguments for Set Operations},
      howpublished = {Cryptology ePrint Archive, Paper 2014/006},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/006}},
      url = {https://eprint.iacr.org/2014/006}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.