Privacy Preserving Data Mining

Abstract

Deze thesis handelt over privacy preserving data mining. Data mining is een tak van de wetenschap waarin men grote hoeveelheden data onderzoekt met de bedoeling er bepaalde patronen in te ontdekken. Enkele belangrijke data mining algoritmes zullen aangehaald en besproken worden. Dankzij de groeiende populariteit van data mining blijft het uitvoeren van de algoritmes niet beperkt tot één partij. Er zijn dikwijls meerdere partijen betrokken bij het data mining proces. Toch is het niet mogelijk om al de data zomaar samen te brengen. In veel gevallen zullen de betrokken partijen dit niet willen. Denk bijvoorbeeld aan concurrerende bedrijven of concurrerende afdelingen binnen een bedrijf die gemeenschappelijke data mining resultaten nodig hebben. Verder moet er ook rekening gehouden worden met de bestaande privacy wetten. Kortom, het wordt al snel duidelijk dat het samenbrengen van de gegevens geen mogelijke oplossing is. Een tweede voorstel, dat op het eerste zicht veel haalbaarder lijkt, is het verwijderen van de identificatie gegevens uit de data. Toch gaat ook dit volledig in strijd met de privacy van de gegevens. Het is namelijk zo dat de mogelijkheid bestaat om uit de algemene gegevens de identificatie gegevens in zekere mate af te leiden. Deze situatie is gekend als het inferentie probleem. Er zijn verschillende methodes bekend die het probleem van data minen in verdeelde data aanpakken. Deze thesis handelt grotendeels over ´e´en aanpak. Deze methode is gebaseerd op de theorie van secure multiparty computation en maakt gebruik van encryptie. De basis van deze aanpak ligt in het feit dat alle data mining problemen bepaalde gemeenschappelijke componenten hebben. Zo zal er bijvoorbeeld in veel gevallen een som moeten berekend worden waarvan elke partij één term heeft. Dit resultaat moet dan op zo een manier bepaald worden dat alle partijen door de uitvoering van het protocol niets meer leren dan het resultaat. Dit vertoont heel veel gelijkenissen met de theorie van secure multiparty computation. De bedoeling bij secure multiparty computation is het berekenen van een functie, die haar input krijgt van verschillende partijen, op zo een manier dat alle partijen niets meer leren dan de uiteindelijke output. Het is aangetoond dat het zowel voor twee partijen als voor meer dan twee partijen mogelijk is om elke functie f waarbij de input verdeeld is over de partijen op zo een manier te berekenen dat de partijen niets meer leren dan de output. De methodes die worden voorgesteld in de secure multiparty computation zijn echter niet effici¨ent genoeg om gebruikt te worden indien er meer dan twee partijen zijn. Aangezien het bij data mining gaat om grote hoeveelheden data is het belangrijk om praktische oplossingen te hebben. Daarom zijn er nieuwe protocollen ontwikkeld voor al de aparte componenten zoals de hierboven aangehaalde som. Deze protocollen zijn zo opgesteld dat ze voldoen aan de veiligheidseisen uit de secure multiparty computation en toch hun efficiëntie behouden. Met behulp van deze bouwstenen kunnen er privacy preserving data mining algoritmes geconstrueerd worden. Zowel de bouwstenen als mogelijke algoritmes zullen in deze thesis verder beschreven worden. Naast de literatuurstudie van het domein bevat deze thesis ook nog enkele uitbreidingen. Er werd onderzocht welke problemen nog geen concrete oplossingen hadden. Door gebruik te maken van de bouwstenen werden nieuwe algoritmes geconstrueerd om deze open problemen op te lossen. Verder werd er ook een speciale situatie bekeken waarin de data op een bijzondere manier verdeeld is over de verschillende partijen. Aan de hand van het ID3 algoritme wordt aangetoond dat ook deze situatie kan opgelost worden met behulp van de bouwstenen. Deze thesis is grotendeels als volgt opgedeeld. In Hoofdstuk 1 wordt een korte inleiding gegeven tot data mining en worden de belangrijkste algoritmes besproken. Hoofdstuk 2 beschrijft de problematiek rond privacy preserving data mining en bespreekt de mogelijke oplossingen. Hoofdstukken 3 en 4 bevatten de nodige achtergrondinformatie in verband met encryptie en secure multiparty computation. In Hoofdstuk 5 worden de privacy preserving protocollen besproken en in Hoofdstuk 6 de privacy preserving algoritmes. Hoofdstukken 7 en 8 bevatten de uitbreidingen van de literatuur. In Hoofdstuk 7 worden enkele ontbrekende algoritmes aangehaald. Hoofdstuk 8 bevat een studie van een speciale verdeling van de data. Als laatste worden in het besluit de hoofdzaken nog eens herhaald en enkele ideëen in verband met toekomstig werk vermeld.