Abstract Privacy preserving dynamic data publication aims at protecting data while simultaneously preserving its utility when the data is published dynamically. For static data (i.e., data published only once), privacy is based on concepts such as k-anonymity and $$\epsilon $$ ϵ -differential privacy. In contrast, for dynamic data, the notions of m-invariance and $$\tau $$ τ -safety are considered. However, most current approaches focus solely on guaranteeing m-invariance and $$\tau $$ τ -safety without paying attention to the quality of the solution, such as maximizing utility. We propose a new heuristic approach for the NP-hard combinatorial problem of m-invariance and $$\tau $$ τ -safety, which is based on a mathematical optimization column generation scheme. The quality of a solution to m-invariance and $$\tau $$ τ -safety can be measured by the Information Loss (IL), a value in [0, 100], the closer to 0 the better. We show that our approach improves by far current heuristics, reducing IL by more than $$60\%$$ 60 % and, in some instances, by more than $$95\%$$ 95 % .

A privacy model is a privacy condition, dependent on a parameter, that guarantees an upper bound on the risk of reidentification disclosure and maybe also on the risk of attribute disclosure by an adversary. A privacy model is composable if the privacy guarantees of the model are preserved, possibly to a limited extent, after repeated independent application of the privacy model. From the opposite perspective, a privacy model is not composable if multiple independent data releases, each of them satisfying the requirements of the privacy model, may result in a privacy breach. Current privacy models are broadly classified into syntactic ones (such as k-anonymity and l-diversity) and semantic ones, which essentially refer to$\varepsilon $-differential privacy (e-DP) and variations thereof. While e-DP and its variants offer strong composability properties, syntactic notions are not composable unless data releases are conducted by a single, centralized data holder that uses specialized notions such as m-invariance and$\tau $-safety. In this work, we propose m-uncoordinated-syntactic-privacy (m-USP), the first syntactic notion with composability properties for the independent publication of nondisjoint data, in other words, without a centralized data holder. Theoretical results are formally proven, and experimental results demonstrate that the risk to individuals does not increase significantly, in contrast to non-composable methods, that are susceptible to attribute disclosure. In most cases, the utility degradation caused by the extra protection is less than 5% and decreases as the value of m increases.

Continuous data publishing consists in the republication of updating microdata. The most relevant syntactic notions in continuous data publishing are based on m-invariance. This notion enforces that no user can be distinguished among, at least,m- 1 other users, each with distinct secret data. To achieve m-invariance, the existing methods must first alter the dataset to satisfy a property called m-eligibility. Essentially, a dataset can be made m-invariant if and only if it satisfies the m-eligibility constraint. Although guaranteeing the m-eligibility property is a crucial step, no theoretical study of the best strategies to achieve it has been carried out. This paper performs such a study by giving strategies and demonstrating their optimality under two approaches: insertion of counterfeit tuples and partial publication. The empirical evaluation of our proposal shows a significant reduction on the number of modifications needed to enforce m-eligbility of up to 41% with respect to the literature.