Complejidad y resolución del problema del K-anonimato

Abstract

There are many situations in which anonymity is important. For example in medical records or the internet. This is why data that can identify a person unambiguously in most cases is not collected. Data necessary for providing the services, though, must be collected and recorded. There can be situations where collecting this information can identify someone. The K-Anonymity is a computer engineering and mathematical problem which entails distributing in a certain number of places a certain number of items, each identifiable by some quasi-identifiers, in the least identifiable way possible group-wise. For example, the places can be different surgeon’s offices and the items can be people that need chemotherapy for their cancer treatment, so their identifiers can be ZIP code, sex or blood type, among others. Understanding anonymity among these people as having close to identical quasi-identifiers so they are indistinguishable, the best solution to the problem is the one that singles out the least amount of patients. This is because, if in a day 30 patients are treated, and only 1 patient lives in a certain ZIP code area, and the record of the day is looked at, this person will not be anonymous at all. If this is a person of interest and its ZIP code is known, the result will be leaked. In this problem study we will ascertain the computational complexity as well as different ways of solving it, such as using an exhaustive algorithm, a genetic algorithm, and a constraint programming-based approach.

Hay muchas situaciones en las que el anonimato es importante, como por ejemplo en los registros médicos o en internet. Por ello, los datos que pueden identificar a una persona de manera inequívoca, en la mayoría de los casos, no se recopilan. Sin embargo, los datos necesarios para proporcionar los servicios sí deben ser recolectados y almacenados. Existen situaciones en las que la recolección de esta información puede identificar a alguien. El K-Anonimato es un problema de ingeniería informática y matemáticas que implica distribuir en un cierto número de lugares un cierto número de elementos, cada uno identificable por algunos cuasi-identificadores, de la manera menos identificable posible en términos de grupo. Por ejemplo, los lugares pueden ser diferentes consultorios de cirujanos y los elementos pueden ser personas que necesitan quimioterapia para su tratamiento contra el cáncer, por lo que sus identificadores pueden ser el código postal, el sexo o el tipo de sangre, entre otros. Entendiendo el anonimato entre estas personas como tener los mismos cuasi-identificadores para que sean indistinguibles, la mejor solución al problema es la que singulariza la menor cantidad de pacientes. Esto se debe a que, si en un día se tratan 30 pacientes, y solo 1 paciente vive en una cierta área de código postal, al revisar el registro del día, esta persona no será anónima en absoluto. Si esta persona es de interés y se conoce su código postal, se filtrará la información. En este estudio del problema determinaremos la complejidad computacional así como diferentes formas de resolverlo, como el uso de un algoritmo exhaustivo, un algoritmo genético y un enfoque basado en programación por restricciones.