基于本地化差分隐私的政务数据共享隐私保护算法研究*

郝玉蓉 朴春慧, 2 颜嘉麒 蒋学红

(1. 石家庄铁道大学 石家庄 050043；2.河北省电磁环境效应与信息处理重点实验室 石家庄 050043；3.南京大学 南京 210023；4.河北省住房和城乡建设厅 石家庄 050051)

智慧政府作为电子政务发展到一定程度后的高级阶段[1-2]，是智慧城市理念对电子政务提出的更高要求。Z.Lv等[3]指出智慧政府作为智慧城市建设生态系统中重要组成部分，是政府利用信息通信技术实现各部门间数据互通、更为公开的可持续发展的政府服务[4]。这一点可以从G.Perboli等[5]建立的智慧城市模型中加以验证。电子政务的发展使政府部门的政务系统数量不断增加，积累了大量的部门业务数据[6]。数据共享成为推进智慧政府建设必不可少的任务。但若在没有适当预防措施的情况下就共享政务数据，将很容易推断出敏感信息，这一点可以从过去二十年中公开的数据泄露事件中得到证明，这些事件包括马萨诸塞州公共健康记录的去匿名化、Netflix用户的去匿名化以及参与全基因组协会研究的个人去匿名化[7]。

现有研究使用隐私保护技术对政务数据中可能存在的敏感信息[8]泄露进行了研究。当前的数据隐私保护技术大致可分为三类：基于匿名的隐私保护技术、基于加密的隐私保护技术和基于差分隐私的隐私保护技术。基于匿名的隐私保护技术根据隐私数据类型与应用场景的差别，又可以进一步划分为关系型数据隐私保护、社交图谱数据隐私保护以及位置与轨迹数据隐私保护。但基于匿名的方法通常缺乏严格的隐私安全保证，因此其更适用于小规模数据的隐私保护。基于加密的方法虽然具有更好的安全性保证，但其加密操作会带来大量的计算开销，这使其难以应用于资源受限的场景中。在过去的十几年中，差分隐私(DP)[9]蓬勃发展。由于其严格的数学定义和组合的灵活性，成为了隐私保护的标准，被广泛应用于大数据收集的各个方面。例如，美国人口普查局对人口统计数据就采用了DP模型。传统的DP模型被部署在了中央服务器上，但在实践中，很难找到一个真正的可信第三方，这在一定程度上限制了传统差分隐私的应用。本地化差分隐私(LDP)[10-11]在DP的基础上应运而生，其不仅可以抵御任意背景知识攻击，还能够抵御不可信第三方攻击。目前，Google[12]、Apple[13]等公司已使用LDP模型用于收集用户默认浏览器主页和搜索引擎设置的信息。但将LDP模型应用于隐私保护政务数据共享中的研究工作还较少，这是由于这些前沿方法需要结合应用场景和变化的需求进行创新应用。在政务数据共享场景中，LDP模型存在准确性低、统计误差大等缺点，在数据域大且数据量较少的情形中尤为显著。

为了解决这些问题，本文在LDP模型中采用数据分箱来降低统计误差，并在不同分布下获得较高的数据效用。本文的主要贡献如下：

a.针对政府部门间共享统计数据的场景，提出了基于LDP的政务数据共享方法，其可在推行数据共享的基础上为敏感信息提供可控制的隐私保护。

b.该方法解决了当前隐私保护算法在数据域较大时对数据量大小要求严格的问题，有效降低了数据的统计误差，能在保护政务数据隐私的同时，提供可用的统计信息。

c.所提方法在不同的数据分布中均保持了较优的数据效用性，能适应于多种不同分布的隐私保护任务。

1 相关工作

在本地化差分隐私中，一个统计数据库的查询结果不会受到任何单一隐私数据的影响，它能在确保处理后统计信息可用的需求下保护个人信息不被泄露。因此可将LDP应用于政府部门间共享统计数据的场景中，确保数据共享过程中敏感信息的安全。

下面通过一个简单示例说明本地化差分隐私技术在统计数据共享应用中的隐私保护作用。数据提供部门(如税务部门)将高收入者(如年收入100万美元以上)按年龄分组，共享人数统计数据，如图1所示。通常，个人收入状况属于敏感隐私数据。攻击者的目的可能是确定某个特定的人(攻击目标)——如u6是否为高收入者。攻击者通过各种方式掌握了大量背景知识——如图1所示统计数据以及表1中5位年龄为30岁的高收入者身份。若攻击者还知道u6的年龄为30岁，则可以判定u6是一位年收入100万美元以上的高收入者，导致u6的收入状况信息遭到泄露。而采用LDP技术，对图1中各个年龄高收入者的统计数据(频数)做扰动处理，30岁对应的频数值可能会从6变为5.5或变为7.2，攻击者根据掌握的背景知识——扰动后的统计数据、5位年龄为30岁的高收入者身份、u6的年龄为30岁，无法判定攻击目标u6是否为高收入者，从而避免了u6收入状况隐私信息的泄露。

表1 部分背景知识

现有LDP的应用研究主要基于随机响应机制，最早于1965年由Warner等人[14]提出。其主要思想是利用对敏感问题响应的不确定性实现对原始数据的隐私保护[15]，进而研究对敏感属性值的隐私化处理及其频数、均值的统计校正处理和发布[16-17]。

1.1本地化差分隐私LDP提供了比中心化差分隐私更强的隐私保障，其正式定义如下：

定义1：本地化差分隐私(ε-LDP)[16]。假设x是一个私有信息，该私有信息从含k个元素的集合X中取值(令X= [k]:= {0,1,2,3,…,k-1},x∈X)。私有化机制Q是从[k]到输出集Z的随机映射，它以概率Q(z|x)将x∈X映射到z∈Z，映射后输出的z被称为私有化样本。如果对于所有的x,x'∈X，当ε>0时，有：

(1)

则认为Q满足ε-本地化差分隐私。由公式(1)可知，较小的隐私预算ε可以保证较高的隐私水平。且任意一对x,x'的映射输出都是相似的，因此不能通过输出结果推断出特定的输入。

(2)

2 问题陈述

现有的本地化差分隐私算法(如代表性算法CMS、RAPPOR等)均是基于随机响应，其不确定性使得估计结果的准确性不稳定。在数据域较大且数据量较少的情况下，这种现象尤为显著。为了更清楚的说明这一问题，本文生成了两个含10万条记录的仿真数据集进行观察，它们分别满足Zipf分布和正态分布。在ε=2下，仿真数据集的频数统计结果与经过GRR处理后数据的频数统计结果如图2所示。

(a) Zipf分布

从图2可得，在数据域较大且数据量较少的情况下(如已在图3中放大的Zipf分布的右端以及正态分布的两端)，处理后的频数统计结果与原始频数统计结果相差较大，易出现远离正常分布的异常数据值。它甚至可能将一个低频属性值所对应的频数值估计为负，这在一定程度上降低了数据的参考价值。故本文研究的目的是对随机响应机制的效用性进行优化，实现具有高数据效用性的LDP算法。

图3 图2部分位置对应放大2倍的分布图

针对上述不足，本文在GRR算法的基础上引入数据分箱思想以解决当前隐私保护算法在数据域较大时对数据量要求严格的问题。这样做的好处是，利用分箱思想可以将数据记录分入更小的数据域范围内。当聚合数据时，不同子域中的数据在各自域内进行聚合处理，可以防止本数据域中的数据被划分到其他子域内，一定程度上提高了数据聚合的可靠性。

3 基于本地化差分隐私的数据共享算法设计

常见的数据分箱有等宽分箱和等频分箱。等宽分箱以敏感属性值的域大小为前提，按相同区间宽度分箱，这时每个分箱内数据量不定。等频分箱则是把敏感属性值按照从小到大的顺序排列，根据记录的个数将其等分为x部分，这时每个分箱内数据量相同。但等频分箱的效果容易受数据分布的影响，特别是当大量数据记录集中在少数几个属性值上，如Zipf分布、几何分布以及正态分布等。因此，本文采用等宽分箱对数据记录进行划分。为简化描述，将改进后的算法记为BRR(Binning Randomized Response)。该算法是对GRR工作的改进，且GRR可作为BRR在特定情况下特定参数选择的方法。

完整的BRR算法在算法1中给出。第1行按照等宽分箱思想划分了敏感属性值的域区间，Zi为划分后更小的域区间。算法在第2行中初始化了一个集合V，用来存放之后得到的扰动数据。其中，Vi用来存放属于域区间Zi的数据的扰动报告。第3～7行由数据提供方执行，依次对共享数据记录中敏感属性值d(i)进行扰动处理。第8～11行由数据需求方根据接收到的扰动报告和相关参数校正并计算每个属性值的频数统计信息。当参数fxs=1时，为GRR算法。

Algorithm 1Binning Randomized Response (BRR)

Input:d(1),d(2),d(3), …,d(n); privacy budgetε, number of binsfxs.

Output:Estimated FrequencyF(d)

1.bins←{Z1,Z2,Z3,Z4, …,Zfxs}

2.Initialize a setV←{V1,V2,V3,V4, …,Vfxs}

3.fori∈[n] do

4. forf∈[fxs] do

5. ifd(i)inZfdo

6.d'(i)←GRR_client(d(i);ε)

7Vf.append(d'(i))

8. forf∈[fxs] do

9. ford∈Zfdo

10. F(d)←GRR_server(d;ε,Vf)

回顾公式(2)可以发现，p接近0或1的值并不可取。这是因为极端情况下当p= 1时，K= 1，此时敏感属性仅有一种取值，即数据不翻转的概率为1，共享数据将使敏感信息处于危险之中；而当p= 0时，数据翻转概率最大，得到的扰动数据越背离原始数据，虽然增大了保护强度，但却违背了共享数据的初衷。算法1中Zi的作用类似公式(2)中提及的K，即敏感属性在子域中可取值的种类数。BRR算法中，敏感属性在子域中可取值的个数由敏感属性列的数据域和分箱数fxs共同决定，要使敏感属性在子域中的取值超过1种，应保证分箱数取值不超过数据域的大小，从而保护共享数据的隐私。

为验证BRR算法的可行性，本文仍选用上文生成的满足几何分布和均匀分布的仿真数据集。图4为原始数据的频数统计结果与经过BRR(fxs=8)算法处理后数据的频数统计结果。不难发现，在相同隐私预算下，经过BRR算法处理后的数据统计值与原始数据统计值相差较小，具有统计学意义，能在控制隐私泄露的条件下为政府部门制定决策提供辅助参考。

(a)Zipf分布

4 实验部分

4.1实验数据集本实验共采用三个数据集进行实验分析：两个仿真数据集和一个真实数据集。仿真数据集分别满足Zipf分布和均匀分布，且每个数据集中包含100 000条数据，主要用于验证数据域大小对统计数据误差的影响。真实数据集则选取了Kaggle提供的菲利宾家庭收入支出数据集(Family Income and Expenditure)。设年收入大于20万比索的家庭属于高收入家庭，以此为条件，共筛选出16685条数据用于后续分析。由于该数据集中含有多个属性字段，因此数据提供部门可以以地区、年龄、婚姻状态等各种维度对高收入家庭的统计分析数据进行共享。本文以年龄维度为例，通过对各个年龄的高收入家庭频数数据进行隐私保护处理，证明本文提出的BCS算法的特性和优势。

4.2实验指标隐私保护后数据的效用性通常由原始数据集与隐私处理后数据集的差异程度来评估。常用的误差度量标准有：相对误差、绝对误差、平均绝对百分比误差以及欧式距离等。本文采用平均绝对百分比误差(MAPE)作为评价BRR算法数据效用性的指标。MAPE[19-20]的定义如下：

(3)

其中|D|为敏感属性列的类别域大小，yi为第i个属性值的真实频数，xi为第i个属性值的估计频数。MAPE的值越小，估计分布越接近真实分布，说明数据的效用越好。

4.3实验结果分析

a.频数估计。为了清楚显示频数分布趋势并便于观察，本文计算了每个年龄属性值下对应高收入家庭的估计频数。根据所选数据分别绘制了三种类型的分布直方图，如图5所示。其中图(a)为原始数据的频数直方图、图(b)为隐私预算参数ε=2时由GRR算法处理后得到的频数直方图、图(c)为ε=2，fxs=16时由BRR处理后得到的频数直方图。

图5 高收入家庭年龄分布直方图

观察图5直方图可以发现，隐私保护后的数据虽然改变了记录的具体值，但是从数据总体分布趋势而言，较好的保留了原始数据的分布性质，仍存在着较强的参考价值。同GRR算法相比，BRR算法处理后的数据的估计频数更接近真实值，在数据量稀疏的两端尤为显著。

b.误差估计。以GRR为对照组，本文分别在ε=2和fxs=16的参数设置下计算了隐私保护处理后每个年龄对应的高收入家庭户数统计量的MAPE值，以观察误差分布趋势，如图6所示。当户主年龄分别为15、17、89、96、98时，由GRR算法隐私保护后的数据对应的统计值误差最大。而这些户主年龄对应的户数分别为2、4、5、3、4，均属于数据量过少的情况。相较于GRR算法，BRR算法在数据量较少时对应的统计误差则小很多，其总体趋势也更平稳。

图6 隐私处理后各年龄统计量的MAPE

c.分箱数对统计数据误差的影响。图7提供了不同分箱数下每个户主年龄对应的高收入家庭户数统计量的MAPE值，用于验证分箱数对统计数据误差的影响。其中隐私预算参数ε=2，可得分箱数越大，MAPE值越低。这是由于分箱可以在一定程度上限制随机响应机制带来的偏差，保证某一低频数的年龄值被隐私保护处理后仍处于距离该原始年龄值较近的位置。上文在第3节提到，分箱数取值不应超过数据域大小，否则会使敏感属性在子类别域Zi中可取值的个数接近于1，即数据不翻转概率接近1。例如图7中，当1≤Zi≤1.5时，分箱数的取值为56≤fxs≤84，此时对应的误差值逐渐接近于0。若直接共享这样的数据，将使敏感信息处于危险之中，这是不可取的。

图7 分箱数对误差的影响

d.数据规模对统计数据误差的影响。为了解BRR在不同规模数据上的效用性，本文对上面筛选的菲律宾高收入家庭原始数据集(16 685条数据)进行了翻倍处理，分别生成4倍(66 740条数据)、8倍、12倍、16倍、20倍(333 700条数据)的数据集进行实验。观察在ε=2和fxs=16参数设置下，BRR算法统计量误差值随数据规模的变化情况。

图8 数据规模对统计数据误差的影响

由图8可得，随着数据规模的增加，经过GRR和BRR隐私保护处理后的数据统计量整体误差逐渐降低。相较于GRR，BRR在不同数据规模下均保持了更好的数据效用性，且数据规模较小时，BRR的优势更为明显。当数据量达到一定规模时，BRR统计量的整体误差在小范围内浮动。此实验结果也验证了Ye Q.Q.等在文献[15]中指出的“用于统计的数据量大小决定了数据效用性高低”这一说法。”

e.隐私预算对统计数据误差的影响。图9为隐私预算在不同取值下(0～5)对BRR数据效用性的影响。同上，以GRR为对照组，选择参数fxs=8。从图9不难发现，随着隐私预算的增加，这两种算法的误差值均越小。即当隐私预算增加时数据不翻转的概率增大，得到的扰动数据越接近原始数据，但相应地其保护强度也将减小，这与预期是一致的。其次，在相同隐私预算下，BRR算法的误差值更小，尤其当ε<3.5时，BRR算法的数据效用性显著优于GRR。如图10所示，本文还在相同参数设置下分别对比了fxs=4，fxs=8，fxs=16时相应的MAPE值。容易发现，在相同隐私预算下，分箱数fxs越大，统计数据误差MAPE的值越小。

图9 隐私预算对统计数据误差的影响

图10 相同隐私预算下分箱数量对统计数据误差的影响

f.数据域大小对统计数据误差的影响。如图11所示，我们在不同的数据域大小下生成了满足Zipf分布和均匀分布的数据集，其中参数设置为ε=2和fxs=8。当数据量一定时，BRR和GRR算法在Zipf分布和均匀分布下的误差均随数据域大小的增大而增大。且相同条件下，BRR算法的效用性显著优于GRR算法。此误差曲线也较好反映了本文所说的“当数据量较少而数据域|D|较大时，统计误差较大”这一问题。

4.4算法特性分析我们从以下两个方面分析BRR算法特性：

a.较好的数据效用性。从频数直方图的误差角度看，GRR算法的误差值主要源于敏感属性取值稀疏的部分。本文提出基于数据分箱的隐私保护算法BRR，通过将数据分入更小的数据域，得到更小的误差量。从数据规模、隐私预算、数据域大小等方面进行讨论分析，表明BRR具有更好的数据效用性。

b.略高的时间复杂度。使用BRR算法所需的时间复杂度与GRR算法O(n+k)相比较，仅多出了数据分箱的时间。但由于政府共享的个人统计数据通常不会涉及很大的数量级，略高的时间复杂度不会成为本算法在政府领域实际应用的制约因素。

(a)Zipf分布

5 结 语

为帮助智慧政府利用数据做出更准确更客观的决策，数据共享是其建设进程中必不可少的任务。由于政务数据中含有大量个人敏感信息，直接共享这些数据或是对已共享的数据进行分析都有可能造成隐私信息的泄露。因此，本文就政府在推行政务数据共享的同时如何保护个人隐私信息不泄露进行了研究。首先，本文针对政府部门间共享统计数据场景，讨论了现有隐私保护技术存在的不足，并在GRR算法的基础上提出了基于本地化差分隐私的政务数据共享算法BRR。通过与算法GRR进行比较，验证了所提算法具有较高的效用性，可在不同分布和数据域大小下保持其效用性。本算法可用于民意调查、电子投票等倾向于政务统计数据共享的情景，目的是为政府部门管理或服务决策提供辅助参考依据。但本文提出的算法目前仅适用于单值敏感属性的情况，下一步工作将考虑如何在多值敏感属性的情况下保证数据的敏感性与效用性问题，完成智慧政务中共享数据的隐私保护。