Cryptology ePrint Archive: Report 2006/418

Analysis of Privacy-Preserving Element Reduction of Multiset

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

Abstract: 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.

Category / Keywords: Privacy-Preserving Operations, Set Operations, Element Reduction, Multi-party

Date: received 14 Nov 2006, last revised 15 Nov 2006

Contact author: jhsbhs at gmail com

Available formats: PDF | BibTeX Citation

Version: 20061119:194354 (All versions of this report)

Discussion forum: Show discussion | Start new discussion