Implementing the Exponential Mechanism with Base-2 Differential Privacy

发表于 分类于 阅读次数： 本文字数： 7.3k 预计阅读时长 ≈ 12 分钟

摘要

现如今差分隐私有很好的理论支持，但是实现却仍是一个挑战，因为差分隐私的理论机制是任意或无限精度的，而在差分隐私具体的实现过程中采用的却是浮点或者固定精度。显然，差分隐私从理论到实际的这一转换过程肯定会存在一些问题，而这一点可能会成为攻击者实施攻击的一种手段。本文提出的方法将差分隐私定义中的基数e转换成基数2，而因为计算机是二进制的，这样转换之后就可以精确地执行算法，且时空复杂度较低。

1.介绍

首先介绍了差分隐私理论（一个理论上十分严格的隐私框架，要求同一查询对邻近数据库的结果不可区分）（邻近数据库：两个数据库之间只相差一个条目）的提出背景；

差分隐私的定义源自：KL散度，最大散度，δ-近似最大散度

差分隐私可以保证数据库中每个个体的隐私，并且对于与其他隐私机制的后处理也是健壮的；但是构建DP系统或机制可能具有挑战性，像拉普拉斯这类的添加噪声的机制容易受到机制规范和有限精度算法之间的转换问题的影响，而且在有限精度值上添加不精确计算产生的噪声可能会泄露原始值的重要信息。

指数机制：不同于拉普拉斯机制，指数机制从一个固定的公共已知结果集中采样，选择每个结果的概率与一个由隐私数据决定的效用值u成比例。人们最初认为该机制不会受到基于浮点的攻击，然而一种基于不精确的浮点算术攻击可能对该机制造成影响。因此本文提出将e作为基数转换到2为基数，然后阐述了本文的核心概念贡献和主要技术贡献。

1.1差分隐私初步

引用前人提出的纯差分隐私，敏感度和拉普拉斯机制，指数机制等相关概念；

Note: 为了实现拉普拉斯机制，必须以任意精度从拉普拉斯分布中取样，而这在实践中肯定是有问题的，因为浮点数不能表示拉普拉斯分布中的每一个可能的值，而这可以被恶意方通过检查结果的最低位进行攻击，即这种攻击得以进行的原因是浮点计算的不精确导致对邻近数据库的查询结果是不同的，幸运的是，这种在拉普拉斯机制上的攻击可以通过细致的计算得到缓解。

2.推翻指数机制

根据浮点数的IEEE表示阐明指数机制的简单实现如何被破坏：一种是不为0的两个很小的数相乘的结果下溢为0；另一种是数量级不同的两个数相加，因为较大的数要占据所有的精度位，所以较小的数被截断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 指数机制的python朴素实现
# Note: weights计算为什么多除了2; c_weights计算括号位置有问题
# The naive exponential mechanism
import numpy as np
# Inputs :
# eps : the privacy parameter ε
# u : the utility function 效用函数
# O : the set of outputs 输出结果集合
# Returns : an element in O 返回O中的一个元素
def naive_exp_mech (eps, u, O):
	# compute the weight of each element 计算每个元素的权重
	weights = [np.exp(-(eps/2.0) * u(o)) for o in O]
    # 计算总权重
    T = sum(weights)
    # cumulative weights 计算累积权重
    c_weights = [sum(weights [0: i])/ T for i in range (1 , len (O) +1)]
    # uniform sample from [0 ,1) 随机取出index
    index = np.random.rand() 
    # return element corresponding to the random index 根据随机取出的index返回元素
    for i in range (0, len(O)):
    	if c_weights[i] > index :
    		return O[i]

上述指数机制被破坏的两种场景转化位以下两种攻击方式

Zero-rounding

假设攻击者希望知道Alice是否在数据库中。攻击者选择一个结果空间O=[O0, O1]，以及一个效用函数：如果Alice在数据库中，那么𝑢(𝑜0) = 𝑥 且 𝑢(𝑜1) = 𝑥 + 1；如果Alice不在数据库中，那么𝑢(𝑜0) = 𝑥 + 1 且 𝑢(𝑜1) = 𝑥。（以上场景中u的敏感度是1）。攻击者然后设置𝑥，使得np.exp(−(eps/2) ∗ x) > 0 但是np.exp(−(eps/2) ∗ (x + 1)) = 0。攻击者这样设置之后，如果Alice在数据库中，那么会得到结果O0的权重大于零，而结果O1的权重等于零，那么唯一可行结果就是O0；反之唯一可行结果就是O1。这样攻击者基本上可以确定Alice是否在数据库中。

Note：攻击者可以这样设置的原因就在于对x+1的权重进行计算时，计算出来的权重可能特别小以至于只能用0进行表示；而对x的权重进行计算时却正常

有人会说：只要保证所有元素的权值都大于零，那这种攻击就无效了

Truncated addition

攻击者选择两个值𝑥𝑙 和 𝑥𝑠，以及结果空间O=[k]，使得XXX成立。攻击者然后选择一个效用函数使得：如果Alice不在数据库中，那么𝑢(𝑜1) = 𝑥𝑙 + 1 且 𝑢(𝑜𝑖>1) = 𝑥𝑠；如果Alice在数据库中，那么𝑢(𝑜1) = 𝑥𝑙 且 𝑢(𝑜𝑖>1) = 𝑥𝑠 +1。攻击者这样设置之后，如果Alice在数据库中，因为结果O1的概率非常的大，甚至等于总权重t，所以唯一可行结果就是O1。

Note：攻击者可以这样设置的原因就在于对𝑥𝑠 +1进行权重计算时，计算出来的权重比起𝑥𝑙计算出来的权重太小以至于可以忽略

一个解决办法：可以在机制执行的过程中监视每一次加法，但是这样的监视是非平凡的，因为e^x不能在有限位数内精确表达使得加法不能精确执行

缓解攻击方法一：将允许的效用值限制在一个范围内，使得在最小和最大可能权值内可以安全进行加法计算

但是要怎么把效用值限制在一个范围内？不精确的计算对隐私有什么影响？声明一个安全的范围确定的效用函数集的关键问题在于难以描述由于不精确计算带来的隐私损失，而且我们对实现的隐私损失作出的一般保证都是悲观的。

缓解攻击方法二：将分析限制在一组以前审查过的效用函数或工具上

但是即使是具有容易理解的灵敏度特性的简单小工具，例如标量乘法或加法，也可以用来构造上述攻击。

3.精确实现指数机制

针对上述问题，提出一个简单、精确的指数机制实现，并列出结果的四个贡献：

（1）定义base-2 DP，说明base-2和base-e之间的关系，并且证明当正确实现base-2指数机制时可以给出一个精确的隐私保证

（2）如何选择隐私参数和处理非整数效用函数（随机舍入），关键点在于随机舍入不会因为不精确的实现带来隐私损失，因为可以证明隐私损失原子最坏情况的舍入行为

（3）不使用除法从归一化概率中进行采样

（4）实现（python，Rust）

3.1Base-2差分隐私

这一动机源自观察，即计算机非常擅长于精确的二进制计算。本文不计算e^x，反之合适地选择一个y并计算2^y，使得从隐私角度能实现相同的结果，同时仍然能够利用精确的浮点运算。

根据Base-e差分隐私提出Base-2差分隐私（以及Base-2的指数机制），并阐明两者之间的关系：满足𝜂|2-DP的所有机制一定满足ln(2)𝜂−DP

3.2非整数隐私参数和有效性（22/04/19 page5）

整数效用值情形下隐私参数的选择

第一，描述一个𝜂的大的集合（2^−𝜂可以精确计算）；第二，在这个集合中表达2^−𝜂的精度位数不会太大

对于一个二进制q和一个整数n，q^n最多需要max(1, bqn)个精度位；因此对于2^(−𝜂) = (x2^(-y))^z，最多需要的精度位数为z*(y+bx)，所以对于(2^(−𝜂))^𝑢，最多需要的位数为max(1, uz(y+bx))

因为当设置z=1且选择小的y时，𝜂的范围还是很大，所以实际上主要关注点就是𝑢的数量级，即控制精度的主要考虑时效用值的范围：自然的想法时直接给一个预规定的𝑢的一个可接受范围，并将观测到的效用值都限制到这个范围中（只要这个范围独立于隐私数据库，那么限制这个范围就不会给隐私保证带来影响）

确定最小精度的两种途径
（1）以给定的精度运行机制，如果执行的算法不精确，则以更高的精度重复该机制

（2）在运行机制前，对允许的效用值和结果空间大小使用公共指定边界，从而确定最小精度

第二种途径有两种方法
（1）最坏情况的理论分析：源自引理3.4，该引理得出最坏情况下计算权重组合所需精度的最坏情况下的边界。这一方法的缺点是它忽略了浮点表示中任何可能的抵消或效率

（2）最坏情况的经验程序：计算每一种假设的最坏情况并报道其所需精度。这种情况下就可以保证有充足的精度位去计算（a）每一个结果的权重；（b）最大可能结果的权重 + 一个有着最高小数精度位的权重。

因为尾数需要的最大尾数由最大可能权重和与表示任何单个权重所需的最高小数精度所决定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 算法一：确定最小精度
# 输入：𝑢𝑚𝑖𝑛：最小效用值, 𝑢𝑚𝑎𝑥：最大效用值,𝑜𝑚𝑎𝑥：最大结果个数, 𝜂：隐私参数
# 输出：p：一个足够的精度，它不超过最小精度大小的两倍且可以成功运行base-2的指数机制
procedure ComputePrecision(𝑢𝑚𝑖𝑛, 𝑢𝑚𝑎𝑥, 𝑜𝑚𝑎𝑥, 𝜂)
	# 初始化为1
	𝑝 ← 1
    # 如果检测精度失败则p加倍，并再次进行检测
	while CheckPrecision(𝑢𝑚𝑖𝑛, 𝑢𝑚𝑎𝑥, 𝑜𝑚𝑎𝑥, 𝜂, 𝑝) fails do
		𝑝 ← 2𝑝
	return 𝑝
# 一旦程序中存在不精确计算就会返回failure
function CheckPrecision(𝑢𝑚𝑖𝑛, 𝑢𝑚𝑎𝑥, 𝑜𝑚𝑎𝑥, 𝑏𝑎𝑠𝑒, 𝑝)
	Set the precision to 𝑝
	return failure on inexact arithmetic for:
	𝑚𝑎𝑥𝑠𝑢𝑚 ←𝑖∈[𝑜𝑚𝑎𝑥] 2^(−𝜂𝑢𝑚𝑖𝑛)
	for 𝑢∈[𝑢𝑚𝑖𝑛, 𝑢𝑚𝑎𝑥] do
		𝑐𝑜𝑚𝑏𝑖𝑛𝑒𝑑𝑠𝑢𝑚 ← 2^(−𝜂𝑢) + ⌈𝑚𝑎𝑥𝑠𝑢𝑚⌉

非整数效用值情形下隐私参数的选择

这种情况下采用的解决方法是：采用随即舍入，即向上或向下四舍五入到最接近的整数，其概率与整数的接近程度成正比。

基本策略：表明随机舍入不会因为不精确的实现而带来隐私损失

随机舍入指数机制会先分配一个整数代理效用值，然后再用这个值当作效用值进行之后的运算。

引理：具有任意精度随机舍入功能的指数机制是满足差分隐私的，这一论点来源于考虑最坏的舍入选择集，并认为隐私损失并不比这种情况更糟。

虽然随机舍入不会因为低精度的实现带来隐私损失，但是这一机制在多大程度上接近于原始的非整数效用方法还不是很明显。

命题3.6指出随即舍入不会很大程度地改变概率

3.3不用除法进行归一化采样

除法的问题在于：即使被除数和除数都可以用很小的二进制位精确表示，但是它们的商却不能被简单地表示。为此，提出了两种不采用除法的归一化方法

第一种方法

该方法源自观察：从[0, 𝑡)中均匀随机取样等同于从归一化分布中随机取样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 算法二：不使用除法进行权重归一化采样
# 输入：W：一个权重集合
# 输出：i：根据权重选出的采样下标
procedure NormalizedSample(𝑊)
	# 计算总权重
	𝑡 ← ∑𝑤∈𝑊 𝑤
	𝑠 ← GetRandomValue(𝑝, 𝑡)
    # 计算累积权重
	for 𝑖 ∈ {1,...,|𝑊|} do
		𝑐𝑖 ← ∑𝑖,𝑗=1 𝑤𝑗
	return min{𝑖|𝑐𝑖 > 𝑠}
# 输入：p:精度位数，t：范围上限
# 输出：一个从[0, 𝑡)中均匀随机采样取出的数
function GetRandomValue(𝑝, 𝑡)
	# argmax：取最大值函数，求出g
	𝑔 ← arg max 𝑔{2^𝑔 ≤ 𝑡}
    # 初始化s
	Initialize 𝑠 ← ∞
    # 如果s不在[0, 𝑡)内则继续循环
	while 𝑠 ≥ 𝑡 do
		for 𝑖 ∈ {1,...,𝑝} do
        	# 简单均匀随机取样
			𝑟𝑖 ∼ Unif(0, 1)
		𝑠 ←∑𝑝,𝑖=0 𝑟𝑖*2^(𝑔−𝑖)
	return 𝑠

第二种方法

在范围[0, 𝑡)中通过在每一步丢弃一半的剩余范围执行随机的二分查找，当只剩余一个有效元素时停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 算法三：权重归一化采样算法
# 输入：W：一个权重集合
# 输出：i：根据权重选出的采样下标
procedure NormalizedSample(𝑊)
	# 计算总权重
	𝑡 ←∑𝑤∈𝑊 𝑤
    # 计算累积权重
	for 𝑖 ∈ {1,...,|𝑊|} do
		𝑐𝑖 ←∑𝑖,𝑗=1 𝑤𝑗
	𝑘 ← arg min𝑘{2^𝑘 ≥ 𝑡 } ⊲ The smallest power of two ≥ 𝑡.
	if 2^𝑘 > 𝑡 then
		𝑊 ← 𝑊 ∪ {⊥} ⊲ Add element ⊥ with weight 2^𝑘 − 𝑡.
		𝑐|𝑊| ← 2^𝑘 − 𝑡 ⊲ Total weight is now 2^𝑘.
	𝑠 ← 0
	𝑗 ← 𝑘 − 1
	𝑅 ← [|𝑊|] ⊲ the remaining elements
	while |𝑅| > 1 do
		𝑟𝑗 ∼ Unif(0, 1)
		𝑠 ← 𝑠 + 𝑟𝑗*2^𝑗
		for 𝑖 ∈ 𝑅 do
			if 𝑐𝑖 ≤ 𝑠 then ⊲ 𝑠 cannot be in [𝑐𝑖−1, 𝑐𝑖), even if all draws are 0.
				𝑅 ← 𝑅\{𝑖}
			if 𝑖 > 0 and 𝑐𝑖−1 ≥ 𝑠 + 2𝑗 then ⊲ 𝑠 cannot be in[𝑐𝑖−1, 𝑐𝑖), even if maximum value added.
				𝑅 ← 𝑅\{𝑖}
		𝑗 ← 𝑗 − 1
		if |𝑅| = 1 and ⊥ ∈ 𝑅 then ⊲ Restart if dummy value.
			𝑠 ← 0
			𝑗 ← 𝑘 − 1
			𝑅 ← [|𝑊|]
return 𝑙

引理3.7证明算法二和算法三等同于指数机制采样，且程序有很大概率最多使用O(p)的随机位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 算法四：用最小的拒绝次数进行GETRANDOMVALUE操作
# 输入：p:精度位数，t：范围上限
# 输出：一个从[0, 𝑡)中均匀随机采样取出的数
function GetRandomValue(𝑝, 𝑡)
	𝑔 ← ⌊log2(𝑡)⌋
	Initialize 𝑠 ← ∞, s∗ ← ∞, c ← 0
	while 𝑠 ≥ 𝑡 and c < k do ⊲ Reject 𝑠 if it falls outside [0, 𝑡) or fewer than 𝑘 iterations.
		for 𝑖 ∈ {1, . . . , 𝑝} do
			𝑟𝑖 ∼ Unif(0, 1)
		𝑠 ← ∑𝑝,𝑖=1𝑟𝑖2^(𝑔−𝑖)
		if 𝑠∗ = ∞ and 𝑠 < 𝑡 then
			𝑠∗ ← 𝑠 ⊲ update 𝑠∗if 𝑠 is in range.
		𝑐 ← 𝑐 + 1
	return 𝑠∗

4.实现

精确计算

采用GNU多重精度算法(GMP)和GNU MPFR库来实现高精度整数和浮点运算，通过python和rust语言访问这些库。这些库也提供了在运行时确定在给定系统上可实现的最大精度，避免由于超过任何系统特定的阈值而引发的错误的产生，且使得代码更容易进行审查。

MPFR提供了一组有用的标识符来指示操作不精确，结果溢出，下溢等问题

分离数据独立和数据依赖的逻辑

确定隐私参数

随机性来源

逻辑

实现的逻辑基本与朴素的指数机制相同，但是包括了效用函数的随机舍入，效用值夹紧，以及精确计算的额外监测

特定语言细节

python和rust语言实现上的区别

4.1性能和应用

所有的测试在拥有2核2GB内存的Linux虚拟机上，总体来说，Rust性能远远高于python，但是，由于基准测试的差异，呈现的实践不具有严格的可比性。

结果空间大小

选择了一个结果集𝑂 = [𝑛]，且效用函数𝑢(𝑜) = 𝑜。随着n的增大， 效用值范围和结果空间大小都增加。该测试证明：特别是在Rust语言中，即使是在低端配置情况下，当n=75k时也能在大约10s内完成。

Note：base-2指数机制效率没有原始的指数机制效率高

精度确定方法

通过改变结果空间大小来展示经验精度确定的计算开销与精度降低之间的相对权衡导致的性能差异。该测试表明：随着n的增加，PythonEmp的性能远好于PythonTher的性能，即性能的改善效果要由于开销成本的增加；相反，RustEmp的性能却不如RustTher的性能

效用值范围

结果空间集固定为O=1000，测试效用值范围增加时会怎样影响性能。设置𝑂 = {0} ∪ {𝑖 +𝑛|𝑖 ∈ [𝑘]} 且𝑢(𝑜) = 𝑜. 增长曲线是线性的，因为随着n的增加，成本增加的唯一原因是计算过程带来了更多的时间开销。

拉普拉斯

从拉普拉斯机制中采样的标准方法是使用逆变换采样，即在[0,1]中采样出一个均匀值U，然后求解CDF(t)=U（CDF代表拉普拉斯分布的累积密度函数：对概率密度函数从−∞ 到t进行积分）。通过标准的ln函数实现该机制存在危险，但是通过[6]中提出的方法可以解决。

然后，拉普拉斯机制也可以通过将效用函数设置为𝑢(𝑑, 𝑜) = |𝑓 (𝑑) −𝑜|进行实现。该测试表明：Python的性能由于PythonNaive，

--------------------------------------- 本文结束，感谢您的阅读 ---------------------------------------
正在加载今日诗词....
HL 微信 微信
HL 支付宝 支付宝
欢迎关注我的其它发布渠道