用于在分布式数据集上安全估计交集个数的隐私保护草图方法

《IEEE Transactions on Dependable and Secure Computing》:Privacy-Preserving Sketches for Securely Estimating Intersection Cardinality Over Distributed Data Sets

【字体: 大 中 小 】 时间:2025年12月31日 来源:IEEE Transactions on Dependable and Secure Computing 7.5

编辑推荐:

  隐私保护集合交集基数估计方法研究,提出SetXor静态集和SetXorDyn流式集的隐私安全方案,通过随机响应噪声注入和抽样机制降低误差,实现AARE减少110倍(合成数据)和80倍(真实数据),速度提升18.7倍。

  

摘要:

计算两个集合交集中的不同元素数量(即基数)是各种分布式系统中的基本任务,包括在广域网中测量源到目的地的流量以及在分布式数据库中进行数据同步。由于数据量巨大,这些系统中广泛使用了轻量级的概率方法(如FM Sketch和HyperLogLog Sketch)来估计集合交集的基数,这些方法具有内存效率高、准确性强和通信成本低的优点。然而,如果集合的摘要以及用于构建摘要的哈希函数被泄露给不可信的第三方,那么集合中敏感元素的隐私可能会受到威胁。直接应用差分隐私机制来保护摘要的隐私可能会导致较大的估计误差。为了解决这一挑战,我们提出了一种新的隐私保护摘要方法SetXor,用于安全地估计静态集合的交集基数。具体来说,我们在构建的摘要中加入了随机响应噪声,以实现局部差分隐私,同时确保SetXor摘要的可合并性。我们建立了一个具体的概率模型来减少噪声引起的估计误差,并对误差方差进行了理论分析。此外,我们还提出了一种新的摘要方法SetXorDyn,用于流式集合的交集基数估计,这些集合中的元素是按顺序出现的并且可能包含重复项。我们采用了一种类似采样的方法来消除元素出现次数的不同奇偶性对估计结果的影响,从而能够无偏地处理所有元素。我们在合成数据和四个真实世界数据集上进行了广泛的实验。实验结果表明,与现有的最佳方法相比,我们的方法在合成数据集上的平均绝对相对误差(AARE)降低了高达110倍,在真实世界数据集上降低了80倍,同时在相同的设置下实现了高达18.7倍的速度提升。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号