AuthorsP. Fauzi, H. Lipmaa and B. Zhang
EditorsN. Christin and R. Safavi-Naini
TitleEfficient Non-Interactive Zero Knowledge Arguments for Set Operations
Project(s)No Simula project
Publication TypeProceedings, refereed
Year of Publication2014
Conference NameFC 2014: Financial Cryptography and Data Security
Pagination216 - 233
PublisherSpringer Berlin Heidelberg
Place PublishedBerlin, Heidelberg
ISBN Number978-3-662-45471-8
ISSN Number0302-9743

We propose a non-interactive zero knowledge pairwise multiset sum equality test (PMSET)argument of knowledge 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. As a 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 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.

Citation Key26619