Paper 2008/523

Privacy Preserving Multiset Union with ElGamal Encryption

Jeongdae Hong, Jung Woo Kim, Jihye Kim, 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.