Journal of the
Korean Mathematical Society
JKMS

ISSN(Print) 0304-9914 ISSN(Online) 2234-3008

Article

HOME ALL ARTICLES View

J. Korean Math. Soc. 2009; 46(1): 59-69

Printed January 1, 2009

Copyright © The Korean Mathematical Society.

Analysis of privacy-preserving element reduction of a multiset

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

Seoul National University, Seoul National University, Inha University, Seoul National University, and Electronics and Telecommunications Research Institute

Abstract

The element reduction of a multiset $S$ is to reduce the number of repetitions of an element in $S$ by a predetermined number. Privacy-preserving element reduction of a multiset is an important tool in private computation over multisets. It can be used by itself or by combination with other private set operations. Recently, an efficient privacy-preserving element reduction method was proposed by Kissner and Song [7]. In this paper, we point out a mathematical flaw in their polynomial representation that is used for the element reduction protocol and provide its correction. Also we modify their over-threshold set-operation protocol, using an element reduction with the corrected representation, which is used to output the elements that appear over the predetermined threshold number of times in the multiset resulting from other privacy-preserving set operations.

Keywords: privacy-preserving operations, set operations, element reduction, multi-party computations

MSC numbers: 94A60

Stats or Metrics

Share this article on :

Related articles in JKMS