Tasnim Naima, Mohammadi Jafar, Sarwate Anand D, Imtiaz Hafiz
Department of Electrical and Electronic Engineering, Bangladesh University of Engineering and Technology, Dhaka P.O. Box 1205, Bangladesh.
Nokia, Werinherstraße 91, 81541 Munich, Germany.
Entropy (Basel). 2023 May 22;25(5):825. doi: 10.3390/e25050825.
Large corporations, government entities and institutions such as hospitals and census bureaus routinely collect our personal and sensitive information for providing services. A key technological challenge is designing algorithms for these services that provide useful results, while simultaneously maintaining the privacy of the individuals whose data are being shared. Differential privacy (DP) is a cryptographically motivated and mathematically rigorous approach for addressing this challenge. Under DP, a randomized algorithm provides privacy guarantees by approximating the desired functionality, leading to a privacy-utility trade-off. Strong (pure DP) privacy guarantees are often costly in terms of utility. Motivated by the need for a more efficient mechanism with better privacy-utility trade-off, we propose Gaussian FM, an improvement to the functional mechanism (FM) that offers higher utility at the expense of a weakened (approximate) DP guarantee. We analytically show that the proposed Gaussian FM algorithm can offer orders of magnitude smaller noise compared to the existing FM algorithms. We further extend our Gaussian FM algorithm to decentralized-data settings by incorporating the CAPE protocol and propose capeFM. Our method can offer the same level of utility as its centralized counterparts for a range of parameter choices. We empirically show that our proposed algorithms outperform existing state-of-the-art approaches on synthetic and real datasets.
大公司、政府实体以及诸如医院和人口普查局等机构通常会收集我们的个人和敏感信息以提供服务。一个关键的技术挑战是为这些服务设计算法，既要提供有用的结果，又要同时保护所共享数据的个人隐私。差分隐私（DP）是一种出于密码学动机且数学上严谨的方法来应对这一挑战。在差分隐私下，一种随机算法通过近似所需功能来提供隐私保证，从而导致隐私与效用之间的权衡。强大的（纯差分隐私）隐私保证在效用方面往往成本高昂。出于对一种具有更好隐私 - 效用权衡的更高效机制的需求，我们提出高斯功能机制（Gaussian FM），它是对功能机制（FM）的一种改进，以较弱的（近似）差分隐私保证为代价提供更高的效用。我们通过分析表明，与现有的功能机制算法相比，所提出的高斯功能机制算法可以提供数量级更小的噪声。我们通过纳入CAPE协议将高斯功能机制算法进一步扩展到分散数据设置，并提出capeFM。对于一系列参数选择，我们的方法可以提供与其集中式对应方法相同水平的效用。我们通过实验表明，我们提出的算法在合成数据集和真实数据集上优于现有的最先进方法。
