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 | ||
2067
total views1263
total downloads1
views this month0
downloads this month