On Distributed k-Anonymization

Article type: Research Article

Authors: Zhong, Sheng

Affiliations: Computer Science and Engineering Department, State University of New York at Buffalo, Amherst, NY 14260, U. S. A. [email protected]

Note: [] Address for correspondence: Computer Science and Engineering Department, State University of New York at Buffalo, Amherst, NY 14260, U. S. A.

Abstract: When a database owner needs to disclose her data, she can k-anonymize her data to protect the involved individuals' privacy. However, if the data is distributed between two owners, then it is an open question whether the two owners can jointly k-anonymize the union of their data, such that the information suppressed in one owner's data is not revealed to the other owner. In this paper, we study this problemof distributed k-anonymization. We have two major results: First, it is impossible to design an unconditionally private protocol that implements any normal k-anonymization function, where normal k-anonymization functions are a very broad class of k-anonymization functions. Second, we give an efficent protocol that implements a normal k-anonymization function and show that it is private against polynomial-time adversaries. Our results have many potential applications and can be extended to three or more parties.

Keywords: k-anonymity, protocol, secure computation

Journal: Fundamenta Informaticae, vol. 92, no. 4, pp. 411-431, 2009