有限计算机上的差分隐私

Sep, 2017

Differential Privacy on Finite Computers

Victor Balcer, Salil Vadhan

TL;DR提供严格多项式时间的离散算法，用于近似分类数据集的直方图，同时保留与拉普拉斯机制相同的（纯）差分隐私保证，并基于受限离散计算模型，避免了基于实际算术的不同隐私算法攻击实现的可能性。

Abstract

We consider the problem of designing and analyzing differentially private algorithms that can be implemented on {\em discrete} models of computation in {\em strict} polynomial time, motivated by known attacks on floating point implementations of real-arithmetic differentially private algorithms (Mironov, CCS 2012) and the potential for timing attacks on expe

differential privacy discrete algorithms histogram approximation polynomial-time geometric mechanism

发现论文，激发创造

差分隐私的几何学：稀疏和近似情况

通过使用关联的高斯噪声和线性回归步骤，我们基于差分隐私机制的多项式对数组进行了矩阵突触连接和遗传差异，从而在线性查询的上下文中研究了准确性和隐私之间的权衡。

Dec, 2012

隐私感知的线性规划随机量化

该研究提出一种无偏差且具有差分隐私的量化机制，通过线性优化方法可以高效地找到最佳机制，实验证明该机制与基准方法相比可以获得更好的准确性和隐私权衡。

Jun, 2024

通过直方图实现本地和混洗差分隐私的分离

本文探讨如何在差分隐私的前提下，采用洗牌模型的协议来估算直方图，实现样本复杂度的大幅降低并确保数据的安全性。同时发现当遵守纯差分隐私和单信息的随机器的条件时，洗牌模型的效果和局部模型相当。

Nov, 2019

使用 FFT 的离散值机制和子采样高斯机制的严格差分隐私

提出一种基于隐私损失分布的数值账本方法，用于准确隐私计算，尤其是对子采样高斯机制的严格上下界隐私参数的计算，并给出幂系数约束下的隐私损失分布的误差分析，应用于计数查询的指数机制的计算也满足严格下界隐私参数。

Jun, 2020

普适效用最大化的隐私机制

本文提出了一种基于差分隐私的机制，以保证数据查询的数据隐私和查询效用之间的平衡。机制包含了每个可能的用户的期望最小化的代价函数，并且针对每个固定数量的查询和差分隐私级别，存在一种几何机制可以同时保证每个可能用户的最佳实用性，这是一种极强的实用性保障。

Nov, 2008

差分隐私的离散高斯

本研究探讨了在差分隐私框架下，使用离散高斯噪声可以提供与连续高斯噪声相同的隐私性和准确性保证，而且还提出了可用于准确采样的简单高效算法，表明其适用于私密回答计数查询或低敏感度整数值查询。

Mar, 2020

纯差分隐私与近似差分隐私之间

该研究通过指定参数 delta 来构建一个全新的下界，从而优化（epsilon，delta）差分隐私算法在高维数据库上精确回答统计查询的样本复杂度。除了新的下界之外，该研究还提出了纯粹和近似的差分隐私算法，用于回答任意统计查询，并通过对比标准拉普拉斯和高斯机制在最坏情况下精度保证方面的样本复杂度，改善了对该问题的解决方法。

Jan, 2015

差分隐私中拉普拉斯机制的最优性

研究了在物联网高度互联且敏感信息交换的背景下，拉普拉斯机制和李普希兹隐私的应用，以及不同维度空间下不同范数的误差最小化机制。

Mar, 2015

基于分布鲁棒优化的差分隐私

本文利用分布式鲁棒优化技术，开发了一种机制设计模型，以实现最高准确度和隐私预选级别的非渐近和无条件最优性保证。

Apr, 2023

优化差分隐私下的直方图查询

该研究提出了一种基于计数查询的线性组合方法，通过最优策略支持一组相关查询的答案，并对该策略的误差进行几何特征化并提出了优化方法，以应用于不同数据分析任务中的隐私保护。

Dec, 2009