Central Piecewise Mechanism for Numeric Queries

With the flourishing of data science, further enhancement of privacy-preserving theories and techniques is required. Particularly, the concept of differential privacy has garnered attention in a wide range of fields and is being actively explored. Although various$\epsilon$-differentially private mechanisms have been proposed for a numeric query, a fundamental task in data analysis, the following two issues had remained unaddressed for a long time. The first is unrealistic results owing to the unbounded range of output values, and the second is the occurrence of bias in the modified results. The first methods to address these issues, the composite differentially private mechanisms (CDPMs), were recently proposed; however, room for improvement remains. The notable issues are complicated hyper-parameters making theoretical analysis of output errors difficult, and insufficient consideration of global sensitivity for noise generation. Therefore, this study first proposes a novel concise$\epsilon$-differentially private mechanism for a numeric query, the central piecewise mechanism (CPM). The CPM indeed provides bounded and unbiased output, and the variance of the output values is also shown theoretically. By capturing the characteristics of global sensitivity in detail, the amount of noise can be significantly reduced compared with the state-of-the-art CDPM. Subsequently, we further enhance the CPM for handling multiple numeric queries while considering a situation in which each query has its own privacy level. Given the required privacy level for each query, an optimal privacy guarantee when using the CPM can be achieved in its entirety. Moreover, we propose an efficient heuristic algorithm for providing sub-optimal guarantees. This ultimately improves the output accuracy when the overall privacy budget is fixed, because more budget can be distributed to each query. Experiments demonstrate that the proposed methods outperform existing methods by using real census data as well. Overall, this study is an important step in further exploring of bounded and unbiased$\epsilon$-differentially private mechanisms that provide more accurate and reliable outputs. The codes for the experiments are available athttps://github.com/ay0408/Central-PM.