k-anonimato

El k-anonimato (en inglés, k-anonymity, también traducido literalmente como k-anonimidad) es una propiedad característica de los datos anonimizados. Este concepto fue formulado por primera vez por Latanya Sweeney en un trabajo publicado en 2002 con el objeto de resolver el problema: "Dados unos datos estructurados con campos específicos personales, como poder asegurar con garantía científica, que en una nueva versión modificada de estos datos no se puedan reidentificar los individuos a los que se refieren, a la vez que los datos sigan siendo útiles en la práctica."^[1]​^[2]​ Se dice que un conjunto de datos publicados tiene la propiedad de k-anonimato (o es k-anónimo) si la información de todas y cada una de las personas contenidas en ese conjunto es idéntica al menos con otras k-1 personas que también aparecen en dicho conjunto.

Existen varios procedimientos para generar datos anonimizados con k-anonimato que han sido patentados en los Estados Unidos (Patente 7,269,578).^[3]​

Métodos para la k-anonimización

En el contexto de la k-anonimización, una base de datos es una tabla con n filas y m columnas. Cada fila de la tabla representa un registro relacionando con un miembro concreto de una población. Los valores en las columnas corresponden a los atributos que se asocian con los miembros de la población. La tabla siguiente es una base de datos no anonimizada que incluye los registros de pacientes de un hospital ficticio en Cochin.

Nombre	Edad	Género	Estado de residencia	Religión	Enfermedad
Ramsha	29	Mujer	Tamil Nadu	Hindu	Cáncer
Yadu	24	Mujer	Kerala	Hindu	Infección Viral
Salima	28	Mujer	Tamil Nadu	Musulmán	Tuberculosis
Sunny	27	Varón	Karnataka	Parsi	Ninguna enfermedad
Joan	24	Mujer	Kerala	Cristiano	Cardiológica
Bahuksana	23	Varón	Karnataka	Budista	Tuberculosis
Rambha	19	Varón	Kerala	Hindu	Cáncer
Kishor	29	Varón	Karnataka	Hindu	Cardiológica
Johnson	17	Varón	Kerala	Cristiano	Cardiológica
John	19	Varón	Kerala	Cristiano	Infección Viral

Hay 6 atributos y 10 registros en estos datos. Hay dos métodos comunes para obtener k-anonimato para un cierto valor deseado de k.

1. Supresión: En este método, algunos valores de los atributos son reemplazados por un asterisco '*'. Todos o algunos de los valores de una columna pueden ser reemplazados por '*'. En la tabla anonimizada inferior, todos los valores en el atributo 'Nombre' y en el atributo 'religión' han sido reemplazado por un '*'.
2. Generalización: En este método, los valores individuales de atributos son reemplazados por una categoría más amplia. Por ejemplo, el valor '19' del atributo 'Edad' puede ser reemplazado por ' ≤ 20', el valor '23' por '20 < Edad ≤ 30' , etc.

La siguiente tabla muestra la base de datos anonimizada.

Nombre	Edad	Género	Estado de residencia	Religión	Enfermedad
*	20 < Edad ≤ 30	Mujer	Tamil Nadu	*	Cáncer
*	20 < Edad ≤ 30	Mujer	Kerala	*	Infección Viral
*	20 < Edad ≤ 30	Mujer	Tamil Nadu	*	Tuberculosis
*	20 < Edad ≤ 30	Varón	Karnataka	*	Ninguna enfermedad
*	20 < Edad ≤ 30	Mujer	Kerala	*	Cardiológica
*	20 < Edad ≤ 30	Varón	Karnataka	*	Tuberculosis
*	Edad ≤ 20	Varón	Kerala	*	Cáncer
*	20 < Edad ≤ 30	Varón	Karnataka	*	Cardiológica
*	Edad ≤ 20	Varón	Kerala	*	Cardiológica
*	Edad ≤ 20	Varón	Kerala	*	Infección Viral

Estos datos son 2-anónimos respecto a los atributos 'Edad', 'Género' y 'Estado de residencia', ya que para cualquier combinación de estos atributos encontrados en cualquier fila de la tabla existen al menos 2 filas con idénticos atributos. Los atributos disponibles para un adversario se denominan cuasiidentificadores. Cada tupla cuasiidentificadora se presenta en al menos k registros para un conjunto de datos con k-anonimato.^[4]​

Meyerson y Williams (2004) demostraron que el k-anonimato es un problema NP-completo; no obstante con métodos heurísticos como el de k-optimización propuesto por Bayardo y Agrawal (2005) a menudo se obtienen resultados eficaces.^[5]​^[6]​

Advertencias

Ya que la k-anonimización no incluye aleatorización, los atacantes pueden realizar inferencias sobre los datos que podrían perjudicar a un individuo. Por ejemplo, si sabemos que John de 19 años de Kerala está en la base de datos anterior, podemos inferir que o padece cáncer, o enfermedad cardiológica o una infección viral.

La k-anonimización no es un buen método para anonimizar un conjunto de datos de muchas dimensiones.^[7]​ Por ejemplo, se ha demostrado que, dadas 4 ubicaciones, la unicidad (k=1) de los conjuntos de datos de teléfonos celulares puede ser del orden del 95%.^[8]​

Referencias

1. L. Sweeney. «Database Security: k-anonymity». Consultado el 19 de enero de 2014. 
2. L. Sweeney. k-anonymity: a model for protecting privacy.
3. «Systems and methods for de-identifying entries in a data source». United States Patents and Trademarks Office. Consultado el 19 de enero de 2014. 
4. Narayanan, Arvind; Shmatikov, Vitaly. «Robust De-anonymization of Large Sparse Datasets». 
5. Roberto J. Bayardo; Rakesh Agrawal (2005). «Data Privacy through Optimal k-anonymization». ICDE '05 Proceedings of the 21st International Conference on Data Engineering: 217-28. ISBN 0-7695-2285-8. ISSN 1084-4627. doi:10.1109/ICDE.2005.42. «Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k - 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a nontrivial dataset under a general model of the problem. » 
6. Adam Meyerson; Ryan Williams (2004). . PODS '04 Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (New York, NY: ACM): 223-8. ISBN 158113858X. doi:10.1145/1055558.1055591. Archivado desde el original el 28 de mayo de 2014. Consultado el 30 de marzo de 2016. «The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4. However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k logm)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice. » 
7. Aggarwal, Charu C. . Archivado desde el original el 4 de marzo de 2016. Consultado el 30 de marzo de 2016. 
8. de Montjoye, Yves-Alexandre; César A. Hidalgo; Michel Verleysen; Vincent D. Blondel (25 de marzo de 2013). «Unique in the Crowd: The privacy bounds of human mobility». Nature srep. doi:10.1038/srep01376. 

•   Datos: Q17061432