差分隐私在双向异质频谱拍卖方案中的研究①

巫朝霞, 王 路

(新疆财经大学统计与数据科学学院,乌鲁木齐 830012)

0 引 言

为保证频谱用户私密信息得到有效保障，针对拍卖过程中的隐私泄露和安全性能低等问题, 现有许多新的安全算法。文献[1]提出的采用混合图的双向异质频谱拍卖算法使用混合图准确量化了买家之间的频谱干扰情况，显著提高了频谱利用率，隐私安全性能有待提高。Zhou等人中首先引入了现代市场经济学理论中的频谱拍卖模型,提出了一种新的频谱拍卖计算方案[2]。TRUS第一个成功地设计实现了这种频谱的可复用性的真实双向同质频谱拍卖定价机制的解决方案[3]，在设计的拍卖机制中，多个参与方可以根据各自的需求进行频谱交易。文献[4](结合同态加密和加密电路的高效频谱拍卖方案)有机结合了同态加密和加密电路技术对用户隐私信息提供了安全保证，可花费通信开销过大。基于此，保护买家的隐私是设计频谱拍卖方案时的需要着重考虑的。在具有隐私保护的前提下，设计了具有隐私保护的频谱拍卖方案DPDA，具有较好的频谱收益和隐私安全性。

1 预备知识

1.1 拍卖模型

DPDA频谱拍卖方案建立在双向异质频谱拍卖模型的基础上，频谱买家可以根据不同的喜好购买一个或多个频段，对不同的频段具有不同的频谱报价，同时具有多个频谱卖家，这假设每个频谱买家仅出售一个频段，对出售的频段有频段的频谱报价，拍卖人作为中间代理，主持并完成频谱拍卖的整个流程。如图1所示：

图1 双向频谱拍卖模型

1.2 差分隐私

差分隐私通过对原始数据集添加噪声扰动，对真实的数据进行掩盖，从而达到保护隐私的目的。差分隐私对于一个随机差分算法M,Pm为该随机算法M中可以被导入输出的全部函数值的集合。如果对于任意的一对相邻映射数据的子集D和D′,Pm的任意一个相邻子集Sm, 算法都可以满足:

Pr[M(D)∈Sm]≤eεPr[M(D)∈Sm]

(1)

则称该分析算法M所满足的为差分个人隐私, 其中参数ε是进行差分个人隐私保护的隐私保护成本预算，D表示原来的数据集，D则是其中相邻的数据集。差分隐私严格的数学推理，保障两个临近数据集最多相差一个记录数据。不管两者是否同时包含某条记录数据，输出结果的概率分布函数无显著变化，其中ε隐私预算一定程度上决定了概率分布函数差异程度。

1.3 Diffie-Hellman算法

首先Alice和Bob选取大素数P和a，其中a是P的本原元。这两个整数不必是秘密的，故Alice和Bob可以通过即使是不安全的途径协商它们。它们可以在一组用户中公用。

协议如下：

(1)Alice选取一个大的随机整数xA，并发送给Bob：YA=axAmodP

(2)Bob选取一个大的随机整数xB，并发送给Alice：YB=axBmodP

(3)Alice计算k1=YBxAmodP

(4)Bob计算k2=YAxBmodP

则会有：

k1=YBxAmodP=axAxBmodP

k2=YAxBmodP=axAxBmodP

(2)

2 差分隐私频谱拍卖方案DPDA

2.1 DPDA模型框架

对于卖家而言，其效用函数可以如(3)表示：

(3)

其中pj表示买家的报价，aj,i用来表示频段i是否已经分配给买家j，当aj,i=1时，意味着买家j成功获取频段i，否则aj,i=0。

对于买家而言，其效用函数可以如(4)表示：

(4)

每位卖家和买家都向代理人提交加了噪声的结果以保证投标价格的隐私。通过加密系统将数据安全传输给代理人之后，代理人对数据进行处理之后利用匹配原则对频谱进行匹配，从而达到对资源的最大利用。差分隐私DPDA方案分三个阶段：差分隐私投标阶段、差分隐私价格判定阶段、确定赢家阶段。具体流程图如图2。

图2 DPDA算法流程图

2.2 方案具体实施

2.2.1 差分隐私投标阶段

拍卖人选取大素数m和n其中m和n对应的本原元分别为a和b，并将m和a、n和b分别公开。

(1)拍卖人选取两个大的随机整数xA、xB分别计算Xs=axAmodm和Xr=bxBmodn发送给频谱卖家和频谱买家。

(2)每位频谱卖家选取一个大的随机整数yA，并计算Ys=ayAmodm发送给拍卖人。

(3)每位频谱买家选取一个大的随机整数zA,并计算Zr=bzAmodn发送给拍卖人。

(4)此时拍卖人分别计算Ks=aYsmodm和Kr=bZrmodn。

(5)每位频谱卖家计算Ks=aXsmodm获取密钥Ks。

(6)每位频谱买家计算Kr=bXrmodn获取密钥Kr。

影响高速公路施工的因素主要有四个方面：施工材料的储备、拌和、运输和摊铺。施工材料在施工过程中是对施工质量影响最大的因素，而材料的储备和拌和更是直接影响着施工材料的质量以及效果。尽管施工材料的问题影响非常大，然而目前还没有关于施工材料的储备、运输的安全标准，因此实际施工中较容易出现安全问题。材料的管理与统筹需要更加标准化的方式。

(7)频谱卖家和拍卖人完成密钥交换Ks=aXsmodm=axAyAmodm=Ks。

(8)频谱买家和拍卖人完成密钥交换Kr=bXrmodn=bxBzAmodn=Kr。

(5)

(6)

将频谱卖家和频谱买家发加密后的数据CM={C1,C2,…,CM}和CN={C1,C2,…,CN}传输给拍卖人。

2.2.2 差分隐私价格判定阶段

拍卖人在收到频谱卖家和频谱买家发送的数据后，通过加和这些加密的数据值，得到如(7)元组：

(7)

(8)

(9)

对于频谱买家的发送的加密数据，拍卖人进行数据加和得到：

(10)

拍卖人利用自己的密钥SL0获得解密买家的报价价格：

(11)

确定的频谱交易价格Pc由如(12)计算得到：

(12)

根据计算的出的最终频谱交易价格，将其定义为基准价格，对于频谱卖家而言，如果存在PiPc则意味着所有大于基准价格的竞标价可以被允许购买。最后将符合条件的买家和卖家写进一个列表中。

2.2.3 买卖匹配阶段

考虑到频谱拍卖所具有的可复用性，使用频谱买家提供的地理位置信息L=[L1,L2,L3,…LN]对频谱买家构建拓扑图，也就是说可以为一个频谱分配多个互不干扰的获胜买家，以最大限度地提高频谱卖家的收入。使用冲突图G=(V,E)来描述买家之间的干扰关系。在干扰图G中，每个顶点和边分别表示所有买家对频谱卖方的出价及其干扰关系。连接两个买家的边缘表示他们在通过同一频谱传输时相互干扰。因此，将哪些买家可以同时分配给一个频谱的问题，转化为在冲突图上找到最大独立集的问题。最后，如果存在买家想要继续匹配其他频谱资源，根据买家的意向列表可以对资源进行再匹配，实现资源的最大利用。

2.3 安全性分析

DPDA是在双向异质频谱拍卖方案下结合了差分隐私机制以及Diffie-Hellman算法所提出的，该算法在三个阶段保证了频谱需求者的敏感信息隐私安全。差分隐私投标阶段,频谱买卖双方在该阶段用噪音掩盖自己真实的频谱报价价格，使用Diffie-Hellman密钥交换协议与拍卖人进行密钥交换，加密自己的报价，可以看到在该阶段，除却身份ID、地理位置等信息外，任何有关频谱拍卖的价格敏感信息都做了噪音以及加密处理，没有任何敏感信息的泄露。差分隐私价格判定阶段，计算小组价格，确定基准价格，在整个计算过程中，所有的有关价格的敏感信息都是加入噪音扰动的。也就是说没有拍卖人并不能对有关价格的敏感信息得到有价值的东西。确定赢家阶段，拍卖人确定买家价格对比基准价格判定，确定最终的赢家价格，根据设定的差分隐私噪声机制可以发现最终价格是小组的平均价格，也就是说频谱买家和频谱卖家提交的报价信息是没有办法知道的，故在该阶段该算法也是安全的。以下是基于文章中差分隐私方案DPDA证明机制符合差分隐私的相关证明：

其中，∈是一个大于0的参数，e1,e2,…em是从集合分布中提取的一组独立的随机变量，b″的兄弟价格设为b',可以显然得到所有价格的和如下表示：

(13)

该函数的概率密度函数如(14)表示：

(14)

根据价格和的输出空间及概率，推导如(15)：

(15)

由此可见，差分隐私拍卖方案DPDA符合ε-差分隐私。

时间复杂度计算：

DPDA的算法复杂度为O(KM2N2X),其中K与X为密钥的长度，M与N代表买家与卖家的数目。

证明：算法的复杂性包括三个部分：(1)M个频谱买家和N个频谱卖家加密噪声价格的算法复杂性，以及拍卖人解密这些加密数据所耗费的计算量；(2)寻找频谱买家与其偏好的最大独立集的复杂性；(3)买家与卖家之间匹配的复杂性。首先，加密方案的复杂性来自密钥大小和买家、卖家的数量，即O(KMN)，其中K是密钥大小。然后，由于贪婪算法求最大独立集的复杂性，将其设置为O(X)。最后，匹配的复杂性由买家和卖家的总数决定，即O(MN)。因此，总的复杂度为O(KM2N2X)。

2.4 实验结果与分析

2.4.1 实验配置

实验背景是在双向频谱拍卖模型之下，多个频谱卖家提供多个频谱资源给购买者。设置卖家的数量从5位到40位不等，以5为单位递增；买家的数量定为20。由于考虑到频谱资源的干扰距离对分组匹配有影响，固定设置任何两位买家的距离不少于50m以避免重叠。卖家和买家的距离被随机设置区间为[20，80]。在实验中，假设每一位频谱买家的频谱需求和每一位频谱卖家的卖出请求都是符合在区间(0,1]的统一分布，竞标结果从区间[1，20]随机抽取。每一组实验的重复计算次数为100次。

2.4.2 频谱交易的有效性

图3呈现的是DPDA方案对比随机选择方案和分组选择方案的结果。图中可以看到，随着卖家数量的增加，DPDA方案中可接受的卖家数量大于随机选择方案和分组选择方案的，并且线性增加趋势，收入取决于明确价格和DPDA接受的卖家的数量，如图4所示我们可以看到参与人数越多，获得的收入就越高。评估匹配算法的性能在DPDA中以卖家满意度衡量为标准，即满足其优先级的卖家的数量。可以得出：DPDA不仅可以获得更好的性能，而且可以提高卖家参与频谱拍卖的动机。

图3 可接受的卖家数量

图4 收入对比

2.4.3 投标隐私保护性能

图5和图6说明了接受的差分隐私下可接受的卖家数量和买家的收入。可以注意到，在差分隐私添加噪声的情况下，接受后的卖家数量和买家的收入对比没有噪音的性能稍差。另外，它的表现当∈为1时更接近。原因是∈表示隐私差异隐私预算，当∈较小时，表示较高差异隐私级别，导致参与者提交的数据有更多的噪音。

图5 可接受的卖家数量

图6 收入对比

3 结 语

差分隐私频谱拍卖方案DPDA方案综合考虑了双向异质的频谱拍卖模型中个人隐私安全问题，通过对频谱买卖双方提交的个人隐私信息加入噪声机制对进行掩盖，并利用Diffie-Hellman算法在拍卖人和频谱买卖双方之间进行密钥交换，保护了频谱拍卖过程中的个人隐私。在安全性分析中通过对DPDA方案的安全性证明、服从差分隐私的数学证明以及时间复杂度的计算，说明了该方案的安全有效性，实验仿真模拟对DPDA方案频谱交易的有效性和隐私保护性能两个指标做了对比分析，结果证明，差分隐私的双向异质频谱拍卖方案DPDA具有高效益性和隐私安全性。