Dec, 2023

通过散列函数降低局部差分隐私下的子图计数通信成本

PDF
TL;DR使用哈希函数来减少子图在边缘局部差分隐私下的通信成本，通过将沟通成本降低为 $s^2$ 倍的采样速率方法，减少三角计数的误差 1000 倍。
发现论文，激发创造
  • 图统计数据的局部差分隐私分析

    在本研究中，我们考虑了一种本地模型，提出了使用局部差分隐私的子图计数算法，包括三角形计数和 K 星计数，并证明了另一个轮可以显著提高效用，在实验中表明可以在局部差分隐私模型中准确估计子图计数。

    Oct, 2020

  • 来自匿名消息的私人计数：凭借消失通信开销的接近最优准确性

    本文介绍了中心模型、本地 DP 模型和洗牌 DP 模型，并提出了在洗牌 DP 模型下用于机器学习的两种基本聚合方法，其精度接近中心 DP 算法，而通信效率与不加隐私约束的通信需求基本匹配。

    Jun, 2021

  • 有限计算机上的差分隐私

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

    Sep, 2017

  • 本地、私有、高效的简明直方图协议

    本研究给出了关于差分隐私的本地模型下的频率估计的有效协议和匹配准确性下限，研究了能产生数据简明直方图表征的协议，以及在公共硬币模型下的协议。

    Apr, 2015

  • 打破通信 - 隐私 - 准确性三难题

    该研究提出了一种基于 Kashin 表示和随机抽样的方案以及利用 Walsh-Hadamard 矩阵的递归结构来实现隐私和通信效率的联合优化编码和解码机制，对平均值估计和频率估计等问题进行了研究。

    Jul, 2020

  • 基于通信复杂度的局部隐私估计的下限

    本文为研究局部隐私约束下的估计方案制定下限，推导出了私有估计和受通信限制的估计问题之间的等价性，适用于任意交互的隐私机制，并且得出了所有不同隐私保护级别的尖锐下限。作者作为对研究结果的一个重要推论，证明了有界或高斯随机向量的均值估计的最小最大均方误差按比例缩放的结论为 $d/n * d/min (ε,ε^2)$ 。

    Feb, 2019

  • 局部隐私分布估计和重要元素中的通信复杂度

    本文研究在保障隐私和通讯限制下分布估计和重头分估计的问题，提出了使用局部差分隐私的样本最优方案，并表明 Hadamard 反应方案可以用于重头分估计。

    May, 2019

  • 差分隐私密度最大子图检测

    该研究提出了首个用于私有网络中寻找最密子图的差分隐私算法，并展示了该算法在实际网络中隐私和准确性之间的权衡。

    May, 2021

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

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

    Dec, 2009

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

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

    Nov, 2019