Page 220 - 《软件学报》2021年第11期

3546 Journal of Software 软件学报 Vol.32, No.11, November 2021

π () Pr[ ( )v ⋅ f v = ] y
MPC = max Pr[ | ]v y = max (3)
, v y CandI∈ , v y CandI∈ ∑ z CandI∈ π () Pr[ ( )z ⋅ f z = ] y
其中,CandI 为项集域 I 的候选项集;π(v)为 v 的先验知识;f 为隐私机制,如 LDP 或 CLDP.MPC 量化了攻击者的攻
击能力,对其进行限制为 MPC≤ρ,可以推断出 LDP 或 CLDP 的隐私参数与ρ的联系,从而可以从直观意义上设
置隐私参数.
3 事务数据的本地差分隐私收集方法

事务数据集的本地随机响应远比一般的数据集要复杂,主要原因有如下两个:(1) 项集域的候选项集是指
数级的;(2) 事务数据的长度往往是不相等的,每个用户拥有的数据长度范围为[0,m],其中,m 为事务数据可能的
最大长度,导致事务数据的长度信息 [34] 无法保护.
本节是论文的核心,将介绍本文提出的事务数据收集方法.首先提出第 1 种方法 TDC_CLDP_Cand,该方法
先计算所有候选项集与 t 之间的分值,并得到抽样概率,然后从候选项集中选择一个.但该方法存在的主要问题
|I|
是候选项集的数量是指数级的,其数量为 2 −1,其中,I 为项集域.为解决指数级的抽样问题,本文提出第 2 种方法
TDC_CLDP.该方法的思想来自于 TDC_CLDP_Cand,但不直接从候选项集随机抽取一个项集,而是将候选项集
的样本空间划分为 k+1 个部分;然后,基于分值函数的抽样概率从 k+1 个部分中随机抽取一个;最后,基于这个确
定的子空间继续抽取生成事务数据并发送给数据中心.接下来详细介绍两种方法.整体研究思路如图 2 所示.
(1) 基于CLDP隐私模型的 (2) 基于TDC_CLDP_Cand (3) 基于最大后验置信度
指数机制与新的距离函数, 算法的思想改进抽样 攻击模型,提出启发式
提出TDC_CLDP_Cand算法 过程,提出TDC_CLDP 隐私参数设置策略

Fig.2 Overall research idea
图 2 整体研究思路
3.1 TDC_CLDP_Cand算法
令 t 表示用户的事务数据,每个用户在本地从 I 的所有候选项集 CandI 中基于 CLDP 隐私模型随机抽取一
个候选项集 s,CLDP 模型的关键是距离函数 dist,该距离函数必须是一个距离度量,即需要满足非负性、对称性、
三角不等式等特性.本文定义的距离函数 dist 为候选项集 s 与 t 的相异度,如公式(4)所示.
max(||,| |)ts max(||,| |)ts
dist (, )t s = max(| |,| |)t s − [t = i i ] s = ∑ ∑ | t − i s i | (4)
i= 1 i= 1
其直观意义为 s 与 t 的最大长度减去二者的相似度,本质上是 t 与 s 之间的曼哈顿距离(Manhattan distance),
曼哈顿距离是一个有效的距离度量.
公式(4)中,t i 与 s i 代表 t 与 s 中的第 i 项,当 t i 与 s i 相等时,[t i =s i ]=1,反之为 0.如:当 t={abc},s={ae}时,将 t 与 s
分别转成字符串形式得到 t=[11000],s=[10001],则 t 与 s 的相异度为 2,相似度为 3.值得注意的是:当 t 与 s 长度
不等时,可以通过加 0 进行补全.用户的事务数据 t 与每个候选项集 s 的分值函数为
−⋅ dist (, )t s
α
score ()s = e 2 (5)
从公式(5)定义的分值函数可以发现,每个 s 的分值与 t,s 的曼哈顿距离成反比.该定义合理且符合直观语义,
因为曼哈顿距离代表数据之间的差异性,差异性越大,分值越小;差异性越小,分值越大.基于所有 s 对 t 的分值函
数,指数机制的抽样概率为
Pr[ is sampled]s′ = score ()s′ (6)
∑ s CandI∈ score () s
可见,该抽样概率与距离度量函数有关.基于上述原理,本文提出第 1 种算法 TDC_CLDP_Cand,见算法 1.但
d
该算法需要遍历所有的候选项集,并计算其距离与分值,该过程是指数级的,其时间复杂度为 O(2 ),即与项集域
的大小呈指数关系.实验表明:当 d≥16 时,很难得到结果.