Privacy preserving data mining

Abstract

Medical, financial, or social databases are analyzed daily for the discovery of pat- terns and useful information. Privacy concerns have emerged as some database segments contain sensitive data. Data mining techniques are used to parse, process, and manage enormous amounts of data while ensuring the preservation of private information, as data can be exploited by potential aggressors. Regarding social networks, their privacy preserving analysis aims to understand better the network and its behavior, while at the same time protecting the privacy and identity of its individuals. Network data contain sensitive information and due to the increasing popularity of social networks that are released publicly, effective anonymization techniques are required to make the data available for research. Considering the above, this thesis is divided in two parts and focuses on privacy preservation of distributed databases and social network data. In the first part, a privacy preserving data mining protocol is presented, thoroughly designed and developed for both horizontally and vertically partitioned databases, which contain either nominal or numeric attribute values. At the same time the accuracy of final outcomes and the preservation of privacy is the main goal of the proposed protocol. Cryptography, as shown by previous research, is the most accurate approach to acquiring knowledge while maintaining privacy to assure both confidentiality and integrity of data. The proposed algorithm exploits the multi-candidate election schema to construct a privacy-preserving tree-augmented naive Bayesian classifier, a more robust variation of the classical naive Bayes classifier. The exploitation of the Paillier cryptosystem and the distinctive homomorphic primitive shows in the security analysis that privacy is ensured and the proposed algorithm provides strong defences against common attacks. In the second part, an anonymization algorithm is developed for weighted graphs, i.e., for social networks where the strengths of links are important. Previous studies concentrate mainly on preventing identity disclosure in unweighted graphs. How- ever, a weighted graph is more descriptive, revealing more information about the relationships between entities, which allows adversaries to take advantage of potential security holes. Weights can be essential for social network analysis, but they pose new challenges to privacy preserving network analysis. For instance, an adversary may use his information about some edge weights to re-identify individuals. This in contrast with many previous studies which only consider unweighted graphs. The proposed anonymization method considers identity, edge and edge weight disclosure for anonymizing weighted graph data, assuming that adversaries have knowledge about the neighborhood of a targeting entity. In particular, a k-anonymous technique is presented that groups entities with same neighborhoods into supernodes and the corresponding connections into superedges. The method provides k-anonymity of nodes against attacks where the adversary has information about the structure of the network, including its edge weights. Both approaches are proven efficient and have been evaluated in terms of privacy and utility. Experiments deriving the benefits of real world databases demonstrate the preservation of private data while mining processes occur.

Ιατρικές, οικονομικές ή κοινωνικές βάσεις δεδομένων αναλύονται καθημερινά για την ανακάλυψη προτύπων και χρήσιμων πληροφοριών. Προβλήματα απορρήτου προκύπτουν καθώς ορισμένα τμήματα βάσης δεδομένων περιέχουν ευαίσθητα δεδομένα. Οι τεχνικές εξόρυξης δεδομένων χρησιμοποιούνται για την ανάλυση, την επεξεργασία και τη διαχείριση τεράστιων ποσοτήτων δεδομένων, διασφαλίζοντας παράλληλα τη διατήρηση των ιδιωτικών πληροφοριών, καθώς τα δεδομένα μπορούν να αξιοποιηθούν από πιθανούς επιτιθέμενους. ́Οσον αφορά τα κοινωνικά δίκτυα, η ανάλυσή τους για την προστασία της ιδιωτικότητας στοχεύει στην καλύτερη κατανόηση του δικτύου και της συμπεριφοράς του, ενώ ταυτόχρονα προστατεύει το απόρρητο και την ταυτότητα των ατόμων του. Τα δεδομένα δικτύου περιέχουν ευαίσθητες πληροφορίες και λόγω της αυξανόμενης δημοτικότητας τους που δημοσιεύονται δημοσίως, απαιτούνται αποτελεσματικές τεχνικές ανωνυμοποίησης για τη διάθεση των δεδομένων για έρευνα. Λαμβάνοντας υπόψη τα παραπάνω, αυτή η διατριβή χωρίζεται σε δύο μέρη και εστιάζει στη διατήρηση της ιδιωτικότητας σε κατανεμημένες βάσεις δεδομένων και δεδομένα κοινωνικών δικτύων. Στο πρώτο μέρος, παρουσιάζεται ένας αλγόριθμος εξόρυξης δεδομένων διατήρησης απορρήτου, σχεδιασμένος και υλοποιημένος διεξοδικά για οριζόντιες και κατακόρυφες κατατμημένες βάσεις δεδομένων, οι οποίες περιέχουν χαρακτηριστικά είτε με ονομαστικές είτε με αριθμητικές τιμές. Ταυτόχρονα, η ακρίβεια των τελικών αποτελεσμάτων και η διατήρηση της ιδιωτικότητας είναι ο κύριος στόχος του προτεινόμενου πρωτοκόλλου. Η κρυπτογραφία, όπως φαίνεται από προηγούμενη έρευνα, είναι η πιο ακριβής προσέγγιση για την απόκτηση γνώσεων, διατηρώντας παράλληλα το απόρρητο για να διασφαλιστεί τόσο η εμπιστευτικότητα όσο και η ακεραιότητα των δεδομένων. Ο προτεινόμενος αλγόριθμος εκμεταλλεύεται το πολυ-υποψήφιο σχήμα εκλογής για να κατασκευάσει ένα tree-augmented naive Bayesian ταξινομητή, μια πιο ισχυρή παραλλαγή του κλασικού αφελής ταξινομητή Bayes. Η εκμετάλλευση του κρυπτοσυστήματος Paillier και η θεμελιώδης ομομορφική αρχή δείχνουν στην ανάλυση ασφάλειας ότι διασφαλίζεται η προστασία της ιδιωτικότητας και ο προτεινόμενος αλγόριθμος παρέχει ισχυρές άμυνες ενάντια σε κοινές επιθέσεις. Στο δεύτερο μέρος, αναπτύσσεται μια μέθοδος ανωνυμοποίησης για σταθμισμένα γραφήματα, δηλαδή για κοινωνικά δίκτυα όπου η ισχύς των συνδέσμων είναι σημαντική. Προηγούμενες μελέτες επικεντρώνονται κυρίως στην αποτροπή της αποκάλυψης ταυτότητας σε μη σταθμισμένα γραφήματα. Ωστόσο, ένα σταθμισμένο γράφημα είναι πιο περιγραφικό, αποκαλύπτοντας περισσότερες πληροφορίες σχετικά με τις σχέσεις μεταξύ οντοτήτων, γεγονός που επιτρέπει στους επιτιθέμενους να επωφεληθούν από πιθανές τρύπες ασφαλείας. Tα βάρη μπορούν να είναι απαραίτητα για την ανάλυση κοινωνικών δικτύων, αλλά θέτουν νέες προκλήσεις στην προστασία του απορρήτου για την ανάλυση δικτύων. Για παράδειγμα, ένας επιτιθέμενος μπορεί να χρησιμοποιήσει τις πληροφορίες του σχετικά με κάποια βάρη συνδέσμων για να επαναπροσδιορίσει τα άτομα. Αυτό έρχεται σε αντίθεση με πολλές προηγούμενες μελέτες που θεωρούν μόνο μη σταθμισμένα γραφήματα. Η προτεινόμενη μέθοδος ανωνυμοποίησης λαμβάνει υπόψη την ταυτότητα, την σύνδεση και το βάρος της σύνδεσης για την ανωνυμοποίηση σταθμισμένων δεδομένων γραφήματος, υποθέτοντας ότι οι επιτιθέμενοι έχουν γνώση σχετικά με τη γειτονιά μιας στοχευμένης οντότητας. Συγκεκριμένα, παρουσιάζεται μια k - ανώνυμη τεχνική που ομαδοποιεί οντότητες με τις ίδιες γειτονιές σε υπεροντότητες και τις αντίστοιχες συνδέσεις σε υπερσυνδέσεις. Η μέθοδος παρέχει k - ανωνυμία κόμβων έναντι επιθέσεων όπου ο επιτιθέμενος έχει πληροφορίες σχετικά με τη δομή του δικτύου, συμπεριλαμβανομένων των βαρών. Και οι δύο μεθοδολογίες έχουν αποδειχθεί αποτελεσματικές και έχουν αξιολογηθεί ως προς το απόρρητο και τη χρησιμότητα. Τα πειράματα που αντλούν τα οφέλη από πραγματικές βάσεις δεδομένων δείχνουν τη διατήρηση των ιδιωτικών δεδομένων κατά τη διάρκεια τεχνικών εξόρυξης γνώσης.