Cryptology ePrint Archive: Report 2008/523

Privacy Preserving Multiset Union with ElGamal Encryption

Jeongdae Hong and Jung Woo Kim and Jihye Kim and Kunsoo Park and Jung Hee Cheon

Abstract: The privacy preserving multiset union (PPMU) protocol allows a set of parties, each with a multiset, to collaboratively compute a multiset union secretly, meaning that any information other than union is not revealed. We propose an efficient PPMU protocol, using multiplicative homomorphic property of ElGamal encryption over F_q[x]=f(x) where q is a prime and f(x) is an irreducible polynomial over F_q. The protocol involves a constant number of rounds and improves the computation and communication complexities of the scheme proposed by Kissner and Song. We also prove the security of the protocol in the random oracle model.

Category / Keywords: cryptographic protocols / Privacy, Multiset Union, ElGamal Encryption, Homomorphic Encryption

Date: received 14 Dec 2008, withdrawn 19 Mar 2011

Contact author: jkim at theory snu ac kr

Available format(s): (-- withdrawn --)

Version: 20110319:141930 (All versions of this report)

Short URL: ia.cr/2008/523

Discussion forum: Show discussion | Start new discussion