面向隐私保护的多属性逆向频谱拍卖方案

王佳琪，鲁宁,2，程庆丰，巫朝霞，史闻博

（1.东北大学计算机科学与工程学院，辽宁 沈阳 110819；2.西安电子科技大学计算机科学与技术学院，陕西 西安 710126；3.信息工程大学四院，河南 郑州 450001；4.数学工程与先进计算国家重点实验室，河南 郑州 450001；5.新疆财经大学应用数学学院，新疆 乌鲁木齐 830012；6.东北大学秦皇岛分校计算机与通信工程学院，河北 秦皇岛 066004）

1 引言

近几年，由于无线通信业务的迅猛发展，对频谱资源的需求呈爆炸性增长趋势[1-3]。为提高其利用率，业界提出频谱拍卖的概念[4]，一方面鼓励频谱拥有者可随时自行售卖或出租空闲的频谱资源；另一方面允许频谱买家购买回收已出售的频谱资源，实现二次分配。基于此，根据拍卖活动的开展方式，频谱拍卖方案可分为“一对多”和“多对一”2种。前者是正向拍卖，其中拍卖人为频谱拥有者，竞标人则为购买用户，在每轮拍卖过程中，频谱拍卖人以最大化自身收益为目的，采用竞价方式来选定频谱赢家。后者是逆向拍卖，它以频谱买家为拍卖人，频谱拥有者为竞标人，通过采购方式来选定拍卖赢家，最大化自身利益。目前，绝大部分研究工作都偏向于频谱交易市场上更常见的“一对多”正向拍卖，忽略了可完成频谱二次分配的“多对一”逆向拍卖，而后者也是提高频谱资源利用率所需的手段。例如，美国于2017年就曾通过逆向拍卖回收部分已分配但被闲置的频谱资源，进而实现了频谱资源的二次利用[5]。因此，本文重点关注“多对一”的逆向频谱拍卖方案。

目前，政府利用逆向频谱拍卖向频谱拥有者回收闲置频谱并二次分配频谱资源，以提高频谱利用率[6]。现有逆向频谱拍卖的买卖双方只以价格展开博弈，进而确定赢家。虽然以价格展开博弈的单属性逆向频谱拍卖比较容易实现，但在实际拍卖场景中，出让频谱报价较低的卖家并不一定会成为拍卖赢家。因为政府回收闲置频谱的目的是将频谱重新打包规划，进而将其分配给那些真正需要频谱、展开频谱业务的频谱买家。因此，除了价格，政府还需参考待分配频谱买家的业务需求。例如，美国联邦通信委员会（FCC,Federal Communications Commission）在评估广播业务出让频谱的价格时，往往将服务人口、覆盖地区范围以及放弃原频段的方式等属性考虑在内。国内由于网络制式不同，所需的频率范围、带宽、不同服务地区等属性都会影响某一段频谱的价格以及再分配的利用率。由此可见，为提高频谱资源的利用率，政府应将与频谱有关的多属性因素考虑在内，开展多属性的逆向频谱拍卖。

除了上述存在的问题，网络环境的复杂性也使逆向频谱拍卖面临诸多安全风险，主要包括以下几个方面。1)隐私问题。竞标信息是敏感信息，一旦被不法分子获取并贩卖给他人，可能会导致拍卖失败，甚至给用户造成无法估量的经济损失。因此，竞标信息需要保密。2)安全的数据传输。在频谱拍卖执行时，需要确保频谱拍卖参与者之间数据传输的安全性，防止被对手恶意篡改数据，从而导致错误的拍卖结果。3)欺诈勾结。频谱拍卖的拍卖人通常由频谱拥有者或频谱买家授权的第三方代理机构所担任。拍卖人为赚取更多利润可能与一个或多个频谱竞标人合谋操纵拍卖，将拍卖结果导向对他们有利的一方致使拍卖失败。4)公开验证。公开验证频谱赢家的合法性，证明频谱拍卖结果的正确性、频谱拍卖执行的公平性。

针对上述挑战，本文提出了一个面向隐私保护的多属性逆向频谱拍卖（PMRA,privacy-preserving multi-attribute reverse spectrum auction）方案。PMRA方案将频谱的非价格正向属性（如带宽、地理覆盖范围等属性）引入逆向频谱拍卖中，并利用多属性决策效用理论，由频谱的非价格正向属性值、频谱价格来计算频谱决策效用函数，从而确定频谱赢家以及最优的频谱资源方案。其次，逆向频谱拍卖往往忽略了频谱拍卖中所涉及的安全问题，为确保逆向频谱拍卖的安全性，PMRA方案提出多属性逆向频谱拍卖架构并设计安全协议。PMRA方案安全协议不仅利用Paillier加密及其门限机制确保了频谱拍卖服务器的安全性与可靠性，还引入了不经意传输技术、匿名化技术，保证了频谱拍卖中所需的安全特性。

2 PMRA方案

本节首先介绍PMRA方案的多属性逆向频谱拍卖架构，并给出在该架构下各个参与方的定义。其次，介绍PMRA方案在多属性逆向频谱拍卖架构下的威胁模型。

2.1 多属性逆向频谱拍卖架构

频谱拍卖中的买卖双方只针对价格展开博弈，从而确定频谱赢家，并未将与频谱有关的非价格多属性考虑在内。其次，在复杂的网络环境下，已有的频谱拍卖方案通常引入一个半诚实的第三方代理机构，频谱买家与代理机构协作共同完成频谱拍卖。但在实际应用环境中，代理人有可能被频谱竞标人收买，从而泄露重要的隐私数据，这可能导致错误的频谱拍卖结果。因此，如何使频谱买家获得最优的频谱资源并保证频谱拍卖的安全性十分重要。频谱拍卖的目的是为频谱拥有者赚取利润并满足频谱买家对频谱资源的诉求，在确保频谱拍卖安全运行的同时合理地分配频谱资源。以此为出发点，本文将传统频谱拍卖中存在的单一半诚实代理机构由一组频谱拍卖人所取代，提出一个多属性逆向频谱拍卖架构。PMRA方案基于此架构，利用Paillier门限机制可有效地防止频谱参与方任意两方的相互勾结，可避免因隐私数据的泄露而导致错误的频谱拍卖结果，从而确保了频谱拍卖服务器的可靠性与安全性。在频谱拍卖执行过程中，为确保竞标人（频谱拥有者）身份的匿名性与竞标方案的隐私性，方案利用匿名化技术隐藏竞标人的身份信息，并利用Paillier加密方案加密频谱竞标人的竞标信息（频谱价格与非价格正向属性值）。每个频谱拍卖人所拥有的分治集中式频谱拍卖服务器通过不经意传输技术获取频谱竞标人加密的频谱竞标方案，并计算密文状态下的频谱决策效用函数。最后，频谱买家收到服务器发送的部分解密与验证信息以还原明文，当还原所有频谱竞标人的频谱决策效用函数后，判断决策赢家完成频谱拍卖。

多属性逆向频谱拍卖架构如图1所示。该架构由一组数量为m的频谱竞标人、n个拥有分布式频谱拍卖服务器的拍卖人以及频谱买家3个参与方组成。首先，每个频谱竞标人根据实际情况出让频谱资源并拟定频谱竞标方案。其次，n个频谱拍卖人分别获取频谱竞标方案中加密后的频谱竞标价格与非价格的正向属性值，利用各自的频谱拍卖服务器计算密文状态下的频谱正向属性的权值、频谱决策效用函数值。拍卖服务器再利用子密钥解密得到部分消息。最后，频谱买家收到n个服务器发送的部分解密消息，还原密文状态下的频谱决策效用函数。当频谱买家还原了m个频谱竞标人的决策效用函数值后，则可判断拍卖赢家。

图1 多属性逆向频谱拍卖架构

在多属性逆向频谱拍卖架构下，频谱买家、频谱竞标人与频谱拍卖人的定义如下。

定义1频谱买家。频谱买家是需要回收购买频谱的频谱管理部门。频谱买家主要执行2个步骤，一是在频谱拍卖开始前，频谱买家需要在电子公告板上发布所回收频谱资源的必要信息。二是在判断拍卖赢家阶段，频谱买家接收服务器发送来的部分解密密文、部分有效验证证明，可依次解密还原每个竞标人的频谱决策效用函数值。频谱买家通过频谱决策效用函数值判断竞标赢家。

频谱买家为获取竞标人提供最优的频谱资源时，往往要将频谱带宽、覆盖地理范围等向上增长的正向属性考虑在内，即频谱的正向属性值越大，则频谱资源越优质。由此猜想，若以频谱决策效用函数值确定频谱赢家，所计算出的频谱决策函数效用值应随着频谱的正向属性值增大而呈现线性递增的趋势。而多属性决策（MADM,multiple attribute decision making）理论中的线性加权法刚好满足这一特征。多属性决策又称为有限方案的多目标决策理论，即在考虑多个属性的情况下，需要选择最优的候选方案或对方案进行排序的决策问题。多属性决策的数学模型描述如下。设多属性决策的方案集合为D={d1,d2,…,dm}，属性集合为A={a1,a2,…,an}。则矩阵X(xij)m×n(i=1,2,…,m;j=1,2,…,n)表示方案集D关于属性集A的决策矩阵。决策矩阵X表示为

线性加权法作为多属性决策理论的方法之一，它的决策系数由属性的权重决定，将各个正向属性线性加权求和即可实现最优的决策判断。由此，PMRA方案使用多属性决策理论中的线性加权法描述频谱决策效用函数[7]，当计算得出频谱决策效用函数的最大值时，即可确定频谱买家的最优方案。设频谱决策效用函数为Utility(-bi,ASi)，其中bi表示频谱竞标人i的频谱竞标价格。设有T个与频谱有关的正向属性，则ASi={Ai1,Ai2,…,AiT}表示竞标人i提供的频谱正向属性值的竞标集合，W={w1,w2,…,wT}则表示频谱正向属性的权重集合。例如实际拍卖场景下，在针对某些运营商放弃部分频谱使用权时，政府在回收频谱的过程中往往需要考虑频谱的带宽、地理覆盖范围等正向频谱属性因素，因此带宽越大、地理覆盖范围越广，频谱资源越优质。对于政府而言，频谱竞标人的竞标价格越低，则越有利于回收。由此，在频谱决策效用函数中的频谱竞标价格取值为-bi。频谱决策效用函数表示为

其中，Aij为频谱竞标人i的第j个频谱正向属性值，可简记为Aj；wj为对应的频谱属性权重值；T为频谱的正向属性个数。本文以式(2)为依据设计安全协议。由式(2)可知，除频谱竞标价格以外，频谱正向属性的权值影响频谱决策效用函数值的高低。根据上文讨论可知，在参与竞标的频谱竞标人中，计算得出频谱决策效用函数的最大值时则为频谱资源的最优方案。因此，频谱买家以式(3)确定频谱竞标赢家。

由于频谱的竞标价格与频谱属性值的单位和取值范围都不同，故难以使频谱的竞标价格与频谱的属性值直接参与频谱决策效用函数值的计算。例如，当回收网络服务提供商的部分频谱资源时，设当频谱的正向属性个数T=3时，可选定频谱的正向属性值的集合为{频谱的带宽（MHz），地理覆盖范围（km），频率范围（MHz）}。频谱的竞标方案为{频谱价格（亿元），频谱的带宽（MHz），地理覆盖范围（km），频率范围（MHz）}。由于频谱不同，属性的取值单位不同，因而无法进行频谱决策效用函数值的计算。为消除不同数量级、量纲和类型对频谱决策效用函数值的影响，需要对数值进行规范化处理，将量级、量纲和类型不同的频谱竞标价格与频谱属性利用数学变换，统一变换到相应的取值范围内。常用的方法有向量规范化、线性变换与极差变换法。因数值的规范化并非本文研究的重点，在此不做介绍。

定义2频谱竞标人。频谱竞标人即频谱拥有者，由一组数量为m，为获利放弃部分频谱使用权而售卖其频谱资源的卖家用户构成。设频谱竞标人i(1≤i≤m)的竞标方案为Bi={bi,ASi}(Aj∈ASi,1≤j≤T)。频谱竞标人查看电子公告板上频谱买家发布的频谱资源需求信息，判断所拥有的频谱是否符合频谱买家的需求，从而决定是否参与频谱拍卖。若确定参与频谱拍卖，则频谱竞标人根据频谱资源的属性信息拟定频谱竞标方案。为保护频谱竞标方案的隐私性，频谱竞标人利用可信机构产生的公钥加密频谱竞标方案。

定义3频谱拍卖人。频谱拍卖人的数量为n，且每个频谱拍卖人都拥有各自的分布式频谱拍卖服务器Pi(1≤i≤n),n=T+1。频谱拍卖服务器的主要功能有3个。1)存储频谱买家预先设定的频谱属性权重，即权重集合W={w1,w2,…,wT}的每个权重分别存储在n-1个频谱拍卖服务器中。2)频谱拍卖服务器Pi(1≤i≤n)获取频谱竞标人的加密竞标方案，并计算密文状态下的频谱属性的权值以及频谱决策效用函数值。3)n个频谱拍卖服务器利用可信机构产生的子密钥与验证子密钥解密频谱决策效用函数值的部分消息，并将其发送给频谱买家。

2.2 威胁模型

在实际的频谱拍卖场景中，频谱拍卖人虽然在拍卖过程中可以完全遵守频谱拍卖规则执行，但他们为了获取更多的利润可能与某一频谱竞标人合作，并将服务器获取的敏感信息以及拍卖过程中产生的中间结果透露给频谱竞标人。这一行为可能会让频谱竞标人推测出其他竞标人的竞标信息，从而造成隐私数据的泄露，更严重时还会导致错误的频谱拍卖结果。由此可见，频谱拍卖人与频谱竞标人是半诚实的。而每位频谱竞标人都想赢得频谱拍卖，频谱竞标人之间属于竞争关系，因此并不存在频谱竞标人之间的相互勾结。频谱买家希望通过频谱拍卖寻求合适的频谱资源，因而频谱买家是诚实的。由此，该架构下的3个参与方构成一个频谱拍卖的半诚实模型。半诚实模型中存在着被动攻击者，换句话说，被动攻击者可以在频谱拍卖过程中获得他人信息，但无法篡改参与方在拍卖过程中的输入值与中间值，更不能使拍卖终止。半诚实模型安全定义如下[8-9]。

定义4半诚实模型下的隐私性。设频谱拍卖所执行的协议为∏，协议∏需执行的确定性功能函数为f，当存在2个参与方A和B时，x和y分别对应参与方A和B在协议中的私有输入值，则参与方A和B在执行频谱拍卖协议∏中所得到的信息值可分别记为这里的r1和r2表示参与方A和B生成的随机数，则表示参与方A和B在频谱拍卖协议∏执行过程中所接收到的第j条信息。参与方A和B执行协议后的输出可分别记为和由此可知参与方A和B执行协议后的输出实际上是的其中一部分。因此，在执行协议∏的过程中计算确定性功能函数f时，存在多项式时间算法S1和S2，应当满足

其中，|x|=|y|。

3 安全协议设计

本节首先介绍PMRA方案安全协议的整体设计，其次详细阐述安全协议所需执行的协议的初始化、频谱拍卖的竞标以及判断拍卖赢家3个阶段，最后给出方案的案例评估。

3.1 协议的整体设计

频谱拍卖中存在的单一半诚实代理机构可能被某一频谱竞标人收买。当代理机构获取解密密钥解密任意加密的频谱信息时，很可能将信息透露给频谱竞标人，从而泄露数据隐私导致错误的频谱拍卖结果。由此，本文所提出的PMRA方案安全协议将利用Paillier门限机制的基本思想[10]解决上述存在的“勾结欺诈”行为。Paillier门限机制由一个组合者、一个可信任的密钥分发者、n个服务器Pi(1≤i≤n)和多个用户组成。在本文方案的安全协议中，组合者即为频谱买家，n个服务器则对应着n个频谱拍卖人的分治集中式频谱拍卖服务器，多个用户即为多个频谱竞标人。Paillier门限机制是将门限机制的基本思想运用到Paillier公钥密码方案中。Paillier门限系统的Paillier公钥加密方案以及Paillier方案的同态性质的定义如下[11]。

定义5Paillier加密方案及其同态性质。

密钥生成。设p和q是2个大素数，计算N=pq，，g满足gcd(L(gλmodn2),n)=1，L(x)=(x-1)。公钥为pk=(N,g)，私钥为sk=λ(N)=lcm(p-1,q-1)。其中gcd为最小公倍数，lcm为最大公约数。

加密阶段。随机选择任意明文m∈ZN，则设密文为c，且Epk(m,r)=gmrNmodN2。

解密阶段。解密加密后的密文c并还原明文m，则m=Dsk(c)=L(cλ(N) modN2)。

Paillier加密方案同态性质如下。

设2个明文m1和m2，则对应密文分别为c1和

关于Paillier门限机制的具体实现内容，将会在3.2节～3.4节中详细阐述。

基于Paillier门限机制的基本思想，PMRA方案安全协议流程如图2所示。PMRA方案安全协议的设计主体需要执行以下3个阶段。

图2 安全协议流程

1)协议的初始化。首先，频谱买家在电子公告板上发布频谱资源的需求信息（可接受的频谱价格范围以及非价格正向属性的取值范围信息）的同时，将已经确定的T个非价格正向属性值的权重分别发送给对应频谱拍卖人的服务器Pi(1≤i≤n-1)。频谱竞标人i查看电子公告板上频谱买家所发布的信息，拟定频谱竞标方案Bi={bi,ASi}。其次，协议的初始化阶段引入可信机构。可信机构利用Paillier门限机制生成密钥(pk,sk)，将公钥pk公开发布到电子公告板上，依次将部分密钥ski、公开验证密钥(vk,vki)发送给每个频谱拍卖服务器。当完成上述工作后，可信机构销毁sk并退出该协议。

2)频谱拍卖的竞标。首先，频谱竞标人i利用匿名化技术以及协议初始化产生的公钥pk隐藏身份信息并加密已拟定的频谱竞标方案。其次，为确保数据传输的安全性与隐私性，每个频谱拍卖服务器Pi(1≤i≤n-1)以不经意传输的方式分别获取对应权重的加密属性值Epk(Aj)以及加密的频谱竞标价格Epk(-bi)。最后，由n个分布式频谱拍卖服务器相互协作，协议利用Paillier加密方案的同态性质计算密文状态下的各个属性的权值和频谱决策效用函数值Epk(Utility(-bi,ASi))以完成频谱拍卖的竞标过程。

3)判断拍卖赢家。首先，频谱拍卖服务器Pn计算得到Epk(Utility(-bi,ASi))并将其发送给其他n-1个频谱拍卖服务器Pi(1≤i≤n-1)。其次，每个拍卖人的频谱拍卖服务器Pi(1≤i≤n-1)用各自持有的部分子密钥ski，验证密钥(vk,vki)解密Epk(Utility(-bi,ASi))，从而各自得到部分解密消息ci、部分有效证明proofi。最后，为了还原明文Utility(-bi,ASi)，根据Paillier门限机制的基本思想，只有当频谱买家收到至少t（这里令t=n）个proofi被验证正确时，协议利用Paillier门限机制的组合算法才能得到频谱决策效用函数值Utility(-bi,ASi)。当获取m个频谱竞标人的频谱决策效用函数值后，频谱买家可计算值argmaxi(Utility(-bi,ASi))以判断频谱赢家。

3.2 协议的初始化

根据频谱买家提供的频谱资源信息，频谱竞标人i(1≤i≤m)拟定频谱竞标方案Bi={bi,ASi},Aj∈ASi,1≤j≤T。设频谱竞标人的i频谱价格为bi，非价格正向属性值的集合为{ASi}1≤i≤m，则对应的权重值集合为{wj}1≤j≤n-1。为在频谱拍卖过程中保护频谱竞标人竞标信息的隐私性，协议还引入可信机构。可信机构通过利用Paillier门限机制为频谱拍卖生成公钥与私钥。频谱拍卖的密钥生成步骤如下。

步骤1选择一个整数N，有N=pq，p与q为2个素数且p=2p′+1，q=2q′+1，gcd(N,Φ(N)=1。设m=p′q′，β是中随机选择的元素，随机选择并且设g=(1+N)abNmodN2。

步骤2设密钥sk=βm与Shamir方案共享：设a0=βm，在{0,…,Nm-1}中随机选择t个值记为ai，且有，则第i个拍卖服务器Pi子密钥si为f(i) modNm。

步骤3产生公钥pk，且公钥pk由g、N、θ=L(gmβ)=amβmodN组成。

步骤4设vk=v是在平方数组成循环群的生成元，验证密钥其中，Δ=n!，n表示频谱拍卖服务器的数量[12]。

在协议的初始化阶段，首先，可信机构将部分子密钥si发送给各自对应的频谱拍卖服务器Pi(1≤i≤n)，完成分发后则销毁密钥sk。其次，可信机构公开公钥pk、分发验证密钥(vk,vki)后退出频谱拍卖协议。频谱买家将非价格正向属性的权重值wj(1≤j≤n-1)依次发送给对应的频谱拍卖服务器Pi(1≤i≤n-1)保存。

3.3 频谱拍卖的竞标

频谱拍卖的竞标过程由频谱竞标人i与频谱拍卖服务器Pi(1≤i≤n)完成各自的竞标操作，主要分为以下3个阶段。

阶段1竞标人身份信息的匿名化。频谱竞标人i利用匿名化技术[13]隐藏其真实身份R_idi得到一个虚拟的假身份V_idi。V_idi的计算式为

其中，pad代表一个将频谱需求用户的指定位置填充适当长度的随机填充位。匿名化技术的安全性与唯一性详细证明见文献[14]。当完成m个频谱竞标人身份信息匿名化处理后，则将每个频谱竞标人的V_idi(1≤i≤m)发送到电子公告版上。

阶段2加密属性值与数据传输。首先，频谱竞标人i利用公钥pk加密频谱竞标方案。加密的频谱价格为加密的非价格正向属性值为其中其次，为确保数据的隐私性与数据传输的安全性，频谱拍卖服务器Pi(1≤i≤n)利用不经意传输技术获取对应的加密的非价格正向属性值与频谱竞标价格。不经意传输技术又叫茫然传输协议，是一种应用广泛的通信协议，能使双方以一种模糊化的方式发送和接收消息，发送方无法得知接收方接收到的具体信息内容，从而保护接收方的隐私不会被泄露。不经意传输技术定义如下[15]。

定义6不经意传输协议。设q为一个大素数，Gq为q阶循环群，Zq为拥有q个元素的有限加法群。(g,h)则为Gq的2个生成元。初始化参数输入(g,h,Gq)，发送方输入s1,s2,…,sn∈Gq，接收方选择ε∈[1,n]，也就是说，每一个接收方只能获取发送方输入其中的一个元素，且发送方并不知道接收方获取的是哪一个元素。发送方将含有ε的信息y=grhε，r∈Zq发送给接收方，然后接收方返回应答当发送方接收到{cj}后，发送方由cε=(d,f)可计算

频谱拍卖人的n个拍卖服务器Pi(1≤i≤n)利用不经意传输协议并发地选取频谱竞标人i加密后的价格与非价格正向属性值。因此，频谱拍卖服务器Pi(1≤i≤n)获取加密值的传输过程分别为以下3个步骤。

步骤1Pi(1≤i≤n)随机选取下标x，发送y=grhx给匿名的频谱竞标人i。

步骤2匿名的频谱竞标人i返回一个应答集合c={c1,c2,…,cn}，且

步骤3Pi(1≤i≤n)在应答集合c={c1,c2,…,cn}中选取对应x的元素的cx=(d,f)。Pi(1≤i≤n)获取并计算加密的频谱正向属性值，则有Pn计算获取频谱竞标价格

阶段3计算密文下的频谱决策效用函数。首先，Pi根据Paillier的同态乘法性质：对于明文m，，有Dsk(Epk(m,r)λmodN2)=λmmodN，计算密文状态下的频谱正向属性权重值其次，将每个Pi(1≤i≤n-1)计算得到的发送到Pn，利用Pailier的同态加法性质Dsk(Epk(m1,r1)Epk(m2,r2) modN2)=m1+m2modN，计算密文状态下的频谱正向属性的权重和为

因此，Pn可计算出密文下的决策效用函数值为

Pn将式(8)计算得到的密文状态下的频谱决策效用函数值发送给其余n-1个拍卖服务器。由此，完成频谱拍卖竞标的全部过程。

3.4 判断拍卖赢家

每个拍卖人的频谱拍卖服务器Pi(1≤i≤n)得到密文状态下的频谱决策效用函数值之后，首先利用自己持有的子密钥si进行部分解密。设明文c=Epk(Utility(-bi,ASi))，Pi(1≤i≤n)计算部分明文ci=c2ΔsimodN。其次，Pi(1≤i≤n)发送(ci,proofi)给频谱买家。由Paillier的门限机制的组合阶段可知，如果频谱买家收到不少于t(t=n)个有效(ci,proofi)，则可成功恢复明文Utility(-bi,ASi)；反之，则失败。由此，设S为t个有效部分解密，则其恢复值Utility(-bi,ASi)为

当频谱买家恢复其余m-1个频谱竞标人的频谱决策效用函数值后，利用式(3)排序选出最优的频谱竞标方案，判断拍卖赢家。

3.5 案例评估

本节通过实例以说明本文方案的执行全过程。设频谱买家（可能为频谱的管理部门）向频谱竞标人（可能为网络服务提供商）回收频率范围在470～600 MHz的特高频广播电视频段的频谱资源。方案的协议执行分为以下3个部分。

1)协议的初始化。频谱买家结合自身实际情况发布频谱资源的需求信息：频谱买家可接受的频谱价格范围为1～40亿元，且频谱买家所选择确定的频谱正向属性包括频率范围、地理覆盖范围、带宽。频谱买家根据自身需求预设对应的属性权重值，分别为w1=0.35、w2=0.375、w3=0.275，并分别发送到任意的3个频谱拍卖服务器中保存。频率范围根据频谱买家的实际偏好对其进行正向划分确定回收的优先级。因此，设470～520 MHz的优先级为1，520～570 MHz的优先级为2，570～600 MHz的优先级为3。优先级数值越大，频谱买家越偏好该频率范围的频谱资源。频谱买家需回收的带宽范围为5～50 MHz，地理覆盖范围在100～500 km。存在频谱竞标人A、B、C根据频谱买家所发布的频谱需求信息拟定频谱竞标方案。竞标人A、B、C的频谱竞标方案分别为{4亿元，10 MHz，1级，200 km}、{5.2亿元，14 MHz，2级，300 km}、{4.5亿元，8 MHz，3级，350 km}。频谱竞标人利用线性变换将单位不统一的属性值进行规范化处理，得到的竞标方案分别为{-0.1,0.2,0.33,0.4}、{-0.13,0.28,0.67,0.6}、{-0.1125,0.16,1,0.7}。该频谱拍卖引入可信机构利用Paillier门限机制生成公钥pk与私钥sk。可信机构将部分子密钥si发送给对应的频谱拍卖服务器Pi(1≤i≤4)，分发完成后销毁密钥sk。当可信机构公开pk并分发验证密钥(vk,vki)后退出频谱拍卖。

2)频谱拍卖的竞标。频谱竞标人A、B、C首先利用匿名化技术得到虚拟身份记为V1、V2、V3。其次，利用公钥pk加密各自的竞标方案。则加密后的竞标方案分别为V1:{Epk(-0.1),Epk(0.2),Epk(0.33),Epk(0.4)}、V2:{Epk(-0.13),Epk(0.28),Epk(0.67),Epk(0.6)}、V3:{Epk(-0.1125),Epk(0.16),Epk(1),Epk(0.7)}。以V1为例，P1、P2、P3、P4利用不经意传输技术分别获取对应加密后的频谱属性值与频谱竞标价格分别为Epk(0.33)、Epk(0.2)、Epk(0.4)、Epk(-0.1)。每个频谱拍卖服务器Pi(1≤i≤4)利用Paillier的同态性质计算各自加密后的权值。以频谱拍卖服务器P1为例，P1计算得到的加密权值为同理，P2、P3的加密权值分别为最后，将P1、P2、P3加密后的权值发送给P4。再次利用式(7)计算密文状态下，频谱属性的权重和Epk(0.2)0.35Epk(0.33)0.375Epk(0.4)0.275=Epk(0.2×0.35+0.33×0.375+0.4×0.275)=Epk(0.303 75)。则加密的频谱决策效用函数值可利用式(8)计算得出，有Epk(0.300 5)=Epk(-0.1+0.303 75)=Epk(0.203 75)。将密文状态下的频谱决策效用函数值Epk(0.203 75)分别发送给其他频谱拍卖服务器(P2,P3,P4)以完成频谱拍卖竞标的全过程。

3)判断拍卖赢家。当所有频谱拍卖服务器均收到密文状态下的频谱决策效用函数值后，Pi(1≤i≤4)则利用各自的子密钥si解密，计算得到部分解密明文以及有效验证(c1,proof1)、(c2,proof2)、(c3,proof3)、(c4,proof4)，并将其发送给频谱买家。当频谱买家收到所有部分解密与有效验证时可利用式(9)恢复频谱决策效用函数值同理0.511。根据式(3)可知，为频谱资源的最优方案，多属性逆向频谱拍卖的获胜者为频谱竞标人C。

4 安全分析

PMRA方案的安全协议是基于Paillier密码体制提出的，频谱投标人竞标值的隐私性依赖于Paillier密码体制。首先，对Paillier加密方案的安全性进行分析。其次，在提出的PMRA方案中，频谱拍卖人的频谱拍卖服务器可提供验证密文属性的有效性、部分解密密钥正确性的定理，并基于零知识证明给出交互式与非交互式证明过程。这确保了频谱拍卖服务器的可靠性与安全性。最后，为说明本文提出的频谱拍卖协议具有较强的安全性，本节不仅阐述了频谱拍卖方案所满足的安全特性，还给出本文方案协议与仅考虑价格单属性的正向频谱拍卖安全方案以及可应用到频谱拍卖场景下的多属性逆向拍卖安全方案的安全性比较。

4.1 Paillier加密方案的安全性分析

定义7合数幂剩余类的判定。设N=pq，p,q为2个大素数，对于如果存在使等式成立，则z叫作模N2的N次剩余。合数幂剩余类的判定问题是指区分模N2的N次剩余，用CR[N]表示。CR[N]是随机自归约的。设那么可得z2≡如果z1是N次剩余，那么z2同理。即任意2个实例都是多项式等价的。猜想CR[N]被称为判定合数幂剩余类假设（DCRA,decisional composite residuosity assumption）。

定义8计算合数剩余类假设。设g∈B，且表示阶为nα的元素组成的集合，B为Bα的并集，其中α=1,2,…,λ。对于，如果存在y∈使ω=Φg(x,y)=gxyNmodN2，g为阶N的非零倍，则称x∈ZN为ω关于g的N次剩余，记作[[ω]]g。求[[ω]]g称为g的N次剩余类问题，表示为Class[N,g]。由证明可得，Class[N,g]的复杂性与g无关，可将其看成仅依赖于N的计算问题[16]。即已知，g∈B，计算[[ω]]g，可记为Class[N]问题。猜想不存在求解合数幂剩余类问题的概率多项式时间算法，即Class[N]的困难问题。显然这仍旧被认为是一个困难问题。这一猜想被称为计算合数剩余类假设（CCRA,computational composite residuosity assumption）。其随机自归约性使CCRA的有效性只依赖于N的选择，可知假设DCRA是正确的，则CCRA也是正确的。

Paillier公钥加密方案系统是基于合数幂剩余类问题。当Class[N]是困难的，即计算合数剩余类假设CCRA下，Paillier加密方案是单向的（密文计算明文是Class[N]问题）。当CR[N]是困难的，即判定合数幂剩余类假设DCRA下，Paillier加密方案是语义安全的。由此，Paillier加密体制选择明文下的不可区分性则可通过实验的方式验证：存在攻击者A（Adversary）、拥有加密算法的挑战者C（Challenger）。A根据加密算法生成密钥对(pk,sk)，保存私钥sk，并将公钥pk发布并发送给C。A选取2个长度相等、值不同的明文M1、M2发送给C。而C随机选取比特值b∈{0,1}且将密文Cb=Epk(Mb)发送给A。A获取密文Cb对其任意计算操作，最后得到明文结果b′，即当确定是对M1加密还是M2加密时，攻击者A猜出b′的正确结果的优势是可忽略的。因此有AdvA(E)=|Pr[C←Epk(M1)]-Pr[C←Epk(M2)]|=ε。其中ε是可忽略的。虽然A知道pk、M1与M2，由于Paillier加密的概率特性，Mb则是众多密文中的一个，在游戏实验中，A始终无法得到更多优势。

4.2 密文属性有效性与部分解密密钥si的正确性

PMRA方案所提供的验证密文属性的有效性与部分解密密钥si的正确性不仅为频谱拍卖服务器提供了安全性和可靠性，还为频谱拍卖参与者的隐私性提供了有效的验证方法。因此，本节给出PRMA方案密文属性有效性与解密密钥si正确性的定理，并基于零知识证明给出交互式与非交互式的证明过程[16-18]。定理与证明过程如下。

定理1密文属性的有效性。频谱拍卖服务器Pi(1≤i≤n)收到的Epk(Aj)一定来自对应明文属性集合，且不揭露Epk(Aj)的真实值。

定理2解密密钥si的正确性。频谱拍卖服务器Pi(1≤i≤n)可以向任意一方证明在解密Epk(Utility(-bi,ASi))时使用的si是正确的，且不揭露任何si的真实值。

证明

交互式。公共输入值N，p=2p′+1，q=2q′+1，有|n|=k且|n|为二级制的比特长度证明者P输入si∈Zn§并向验证者V证明存在某个si∈Zn§满足等式modN2。P生成随机数w∈ZN，且计算(x,y)→c4ΔwmodN2，vΔwmodN2。之后P向验证者V发送(x,y)。V选择任意a∈R,Zn§发送给P。P计算b=w+sia，并将b发送给V。V收到b并判断等式是否成立，即以验证解密密钥si的正确性。

非交互式。设H为公开且抗碰撞的哈希函数，输出长度为L。Pi(1≤i≤n)为向任意方证明si在解密密文c时产生的部分解密密文ci，在解密过程中确保不会泄露si的任何信息，即u=c4ΔmodN2，c4ΔsimodN2，验证等式是否成立。则非交互式证明过程步骤如下。

1)承诺。P计算承诺(x,y)，且r∈{0,…,2|N|-1},|N|表示比特长度大小。x=urmodN2，y=v rmodN2。

3)计算应答。z=r+esi，e∈ {0,…,2L+|N|-1}，并生成证明proofi(e,z)。

4)V验证并判断等式是否成立，即若等式成立，则部分解密密钥si有效。

证毕。

4.3 频谱拍卖方案满足的安全特性

1)隐私性

竞标方案中价格属性与非价格正向属性值始终是在密文状态下计算的，频谱买家与频谱拍卖人的服务器Pi无法得知真实的竞标信息，因此保护了竞标方案信息的隐私性。

2)匿名性

在频谱竞标阶段，每个频谱竞标人利用匿名化技术与公钥pk得到一个临时的身份假名参与频谱拍卖。因此，频谱买家与每个频谱拍卖人都无法获取频谱竞标人的真实身份信息，确保频谱竞标人的匿名性。

3)公平性

首先，频谱拍卖方案利用不经意传输技术使频谱竞标人无法确认每个频谱拍卖服务器Pi到底获取了哪一个加密的非价格正向属性值。其次，PMRA方案利用Paillier门限机制使每个频谱拍卖服务器只拥有部分解密密钥si，任意Pi都无法独自恢复加密后的明文信息，即频谱买家与其他任意参与方不存在共谋攻击。因此，确保了频谱拍卖安全协议执行的公平性。

4)公开验证

由4.2节可知，基于Paillier门限的零知识证明协议使频谱拍卖服务器Pi(1≤i≤n)不仅可以向频谱竞标人证明密文属性的有效性，还可以向任意参与方证明部分解密密钥si的有效性。

目前，常用的频谱拍卖方案大多只考虑单一价格、“一对多”模式的频谱拍卖。本文根据实际频谱拍卖场景，提出“多对一”模式的多属性逆向频谱拍卖方案。为分析频谱拍卖场景中所需的安全特性，本文方案与仅考虑单属性的正向频谱拍卖安全方案[19-23]，以及可应用于多属性逆向频谱拍卖场景的多属性逆向拍卖安全方案[24-25]进行安全性比较。如表1所示，本文所提出的PMRA方案安全协议的安全性较强。文献[19-25]方案将在第6节的相关工作中做简要介绍，这里不再阐述。

表1 PMRA方案安全协议与各方案的安全协议的安全性比较

5 性能评估

本文提出的频谱拍卖安全协议的计算开销主要来自Paillier门限机制的随机数生成、加密与解密、模幂运算操作。为便于描述协议的计算开销，设频谱竞标人的数量为m、属性个数为T、公钥加密操作记为PKE、解密操作记为PKD、模幂运算记为ME、随机数生成记为R。

在协议的初始化阶段，由可信机构作为Paillier门限机制密钥的生成者和分发者，产生公钥pk、部分解密密钥si、验证密钥vki。则计算开销为Paillier机制的密钥初始化，所需要执行的操作为2R+PKD+PKE+2ME。

在频谱拍卖的竞标阶段，每个频谱竞标人利用匿名化技术隐藏身份并用pk加密频谱的价格属性与非价格正向属性，则需要执行的操作为(T+1)PKE。其次，当所有Pi得到加密后的频谱决策效用函数值时，需要用各自的部分解密密钥si解密，执行的操作为(T+1)PKD。

在判断拍卖赢家阶段，频谱买家需要收到不少于t个频谱拍卖服务器的有效验证值(ci,proofi)，从而恢复明文得到频谱决策效用函数值，执行的相应操作为2ME。因此，当频谱竞标人数量为m、属性个数为T时，各阶段各参与方的计算开销如表2所示。

据表2分析可知，安全协议总体的计算开销与频谱竞标人的数量m、属性个数T有关。当m增加时，各个参与方在各阶段的计算开销均相应增加，因此，安全协议总体的计算开销增加。当T增加时，竞标阶段频谱拍卖服务器与频谱竞标人所需的加密解密计算开销也随之增加，然而T的取值并不影响频谱买家在判断拍卖赢家阶段的计算开销。

为讨论PMRA方案的效率，可将其与应用于多属性逆向频谱拍卖场景下的匿名与可验证的多属性逆向拍卖（VMRA,anonymous and verifiable multi-attribute reverse auction）方案[24]、安全的在线可信的第三方多属性多轮逆向拍卖（SMRA,secure multi-attribute multi-round reverse auction using online trusted third party）方案[25]在计算开销上进行对比。通过分析PMRA方案、VMRA方案与SMRA方案的安全协议，给出3个方案在各个阶段的计算开销如表3所示。

通过表3的计算开销分析，模拟PRMA方案与VMRA方案计算开销的实验结果，计算任务都运行在一台PC机（Windows7 32,Intel Core i5,GHZ processor,1.86 GB of RAM）上。通过引入MRICAL库的C语言进行仿真实验[26]。由于RSA的计算消耗可简化为模幂的运算操作，且哈希操作与随机数的生成操作可以忽略不计。为便于本文方案协议的实验测试，加密操作PKE与解密操作PKD都可简化为模幂运算操作且记为ME。在模幂运算中，定义素数p的长度分别为512 bit、1 024 bit，则由此可计算出单个模幂运算的平均时间分别为1.5 ms与6 ms。

由表3可知，在准备阶段，VMRA方案与PMRA方案所消耗的运行时间均可忽略不计，而SMRA方案的加密操作则需要花费较多时间。对于中小规模的系统设计，设当m>T（m=50，T=10），公钥长度p为512 bit、1 024 bit时，通过实验可得VMRA方案、SMRA方案与PMRA方案完成一次拍卖后在各阶段所消耗的运行时间。则VMRA方案、SMRA方案与PMRA方案在各个阶段所消耗的运行时间以及3个方案协议所消耗的总时间分别如图3和图4所示。

由图3与图4可知，在准备阶段，VMRA方案与PMRA方案的运行时间均为0，而SMRA方案在准备阶段需消耗一定的时间。设运行时间为Tim，因此在准备阶段有Tim(SMRA)>Tim(VMRA)=Tim(PMRA)。在竞标阶段，PMRA方案、VMRA方案与SMRA方案之间所需的运行时间相差无几，且SMRA方案所需的运行时间最小。因此，在竞标阶段有Tim(VRMA)>Tim (PMRA)>Tim (SMRA)。在开标阶段，PMRA方案不需要执行任何计算，因此运行时间为0。而VMRA方案与SMRA方案均在此阶段消耗过多的运行时间。VMRA方案在此阶段所需的运行时间是SMRA方案的3倍左右。因此，在开标阶段有Tim(VRMA)>Tim (SMRA)>Tim(PMRA)。在判断拍卖赢家阶段，同样有Tim(VRMA)>Tim (SMRA)>Tim (PMRA)。最后，通过比较VMRA方案、SMRA方案与PMRA方案的运行总时间可知，PMRA方案所消耗的运行时间远远低于其他2个方案。

表2 PMRA方案协议各阶段各参与方的计算开销

表3 PMRA方案协议与VMRA、SMRA方案协议在各阶段的计算开销

图3 各个阶段运行时间（512 bit）

图4 各个阶段运行时间（1 024 bit）

由于VMRA方案、SMRA方案、PMRA方案安全协议计算消耗所需的运行时间均与竞标人数m以及属性个数T有关，因此给出对于中小规模系统设计，公钥长度p为512 bit时的协议运行总时间分别与m、T取值关系的变化曲线（公钥长度p为1 024 bit同理，这里不再赘述），分别如图5和图6所示。

由图5可知，当T=10时，VMRA方案、SMRA方案与PMRA方案协议的运行总时间均随着竞标人数m的增加而呈线性递增的趋势。其中，PMRA方案安全协议运行总时间递增的速率明显小于其他2个方案。由图6可知，当m=50时，VMRA方案、SMRA方案与PMRA方案协议的运行总时间随着属性个数T的增加呈线性递增趋势。同样地，PMRA方案协议运行总时间的增长速率依然远小于VMRA方案与SMRA方案。由上述分析可知，随着m与T的增加，PMRA方案的计算开销所花费的运行总时间远小于VMRA方案与SMRA方案。因此，在系统性能上，PMRA方案要优于VMRA方案与SMRA方案。

图5 协议总运行时间（512 bit，T=10）

图6 协议总运行时间（512 bit，m=50）

6 相关工作

近年来，频谱拍卖的安全性受到研究者们的广泛关注，根据频谱拍卖的应用场景和需求的不同，以价格展开博弈的单属性安全频谱拍卖主要分为三类，分别为单边频谱拍卖、双边频谱拍卖与组合频谱拍卖。

单边频谱拍卖是频谱交易市场中最常见的频谱拍卖类型之一，它广泛应用于一级频谱拍卖市场与二级频谱拍卖市场。“一对多”的正向频谱拍卖与“多对一”的逆向频谱拍卖均为单边频谱拍卖。近年来，研究人员大都针对频谱价格这一单属性、“一对多”正向频谱拍卖的应用场景展开安全性研究。例如，Pan等[19]提出一种安全的频谱拍卖方案，通过利用Paillier加密方案防止频谱竞标人与拍卖人之间的相互勾结。Huang等[20]提出了防策略和隐私保护的频谱拍卖（SPRING,strategy-proof and privacy-preserving spectrum auction）方案，在确保竞标人隐私性的同时满足K匿名等特性。Wu等[21]提出保护隐私与防策略的频谱拍卖（PRIDE,privacy-preserving and strategy-proof spectrum auction）方案，又在SPRING方案基础之上实现了L-多样性。Huang等[22]提出一个防策略的隐私保护频谱拍卖框架（PSS,privacy-preserving strategy-proof spectrum auction framework），旨在保护频谱竞标人的真实估值。Chen等[23]提出了频谱拍卖安全框架，在保护竞标价格隐私性的同时保护了竞标人的地理位置信息。Wang等[27]提出了可验证且隐私保护的频谱拍卖（SPSV,privacy-preserving spectrum auction with public verification）方案，在保护频谱竞标人信息隐私性的同时，提供了公开验证机制，可使方案在频谱拍卖期间不会向其他参与方透露任何敏感信息。

双边频谱拍卖广泛应用于频谱交易的二级市场。首个双边频谱拍卖方案是在2010年提出的，其安全问题引起了人们的关注[28]，研究人员就此展开关于双边频谱拍卖的安全性研究。例如Chen等[29]提出了可证明安全的双边频谱拍卖（PS-TRUST,provably secure double spectrum auction）方案，方案为半诚实的对手提供可证明的安全性，并保护了频谱竞标信息的隐私性。Chen等[30]提出的安全、高效、实用的双边频谱拍卖（SDSA,secure,efficient and practical double spectrum auction）方案可使频谱拍卖中只揭示频谱拍卖结果，从而保护频谱竞标人的隐私性。Wang等[31]设计的保密且真实的在线双边频谱拍卖（PROST,privacy-preserving and truthful online double auction for spectrum allocation）方案在保护频谱竞标人敏感信息的同时，确保了频谱竞标人的地理位置信息、时间动态的隐私性。

频谱组合拍卖在频谱交易市场上出现较少，组合频谱拍卖针对特定的频谱交易场景，允许频谱竞标人因频谱的多样性特点而对各种频谱进行组合竞标。Pan等[32]首次提出了安全的组合频谱拍卖（SCSA,secure combinatorial spectrum auction）方案，该方案解决拍卖人与频谱竞标人共谋操纵投标的安全问题。Chen等[33]提出了一种针对异构频谱的安全组合拍卖，该方案不仅保护了竞标值与地理位置信息，还提供了可验证的支付方案，以防拍卖人伪造付款。

当频谱管理部门回收频谱资源时，“多对一”逆向的频谱拍卖往往需要考虑除频谱竞标价格以外的频谱正向属性因素，以保证在未来重新分配频谱时，为不同服务业务的频谱需求用户提供更优质的频谱资源，从而提高频谱利用率。已有的多属性逆向拍卖安全方案[24-25]可应用到上述提出的逆向频谱拍卖的场景当中。Srinath等[24]提出了VMRA方案。该方案主要为多属性逆向拍卖提供了公开可验证性与匿名性。同年，他又提出了SMRA方案[25]，为竞标人提供了匿名性、不可否认性等安全特性，在一定程度上保护了多属性逆向拍卖的安全性。虽然VMRA方案与SMRA方案都可应用到多属性的逆向频谱拍卖中，但根据第4.3节的安全特性分析可知，VMRA方案与SMRA方案并不能满足频谱拍卖所需的安全性。并且在第5节的性能评估中，PMRA方案的系统效率要优于其他2个方案，PMRA方案的系统所需运行时间远低于VMRA方案与SMRA方案。因此，本文方案在所提出的逆向频谱拍卖场景中，可确保频谱拍卖的安全性并使频谱管理部门高效、合理地回收优质的频谱资源。

7 讨论

本节主要讨论频谱拍卖系统的扩展性。由PMRA方案可知，频谱拍卖服务器的数量和频谱属性呈正相关。当频谱属性增加时，频谱拍卖服务器也随之增加。在实际频谱拍卖的应用中，系统不可能因属性的增多而增加相同数量的频谱拍卖服务器。针对这一问题，本文可以将多个属性值（价格与非价格正向属性值）按照一定的规则进行分组，以小组的形式分别对应特定的频谱拍卖服务器，从而进行相应的数据运算以提高系统的扩展性。而当频谱拍卖服务器或频谱竞标人增加时，频谱竞标人与频谱拍卖服务器、频谱买家与频谱拍卖服务器之间的通信量都会随之增加，这可能导致系统性能的下降。另外，作为以拍卖交易而盈利的频谱拍卖人，随着频谱拍卖服务器的增加，频谱拍卖人的交易费用也随之增加，这也增加了系统的额外交易费用。如何优化系统性能并减少频谱拍卖人的交易费用是本文今后需要研究的内容。

8 结束语

本文提出一个面向隐私保护的PMRA方案。首先，PMRA方案将除频谱价格外其他影响频谱二次分配的频谱正向属性考虑在内，频谱竞标人提供含有频谱竞标价格与频谱正向属性值的竞标方案参与频谱拍卖。利用Paillier加密方案及其门限机制、匿名化技术以及不经意传输技术的密码学工具确保频谱拍卖所需的安全特性，使频谱拍卖协议安全地执行。其次，PMRA方案的安全分析表明，本文所提出的频谱拍卖协议具有较强的安全性。对PMRA方案进行性能评估，实验结果表明，PMRA方案的效率优于已有的多属性逆向拍卖VMRA方案和SMRA方案。最后，讨论了PMRA方案系统的扩展性问题。

本文仅考虑当频谱买家所选择的频谱属性均为正向属性时，通过利用线性加权法以计算频谱决策效用函数值来判断频谱拍卖赢家。然而在实际复杂的逆向频谱拍卖场景中，频谱的非价格属性例如原频谱的不同服务地区、原频谱的服务人口数量等因素并非都为正向属性。而在讨论PRMA方案的系统扩展性问题时，随着服务器的增加，频谱拍卖人的交易费用也随之额外增加。因此，如何设计出更适用于复杂逆向频谱拍卖场景下的频谱决策效用函数，以及如何优化系统性能以减少系统额外的交易费用等问题则是未来工作中需要研究和探讨的主要内容。