Page 319 - 《软件学报》2025年第5期

王源源 等: 本地差分隐私频率估计伪数据攻击及防御方法 2219

k
E[F y (t)] = Pr(F y (t) = 1) = (21)
i i d
代入公式 (20) 得到攻击整体效用:

∑ mrk
ˆ
G = E[∆f t ] = −c (22)
t∈T (n+m)(p−q)d
m[p+(r −1)q]
结论 2. 子集选择机制 RIA 攻击整体效用为 −c .
(n+m)(p−q)
证明: RIA 从目标项目集 T 中随机选择一个项目 t , 再根据概率 p 来确定是否向服务器提交项目 t . 因此, 项目 t
( )
1 1
被提交给数据收集方的概率为 · p+ 1− ·q . 可以计算出计数函数的期望值, 如下所示:
r r
( )
1 1
E[F y (t)] = Pr(F y (t) = 1) = · p+ 1− ·q (23)
i i r r
代入公式 (20) 得到攻击整体效用:

∑ m[p+(r −1)q]
ˆ
G = E[∆f t ] = −c (24)
t∈T (n+m)(p−q)
mr
结论 3. 当 r ⩽ k 时, 子集选择机制 MGA 攻击整体效用为 −c ; 当 r > k 时, 攻击整体效用为
(n+m)(p−q)
mk
−c .
(n+m)(p−q)
证明: 子集选择机制的 MGA 存在 r ⩽ k 和 r > k 两种情况.
当 r ⩽ k 时, 每个假用户向数据收集方发送的数据包含 r 个目标项目和 k – r 个随机选择的非目标项目, 因此,
每个目标项目被选中的概率为 E[F y (t)] = 1 . 根据公式 (20) 得到攻击整体效用:
1,
i
∑ mr
ˆ
G = E[∆f t ] = −c (25)
t∈T (n+m)(p−q)
当 r > k 时, 每个假用户从 r 个目标项目中随机选取 k 个项目, 向数据收集方提供的 k 个项目全是目标项目, 因
k/r E[F y (t)] = k/r . 根据公式 (20) 得到攻击整体效用:
此每个目标项目被选中的概率为 ,

i
∑ mk
ˆ
G = E[∆f t ] = −c (26)
t∈T (n+m)(p−q)
m
根据公式 (2)、公式 (3) 可以得到 p,q 的具体值, 用 β = 表示假用户比例, 将 p,q,β 代入攻击整体效用 G
n+m
中, 可以得到攻击效用的具体表示, 如表 1 所示.

表 1 子集选择机制攻击效用分析

攻击类型 RPA RIA MGA
ε
r (d −1) re +(d −r −1)(ke +d −k)
( ) [ ( ) ] [ ]
ε
攻击效用 β − f T β(1− f T ) β r 1+ β − f T (r > k)
ε
d k(e −1) − f T (r ⩽ k)或 (d −k)(e −1)
ε

r ( r )
本文分析 3 种攻击效用的大小. 在表 1 中, 不难看出 < 1 β > 0 且 f T < 1 , 可得 β − f T < β(1− f T ) . 因此
,
d d
( )
(d −1) (d −1)
R P A 攻 击 效 用 小 于 R I A 攻 击 效 用 . 对 于 M G A 攻 击 , 当 r ⩽ k 时 , 1+ > 1 , r 1+ > 1 ,

ε
k(e −1) k(e −1)
ε
[ ( ) ]
(d −1)
β r 1+ − f T > β(1− f T ) , 因 此 r ⩽ k 时 , M G A 攻 击 效 用 大 于 R I A 攻 击 效 用 . r > k 时 , 将 分 式

ε
k(e −1)
ε
ε
re +(d −r −1)(ke +d −k) ε
ε
ε
ε
的分子 [re +(d−r−1)(ke +d −k)] 减去分母 (d−r)( e −1), 化简后可以得到 (d −r)[(k −1)e +
ε
(d −k)(e −1)
ε
ε
re +(d −r −1)(ke +d −k)
ε
,
,
(d −k)] . 已知 d −r > 0 k −1 ⩾ 0 d −k > 0 , 可以判断出 (d −r)[(k −1)e +(d −k)] > 0 , 那么 ε
(d −k)(e −1)
[ ]
ε
ε
re +(d −r −1)(ke +d −k)
β r > k 时, MGA 攻击效用大于
> 1 . 因为 β > 0 且 f T < 1 , 所以 − f T > β(1− f T ) . 因此
(d −k)(e −1)
ε
RIA 攻击效用. 综上, 可以得到攻击效用的大小比较: G MGA > G RIA > G RPA .