1. 引言

随着科技的飞速发展和信息技术的普及应用，人们时时刻刻都在不断地产生大量的数据信息。其中，键值数据在日常生活中有着广泛的应用场景，如购买过的物品及其价格、看过的电影及对其的评价分数、用过的手机软件及每日使用时长。通过对这些数据进行收集、记录和分析，可以挖掘出它们中的隐藏信息，对学术、工业、社会服务等多个领域都有重要意义。例如通过分析用户的购买记录，可以得出市场供给需求信息、通过分析用户的观影记录及评分，可以得出值得推荐的电影、通过分析用户手机软件使用情况，可以得出软件的受欢迎程度。但这些数据中往往包含着大量隐私信息，如购物数据会反映个人生活习惯和财务状况、电影评分数据会透露个人喜好偏向，如果直接将这些数据提供给其他人使用，不仅会对个人的人身安全、财产安全造成极大的威胁，也会使得降低用户共享数据的意愿。现如今，已有多个领域关注到了隐私保护问题的重要性，并针对特定问题提出了隐私保护的解决方案。然而，如何在保护用户隐私的前提下对数据进行收集，仍是亟待解决的问题。

目前，差分隐私[1] [2]作为一种效率高开销低的隐私保护技术，是学术界研究的热点方向之一。其中，本地差分隐私[3]于2013年被提出，它兼具差分隐私的优点，又摒除了对可信第三方的依赖，具有极高的实用性，在工业场景也得到了广泛的应用。谷歌公司设计了基于本地差分隐私的组件RAPPOR [4]来采集用户行为数据，苹果公司将其应用到手机上来保护用户的使用数据。

但是，现有的本地差分隐私机制大多未考虑到，实际应用中数据域快速变化的情况，需要在用户端实现与键域无关的扰动，才能增强隐私保护的鲁棒性。以本文主要研究的键值数据的收集估计为例，现有方案主要有PrivKVM [5]，PCKV-GRR [6]以及PCKV-UE [6]，这几个方案在用户端扰动环节都比较依赖于键域。实际应用中，数据域的随时变动会给现有方案造成较大的通信和计算负担。例如，PrivKVM是在整个大键域中进行随机抽样，而键域的变动会导致无效抽样；PCKV-GRR的随机扰动概率依赖于键域大小，随机扰动的映射对象依赖于键域内容，而键域的变动会导致扰动概率变化，扰动映射的对象不满足本地差分隐私的概念；PCKV-UE的编码方式依赖于键域，键域的变动会导致额外的通信开销或者错误的信息传输。因此，需要使用一种键域独立的键值数据扰动机制来应对实际应用中键域频繁变化的场景。

本文首先针对键域频繁变化的场景提出使用一种键域独立的本地差分隐私保护机制，该机制是一种键域独立的扰动机制，它在用户侧与键域大小和内容无关，具有较高的可用性。随后，本文将具体分析键域增加或减少情况下，各个方案对于扰动机制的处理与分析，通过对比实验验证本方案的优越性。最后，本文将在服务器端设计个性化的统计机制，使得数据的使用与分析更便捷且具有多样性。

本文的主要贡献包括3个方面：

1) 根据目前数据信息飞速变化的情况，定义了一个用户侧数据域独立的概念，以此应对数据域的新增和删减；

2) 基于本地差分隐私下键值数据的收集估计，对比几种机制面临键域新增或删减时，产生的问题和消耗的代价，以及实际发生时对应的策略；

3) 使用键域独立的方案，为服务器端数据收集统计设计出多样性的方案。

2. 理论基础

2.1. 相关工作

键值数据的收集与统计分析在推荐系统等领域有着极高的研究价值，但目前的相关工作都是基于固定的数据域去进行研究的。叶等人首次提出PrivKV、PrivKVM和PrivKVM+，其中PrivKVM迭代估计平均值以保证非偏性。PrivKV可以看作是只有一次迭代的PrivKVM。高级版本的PrivKVM+会选择了适当的迭代次数来平衡非偏性和通信成本。孙等人在PrivKV的框架下提出了另一种频率和平均值的估计器和几种机制来完成相同的任务[7]。他们还为机器学习[8] [9]中的其他复杂分析任务引入了关键值数据的条件分析。最近，顾等人提出了一种替代的键值扰动协议PCKV。PCKV调整了填充和采样协议，从每个用户的密钥值集中采样一个密钥值对。如果用户的键值对少于1个，则虚拟对将被填充，直到拥有l个键值对。然后，PCKV随机选择一组键值对，通过UE或GRR (即PCKV-UE或PCKV-GRR)干扰它，并将其发送给数据收集器。然而，PrivKVM需要运行多轮测试。这要求所有用户在所有过程中在线，这在许多应用程序中是不切实际的。PCKV的两种机制也有一些其他的限制。对于PCKV-UE，通信带宽成本与键域大小成正比，这在许多实际应用程序中可能是不可接受的。对于PCKV-GRR，其扰动概率与键域大小有关，因此GRR的估计精度随着键域大小的增大而迅速降低。

2.2. 基本原理

在本地差分隐私中，用户端在本地对数据进行扰动，然后将扰动后的数据发送给服务器，服务器再利用接收到的数据计算得到所需的统计信息。由于服务器无法接触到用户的原始数据，因而无法获得用户的隐私信息。本地差分隐私的形式化定义如下。

定义1. 本地差分隐私[3]。给定隐私预算，随机机制满足，当且仅当对于任意一对输入、和任意输出，输出相同的概率比满足

(1)

如果用户根据之前的输出，采用随机化机制而不是固定通用的，我们称这种随机化机制为提供交互式的。

定义2. 交互式本地差分隐私[3]。定义为随机扰动机制的输出域，随机变量是的一个视图。如果

(2)

适用于所有的，任意数据对，任意输出，我们称这种机制满足交互式的，的非交互版本当且仅当。

3. 算法设计

3.1. 方案设计

Wheel机制[10]是由王等人在2020年提出的用于集合数据频率估计的机制，而Wheel-KV方案是基于键值数据提出的一种新的机制，该机制对键值数据的收集与统计在效益上有较大的提升。

算法1. Wheel-KV用户端扰动算法。

输入：键值数据集合，其中，，随机种子为的哈希函数，隐私预算，覆盖参数。

输出：满足的隐私视图。

① 或；/* 将离散到*/ 。

② ；/* 将原始数据映射到*/ 。

③ 。

④。

⑤；/* 根据value的大小对进行调整，得到最终输出*/ 。

⑥输出。

算法2．Wheel-KV服务器端聚合算法。

输入：用户的隐私视图和对应的随机种子。

输出：所有键的频率估计与对应值的均值估计。

• ，；

• for ；

• for ；

• ；

• if or ；

• if or ；

• ；

• else ；

• end if

• end if

• end for

• end for

• for to ；

• ；

• ；

• end for

• 输出 频率估计与对应值的均值估计。

3.2. 键值数据域突然变化时的键值数据收集机制对比

PrivKVM机制：从当前键域中随机抽取一个序号，将扰动后的键值对发给服务器，扰动概率与键域大小无关，且扰动对象为当前键域的所有键。

PCKV-GRR机制：扰动概率，，与键域大小有关，且扰动对象为当前键域的所有键，输出为一个扰动后的键值对。

PCKV-UE机制：扰动概率，，与键域大小无关，且扰动对象为当前键域的所有键，输出为一个长度与键域大小有关的键值对向量。

Wheel-KV机制：扰动概率介于和之间，与键域大小无关，扰动对象为当前或更新后键域的所有键，输出为一个隐私视图实数。

键域新增时各机制对比如表1所示。

Table 1. Comparison of mechanisms when adding key fields

表1. 键域新增时机制对比

键域删减时各机制对比如表2所示。

Table 2. Comparison of mechanisms for key field deletion

表2. 键域删减时机制对比

3.3. 服务器端个性化榜单设置

根据Wheel-KV机制在用户端与键域无关的性质，我们可以在服务器端设计出个性化的榜单设置，以提高效用。

场景1：本地差分隐私下的新歌推荐榜

令歌曲ID为键值对的键，歌曲喜好程度为键值对的值，新歌曲库为全曲库的子集；发新歌时，新歌键域新增，发歌时间到达某时长后，歌曲不再计入新歌曲库，键域删减。该场景满足键域随时变化的模型，框架如图1所示。

Wheel-KV机制实现：

用户端：正常扰动。

服务器端：聚合操作只对新歌键域进行遍历扫描，而则根据新歌的发布或过期进行新增和删减。

Figure 1. New song chart data collection process

图1. 新歌榜数据收集过程

场景2：本地差分隐私下热搜键值对的统计分析

在很多情况下，我们只对频繁项更为关注，对于全键域的统计分析往往需要耗费大量通信资源和计算资源，无法支持实时更新。因此，可以考虑在较长间隔里进行全键域的统计分析，取出前10%的高频子键域，作为Wheel-KV机制遍历的键域，以此来统计前1%的高频键值对，针对突发热词，可以人为添加进该键域。该场景满足键域随时变化的模型，框架如图2所示。

Wheel-KV机制实现：

用户端：正常扰动。

服务器端：聚合操作只对一级频繁键域进行遍历扫描，而则根据人为改动进行新增和删减。

Figure 2. Real time high-frequency key value pair data collection process

图2. 即时高频键值对数据收集过程

4. 实验分析

4.1. 评价指标

我们通过所有键或部分键之间的均方误差(MSE)来评估频率和均值估计。

(3)

(4)

其中：和是真实频率和均值，和是估计的频率和均值，是键域的子集，默认域为；我们还考虑是前N个频繁键的集合(如前50个)，因为我们通常只关心频繁键的估计结果，且不常见的键可能并没有足够的样本来获得值均值的准确估计。

4.2. 参数设置

我们在数据集上进行了实验，在数据集中，用户数为，每个用户所拥有的和的值均满足均匀(或高斯)分布。高斯分布由，，生成。表3总结了我们所使用的不同域大小和数据分布的数据集。

Table 3. Statistical information of experimental database

表3. 数据集参数描述

4.3. 实验结果

4.3.1. 隐私预算对MSE的影响

本节对比了5种机制在不同隐私预算下的性能差异，实验结果如图3所示。可以看出，随着隐私增大，5种机制的MSE都在减小，相应地，频率估计和均值估计的结果会更加准确，数据效用也就越高。即越大，隐私保护程度越低，MSE越小，数据效用越高。同时，可以看到本文使用的WheelKV机制具有较好的效用，在频率估计和均值估计两方面都有不错的表现。

Figure 3. Effect of epsilon on MSE

图3. 不同机制下隐私预算对均值估计MSE的影响

4.3.2. 不同场景下额外通信次数

正本节对比了4种机制在面临键域变化时，额外通信的次数，结果如表4所示。可以看出，当键域新增或减少时，3种机制都需要进行额外通信，而Wheel-KV机制则不需要这一额外开销。

Table 4. The number of communications when the keyfield change

表4. 不同机制下遇到键域改变时的通信次数

4.3.3. 不同场景下额外通信次数通信带宽

Table 5. Communication bandwidth when the keyfield change

表5. 不同机制下遇到键域改变时的通信带宽

本节对比了当为8，为10,000时，不同机制的通信带宽，结果如表5所示。可以看出，当键域新增至两倍或减少至一半时，3种机制带宽有较大变化，且均大于Wheel-KV机制的带宽。

4.3.4. 对比新增键的统计准确性

在本节对比了当键域新增时，Wheel-KV机制分批处理和朴素地将所有数据一视同仁处理的性能差异，实验结果如图4所示。可以看出，随着键域增大，数据量变大，2种机制的MSE都在减小，但分批处理地MSE显然小于一致处理，数据效用更高。

Figure 4. Effect of epsilon on MSE when adding key fields

图4. 不同机制下键域新增时的MSE

4.3.5. 对比删减键的统计准确性

本节对比了当键域删减时，Wheel-KV机制分批处理和朴素地将所有数据一视同仁处理的性能差异，实验结果如图5所示。可以看出，随着键域减小，数据量变大，2种机制的MSE都在减小，但分批处理地MSE显然小于一致处理，数据效用更高。

Figure 5. Effect of epsilon on MSE for key field deletion

图5. 不同机制下键域删减时的MSE

4.3.6. 服务器端个性化设置频繁项集

本节对比了频繁项集处理和全域处理的性能差异，实验结果如图6所示。可以看出，MSE的差异不大，而频繁项集处理的耗时显著降低。

(a)

(b)

(a) 频繁项处理对MSE的影响；(b) 频繁项处理对MSE耗时的影响

Figure 6. Personalized frequent item processing

图6. 个性化频繁项处理

5. 总结

本文首先针对键域频繁变化的场景提出使用一种键域独立的本地差分隐私保护机制，该机制是一种键域独立的扰动机制，它在用户侧与键域大小和内容无关，具有较高的可用性。本文具体分析了键域增加或减少情况下，各个方案对于扰动机制的处理与分析，通过对比实验验证本方案的优越性。本文在服务器端设计个性化的统计机制，使得数据的使用与分析更便捷且具有多样性。

未来的工作是针对本文所提的键域独立的思想，对本地差分隐私下的其他机制进行深入研究，探索实际应用中键域随时变化情况下，达到更高的数据效用的方法和机制。

基金项目

江苏省重点研发计划(产业前瞻与关键核心技术)项目(BE2022068, BE2022068-1)；

中国高校产学研创新基金——新一代信息技术创新项目课题(2023IT049)。

参考文献