Central Piecewise Mechanism for Numeric Queries
Open Access
- 3 March 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Privacy
- Vol. 3, 13-25
Abstract
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 at https://github.com/ay0408/Central-PM.Keywords
Funding Information
- JSPS KAKENHI (20H05967)
- JSPS KAKENHI (21H05052)
- JSPS KAKENHI (23K28035)
- JSPS KAKENHI (23K18501)
- JSPS Grant-in-Aid for JSPS Fellows (23KJ0649)
This publication has 30 references indexed in Scilit:
- Privacy-Preserving Genomic Statistical Analysis Under Local Differential Privacy2023
- Differential privacy in deep learning: Privacy and beyondFuture Generation Computer Systems, 2023
- Differential Privacy via a Truncated and Normalized Laplace MechanismJournal of Computer Science and Technology, 2022
- Privacy-preserving techniques of genomic data—a surveyBriefings in Bioinformatics, 2017
- Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds2016
- Differential Privacy: An Economic Method for Choosing Epsilon2014
- Differentially Private Data Release through Multidimensional PartitioningLecture Notes in Computer Science, 2010
- Our Data, Ourselves: Privacy Via Distributed Noise Generation2006
- Differential Privacy2006
- Calibrating Noise to Sensitivity in Private Data Analysis2006