In order to adhere to Open Government doctrine, Public Administrations (PAs) are requested to publish Open Data while preventing the disclosure of personal information of their citizens. Therefore, it is crucial for PAs to employ methods that ensure Privacy-preserving data publishing by distributing useful data while protecting individual privacy. In this paper, we study this problem by providing a two phases approach. First, we detect privacy issues by recognizing the minimum number of attributes that expose the highest number of unique values (that will be referred to as singletons) as Quasi-Identifier. We test our approach on real datasets openly published by the Italian government, and we discover that the quasiidentifier (year_of_birth, sex, ZIP_of_residence) discloses up to 2% unique values in already anonymized datasets. Once accomplished the detection phase, we propose an anonymization approach to limit the privacy leakage. We investigate which combination of attributes must be generalized to achieve the minimum number of singletons while minimising the amount of modified and removed rows. We tested our approach on real datasets as in the previous phase, and we noticed that by generalizing only rows corresponding to the singletons, we achieve nearly no singletons while affecting only the 2% of rows.
Data owners are spur in opening up their data to enable informed decision making, ensure
transparency, audience engagement, and release social and commercial value (OKF). Open data (OD)
is any information that people are free to use, re-use, and redistribute - without any legal,
technological, or social restriction (OKF). Unfortunately, data in their raw and original form could
contain personal and sensitive information about individuals. Publishing such data violate
individual privacy (GDPR, 2016). Thus, data providers should perform Privacy-preserving data
publishing (PPDP)
Data owners, such as public administrations (PAs), health care, and financial institutions, may
release the data they collect by de-identifying them, i.e., by masking, generalizing, or deleting IDs.
However, even anonymized public information may be re-identified by exploiting other pieces of
available data. A 2002 study found that 87% of the U.S. population can be identified using gender,
birthdate, and zip code as QID by matching anonymized hospital visit records and voting lists
The choice of the QID is an open question
In this article, we aim to prove that PAs current anonymization practices are not as waterproof
as first perceived. We propose an approach to identify the best QID by counting the number of
uniquely occurrences of a combination of values in a dataset. These unique occurrences will be
referred to as singletons. We define the best QID as the minimum number of columns/attributes that
leads to the disclosure of the highest number of singletons. By recalling that PPDP is interested in
minimising both the information loss and the privacy leakage
RQ1: What is the best QID according to our approach, and how many singletons does it disclose? RQ2: The generalization of which attribute or set of attributes among date of birth, ZIP and sex (one of the most common QID in the literature) leads to the minimum number of singletons while minimising the affected rows?
We designed and implemented an algorithm that classifies the minimum set of attributes that exposes the greatest number of singletons as the best QID where singletons are the unique occurrence of a combination of values for a set of attributes. Its implementation is freely available on GitHub (https://github.com/isislab-unisa/qid_identifier_and_anonymizer); We observed that by generalizing only singletons detected by the QID (sex, ZIP, date_of_birth), we obtain nearly no singletons, and we just affected up to 2% of rows. The experiments have been performed on real open datasets released by the Italian Ministry of Infrastructure and Transport (freely available on GitHub https://github.com/isislabunisa/driver-license-datasets).
The rest of the article is structured as follows: in Section 2, we overview alternative approaches proposed in the literature to detect QID and perform anonymization; in Section 3, we present our approach to detect privacy issues by the number of occurred singletons, and we propose an anonymization approach based on the generalization and suppression; in Section 4, we report and discuss the performed evaluation; then, we conclude with some final considerations and future research directions.
In this section, we aim to overview the alternatives in detecting QIDs and corrective actions to sanitise a dataset. According to the PPDP principles, we focus on microdata, i.e., data records about individuals instead of data mining results. 2.1.
The anonymization approaches explicitly removes IDs and hide the sensitive information assuming that the latter should not be used in data mining algorithms. ID removal might not be enough: it is still possible to recognise individuals by QIDs. To prevent linking attacks, the datasets must be sanitized (Samarati, 2001) by applying anonymization operations among generalization, suppression, anatomization, permutation, and perturbation (Federal committee of statistical methodology, 2005).
Among the most famous privacy models, we cite k-Anonymity
Our approach is based on privacy issues detection, followed by an anonymization approach based on generalization and suppression. The workflow starts from the human provision of the dataset to test, and it automatically returns the best QID. If the best QID matches (year, municipality, gender), it also provides the corresponding generalization. 3.1.
We interpreted the detection of privacy issues as the occurrence of unique values by considering a single column or a combination of them. These unique values are referred to as singletons. We elect IDs and QIDs by the number of occurred singletons. The implemented pseudo-code follows: def detect_ID_and_QID(dataset): identifiers = [] stats = {} for size in range(1, num_columns): # all the dataset column subsets of "subset_size" subsets = get_subsets(columns_to_check, size) # IDs: columns containing all distinct values temp_IDs, still_to_check = get_IDs(dataset, subsets) IDs += temp_IDs # for each subset, it stores the singletons number stats.update(get_stats(dataset, still_to_check)) columns_to_check = list(set(still_to_check)) # best QID: the smallest subset of columns exposing the greatest number of singletons best_QID = get_best_QID(stats)
In the best QID election, we first consider the number of singletons detected by each set of attributes. If more than one set of columns share the same number of singletons, we elect as best QID the minimum set of columns. 3.2.
To ameliorate the detected privacy issues, we propose an anonymization approach based on generalisation and suppression. We suppress incomplete rows at the beginning of our technique; then, only the generalization is permitted. We favor the generalization to the suppression since we prefer to publish incomplete information rather than preventing the publication at all.
We focus on the QID (date_of_birth, ZIP, sex) since it is a well-known QID. In particular, we focus on a slightly simplified version of this QID, where we only have access to the year_of_birth. It is simplification without loss of generality since it can be easily generalized to the entire date. However, by only considering years, we can straightforwardly generalize dates by the mean value of a range. Moreover, in Italy, there is a two-way correspondence between ZIP codes and Municipalities. Therefore, they can be used interchangeably. We aim to detect which column or combination of columns is worth to generalize to achieve the minimum number of singletons by modifying the minimum amount of rows.
For the numerical attribute (i.e., year_of_birth), we consider the standard approach of substituting values by intervals. Therefore, we sort rows by year_of_birth, split all the rows into groups of at least k values. If we split two rows containing the same year in creating groups, we iteratively merge those rows in the same group until the cut splits rows with different years. Each year is substituted with the interval [min_year, max_year). We also apply a second strategy where the average value of the interval replaces each interval. We hypothesize that if current years mainly correspond to the mean value of the range, fewer rows will be modified while still reducing the number of singletons.
About the sex column, we replace male and female values by any gender. In this case, the generalization plays the same role as cell suppression. About the municipality column, we exploit the hierarchy induced by our national administrative levels: municipalities are generalized by provinces, provinces by regions, regions by states. In our experiments, we only consider the first level of this hierarchy by generalizing municipalities by provinces. For categorical attributes (i.e., sex and municipality), we apply both a global and a local recording. While in the global recording we affect the entire dataset, at a local level, we only modify rows related to the singletons disclosed by the best QID. We hypothesize that the local recording can introduce a sufficient level of privacy protection while affecting a minimal number of rows (i.e., slightly decreasing the overall dataset quality). The implemented approach can be resumed as follows: the rows containing empty values are dropped out, and the removed rows alter the counter of affected rows. The full version of the dataset (i.e., only rows without any empty cell) is considered in the following steps; the following generalizations are performed: all the municipalities are generalized by the corresponding province; only the municipalities of the rows corresponding to the singletons detected by the best QID are generalized by the corresponding province; all the values of the sex column are generalized by any gender; only the values of the sex columns corresponding to the singletons detected by the best QID are generalized by any gender; all the birth_years are generalized by the corresponding intervals; all the birth_years are generalized by the mean value of the intervals generated as before; all the attributes are generalized by combining every pair of the generalizations described so far and by generalizing all fields at once; for each performed generalization, we compute the number of singletons, the percentage of singletons, the number of distinct values, the number of modified and removed rows; we elect the best generalization by considering the one that achieves the minimum number of singletons while affecting the minimum number of rows.
We tested our approaches on real datasets released by the Italian Ministry of Infrastructure and Transport. These (anonymized) datasets contain information related to the driver licenses of all the Italian regions. We downloaded them in October, 2019 from the official site (http://dati.mit.gov.it/catalog/dataset/patenti). In January 2020, the Ministry updated the online version by significantly reducing the (already minimal) available content. The tested datasets (in their original form) are available on the GitHub (https://github.com/isislab-unisa/driver-licensedatasets). 4.1.
We selected only the columns related to personal information (i.e., the municipality and the province reported as the driver residence, the year of birth, and the sex), while we discarded all the Nonsensitive information, such as the driver's license details, and the numerical ID. The algorithm is linearly correlated to the dataset size. It takes 0.0152 seconds for processing datasets with 6M rows. Results of the QID identifier. The results of our privacy issue detecting approach are available on GitHub, here omitted due to the lack of space. [Birth_year, ZIP, Sex] is reported as best QID in all the regions. Even if datasets are anonymized, our approach highlights the possibility of distinguishing up to 2% (1.93%) of singletons uniquely. If 2% seems to be a negligible amount of disclosed identities, it is worth noticing that the maximum number of disclosed singletons is more than 25K. It implies that removing IDs is not enough, and further anonymization actions must be performed to publish sanitized datasets. These results reply to RQ1. 4.2.
We considered three datasets used in the previous analysis, heterogeneous in the disclosed percentage of singletons. Results are provided in Table 1.
Year range VS Year mean value. By comparing the year generalization by intervals (row Y_ran of Table 1) and by mean values (row Y_avg of Table 1), we observed that the mean value gains 95% fewer singletons while affecting 7% rows less than the range approach.
Global VS Local recording. By comparing the global generalization of the Municipality (M row of Table 1) and its local recording (M_loc row of Table 1), we observed the local recording achieves results close to 0, while the global recording succeeds in completely avoiding the disclosure of singletons. On the other side, the global recording affects the entire dataset, significantly decreasing the dataset quality, while the local recording affects only the 2% of the rows. We consider a good thread-off between privacy-preserving and data quality the generalization of the municipality (and the sex) only of singletons disclosed by the QID (year_of_birth, sex, ZIP) (RQ2). Comparison with k-Anonymity. We used the Valle d'Aosta dataset to compare our approach and kAnonymity (https://dzone.com/articles/an-easy-way-to-privacy-protect-a-dataset-using-pyt). We run kAnonymity by generalizing Municipalities by their Provinces, Sex by any gender, and the Year by intervals of width 4. We consider the generalization of any set of attributes. We allowed suppression equals to 0.01 in all cases, but in the sex, generalization is set to 0.05. At the global level, both our approach and k-Anonymity modify almost the entire dataset. While we obtain a generalized version of the dataset information, k-Anonymity removes many rows. When a small number of singletons occurs, k-Anonymity drops the corresponding rows. In all the other cases, it drops at least 200 rows and modifies all the other ones. Thanks to the local recording performed by our approach, we can obtain a minimum number of singletons (near to 0) while affecting a small portion of the dataset (up to 2%). Concluding, we achieve the same results in privacy-preserving, while our results lead to better data quality thanks to the local recording.
In this article, we propose to detect QID by counting singletons in a dataset. We observed that the best QID (date_of_birth, sex, ZIP) discloses up to 2% (and up to 25K) of singletons in already anonymized datasets. When a privacy leakage is reported, PAs usually react by closing data or publish poorly informative datasets. As an example, the datasets we analyzed were substituted with a version with significantly lower informativeness, as only the province of residence, driving license category, and release date are provided. These datasets, in our opinion, are reduced to pointless Open Data. Instead of making data useless, we suggest investing in further sanitation actions. In this article, we observed that we achieve the minimum number of modified rows (up to 2% of affected rows) while obtaining the number of singletons close to 0 thanks to a local recording. We aim to provide our proposal as a framework to support PAs in publising datasets significantly more informative than the currently available on their websites while preserving citizens privacy. Federal Committee on Statistical Methodology (2005) Statistical policy working paper 22. Report on Statistical
Disclosure Limitation Methodology . IEEE Trans-actions on Knowledge and
Matteo Pastore Maria Angela Pellegrino Matteo Pastore was Born in Salerno in 1998. He will graduate at the University of Salerno in 2020. He will continue his studies with a Master's degree in Computer Science. He is interested in Cloud Computing, Cybersecurity, Open Data, Networks.
Maria Angela Pellegrino, born in 1994, graduated in Computer Science at Master Level in 2018 at the University of Salerno. From 2018, she is a Ph.D. student in Computer Science at the University of Salerno under the supervision of Professor Vittorio Scarano. Her studies focus on how to improve the quality of (Linked) Open Data while preserving the privacy of individuals. Research interests include data quality, privacy, Open Data, and Semantic Web.
Vittorio Scarano
Vittorio Scarano is a Full Professor of Computer Science at the University of Salerno (Italy).
Since 1996, he (with Alberto Negro) funded and co-directs the ISISLab laboratory within the Department.
ISISLab has been hosting, until now, the research activity of 20 PhD students, more than 20 collaborators
(grants, fellowships) and provided support for more than 120 theses (Bachelor and Master level) with
computing facilities such that a 38-nodes IBM cluster, file and application servers, teaching lab, a
stereoscopic screen, augmented reality devices etc.He is co-author of more than 140 papers in
internationally refereed journals and conferences of IEEE, ACM, etc. and he has been the PhD supervisor of
several PhD students of the Computer Science PhD program at the University of Salerno. In 2000, he has
been awarded (with his co- t poster award'' at the 9th World Wide Web Conference (WWW9).
In 2008, he has been awarded by IBM with the International IBM Jazz Innovation Award as a grant of 25.000$.
He coordinated the