Advanced Central Piecewise Mechanism with Smooth Sensitivity

We propose an advanced central piecewise mechanism with smooth sensitivity (SS-CPM), which provides bounded and unbiased output while introducing tailored perturbation for each input dataset. We also enhance it by varying the allocation of the privacy budget to the $\alpha$ and $\beta$ values in the SS-CPM.

In "stats_feature" folder, we pre-evaluated the features of TDT statistics and $\chi^2$-statistics for the experiments.

In "SS-CPM vs. CPM" folder, we compared the output accuracy between the SS-CPM and the original CPM. The results indicate that the SS-CPM can provide the highest output accuracy among the existing bounded and unbiased differentially private mechanisms. We also evaluated the changes in the output range.

In "Varying $\alpha$ and $\beta$" folder, we evaluated the effects of the allocation of the privacy budget.

Supplemental Results

In "Varying h" folder, we compared the accuracy while varying the distribution $h$. We considered the cases where $h(z)$ is $\frac{\sqrt{2}}{\pi(z^4+1)}$, $\frac{2}{\pi(z^2+1)^2}$, $\frac{3}{2 \pi (z^6 + 1)}$, and $\frac{5 \sqrt{5} - 5}{4 \pi (z^{10} + 1)}$. From the results, we employed $h(z) = \frac{\sqrt{2}}{\pi(z^4+1)}$ in the main experiments.

In "vs. Unbounded SS" folder, we compared the SS-CPM with the conventional unbounded smooth sensitivity-based mechanism. The results indicate that the averaged output error of the SS-CPM is expeceted to be larger than that of the unbounded mechanism, although the SS-CPM has an bounded output range. Possilbe solutions to this issue would include considering distributions that allow the simultaneous handling of the sliding and dilation properties. Ultimately, we aim to construct a mechanism that achieves bounded and unbiased outputs while providing theoretically higher accuracy than any unbounded or biased mechanism.

Future Directions

・Developing a privacy-optimized SS-CPM for multiple numeric queries.

・Integrating the concept of direction-oriented smooth sensitivity [DOSS, Enhanced DOSS].

・Conducting sophisticated analysis of the variation in the $s$, $k$, and $l$ values.

・Finding optimal distributions for $h$.

・Considering varying $T$.

・Exploring mechanisms without $H(w)$.

Note

For details of our methods and discussion, please see our paper entitled "Advanced Central Piecewise Mechanism with Smooth Sensitivity".
(cf. Central Piecewise Mechanism)

Contact

Akito Yamamoto

Division of Medical Data Informatics, Human Genome Center,

the Institute of Medical Science, the University of Tokyo

a-ymmt@ims.u-tokyo.ac.jp