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

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

依照公式 (2) 概率, 如果用户选中自己的真实数据进行提交, 则需要从剩余 d – 1 个数值中随机选取 k – 1 个不
同的数值提交. 如果用户没有选中自己的真实数据, 则将从剩余 d – 1 个数值中随机选取 k 个不同的数值提交. 如
果直接发送选中的 k 个不同的数值, 通信代价过大. 因此, 每个用户向数据收集方发送一个长为 d 的二进制向量,
用来代表自己选中的数据. 数据收集方根据收到的扰动数据, 推导出项目频率估计值, 频率估计公式如下:

k −1 k k − p
q = p· +(1− p)· = (3)
d −1 d −1 d −1

˜
f v −q
ˆ
f v = (4)
p−q
ˆ 表示项目 ˜ 表示用户提交的扰动数据中项目 v 的频率, 数据收集方可以根
其中, f v v 的估计频率, v ∈ {1,2,...,d} . f v
据用户发送的数据直接进行统计. f v 表示项目 v 的真实频率, 估计值 f v ˆ 是对 f v 的无偏估计:

[ ]
˜
E f v −q
[ ] f v p+(1− f v )q−q
ˆ
E f v = = = f v (5)
p−q p−q
总方差为:

( )
d d f v − p 1 d
∑ ( ) ∑ ˜ ∑ ( )
ˆ
Var f v = Var = Var f v ˜
v=1 v=1 p−q (p−q) 2 v=1
1 ∑ d [ ]
= f v p(1− p)+(1− f v )q(1−q)
(p−q) 2 v=1
1 [ ]
= p(1− p)+(d −1)q(1−q)
(p−q) 2
[ ]
ε
ε
(d −1) 4de −(e +1) 2
= (6)
ε
d(e −1) 2

2.3 环机制
环机制 [8] 是一种用于类别型数据和集值数据频率估计的 LDP 协议, 本文采用环机制进行类别型数据的频率
( ε )
e d
估计. 环机制对项目频率的估计是无偏估计, 其均方误差为 Θ 2 . 相比于其他 LDP 频率估计机制, 环机制
ε
n(e −1)
估计频率的均方误差数量级最小, 是一种效用最优的 LDP 协议. 同时, 环机制具有通信代价低、计算成本小的优
点. 在环机制中, 每个用户的真实数据通过以下 3 个步骤进行处理.
第 1 步, 使用用户 ID 或随机生成的数字作为种子, 通过用户特定的哈希函数将用户的项目 x 映射到 [0.0, 1.0)
范围内的一个数值 v.
第 2 步, 用校准的概率分布 Q 在 [0.0, 1.0) 上随机化数值 v, 得到符合该概率分布的随机变量 y. 概率分布 Q 的
定义如公式 (7) ( 0.0 ⩽ y,v < 1.0 ), 其中覆盖参数 w ∈ (0.0,0.5) 用来控制真/假覆盖概率的覆盖区长度:

 ε
 e
 , 若 v ⩽ y < v+w 或 0 ⩽ y < v+w−1

 ε
 w·e +(1−w)


Q[y|v] =  (7)
 1


 , 若 y ⩾ v+w 或 y ⩽ v

w·e +(1−w)
 ε
第 3 步, 从分布 Q[y|v] 中抽取一个值 z ∈ [0.0,1.0) , 然后将其发送给服务器 (连同种子一起). 根据用户发送的
z 值, 服务器可以估计出每个项目的频率.
形式上, 把用户的真实项目 x 在 [0.0, 1.0) 中的映射值表示为 v, 把覆盖区域 [v,v+w) 或 [0,v+w−1) 表示为 C v .
用户真实项目 C v 的概率为:
x 的扰动数据 z ∈ [0.0,1.0) 在 x 的覆盖区域
w·e ε
P t = P[z ∈ C v |x] = (8)
ε
w·e +(1−w)
′
′
′
当用户的真实数据为 x , 假设哈希函数 h 是完美的, 即 h(x ) 是均匀随机的, 且与 h(x) 无关, 那么 x 的扰动数据
z ∈ [0.0,1.0) 在 x 的覆盖区域 C v 的概率为: