Data anonymization: k-anonymity and de-anonymization attacks

Abstract

The need for access to data concerning individuals is steadily increasing the last years. These data may be collected by governments and companies for various reasons and purposes. However, the release of data may cause several issues if we don’t take the appropriate actions. There is high risk of disclosure of confidential information concerning individuals. Modifications to the data must be applied in order to protect individuals’ privacy, but attention must be paid in order to keep a good balance between the desired level of privacy and data utility. Different anonymization methods have been proposed and the selection of which to apply depends on several variables: the type of release, the data type (e.g. numerical, nominal, ordinal), and the desired level of disclosure limitation. k-anonymity was the first privacy model that has been proposed and consists the basis for many other models that followed. However it is vulnerable to several attacks and needs enforcement. In this thesis there is a thorough presentation of the majority of anonymization models classified by the type of disclosure they tried to protect. Most of the models that are presented here are extensions of k-anonymity model but some different approaches are also presented for better understanding of its shortcomings. The algorithms that have been proposed so far for kanonymity implementation have been also presented in a novel classification. Furthermore, applications of k-anonymity in several fields are examined. An allusion to different types of attacks to released data is maid, attack algorithms and their metrics are presented and a new de-anonymization tool with a series of new attack algorithms and their metrics is proposed.

Η ανάγκη για πρόσβαση σε δεδομένα που αφορούν πολίτες ολοένα αυξάνεται τα τελευταία χρόνια. Αυτά τα δεδομένα μπορεί να έχουν συλλεχθεί από κυβερνήσεις ή επιχειρήσεις για διάφορους σκοπούς και λόγους. Παρόλα αυτά η δημοσίευση των δεδομένων μπορεί να προκαλέσει διάφορα θέματα εάν δεν ληφθούν κατάλληλα μέτρα. Υπάρχει μεγάλη πιθανότητα διαρροής εμπιστευτικής πληροφορίας που να αφορά πολίτες. Τα δεδομένα πρέπει να τροποποιηθούν προκειμένου να προστατευτεί η ιδιωτικότητα των ατόμων, όμως πρέπει να δοθεί προσοχή προκειμένου να διατηρηθεί μια καλή ισορροπία ανάμεσα στο επιθυμητό επίπεδο ιδιωτικότητας και στη χρησιμότητα των δεδομένων. Διαφορετικές μέθοδοι ανωνυμοποίησης έχουν προταθεί και το ποια θα επιλεγεί εξαρτάται από διάφορες μεταβλητές όπως: το είδος της δημοσίευσης, το είδος των δεδομένων και το επιθυμητό επίπεδο δημοσίευσης ευαίσθητης πληροφορίας. Η k-anonymity ήταν η πρώτη μέθοδος προστασίας της ιδιωτικότητας που προτάθηκε και αποτέλεσε τη βάση για πολλές άλλες που ακολούθησαν. Όμως είναι ακόμα ευπαθής σε επιθέσεις και χρειάζεται ενίσχυση. Σε αυτή τη διατριβή παρουσιάζεται η πλειοψηφία των μοντέλων ανωνυμοποίησης ταξινομημένα με βάση των τύπο της διαρροής που προσπαθούν να προστατέψουν. Τα περισσότερα μοντέλα που παρουσιάζονται είναι επεκτάσεις του μοντέλου της k-anonymity όμως παρουσιάζονται και μερικές διαφορετικές προσεγγίσεις για καλύτερη κατανόηση των ελαττωμάτων της. Επιπλέον παρουσιάζονται και οι αλγόριθμοι για την k-anonymity σε μια καινοτόμο ταξινόμηση, καθώς επίσης και οι εφαρμογές της k-anonymity σε διάφορα πεδία. Γίνεται αναφορά σε διαφορετικούς τύπους επιθέσεων, παρουσιάζονται οι αλγόριθμοι των επιθέσεων και τα metrics τους και τέλος παρουσιάζεται ένα νέο εργαλείο αποανωνυμοποίησης που υλοποιεί μια σειρά από νέους αλγορίθμους επιθέσεων και τα αντίστοιχα metrics.