Cryptology ePrint Archive: Report 2011/138

Constant-Round Privacy Preserving Multiset Union

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

Abstract: 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 efficient PPMU protocols, using multiplicative homomorphic cryptosystem. The novelty of our protocol is to directly encrypt a polynomial by representing it by an element of an extension field. The resulting protocols consist of constant rounds and improve communication cost. We also prove the security of our protocol against malicious adversaries, in the random oracle model.

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

Date: received 20 Mar 2011

Contact author: jkim at theory snu ac kr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20110321:024414 (All versions of this report)

Short URL: ia.cr/2011/138

Discussion forum: Show discussion | Start new discussion