【《基于Paillier同态加密的异质频谱安全拍卖协议设计》6400字】

基于Paillier同态加密的异质频谱安全拍卖协议设计目录TOC\o"1-3"\h\u24042基于Paillier同态加密的异质频谱安全拍卖协议设计 ]有无有有本文有有有有1.1.1分组方案分析 方案中未使用常见的McAfee算法用于最终的拍卖定价阶段，原因如下：在同质物品的双拍卖中，两种著名的拍卖算法VCG和McAfee都能确保诚实性。但是，如果我们直接将这些算法应用于异质频谱拍卖，则无法保证拍卖的诚实性。在McAfee双重拍卖中，拍卖人按非增价顺序对买家的出价进行排序，卖家的出价按非减价顺序进行排序：,然后拍卖商找到最大的，使。McAfee计划放弃了利润最低的交易，为买家制定统一价格为以及卖方的统一付款是。在异质频谱的双重拍卖中，虽然一个买家最多可以赢得一个物品，但它可以操纵其出价以获得更高的效用。 如图1.2所示：图1.2McAfee机制操纵效用 有四个买家,其中买家有两个非零出价和，买家和卖家的出价根据McAfee机制进行排序，可以明显看到最不赚钱的交易价格,所以中标组收取的价格为。如果买方降低对卖方信道1的出价，使，若，那么这种不端行为不会改变拍卖结果，但会使价格但可以把价格从8升到7。因此，买家的效用得到增加，已经违背了频谱拍卖的诚实性原则。 相较而言，采用组内最小报价的定价方案满足了频谱拍卖诚实性原则。为了保持异质频谱拍卖中的诚实性，选择剔除准获胜组出价中最小的一个之后求和的方式，这样的方案一方面可以使所有竞标人产生博弈心理，保证竞标人不会比心理估计过低的价格提交报价，否则一旦成为组中最小报价，自己将会无缘自己感兴趣的频谱；另一方面此方案能够避免准获胜组整体出价过低的情况出现，因为准获胜组需将剔除最低价的报价和与频谱提供者的保留价进行对比，若整个准获胜组合谋使得整体出价过低，则有可能导致整体出价低于频谱持有者保留值，使得整组拍卖失败。除此之外，在分组中考虑到频谱的异质性，将对频谱感兴趣但由于地理位置问题无法使用该频谱的竞标人剔除经竞标人独立集，通过对独立集中剩下的竞标人进行两两联合做冲突图的方式确定了不同的无冲突买家组之后，选择买家无冲突组中人数最多的一组作为准获胜组，这样的设计则充分地满足了频谱的复用性最大原则，尽可能地提高了频谱的利用率。综上所述，本方案中使用的分组方法满足了诚实性、空间异质性、频谱复用性，是一种适合异质频谱拍卖的分组算法。1.1.2方案正确性证明初始条件：、共享Paillier密码系统知识，且共享公钥，拥有私钥。 Step1：随机选取小于的和，计算并发送给。 Step2：计算，。 Step3：进行验证，若通过则相信，反之则否定。 证明：假设是非诚实的，即并非拥有私钥，也即并不能解密出明文，但企图伪造明文对进行欺骗，由于本拍卖算法采用Paillier加密系统，所以在不知道私钥的前提下伪造了明文，构造并发送给，则在step3中必然会因为检验失败而拒绝接受的证明。导致此情况的原因是，在此前的step2之前，没有获取到更多关于明文的信息，除穷举法外别无他法，然而穷举法获得正确明文的概率仅为，当足够大时，欺骗行为的成功率可以忽略不计。1.1.3方案安全性分析本方案的参与方有三个，分别是有频谱需求的要进行竞拍的竞标人，以及执行拍卖的拍卖商和为了保证拍卖过程中竞标人出价得到更好保护的诚实可信的拍卖代理。协议设计中主要将频谱出价作为竞标人的敏感信息进行加密保护，而其他诸如频谱干扰距离、频段传输强度等有利于竞标人对不同频谱不同特性进行了解、并提出不同报价的信息则作为非敏感信息直接参与拍卖，因此本节主要证明在方案执行过程中，除去最终确定频谱竞胜者及定价阶段，在其他阶段中竞标人的报价都是被保护的。以下将从异质频谱拍卖的各个阶段论证协议的安全性。 （1）初始化阶段 在初始化这一阶段，首先竞标人参与异质频谱拍卖使用的是匿名ID，其真实的身份得到了隐藏，并且在本方案中，竞标人提交了自己的匿名ID、地理位置和加密报价之后即可下线，分组与频谱分配及确定竞胜者、定价等之后的环节都由拍卖商和可信的拍卖代理进行操作，竞标人不需要参与其中，所以无论是窃听者还是对拍卖诚实性抱持恶意的竞拍人，抑或是拍卖商和拍卖代理，都无法得知竞标人的真实ID，从而无法对其做出恶意行为。其次，使用Paillier同态加密算法，其本身是语义安全的，而竞标人先后用拍卖商和拍卖代理广播的公钥对报价明文进行双重加密处理，所以在没有解密私钥的情况下，任何人都不可能得知竞拍人提交的报价明文值，就算拍卖商和拍卖代理，手中也只有自己这一部分的解密私钥，拍卖商解密自己的公钥加密部分后无法解密拍卖代理的加密部分，拍卖代理也无法绕过拍卖商的加密部分直接用自己的解密私钥对报价密文进行操作，也就是说双方都不可能只经一次解密就获得竞拍人提交的报价明文值，而该协议设计中也假设了拍卖代理是诚实的第三方，并不会与拍卖参与人相勾结。于是，可以说在拍卖的第一阶段本协议的设计是具有安全性的。 （2）投标与频谱分配阶段首先，在竞标人分组阶段，采用的分组方式为依次剔除不能够使用该频段但对频段感兴趣的竞标人，及在此基础上对买家独立集中的竞标人进行两两联合做互不干扰比较得出该频段的买家无冲突图，保证此阶段的拍卖只与竞标人提交的地理位置有关，和竞标人的加密报价无关。其次，拍卖商用自己的解密私钥对竞标人双重加密的报价进行一次解密，在没有拍卖代理解密私钥的情况下拍卖商不能获得竞标人报价明文，之后拍卖商用Paillier同态加密算法的加法同态性，在不知道竞标人报价真实值的情况下对拍卖代理公钥加密过的报价密文进行同态加法操，作对小组价格求和，在这之后拍卖代理得到的是小组内去掉一个值的和值，即便可以得到这个真实值，拍卖代理也无法得知该组出价最小的竞标人是谁。所以在此阶段，所设计的方案是仍然是保持着安全性的。（3）确定获胜者及频谱定价阶段首先，方案采用的分组方法如1.3.1节中所述，既可以避免有投机主义倾向的竞标人恶意拉低小组报价增加自己效用的情况，使拍卖保持着诚实性，又可以避免竞标人之间合谋操纵拍卖的行为，保证定价阶段能够合理避免合谋操纵拍卖的风险。其次，拍卖商通过拍卖代理返回的信息确定该组出价最小的人，但又无法得知这个最小出价的真实值。直到小组和值与该信道保留值对比得出获胜组和频谱价格，拍卖商与拍卖代理都无法得到竞标人的全部信息的真实值，于是在此阶段，本方案依然具有安全性。综上所述，设计中用Paillier同态加密算法设计的双重加密方案结合防投机合谋的定价方案，在异质频谱的拍卖过程中保持着良好的安全性，竞标人的出价信息和其自身的隐私信息都得到了很好的保护，因此本章所设计的异质频谱拍卖协议是安全性良好的。1.1.4方案效率分析本方案采用Paillier同态加密方法进行隐私保护，Paillier同态加密的复杂性较高可以保证方案的整体安全性，异质频谱拍卖参与竞标的买家和待拍频谱较多时，会产生不小的运算量，Paillier同态加密的加法同态性操作极大地减少了解密次数，且密文的同态操作避免了读取用户明文形式的密钥份额。当有多个节点离开或加入时，基于同态技术的批处理密钥分发方案以其较少的加解密开销将更具优势。以下进行仿真：本实验采用inte酷睿i5处理器，频率为3.20GHz，内存16GB，操作系统为64为Windows8，实验主要对通信时间和通信空间和计算时间两个效率参数进行度量。本设计实验参数设置如下表所示：表1.3实验参数设置竞标人地理位置区域竞标人干扰距离频谱保留值区间竞标人报价区间最大报价个数如图1.2和图1.3所示，当竞标