Paper 2006/418

Analysis of Privacy-Preserving Element Reduction of Multiset

Jae Hong Seo, HyoJin Yoon, Seongan Lim, Jung Hee Cheon, and Dowon Hong


Among private set operations, the privacy preserving element reduction of a multiset can be an important tool for privacy enhancing technology as itself or in the combination with other private set operations. Recently, a protocol, over-threshold-set-union-protocol, for a privacy preserving element reduction method of a multiset was proposed by Kissner and Song in Crypto 2005. In this paper, we point out that there is a mathematical flaw in their polynomial representation of element reduction of a multiset and the resulting protocol error from the flaw in the polynomial representation of a multiset. We correct their polynomial representation of a multiset and propose an over-threshold-set-operation-protocol based on the corrected representation. Our over-threshold-set-operation-protocol can be combined with a privacy preserving set operation and outputs those elements appears over the predetermined threshold number times in the resulting multiset of set operation.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Privacy-Preserving OperationsSet OperationsElement ReductionMulti-party
Contact author(s)
jhsbhs @ gmail com
2006-11-19: received
Short URL
Creative Commons Attribution


      author = {Jae Hong Seo and HyoJin Yoon and Seongan Lim and Jung Hee Cheon and Dowon Hong},
      title = {Analysis of Privacy-Preserving Element Reduction of Multiset},
      howpublished = {Cryptology ePrint Archive, Paper 2006/418},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.