Paper 2008/523

Privacy Preserving Multiset Union with ElGamal Encryption

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


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.

Available format(s)
-- withdrawn --
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
PrivacyMultiset UnionElGamal EncryptionHomomorphic Encryption
Contact author(s)
jkim @ theory snu ac kr
2011-03-19: withdrawn
2008-12-16: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.