El k -anonimato es una propiedad que poseen ciertos datos anonimizados . El término k -anonimato fue introducido por primera vez por Pierangela Samarati y Latanya Sweeney en un artículo publicado en 1998, [1] aunque el concepto data de un artículo de 1986 de Tore Dalenius. [2]
El k -anonimato es un intento de resolver el problema "Dados datos estructurados por campos específicos de cada persona, se produce una publicación de los datos con garantías científicas de que los individuos que son sujetos de los datos no pueden ser reidentificados mientras los datos sigan siendo prácticamente útiles". [3] [4] [5] Se dice que una publicación de datos tiene la propiedad k -anonimato si la información de cada persona contenida en la publicación no puede distinguirse de al menos los individuos cuya información también aparece en la publicación. Las garantías proporcionadas por el k -anonimato son aspiracionales, no matemáticas.
Para utilizar el anonimato k para procesar un conjunto de datos de modo que pueda publicarse con protección de la privacidad, un científico de datos primero debe examinar el conjunto de datos y decidir si cada atributo (columna) es un identificador (que identifica), un no identificador (que no identifica) o un cuasi identificador (que identifica en cierta medida). Los identificadores como los nombres se suprimen, se permite que permanezcan los valores no identificativos y los cuasi identificadores deben procesarse de modo que cada combinación distinta de cuasi identificadores designe al menos k registros.
La siguiente tabla de ejemplo presenta una base de datos ficticia, no anonimizada, que consta de los registros de pacientes de un hospital ficticio. La columna Nombre es un identificador, Edad , Sexo , Estado de domicilio y Religión son cuasi-identificadores, y Enfermedad es un valor sensible no identificable. Pero ¿qué sucede con Altura y Peso ? ¿Son también valores sensibles no identificables o son cuasi-identificadores?
Hay 6 atributos y 10 registros en estos datos. Hay dos métodos comunes para lograr el anonimato k para algún valor de k :
La siguiente tabla muestra la base de datos anonimizada.
Estos datos tienen 2-anonimato con respecto a los atributos Edad , Género y Estado de domicilio , ya que para cualquier combinación de estos atributos que se encuentren en cualquier fila de la tabla siempre hay al menos 2 filas con esos atributos exactos. Los atributos disponibles para un adversario se denominan cuasi-identificadores . Cada tupla de cuasi-identificador aparece en al menos k registros para un conjunto de datos con k -anonimato. [6]
El siguiente ejemplo demuestra una falla del k -anonimato: pueden existir otros registros de datos que se pueden vincular en las variables que supuestamente no son identificables. Por ejemplo, supongamos que un atacante puede obtener el registro de la persona que estaba tomando los signos vitales como parte del estudio y descubre que Kishor estuvo en el hospital el 30 de abril y mide 180 cm. Esta información se puede utilizar para vincular con la base de datos "anonimizada" (que puede haber sido publicada en Internet) y descubrir que Kishor tiene una enfermedad relacionada con el corazón. Un atacante que sabe que Kishor visitó el hospital el 30 de abril puede ser capaz de inferir esto simplemente sabiendo que Kishor mide 180 cm, pesa aproximadamente 80-82 kg y proviene de Karnataka.
La raíz de este problema es el problema central del k -anonimato: no hay forma de determinar matemáticamente y sin ambigüedades si un atributo es un identificador, un cuasi-identificador o un valor sensible no identificable. De hecho, todos los valores son potencialmente identificables, dependiendo de su prevalencia en la población y de los datos auxiliares que pueda tener el atacante. Otros mecanismos de privacidad, como la privacidad diferencial, no comparten este problema.
Aunque el anonimato k protege contra la revelación de identidad, no protege contra la divulgación de atributos específicos. Esto se vuelve problemático cuando los atacantes poseen conocimiento de fondo. Además, la ausencia de diversidad en dominios sensibles puede resultar en la exposición de información personal. En tales escenarios, optar por la diversidad ℓ podría ofrecer una protección de privacidad más sólida.[1]
Meyerson y Williams (2004) demostraron que el k -anonimato óptimo es un problema NP-difícil , sin embargo, los métodos heurísticos como k -Optimize propuesto por Bayardo y Agrawal (2005) a menudo producen resultados efectivos. [7] [8] Kenig y Tassa presentaron un algoritmo de aproximación práctico que permite resolver el problema de k -anonimización con una garantía de aproximación de . [9]
Si bien el k -anonimato es un enfoque relativamente sencillo de implementar para desidentificar un conjunto de datos antes de su publicación, es susceptible a muchos ataques. Cuando un atacante tiene acceso a información de fondo, estos ataques se vuelven aún más efectivos. Entre estos ataques se incluyen:
Como la k -anonimización no incluye ninguna aleatorización, los atacantes pueden hacer inferencias fiables e inequívocas sobre conjuntos de datos que pueden perjudicar a las personas. Por ejemplo, si se sabe que John, de 19 años, de Kerala, está en la base de datos anterior, se puede decir con fiabilidad que tiene cáncer, una enfermedad cardíaca o una infección vírica.
La k -anonimización no es un buen método para anonimizar conjuntos de datos de alta dimensión. [11]
También se ha demostrado que el k -anonimato puede distorsionar los resultados de un conjunto de datos si suprime y generaliza desproporcionadamente los puntos de datos con características no representativas. [12] Sin embargo, los algoritmos de supresión y generalización utilizados para k -anonimizar conjuntos de datos se pueden modificar para que no tengan ese efecto distorsionador. [13]
La desidentificación de datos concilia la demanda de divulgación de datos para fines de investigación y la demanda de privacidad de los individuos. Este artículo propone y evalúa un algoritmo de optimización para el poderoso procedimiento de desidentificación conocido como k -anonimización. Un conjunto de datos k -anonimizado tiene la propiedad de que cada registro es indistinguible de al menos k − 1 otros. Incluso las restricciones simples de k -anonimización optimizada son NP-hard, lo que genera desafíos computacionales significativos. Presentamos un nuevo enfoque para explorar el espacio de posibles anonimizaciones que domina la combinatoria del problema y desarrollamos estrategias de gestión de datos para reducir la dependencia de operaciones costosas como la clasificación. A través de experimentos con datos censales reales, demostramos que el algoritmo resultante puede encontrar k -anonimizaciones óptimas bajo dos medidas de costo representativas y un amplio rango de k. También demostramos que el algoritmo puede producir buenas anonimizaciones en circunstancias en las que los datos de entrada o los parámetros de entrada impiden encontrar una solución óptima en un tiempo razonable. Por último, utilizamos el algoritmo para explorar los efectos de diferentes enfoques de codificación y variaciones del problema en la calidad y el rendimiento de la anonimización. Hasta donde sabemos, este es el primer resultado que demuestra una k -anonimización óptima de un conjunto de datos no triviales bajo un modelo general del problema.
La técnica de k -anonimización se ha propuesto en la literatura como una forma alternativa de publicar información pública, al tiempo que se garantiza tanto la privacidad como la integridad de los datos. Demostramos que dos versiones generales de k- anonimización óptima de relaciones son NP-duras, incluida la versión de supresión que equivale a elegir un número mínimo de entradas para eliminar de la relación. También presentamos un algoritmo de tiempo polinomial para k -anonimización óptima que logra una relación de aproximación independiente del tamaño de la base de datos, cuando k es constante. En particular, es una aproximación O ( k log k ) donde la constante en el gran O no es mayor que 4. Sin embargo, el tiempo de ejecución del algoritmo es exponencial en k . Un algoritmo ligeramente más inteligente elimina esta condición, pero es una aproximación O ( k log m ), donde m es el grado de la relación. Creemos que este algoritmo podría ser potencialmente bastante rápido en la práctica.
