Improving data utility in differential privacy and k-anony mity

Autor/a

Soria Comas, Jorge

Director/a

Domingo-Ferrer, Josep, 1965-

Fecha de defensa

2013-06-14

Depósito Legal

T.1018-2013

Páginas

151 p.



Departamento/Instituto

Universitat Rovira i Virgili. Departament d'Enginyeria Informàtica i Matemàtiques

Resumen

We deal with SDC from the computer science community perspective. The focus lies on two mainstream privacy models: k-anonymity and differential privacy. Once a privacy model has been selected, the goal is to enforce it while preserving as much data utility as possible. The main objective of this thesis is to improve the data utility in k-anonymous and differentially private data releases. k-Anonymity has several drawbacks. On the disclosure limitation side, there is a lack of protection against attribute disclosure and against informed intruders. On the data utility side, dealing with a large number of quasi-identifier attributes is problematic. We propose a relaxation of k-anonymity that deals with these issues. Differential privacy limits disclosure risk through noise addition. The Laplace distribution is commonly used for the random noise. We show that the Laplace distribution is not optimal: the same disclosure limitation guarantee can be attained by adding less noise. Optimal univariate and multivariate noises are characterized and constructed. Common mechanisms to attain differential privacy do not take into account the users’ prior knowledge; they implicitly assume zero initial knowledge about the query response. We propose a mechanism that focuses on limiting the knowledge gain over the prior knowledge. Microaggregation-based k-anonymity and differential privacy can be combined to produce microdata releases with the strong privacy guarantees of differential privacy and improved data accuracy.


Aquesta tesi adopta el punt de vista de la comunitat informàtica. Ens centrem en dos models de privadesa àmpliament acceptats: el k-anonimat i la privadesa diferencial. Un cop triat el model de privadesa, l’objectiu passa a ser complir-ne els requisits, alhora que preservar la màxima utilitat possible en les dades resultants. L’objectiu principal d’aquesta tesi és la millora de la utilitat en la publicació de dades k-anònimes i diferencialment privades. El k-anonimat presenta alguns problemes. Pel que fa al risc de revelació, no protegeix contra la revelació d’atributs ni contra intrusos informats. Pel que fa a la utilitat de les dades, tractar amb fitxers amb un nombre elevat d’atributs quasiidentificadors pot ser problemàtic. Proposem una relaxació del k-anonimat que tracta aquests problemas. La privadesa diferencial limita el risc de revelació afegint un soroll aleatori al resultat de les consultes. Mostrem que la distribució de Laplace no és òptima: es poden complir els requeriments de la privadesa diferencial afegint sorolls més petits. A més, caracteritzem i construïm les distribucions òptimes (univariant i multivariant). Els mecanismes habituals per obtener privadesa diferencial no tenen en compte el possible coneixement previ dels usuaris; implícitament, se’ls suposa un coneixement nul. Proposem un mecanismo basat a limitar el guany de coneixement de l’usuari respecte del seu coneixement inicial. El k-anonimat i la privadesa diferencial es presenten sovint com a models contraposats. La privadesa diferencial i el k-anonimat no són conceptes completament inconnexos: si es pren com a punt de partida per obtenir privadesa diferencial un conjunt de dades k-anònim (obtingut mitjançant un cert tipus de microagregació), la quantitat de soroll necessari es veu reduïda significativament.


Adoptamos aquí el proceder de la comunidad informática y nos ocupamos de dos de los principales modelos de privacidad: k-anonimato y privacidad diferencial. Una vez seleccionado un modelo de privacidad, el objetivo pasa a ser cumplir con sus requisitos, a la vez que se trata de preservar la máxima utilidad posible para los datos El k-anonimato presenta algunos problemas. En relación a la limitación del riesgo de revelación, no protege contra la revelación de atributos, ni contra intrusos informados. En relación a la utilidad de los datos, tratar con ficheros que tienen un número elevado de atributos cuasi-identificadores es problemático. Proponemos un nuevo modelo basado en la relajación del requisito de indistinguibilidad que establece el k-anonimato. La privacidad diferencial limita el riesgo de revelación añadiendo un ruido aleatorio al resultado de las consultas. Habitualmente se utiliza la distribución de Laplace para generar dicho ruido. En esta tesis mostramos que la distribución de Laplace no es óptima. Asimismo, caracterizamos y construimos las distribuciones óptimas (univariante y multivariante). Los mecanismos usuales para obtener privacidad diferencial no tienen en cuenta este conocimiento previo; implícitamente, se supone un conocimiento nulo. Proponemos un mecanismo para obtener privacidad diferencial orientado a limitar la ganancia de conocimiento del usuario con respecto a su conocimiento previo. El k-anonimato y la privacidad diferencial son a menudo presentados como nociones de privacidad contrapuestas. Mostramos que tomando como datos de partida para obtener privacidad diferencial un conjunto de datos k-anónimo (construido mediante un cierto tipo de microagregación) se reduce la cantidad de ruido necesaria y se mejora la utilidad de la información.

Palabras clave

Differential privacy; K-anonymity; data privacy

Materias

004 - Informática

Documentos

Tesis.pdf

3.763Mb

 

Derechos

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

Este ítem aparece en la(s) siguiente(s) colección(ones)