Loose associations to increase utility in data publishing¹

Issue title: Data and Applications Security

Guest editors: Lingyu Wang and Basit Shafiq

Article type: Research Article

Authors: De Capitani di Vimercati, Sabrina^{a; *} | Foresti, Sara^a | Jajodia, Sushil^b | Livraga, Giovanni^a | Paraboschi, Stefano^c | Samarati, Pierangela^a

Affiliations: [a] Dipartimento di Informatica, Università degli Studi di Milano, Crema, Italy. E-mails: sabrina.decapitani@unimi.it, sara.foresti@unimi.it, giovanni.livraga@unimi.it, pierangela.samarati@unimi.it | [b] Center for Secure Information Systems, George Mason University, Fairfax, VA, USA. E-mail: jajodia@gmu.edu | [c] Dipartimento di Ingegneria, Università degli Studi di Bergamo, Dalmine, Italy. E-mail: parabosc@unibg.it

Correspondence: [*] Corresponding author: Sabrina De Capitani di Vimercati, Dipartimento di Informatica, Università degli Studi di Milano, 26013 Crema, Italy. E-mail: sabrina.decapitani@unimi.it.

Note: [1] A preliminary version of this paper appeared under the title “Extending loose associations to multiple fragments”, in: Proc. of the 27th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy (DBSec 2013), Newark, NJ, USA, July 2013 [12].

Abstract: Data fragmentation has been proposed as a solution for protecting the confidentiality of sensitive associations when releasing data for publishing or external storage. To enrich the utility of data fragments, a recent approach has put forward the idea of complementing a pair of fragments with some (non-precise, hence loose) information on the association between them. Starting from the observation that in presence of multiple fragments the publication of several independent associations between pairs of fragments can cause improper leakage of sensitive information, in this paper we extend loose associations to operate over an arbitrary number of fragments. We first illustrate how the publication of multiple loose associations between different pairs of fragments can potentially expose sensitive associations, and describe an approach for defining loose associations among an arbitrary set of fragments. We investigate how tuples in fragments can be grouped for producing loose associations so to increase the utility of queries executed over fragments. We then provide a heuristics for performing such a grouping and producing loose associations satisfying a given level of protection for sensitive associations, while achieving utility for queries over different fragments. We also illustrate the result of an extensive experimental effort over both synthetic and real datasets, which shows the efficiency and the enhanced utility provided by our proposal.

Keywords: Loose associations, fragmentation, confidentiality constraints, privacy, data publishing

DOI: 10.3233/JCS-140513

Journal: Journal of Computer Security, vol. 23, no. 1, pp. 59-88, 2015