ARX papers: 2018 2018 ARX SafePub A Truthful Data Anonymization Algorithm With Strong Privacy Guarantees

[idhamari]

Bild, Raffael, Kuhn, Klaus A. and Prasser, Fabian. "SafePub: A Truthful Data Anonymization Algorithm With Strong Privacy Guarantees" Proceedings on Privacy Enhancing Technologies, vol.2018, no.1, 2018, pp.67-87. https://doi.org/10.1515/popets-2018-0004

[idhamari]

The paper is related to the implementation of epsilon-delta differential privacy in ARX i.e. EDDifferentialPrivacy

It presents a data publishing algorithm that satisfies the differential privacy model. The transformations performed
are truthful, which means that the algorithm does not perturb input data or generate synthetic output data. Instead, records are randomly drawn from the input dataset and the uniqueness of their features is reduced.

The approach can be parameterized with different objective functions to optimize its output for different applications. We show this by integrating six well-known data quality models.

The algorithm can be used with reasonable privacy parameters resulting in high degrees of protection.
By parameterizing the generic method with an objective function quantifying the suitability of data for building statistical classifiers, the prediction accuracies compared very well with results obtained using state-of-the-art differentially private classification algorithms.

DP is not good enough:

• Implementations are often non-truthful, i.e. perturbative, as they rely on noise addition.
• The semantics of DP are complex and it has been argued that the approach is much more difficult to explain to decision-makers.
• DP mechanisms are typically special-purpose algorithms developed for specific applications

Note: Microdata is data on the characteristics of units of a population, such as individuals, households, or establishments, collected by a census, survey, or experiment.

[idhamari]

2.1 Dataset:

• D: dataset with m attributes
• Omega_1, Omega_2, ..., Omega_m: domains of the attributes (columns)
• D_m: Univese of all datasets
• r = r_1,r_2,..,r_m: a unique record in the dataset (row)

Q: not clear "and refer to such datasets as microdata"???

2.2 Transformation Models:

Data anonymization is typically performed by reducing the distinguishability of records. Common methods:

- Clustering and aggregation of data items
- The introduction of noise 
- The generalization and suppression of attribute values

The paper focuses on attribute generalization through user-specified hierarchies, which describe rules for replacing values with more general but semantically consistent values on increasing levels of generalization.

• Each value on level 0 is called a leaf e.g. the leaf nodes of “[20, 80[” are “20”, ..., “79”
• The highest level suppresses the value so the root value of all hierarchies is ∗

2.3 Solution Spaces and Search Strategies

• Most anonymization algorithms are search algorithms through all possible outputs of the data transformation model.
• These search algorithms are often implemented in combination with generalization hierarchies.
• The exact nature of the search space depends on the generalization method
• For example, full-domain generalization generalizes all values of an attribute to the same level. With subtree generalization different values of an attribute can be generalized to different levels.
• This paper focuses on full-domain generalization, which results in search spaces that can be described with generalizaion lattices.

The above figure shows a sample of a lattice tree:

• The numbers are the anonymization hierarchy levels e.g. 0 is the original data.
• First level at the bottom represents original data, and the last bottom at the top represents the final level of anonymization (all data are suppressed).
• Following any branch, only one attribute changes it is the anonymization hierarchy level.
• generalisation schem is a mapping function that maps records to genralized records: g:Omega_1x...xOmega_m---> (Omega_1 U A_1)x...x(Omega_m U A_m)
• Solution space G_m is the set of all full-domains generalization schemes of the generalization hierarchies of a dataset.

2.4 Anonymization Operators

• An anonymization operator implements a privacy model.
• It determines whether or not a record or dataset satisfies the privacy requirements and may also modify the data. For example, in clustering algorithms, the anonymization operator may merge the records within a cluster into an equivalence class that satisfies k-anonymity
• The anonymization operator typically suppresses records that do not satisfy the privacy requirements

2.5 Quality Assessment

• Measuring reductions in data quality due to anonymization is non-trivial as usefulness depends on the use case
• Special-purpose (or workload-aware) quality models quantify data quality for a specific application scenario,e.g. statistical classification.
• General-purpose quality models can be employed when use-case is not available
• Estimating data quality by quantifying the amount of information loss, e.g. by measuring similarities between the input and the output datasets
• Three levels of information loss:
  • Aattribute-level: e.g. distributions of attribute values
  • Cell-level: reductions in the granularity of data
  • Record-level: differences in the sizes of equivalence classes
  • Q: cell level? :

2.6 Differential Privacy

see 2013 Practicing differential privacy in health care
(epislon, δ)-Differential privacy can be formally defined with respect to two datasets D 1 and D 2 satisfying |D 1 ⊕D 2 | = 1, which means that D2 can be obtained from D 1 by either adding or removing one record

**Q: definition 2: understanding **