图 1：传统的 shuffle 模型协议和三个挑战
图2：开发了保护隐私的数据分析协议“本地无噪声协议”
由统计数学研究所村上隆夫副教授、电气通信大学清佑一教授和米乐m6官方网站研究员江口丽雄组成的研究小组正在开发一种坚决防止个人数据泄露的方法。差分隐私 (DP)」※１在开发的协议中，每个用户按原样加密他们的个人数据并将其发送到称为“洗牌器”的中间服务器。接下来，shuffler 对接收到的数据进行随机采样，添加虚拟数据，对数据进行打乱，然后将其发送给服务提供者。最后，服务提供商解密接收到的数据并估计所有用户的数据的频率分布。即使服务提供商或某些恶意用户尝试各种欺诈活动，该协议也可以安全、准确地估计频率分布，并且有望应用于基于此的各种数据分析。
这一成果被信息安全领域难度最高的国际会议——第 46 届 IEEE 安全与隐私研讨会 (S&P 2025) 接受（过去 5 年接受率：148%）。
随着智能手机、可穿戴设备、IoT（物联网）等的普及，收集位置信息和身体活动数据等各种个人数据并将其用于各种数据分析已成为可能。另一方面，由于此类数据分析使用个人信息，因此存在隐私问题。采用“差分隐私（DP）”来强力保护个人隐私。※１被广泛用作事实上的标准。
实现差分隐私的模型包括中心化模型、局部模型和洗牌模型。在中心化模型中，服务提供商持有所有用户的个人数据，并在从这些数据获得的数据分析结果中添加满足DP的噪声。虽然这种模式可以实现数据分析结果的高精度，但存在由于未经授权的访问而导致所有用户的原始数据从服务提供商处泄露的风险。在本地模型中，用户在自己的数据中添加满足DP的噪声并发送给服务提供商，服务提供商从噪声数据中获取数据分析结果。在该模型中，只有噪声数据被发送到服务提供商，因此不存在原始数据从服务提供商泄露的风险。但它存在数据分析精度较低的问题，因为每个用户都需要添加大量噪声来满足DP。
shuffle模型是近年来被提出的一种模型，旨在解决集中式模型和本地模型的缺点。具体来说，我们将在用户和服务提供商之间引入一个称为“shuffler”的中间服务器。在传统的shuffle模型协议中（图1），每个用户给自己的数据添加噪声，对其进行加密，并将其发送到shuffler，shuffler对数据进行随机shuffle并将其发送到服务提供商。服务提供商通过对接收到的数据进行解码，提取混洗后的噪声数据，并从中获得数据分析结果。通过该洗牌器进行洗牌具有增加匿名性的效果，并且可以相应地减少用户添加的噪声。此外，由于原始数据不发送给服务提供商，因此可以实现比本地化模型更高的数据分析准确性，同时与集中式模型相比降低了服务提供商泄露原始数据的风险。
但是，传统的随机播放模型存在三个主要问题。第一个问题是容易遭受“投毒攻击”，即一些恶意用户发送与自己数据不同的虚假数据，降低数据分析的准确性。特别是，随着隐私的增加，用户通常需要添加的噪声量也会增加，而攻击者却不必为虚假数据添加噪声，从而导致数据分析的准确性更大程度地恶化。第二个问题是容易受到“共谋攻击”，即服务提供商与某些用户共谋。具体来说，通过从串通用户那里获取噪声数据，服务提供商可以通过洗牌来减少匿名化的影响，从而可以推断其他用户的原始数据（即泄露私人信息）。第三个问题是数据分析的准确性。具体来说，虽然相比局部模型可以减少用户添加的噪声，但问题是用户添加的噪声量仍然很大。例如，所有用户的数据频率分布※2的任务中，不常见的类别（或区间）被淹没在噪声中，无法进行高精度的分析。到目前为止，这些问题还没有提出根本性的解决方案。
在这项研究中，我们专注于估计频率分布作为数据分析任务，并开发了一种名为“局部无噪声协议”的新协议，从根本上解决了传统 shuffle 模型容易遭受“中毒攻击”和“共谋攻击”的脆弱性（图 2）。通过开发的协议，用户可以加密自己的数据并将其发送到 shuffler，而不会添加任何噪音。之后，洗牌器执行三个过程：（1）随机采样，（2）添加虚拟数据，以及（3）洗牌。首先，我们以一定的概率（随机抽样）删除从每个用户收到的数据。接下来，对于数据的每个可能值，根据被称为“伪数分布”的分布来确定伪数据的数量，并且添加该数量的加密伪数据（伪数据的添加）。最后，将剩余的用户数据和虚拟数据随机打乱（shuffle）并发送给服务提供商。服务提供商解密并提取打乱后的数据，并从中计算频率分布。在本研究中，我们将洗牌器不仅对数据进行洗牌，还进行随机采样并添加虚拟数据的模型称为“增强洗牌模型”。
所开发的协议最大的特点是用户不添加任何噪声（即“局部无噪声”）。在传统的shuffle模型协议中，由于用户添加噪声而导致部分用户发送虚假数据的“中毒攻击”，导致数据分析的准确性显着下降。此外，还存在通过“合谋攻击”推断其他用户的原始数据的风险，即服务器与某些用户合谋获取噪声数据。这两个漏洞都是由于用户注入的噪音造成的。另一方面，在开发的协议中，洗牌器而不是用户通过随机采样和添加虚拟数据来执行噪声添加过程，使其能够抵御“中毒攻击”和“共谋攻击”。因此，即使服务提供商或某些用户试图进行欺诈，也可以安全且准确地估计频率分布。此外，由于仅将加密数据发送到shuffler，因此可以避免从shuffler泄露原始数据的风险。此外，shuffler的随机采样、添加虚拟数据和洗牌三个过程可以在不解密从用户接收到的加密数据的情况下执行，并且可以使用任何公钥密码方法轻松实现所开发的协议。
此外，在这项研究中，通过引入一种称为“非对称几何分布”的新分布作为虚拟数分布，我们实现了比传统洗牌模型协议更准确的频率分布估计。本研究首次使用“非对称几何分布”作为满足DP的分布。通过引入这种分布，与7个最先进数据的传统协议相比，我们成功地将所有用户数据的频率分布与其估计值之间的均方误差（MSE）降低了2到4个数量级，这表明可以从高频到低频高精度地估计频率。
本研究中开发的协议可以估计高度准确的频率分布，同时有力地保护隐私。估计频率分布是最基本的数据分析任务之一，有望应用于从位置信息分析热门旅游景点，或从可穿戴设备分析所有用户身体活动数据的总体趋势等用例。
协会名称：第 46 届 IEEE 安全与隐私研讨会 (S&P 2025)
标题：差分隐私下用于准确鲁棒频率估计的增强随机播放协议
作者：Takao Murakami（统计数学研究所跨学科统计数学研究部副教授/国立先进工业技术研究所网络物理安全研究中心客座研究员）、Yuichi Kiyoshi（电子通信大学研究生院信息科学技术研究生院信息学系教授）、Reo Eriguchi（产业技术综合研究所网络物理安全研究中心研究员）
DOI：101109/SP61157202500019
论文发表日期：2024 年 11 月 16 日
这项研究得到了日本学术振兴会科学研究补助金 (22H00521、24H00714、24K20775)、日本科学技术振兴机构 AIP 加速研究 (JPMJCR22U5) 和日本科学技术振兴机构 CREST (JPMJCR22M1) 的部分支持。