PSI

在数据隐私日益重要的今天，如何在保护数据隐私的前提下进行数据交集操作成为了学术界和工业界共同关注的焦点。其中，两方私有集合交集（Private Set Intersection, PSI）作为一种重要的密码学应用，允许两个参与方在不知道对方完整集合的情况下，共同计算出双方集合的交集。本文将深入解读由梁之源等人撰写的论文《Benchmark of Two-party Private Set Intersection》，探讨PSI的基本概念、技术原理、应用场景以及最新进展。

一、PSI的基本概念

PSI的核心目标是允许两个参与方（通常称为发送方和接收方）在保护各自数据隐私的前提下，共同计算出它们集合的交集。在这个过程中，双方均不会了解到交集之外的其他信息。这种隐私保护特性使得PSI在许多场景中都具有广泛的应用价值。

论文原文标题：《Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory》

本文介绍了一种名为HG-LDP的新框架，旨在实现在有限内存空间内准确检测数据流中的前k个高频项，并提供严格的本地差分隐私保护。该框架解决了传统LDP技术在处理大数据集和内存限制时存在的“准确性、隐私性和内存效率”之间的不良权衡问题。通过设计新的LDP随机化方法，该框架能够有效地应对大规模项目域和内存空间受限的问题。实验结果表明，与基准方法相比，该框架能够在保证高精度的同时节省2300倍的内存空间。该框架的代码已经公开发布。

论文方法

方法描述。该论文提出了一种名为HG-LDP的框架，用于在数据流中跟踪Top-k项并保证用户隐私。该框架包含三个模块：随机化模块、存储模块和响应模块。随机化模块位于用户端，用于随机化用户的敏感数据；存储模块和响应模块位于服务器端，其中存储模块使用空间节省的数据结构。具体来说，使用HeavyGuardian（HG）数据结构来存储随机化的数据，并根据指数衰减策略更新计数。响应模块负责从HG中获取热门项目及其相应的计数，并将其映射到发布列表中，在发布之前对所有计数进行偏差校正。

论文原文标题：《Not Just Summing: The Identifier or Data Leakages of Private-Join-and-Compute and Its Improvement》

本篇论文探讨了在隐私保护下进行数据交互的问题，并针对Google提出的Private-Join-and-Compute库中存在的一些安全漏洞进行了分析和改进。具体来说，该库中的PIS协议和Reverse PIS协议在输入数据结构和处理过程中可能存在用户标识符泄露的风险。为了解决这些问题，本文提出了基于差分隐私技术的改进PIS协议，并对开源库进行了优化。通过使用Tamarin工具进行形式化分析和安全性证明，本文证明了改进后的PIS协议能够成功抵御已知攻击，并且不会带来明显的额外开销。