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

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 时,很难得到结果.
   215   216   217   218   219   220   221   222   223   224   225