Implementing the Exponential Mechanism with Base-2 Differential Privacy
Implementing the Exponential Mechanism with Base-2 Differential Privacy
复制标题
实现具有 Base-2 差分隐私的指数机制
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Christina Ilvento
中科院分区：
文献类型：
--
作者：
Christina Ilvento
尽管有很好的理论支持，差分隐私（DP）在实践中仍然是一个挑战。在某种程度上，这一挑战是由于将任意或无限精度的理论机制转化为浮点或固定精度的现实所带来的担忧。从Mironov证明使用浮点实现拉普拉斯机制的安全问题的令人不安的结果开始，已经提出了许多关于DP的真实实现的漏洞的合理问题。在这项工作中，我们研究的实用性，实施McSherry和Talwar的指数机制。我们证明，天真或恶意的实现可能会导致灾难性的隐私失败。为了解决这些问题，我们表明，该机制可以完全实现一组丰富的实用功能和隐私参数的值，有限的实际开销在运行时间和最小的代码复杂性。我们如何实现这一结果？我们采用了一个简单的技巧，从base-e切换到base 2，使我们能够执行精确的base-2算术。一个简短，精确的表达式总是可以用于加密，我们所遇到的唯一近似误差是将base-2隐私参数转换回base-e以用于报告目的。利用开源的高精度算法库可以简单高效地实现该机制的核心base 2算法。此外，实现的确切性质使其适合于简单的正确性监控和隐私证明。
Despite excellent theoretical support, Differential Privacy (DP) can still be a challenge to implement in practice. In part, this challenge is due to the concerns associated with translating arbitrary- or infinite-precision theoretical mechanisms to the reality of floating point or fixed-precision. Beginning with the troubling result of Mironov demonstrating the security issues of using floating point for implementing the Laplace mechanism, there have been many reasonable questions raised concerning the vulnerabilities of real-world implementations of DP. In this work, we examine the practicalities of implementing the exponential mechanism of McSherry and Talwar. We demonstrate that naive or malicious implementations can result in catastrophic privacy failures. To address these problems, we show that the mechanism can be implemented exactly for a rich set of utility functions and values of the privacy parameter epsilon with limited practical overhead in running time and minimal code complexity. How do we achieve this result? We employ a simple trick of switching from base-e to base 2, allowing us to perform precise base-2 arithmetic. A short, precise expression is always available for epsilon, and the only approximation error we incur is the conversion of the base-2 privacy parameter back to base-e for reporting purposes. The core base-2 arithmetic of the mechanism can be simply and efficiently implemented using open-source high precision arithmetic libraries. Furthermore, the exact nature of the implementation lends itself to simple monitoring of correctness and proofs of privacy.
有限计算机上的差异隐私
影响因子：
--
作者：
Balcer, Victor;Vadhan, Salil
通讯作者：
Vadhan, Salil