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

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

TDC_CLDP 基于 CLDP 隐私模型,其输入为:用户的事务数据 t,项集域 I,CDLP 的隐私参数α,输出的事务数

据长度 k;输出为:事务数据 t′,其长度为 k=|t′|.TDC_CLDP 首先对 t 进行预处理得到 t ,使得 ||t = m ,然后从所有的
候选项集中随机选择一个 t′,t′被选中的概率为
α
⎛ −⋅ dist (, )t t′ ⎞
exp ⎜ ⎟ Ω (7)
⎝ 2 ⎠
其中,Ω为概率泛化因子,其定义如公式(8)所示.
− α 0 ⋅ k ⎛ − α ⋅ (k − inter ) ⎞
Ω = e 2 ⋅ C + k ∑ e ⎜ 2 ⋅ (C inter ⋅ C k − inter ) ⎟ (8)
d 1 ⎝ ⎜ m d ⎟ ⎠

* inter=
**
公式(8)中的*部分代表相似度为 0 的子空间,**部分代表相似度大于 0 的子空间.由于其样本空间大小为
C k dm ,当 d 与 m 很大时,运行的时间与空间是指数级的.因此,TDC_CLDP 将候选项集总的样本空间划分为 k+1
+
个样本子空间,每个样本子空间中的候选项集与 t 的相似度大小 inter 是相同的,其范围为[0,k],见表 2.
Table 2 Subspace and corresponding sampling probability
表 2 子空间及对应的抽样概率
样本子空间 每个子空间的概率
max(| |,| |)ts
∑ [ i t = i s ] 0,= inter=0
i= 1
max(| |,| |)ts −⋅ (k − inter )
α
∑ [ i t = i s ] 1,= inter=1 e 2 ⋅ (C inter ⋅ C k −− )
1 inter
i= 1 p inter = m d − 1
… Ω
max(| |,| |)ts
∑ [ i t = i ] s = , k inter=k
i= 1
注:每个子空间中的候选项集与 t 的相似度大小相同

TDC_CLDP 方法中:第 3 步~第 6 步对事务数据作等长处理,使得所有的事务数据 t 的长度均为 m,添加的项
从集合{a d+1 ,…,a d+m }中选择;第 9 步基于 uniform_random(0.0,1.0)生成概率 r;第 12 步~第 15 步基于 r 与 p inter 确

t
定子样本空间;最后,第 16 步、第 17 步利用 sample 抽样函数随机从 t 中抽取项的数目为 inter,从 I − 中抽取
项的数目为 k−inter,拼接后返回给用户,由用户发送给服务器.TDC_CLDP 方法的时间复杂度为 O(d),与项集域
的大小呈线性关系.
定理 1. 基于 CLDP 模型与指数机制实现的 TDC_CLDP 方法满足α-CLDP 约束.
证明:因为 TDC_CLDP 方法是对 TDC_CLDP_Cand 方法的具体实现,本质过程为指数机制的具体实现,针对
原始数据 t,以概率 p 随机选择一个候选项集 t′,概率 p 为
score ()t′
p = (9)
∑ s CandI∈ score () s
命名 TDC_CLDP 方法的随机机制为Φ,则基于 t 得到 t′的概率为
−⋅ dist (, )t t′
α
Pr[ ( ) tΦ = ] t′ = e 2 −⋅ dist t (, ) z (10)
α
∑ z CandI e 2
∈
为了证明 TDC_CLDP 满足α-CLDP 约束,需要证明公式(11)成立:
Pr[ ( )tΦ = ] t′ α⋅ dist (,t 12 )t
1 ≤ e 2 (11)
Pr[ ( ) = ] t′
Φ
t
2
基于指数机制的定义以及公式(10),可以得到二者的比值为