Privacy-preserving protocols in unreliable distributed systems

Przedmiotem tej rozprawy są wybrane problemy agregacji danych z zachowaniem prywatności. Rozprawa jest oparta o prywatność różnicową (differential privacy), która, w odróżnieniu od wcześniejszych definicji prywatności, jest oparta na formalizmie matematycznym. Prywatność różnicowa wiąże się z odpowiednią randomizacją wyniku. Interesują nas praktyczne scenariusze, więc rozważamy agregacje w rozproszonych systemach z zawodnymi węzłami i niezaufanym agregatorem. Zaczniemy od przeanalizowania aktualnego rozwiązania problemu i wskazania, że pomimo dobrych asymptotycznych gwarancji dokładności, w wielu praktycznych scenariuszach błędy wynikające z dodanych szumów są nieakceptowalnie duże. Następnie proponujemy skonstruowany przez nas protokół, który wykorzystuje ograniczoną, lokalną komunikację pomiędzy węzłami. Pokazujemy, że nasz protokół zapewnia dowodliwą prywatność oraz jest znacznie dokładniejszy, nawet gdy wiele węzłów jest zawodnych. Następnie, aby nasze wyniki były użyteczne w szerszej klasie scenariuszy, pokazujemy jak skonstruować lokalne grupy ufających sobie węzłów w realistycznych sieciach. Rozważamy rozproszony system składający się z węzłów, które muszą stworzyć dużą, spójną grupę w sposób efektywny i bez znajomości topologii sieci. Proponujemy i badamy lokalne strategie konstruowania dużych grup z małym narzutem komunikacyjnym i obliczeniowym. Ponadto udowadniamy niektóre własności prawdziwych sieci przy założeniu, że pochodzą z modelu preferential attachment. Na koniec koncentrujemy się na samej definicji prywatności. Rozważamy, znane ˙ wcześniej, osłabienie prywatności różnicowej, noiseless privacy, wykorzystujące ograniczoną losowość danych. Może ona równie ˙ z modelować niepewność adwersarza. W odróżnieniu od istniejących wyników, które skupiały się na wynikach ˙ asymptotycznych, niezależnych danych i konkretnych rozkładach danych, przedstawiamy nieasymptotyczne gwarancje prywatności dla dowolnych rozkładów i szerokiej klasy zależności. Pokazujemy jak połączyć prywatność różnicową z ˙ noiseless privacy oraz przedstawiamy precyzyjne wyniki, które mogą być łatwo wykorzystane w praktycznych zastosowaniach agregacji danych.

This thesis concerns chosen problems of privacy preserving data aggregation. It is based on differential privacy, which is a mathematically rigorous privacy definition resilient to post-processing. Differential privacy is connected with randomization of the result. The goal is to achieve both sufficient privacy and accuracy. We are interested in practical scenarios, so we consider aggregation in distributed systems with unreliable nodes and untrusted aggregator. First, we analyse current state-of-the-art solution and show that despite good asymptotical guarantees for the accuracy, in many practical scenarios the errors are unacceptably high. We present our own fault tolerant privacy preserving data aggregation protocol which utilizes limited local communication between nodes. We show that our protocol provides provable level of privacy and far better accuracy even when facing massive failures of nodes. Next, to make our results useful in wider scenarios, we show how to construct local groups of trust in real-life networks. We consider a distributed system that consists of nodes which need to constitute a huge, connected group in an efficient way, using simple operations and without knowledge of global network topology. We propose and investigate local strategies for constructing large groups of users with low communication and computation overhead. Moreover, we prove some properties of real-life networks while formally assuming that they are generated as a preferential attachment process. Finally, we took a different approach and focused instead on the privacy definition itself. We look from different perspective at an, already known, relaxation of differential privacy called noiseless privacy. It utilizes the randomness in the data, which can either come inherently from the data itself, or model the uncertainty of the Adversary. In contrast to previous work, which focused on asymptotic results, independent data and specific distributions, we give nonasymptotic privacy guarantees for any distribution and a wide class of dependencies. We show a way to combine differential privacy with noiseless privacy and present detailed results which can be easily applied in real-life scenarios of data aggregation.