Differential privacy by sampling

Abstract

Collection and storage of immense volumes of data has become commonplace in today's digital age, making the protection of personal data increasingly important. Private data often includes sensitive information about an individual, and is gathered by medical and financial institutions, research and social science organisations, government, etc., taking full advantage of data-driven analytics and knowledge-based decision-making to improve products and services, enterprise statistical analysis, comprehensive studies of demographic trends, and many others. The disclosure or sharing of such information among different parties could infringe on privacy. This information can be used for malicious purposes, such as identity theft, scams or targeted advertising. This work examines the field of privacy-preserving data publishing. Quality of published data significantly affects not only understanding and processing strategy, but the accuracy of data analysis as well as consequently the interpretation and decisions derived from the data. In order to meet this challenge, synthetic anonymization techniques, such as k-anonymity and its enhanced algorithms, are applied. However, they are based on the background knowledge of the adversary. A semantic model, or differential privacy, is a more rigorous mathematical notion of privacy assurance that operates under no assumptions. Nevertheless, differential privacy applies to the subsequent phase, namely privacy preserving data mining, query answering and aggregate statistics. In the scope of this work, a subsampling anonymization algorithm DP-anonym providing k-anonymity with integrated differential privacy mechanisms, such as Laplace mechanism and exponential mechanisms, is elaborated. The algorithm provides synthetic and semantic privacy, combining the best of the two areas of private data exploration. According to experimental results, the proposed DP-anonym algorithm provides better data utility when compared to standard anonymization algorithms among general data utility metrics. It also provides more precise answers to typical database queries as it uses multidimensional generalization approach. In contrast to standard methods, DP-anonym achieves (epsilon, delta)-differential privacy, which guarantees the privacy of published anonymized data more efficiently.

Im heutigen digitalen Zeitalter sind das Sammeln und Speichern enormer Datenmengen alltäglich geworden, womit die Sicherung persönlicher Daten stetig an Relevanz gewinnt. Private Daten zeichnen sich dadurch aus, dass sie häufig sensible Informationen über die betroffenen Individuen enthalten, welche von medizinischen Einrichtungen und Finanzinstitutionen, Forschungseinrichtungen und Wissenschaftlichen Organisationen, der Regierung und deren Behören sowie diversen anderen Stellen gesammelt und genutzt werden, um die Vorteile auszuschöpfen welche datenbasierter Analysen und wissensbasierter Entscheidungsfindung zur Optimierung von Produkten und Dienstleistungen, statistische Unternehmensanalysen, umfassende Studien zu demografischen Trends um einige zu nennen, mit sich bringen. Die Veröffentlichung oder gemeinsame Nutzung verschiedener Parteien solch sensibler Daten kann zu Verletzungen der Privatsphäre führen. So können die Daten mutwillig missbraucht werden, beispielsweise durch Identitätsdiebstahl, Betrug oder zielgerichtete Werbung. Diese Arbeit untersucht den Bereich der datenschutzfreundlichen Datenveröffentlichung. Die Qualität der veröffentlichten Daten hat erhebliche Auswirkungen auf das Verständnis und die Verarbeitungsstrategie sowie auf die Genauigkeit der Datenanalyse und folglich auf die aus den Daten gewonnenen Erkenntnisse und Entscheidungen. Um diese Herausforderung zu meistern, werden synthetische Anonymisierungstechniken wie k-anonymity und ihre optimierten Algorithmen eingesetzt. Sie basieren jedoch auf dem Hintergrundwissen des Gegners. Das semantische Modell oder die differential Privacy ist ein rigoroserer mathematischer Ansatz zur Gewährleistung der Privatsphäre, der ohne Annahmen auskommt. Allerdings lässt sich die differential Privacy auf die nachfolgende Phase anwenden, d. h. auf die datenschutzfreundliche Data Mining, die Anfragebeantwortung und die aggregierten Statistiken. Im Rahmen dieser Arbeit wird ein Subsampling-Anonymisierungsalgorithmus DP-anonym ausgearbeitet, der k-anonymity mit integrierten differential privacy Mechanismen, wie dem Laplace- und dem Exponentialmechanismus, gewährleistet. Der Algorithmus bietet synthetische und semantische Privatsphäre und kombiniert damit die Vorteile beider Bereiche der privaten Datenexploration. Die experimentellen Ergebnisse zeigen, dass der vorgeschlagene Algorithmus DP-anonym im Vergleich zu Standard-Anonymisierungsalgorithmen einen höheren Datennutzen unter den allgemeinen Datennutzenmetriken bietet. Außerdem liefert er präzisere Antworten auf typische Datenbankabfragen, denn er verwendet einen mehrdimensionalen Generalisierungsansatz. Im Gegensatz zu Standardmethoden erreicht DP-anonym die (epsilon, delta)-differential privacy, was effizienter die Privatsicherheit der veröffentlichten anonymisierten Daten gewährleistet.