The diferential privacy (DP) literature often centers on meeting privacy constraints by introducing noise to the query, typically using a pre-specifed parametric distribution model with one or two degrees of freedom. ...The diferential privacy (DP) literature often centers on meeting privacy constraints by introducing noise to the query, typically using a pre-specifed parametric distribution model with one or two degrees of freedom. However, this emphasis tends to neglect the crucial considerations of response accuracy and utility, especially in the context of categorical or discrete numerical database queries, where the parameters defning the noise distribution are fnite and could be chosen optimally. This paper addresses this gap by introducing a novel framework for designing an optimal noise probability mass function (PMF) tailored to discrete and fnite query sets. Our approach considers the modulo summation of random noise as the DP mechanism, aiming to present a tractable solution that not only satisfes privacy constraints but also minimizes query distortion. Unlike existing approaches focused solely on meet-ingprivacy constraints, our framework seeks to optimize the noise distribution under an arbitrary (ǫ, δ) constraint, thereby enhancing the accuracy and utility of the response. We demonstrate that the optimal PMF can be obtained through solving a mixed-integer linear program. Additionally, closed-form solutions for the optimal PMF are provided, minimizing the probability of error for two specifc cases. Numerical experiments highlight the superior performance of our proposed optimal mechanisms compared to state-of-the-art methods. This paper contributes to the DP literature by presenting a clear and systematic approach to designing noise mechanisms that not only satisfy pri-vacyrequirements but also optimize query distortion. The framework introduced here opens avenues for improved privacy-preserving database queries, ofering signifcant enhancements in response accuracy and utility.展开更多
基金supported by the Director,Cybersecurity,Energy Security,and Emergency Response,Cybersecurity for Energy Delivery Systems pro-gram,of the U.S.Department of Energy,under contract DE-AC02-05CH11231。
文摘The diferential privacy (DP) literature often centers on meeting privacy constraints by introducing noise to the query, typically using a pre-specifed parametric distribution model with one or two degrees of freedom. However, this emphasis tends to neglect the crucial considerations of response accuracy and utility, especially in the context of categorical or discrete numerical database queries, where the parameters defning the noise distribution are fnite and could be chosen optimally. This paper addresses this gap by introducing a novel framework for designing an optimal noise probability mass function (PMF) tailored to discrete and fnite query sets. Our approach considers the modulo summation of random noise as the DP mechanism, aiming to present a tractable solution that not only satisfes privacy constraints but also minimizes query distortion. Unlike existing approaches focused solely on meet-ingprivacy constraints, our framework seeks to optimize the noise distribution under an arbitrary (ǫ, δ) constraint, thereby enhancing the accuracy and utility of the response. We demonstrate that the optimal PMF can be obtained through solving a mixed-integer linear program. Additionally, closed-form solutions for the optimal PMF are provided, minimizing the probability of error for two specifc cases. Numerical experiments highlight the superior performance of our proposed optimal mechanisms compared to state-of-the-art methods. This paper contributes to the DP literature by presenting a clear and systematic approach to designing noise mechanisms that not only satisfy pri-vacyrequirements but also optimize query distortion. The framework introduced here opens avenues for improved privacy-preserving database queries, ofering signifcant enhancements in response accuracy and utility.
