On the complexity of restricted k-anonymity problem
Paper
Paper/Presentation Title | On the complexity of restricted k-anonymity problem |
---|---|
Presentation Type | Paper |
Authors | Sun, Xiaoxun (Author), Wang, Hua (Author) and Li, Jiuyong (Author) |
Editors | Yanchun, Zhang |
Journal or Proceedings Title | Lecture Notes in Computer Science (Book series) |
Journal Citation | 4976, pp. 287-296 |
Number of Pages | 10 |
Year | 2008 |
Publisher | Springer |
Place of Publication | Germany |
ISSN | 1611-3349 |
0302-9743 | |
ISBN | 9783540788485 |
Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-540-78849-2_30 |
Web Address (URL) of Paper | https://link.springer.com/chapter/10.1007/978-3-540-78849-2_30 |
Web Address (URL) of Conference Proceedings | https://link.springer.com/book/10.1007/978-3-540-78849-2 |
Conference/Event | 10th Asia-Pacific Web Conference (APWeb 2008) |
Event Details | Rank C C |
Event Details | 10th Asia-Pacific Web Conference (APWeb 2008) Delivery In person Event Date 26 to end of 28 Apr 2008 Event Location Shenyang, China |
Abstract | One of the emerging concepts in microdata protection is k-anonymity, introduced by Samarati and Sweeney. k-anonymity provides a simple and efficient approach to protect private individual information and is gaining increasing popularity. k-anonymity requires that every tuple(record) in the microdata table released be indistinguishably related to no fewer than k respondents. In this paper, we introduce two new variants of the k-anonymity problem, namely, the Restricted k-anonymity problem and Restricted k-anonymity problem on attribute (where suppressing the entire attribute is allowed). We prove that both problems are NP-hard for k ≥ 3. The results imply the main results obtained by Meyerson and Williams. On the positive side, we develop a polynomial time algorithm for the Restricted 2-anonymity problem by giving a graphical representation of the microdata table. |
Keywords | k-anonymity; database security |
ANZSRC Field of Research 2020 | 461399. Theory of computation not elsewhere classified |
460499. Cybersecurity and privacy not elsewhere classified | |
469999. Other information and computing sciences not elsewhere classified | |
Public Notes | File reproduced in accordance with the copyright policy of the publisher/author. |
Byline Affiliations | Department of Mathematics and Computing |
University of South Australia |
https://research.usq.edu.au/item/9yv57/on-the-complexity-of-restricted-k-anonymity-problem
Download files
Accepted Version
Sun_Wang_Jiuyong_Author's_version.pdf | ||
File access level: Anyone |
Other Documentation
Asia-Pacific_Web_Conference_2008.pdf | ||
File access level: Anyone |
1999
total views1226
total downloads2
views this month0
downloads this month