一种简单高效的密封式电子拍卖方案
2014-06-02程文娟董莹莹韩俊光
程文娟，董莹莹，韩俊光
一种简单高效的密封式电子拍卖方案
程文娟，董莹莹，韩俊光
(合肥工业大学计算机与信息学院，合肥 230009)
针对目前大多数的电子拍卖方案都是假设存在一个可信第三方，使得电子拍卖的安全性有所降低的问题，提出一个基于不可信第三方的密封式电子拍卖方案。采用数字签名技术对竞拍者的身份进行验证，确保竞拍者身份的隐私性。在计算成交价时，基于离散对数求解的困难性，对竞拍价的二进制长度进行加密封装，保证竞拍价的秘密性以及结果的正确性。分析结果证明，该方案设计简单，安全性较高，在计算效率上相对于现有多数电子拍卖方案有较大的提高。
电子商务；密封拍卖；匿名性；竞拍价保密；数字签名；离散对数问题
1 概述
电子商务的发展使得电子拍卖成为电子商务中一个重要组成部分，近年来得到广泛的研究。电子拍卖是指利用Internet，在网站上公开有关待出售物品或服务的信息，通过竞争投标的方式将它出售给竞拍价最高的竞拍者。电子拍卖按获胜价位可分为：第一价位拍卖[1]，第二价位拍卖[2]和+1价位拍卖[3]。按竞拍价是否公开可分密封式和开放式拍卖，密封式拍卖要求在规定时间前，每个投标者秘密地提交一个投标价，在规定时间后才能打开投标并按一定的确定性规则选出中标者。本文讨论的方案属于第一价位密封式拍卖。
一个实用的密封式电子拍卖方案必须满足以下要求[4]：(1)正确性：能正确产生最高价的竞拍者；(2)竞拍者的匿名性：即使在拍卖结果公开后，所有参与者都不能获知其他竞拍失败人的身份及其竞拍价；(3)不可抵赖性：获胜竞拍者不能否认其已经提交的最高竞拍价，而且可以确切地获得的获胜者身份；(4)不可欺骗性：任何人都不能伪装某个已注册的竞拍者进行竞价；(5)竞拍价的保密性：竞拍者的竞拍价保密；(6)高效性：协议的计算量要尽可能的少。
本文设计了一种密封式电子拍卖方案，该方案基于一个不可信第三方即拍卖中心参与成交价的计算，拍卖中心最后仅知道成交价而不知道其他竞拍价，满足密封式拍卖对安全性的要求，并对本文设计的密封式电子拍卖方案与其他密封式电子拍卖协议进行分析比较。
2 密封式电子拍卖的研究现状
现有的大多数电子拍卖方案都是基于一个可信或半可信的第三方，约定第三方不能与竞拍者勾结。然而，这一假设是不现实的，很难确保其安全性[5]。在实际拍卖中，没有竞拍者愿意泄漏自己的竞拍价，甚至不愿意泄漏竞拍价之间的非平凡关系(如大小关系)，防止产生拍卖过程中的作弊行为[6]。因此，拍卖过程中竞拍者的匿名性和竞拍价的秘密性尤为重要，同时使拍卖的效率尽可能的高。研究密封式电子拍卖的方案较多，如加密体制[7]、零知识证明[8]、位承诺[9]、环签名技术[10]、Hash函数[11]、多方的秘密计算等。
文献[1]给出了一种利用矩阵和分布式ElGamal公钥密码体制来实现的第一价位电子拍卖方案，方案可实现完全隐私性，但是并不能排除卖方和某些投标者合谋的可能性，且计算量大、效率低。文献[8]设计的方案主要运用了ElGamal加密体制和零知识证明，与文献[1]方案相比，通信量相当，但计算量明显减少。文献[9]通过改造Bit承诺协议，将盲签名技术应用于Bit承诺协议的生成阶段，设计一种密封式的电子拍卖方案。该方案实现了密封式电子拍卖方案的所有安全要求，同时可以抵御多种合谋攻击行为。但在拍卖结束后，中标者的所有信息都是由中标者自己公布，存在一定程度的不可信性。
本文利用数字签名技术和离散对数问题求解困难性，设计一个密封式第一价位电子拍卖方案，当拍卖结果公开时，只有获胜竞拍者的竞拍价会公开，其余竞拍价都是保密的。本文设计的方案方法简单，安全性较高，在效率上相对于现存的大多数电子拍卖方案有较大的改进。
3 密封式电子拍卖方案设计
3.1 电子拍卖模型设计
本文方案包括4个实体，即竞拍者、注册中心、拍卖中心和卖方。
(1)竞拍者：想购买拍卖的物品并参加竞价活动的参 与者。
(2)注册中心：负责竞拍者参与竞拍活动前的注册并分配注册序号给竞拍者，并选择一种函数作为拍卖规则发送给各竞拍者。当竞拍结果公布后，注册中心根据获胜者的注册序号公布获胜者的身份。
(3)拍卖中心：一个不可信的第三方，验证竞拍者的身份是否合法，当拍卖时间结束后，与竞拍者交互计算出成交价，公布成交价及获胜者的注册序号，通知注册中心公布获胜者身份信息。
(4)卖家：出售物品的人。
这些实体所组建一个电子拍卖模型如图1所示。
图1 电子拍卖模型
在模型中，首先竞拍者要向注册中心注册，注册中心给竞拍者分配一个序号用来参加后来的竞拍；拍卖中心验证竞拍者身份，并在计算成交价时与竞拍者之间存在着交互的过程；当结果产生后，拍卖中心通知注册中心公布获胜者的身份并告知卖家拍卖的结果。值得一提的是，拍卖中心与注册中心之间只存在一个单向通信通道，注册中心不能给拍卖中心发送任何信息，以防止注册中心泄露拍卖规则和竞拍者的身份。
3.2 方案基本思想
密封式电子拍卖事实上是推广了百万富翁问题，百万富翁问题是指2个百万富翁Alice和Bob想知道他们2个谁更富有，但他们都不想让对方知道自己财富的任何信息，其实质就是在不泄露双方信息的条件下比较2个数的大小。在本文设计中，有个参与者1,2,…,P，各有一个秘密输入1,2,…,m，在拍卖中心参与下，安全计算出最高竞拍价。基本思想如下：竞拍价最高的竞拍者将胜出，如果多个竞拍者出了同样的最高价，那么只有先注册的竞拍者胜出，这种解决方法是合理的，因为注册越早表明其得到商品意愿更强烈，注意拍卖的最终意愿是在竞拍价最大化的基础上，把商品分配给最需要的竞拍者，实现社会资源的最优分配。本文采用姚氏百万富翁问题的高效解决方案[12]中任意2个数比较方法的基本思想，把每个竞拍者的竞拍价m转化成二进制数F(m)，再通过一定的函数()对其进行封装，其中，()为一个在第一象限内的单调递增函数，最终比较的是(F(m))的大小，淘汰(F(m))较小的P，被淘汰的P终止比较，以此类推，直到最后的优胜者即为获胜者。
3.3 方案具体执行步骤
密封式电子拍卖方案具体执行步骤如下：
(1)初始化：假设协议中涉及的通信都是采用多方计算标准的安全广播信道模型，所有安全参数都已经由正确的程序产生，关于拍卖商品的信息、拍卖时间、拍卖规则和交易规则都已经公布在公告牌上。
(2)注册：竞拍者P向注册中心提交一个竞拍申请，注册中心按注册的先后顺序分配注册序号给竞拍者，并发送拍卖规则的函数()给各竞拍者，本文方案中，选择()=，为大于1的正小数。
(3)身份验证：竞拍者用ElGamal数字签名技术来证明自己的身份的合法性[13]。令、是大素数，满足|−1，
1)产生签名
P选择一个随机数(<且与−1互素)，计算=gmod，解同余方程g=yrmod，得到，则(,)为的签名，将(,,)发送给拍卖中心。
2)验证签名
拍卖中心计算g=yrmod，若式g成立，则签名有效，说明竞拍者身份合法，允许参加竞拍活动；若式g不成立，则置该注册序号为无效注册号，不允许无效注册号参与竞拍活动。
(4)竞拍：验证完竞拍者的身份后，合法的竞拍者P选择一个竞拍价m，并以m二进制表示的位数F(m)作为自变量计算出U=(F(m))(或点击客户端自动生成)，把它作为自己的秘密输入发送给拍卖中心。
(5)计算成交价：当规定的拍卖时间结束后，拍卖中心开始计算最高竞拍价，产生拍卖活动的获胜者及成交价，为此本文设计了一个简单高效的密封式电子拍卖协议来进行计算，协议具体如下：
一个简单高效的密封式电子拍卖协议步骤如下：
Step1竞拍者P(=1,2,…,)将各自的私有输入U发送给拍卖中心；
Step2拍卖中心比较每个竞拍者私有输入U的大小，选出U的最大值，记()为U=的个数：
(1)若()=1，则U=的这个竞拍者P获胜，转Step5；
Step3拍卖中心通知U=的P计算m=m−2－1，回到Step1继续比较；
Step4若拍卖中心在Step3中一直循环比较，最后()2，则可断定出同样的最高价的竞拍者不止一个人，比较这些出最高价的竞拍者的注册序号的大小，选出其中注册序号最小的竞拍者胜出，即为获胜者；
Step5拍卖中心不断让获胜者P输入F(m)，其中，m=m−2－1，直到F(m)=0为止，那么拍卖中心即可计算出获胜者的竞拍价，即成交价；
Step6拍卖中心公布获胜者的竞拍价及其注册序号并通知注册中心，注册中心公布注册序号为的竞拍者身份信息。
3.4 方案说明
由于每个竞拍者在参与竞拍前都通过数字签名技术进行身份验证，使得竞拍者不能否认自己的竞拍活动，恶意竞拍者也不能伪造竞拍价和发送的数据，整个协议都是在安全的信道下进行。协议在执行过程中，都是把竞拍价转化为以正小数为底数，竞拍价的二进制位数F(m)为指数的单调递增函数，使得拍卖中心很难通过这个信息了解到竞拍者的竞拍价，由于注册中心和拍卖中心之间的信道是单向的，拍卖中心不知道注册中心发送拍卖规则()，即使有恶意的竞拍者和拍卖中心勾结，透露给拍卖中心()，在本文方案的函数也是基于离散对数求解问题，拍卖中心很难通过该函数来破解竞拍者的竞拍价，除非F(m)=1,2时，才容易猜到竞拍价，这样的小数目在电子拍卖中很少出现。
4 密封式电子拍卖方案分析
4.1 安全性能分析
下面从设计安全电子拍卖方案的角度分析该方案能否实现前面叙述的安全电子拍卖的要求。
(1)正确性：根据协议描述，最终由出价最高的竞拍者胜出(在协议中已有详细的描述，这里就不再赘述)。
(2)竞拍者的匿名性：每一个竞拍者都是以注册中心分配的序号参与拍卖活动的，拍卖中心和其他竞拍者不知道竞拍者的真实身份，实现竞拍者身份的匿名性。
(3)不可抵赖性：拍卖中心和获胜者交互计算成交价时，获胜者并不知道此时自己胜出，所以拍卖中心公布成交价后，获胜者不能抵赖或篡改自己的竞拍价。
(4)不可欺骗性：竞拍者在竞拍前都通过数字签名技术来进行身份认证，由于数字签名技术具有能够核实签名者的作用，因此任何人都不能伪装成已注册的竞拍者来参加竞拍活动。
(5)竞拍价的保密性：拍卖中心和所有竞拍者除了知道成交价以外，并不知道其他竞拍者的竞拍价，因此实现了竞拍价的保密性。
4.2 效率分析
本文协议的效率主要是看拍卖中心的计算量，拍卖中心在第一次比较出值时进行了−1次比较，由文献[12]可知，F(m)与F(m)不同的概率为99%，基本上在Step2中即可确定获胜者，而计算成交价时拍卖中心与获胜者之间的交互次数小于或等于，本身就是一个较小的数，在效率计算时可以忽略，所以该方案的计算复杂度()比一般协议的效率高。
下面给出本文协议与其他协议效率和安全性的比较情况。
文献[1]设计的方案计算复杂度为(2)(表示其他方案中给定的竞拍价空间的长度，表示竞拍者的数目)，与其他方案相比效率低。至于安全性方面，方案中的标价信息在竞拍者之间共享，获胜者和成交价由竞拍者联合决定，而不依赖于第三方，最后的成交价只有获胜者和卖方知道，能够在任何勾结的情况下保证获胜者竞拍价的秘密性。虽然该方案在安全性较高，但是效率低下。
文献[8]设计的可达到完全隐私的密封电子拍卖方案的计算复杂度为()(表示其他方案中给定的竞拍价空间的长度，表示竞拍者的数目)，效率较低。安全性类似于Brandt方案，获胜者和成交价由竞拍者联合决定，最后成交价只有获胜者和卖方知道，每个竞拍者仅知道自己是否获胜，达到保护竞拍者隐私的目的。
文献[9]设计的基于不可信第三方的电子拍卖方案的计算复杂度为()(表示竞拍者的数目)，效率较前2种方案高。该方案中结合Bit承诺与盲签名技术，实现了密封式电子拍卖的安全性要求，并可抵御多种合谋攻击行为。该方案能满足密封式拍卖的要求，但是在拍卖过程中，竞拍者可能需要多次出价，违背了竞拍者的本意，而在拍卖结束后，中标者的所有信息都是由中标者自己公布，存在一定程度的不可信性，方案中用到了Bit承诺与盲签名技术等技术，协议较复杂。
本文设计的密封式电子拍卖方案的计算复杂度为() (表示竞拍者的数目)，方案中利用不可信的拍卖中心进行成交价的计算，竞拍结束后，只有成交价公开，其余竞拍价在任何勾结下都是保密的，满足密封式拍卖对安全性的要求。本文方案设计思想简单，而且效率较高。同时，本文设计的电子拍卖方案不仅适用于第一价位的电子拍卖，也同时适用于其他方式的电子拍卖。例如，如果是第二价位的电子拍卖，只需在协议的第2步中选出U排序后的仅次于最大值的第二大值作为，再按协议的顺序进行，同样可产生出成交价及获胜者。综上所述，综合协议的效率、安全性和同一性，本文方案可以适用于各类电子拍卖。
5 结束语
本文设计了一个简单高效的第一价位密封式电子拍卖方案，该方案是基于一个不可信的第三方，其安全性体现在竞拍者身份的隐私性、竞拍价的秘密性以及结果的正确性。结果证明，在拍卖结束后，只有成交价公开，其余竞拍价都未泄露，竞拍者注册后可使用数字签名技术保证协议的不可伪造性、抗重放攻击性和不可否认性，该方案还满足匿名性、保密性和高效性，并且其效率较一般电子拍卖方案的效率要高，但其不能公开验证成交价，而是由拍卖中心计算和公布，后续工作将从可公开验证成交价这个方面进行研究。
[1] Brandt F. Fully Private Auctions in a Constant Number of Rounds[C]//Proc. of the 7th Annual Conference on Financial Cryptography. Munich, Germany: [s. n.], 2003: 223-238.
[2] 陈晓峰, 张方国, 王育民. 一种改进的密封式标价电子拍卖协议[J]. 电子与信息学报, 2002, 24(7): 997-999.
[3] 杨加喜, 王育民. 一种安全高效的M+1电子拍卖[J]. 网络安全技术与应用, 2006, (11): 87-88.
[4] 王晓敏. 基于环签名的电子拍卖方案[J]. 电脑知识与技术, 2011, 7(14): 3422-3423.
[5] 秦 波, 秦 慧, 王尚平. 一种保护标价安全的电子拍卖方案[J]. 计算机研究与发展, 2006, 43(1): 28-32.
[6] 伍前红, 姜正涛, 袁素春. 一个具有最小泄漏的可公开验证M+1电子拍卖[J]. 通信学报, 2005, 26(1): 12-16.
[7] 周 然, 黄根勋, 魏福山, 等. 基于ElGamal公钥密码体制的电子拍卖协议[J]. 计算机工程, 2007, 33(4): 121-124.
[8] 张京良, 马丽珍, 王育民, 等. 可达到完全隐私的密封电子拍卖方案[J]. 通信学报, 2007, 28(11A): 186-189.
[9] 曹 刚. 基于不可信第三方的电子拍卖方案[J]. 计算机工程, 2010, 36(20): 140-141, 144.
[10] Lee Cheng-Chi, Ho Pi-Fang, Hwang Min-Shiang. A Secure E-auction Scheme Based on Group Signatures[J]. Information Systems Frontiers, 2009, 11(3): 335-343.
[11] 杨加喜, 李用江, 王育民. 一种新的基于Hash链的电子拍卖[J]. 计算机工程, 2007, 33(19): 99-100.
[12] 李顺东, 戴一奇, 游启友. 姚氏百万富翁问题的高效解决方案[J]. 电子学报, 2005, 33(5): 769-773.
[13] 曲 娜, 杜洪军, 颜 达, 等. ElGamal数字签名算法的一种变形[J]. 吉林大学学报: 信息科学版, 2009, 27(6): 590- 594.
编辑 陆燕菲
A Simple and Efficient Sealed-bid Electronic Auction Scheme
CHENG Wen-juan, DONG Ying-ying, HAN Jun-guang
(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)
Most of the electronic auction schemes are assumed the existence of a trusted third party, which makes the security of the electronic auction decreased. Aiming at the problem, this paper proposes a sealed-bid electronic auction scheme based on an untrusted third party. It uses the digital signature technique to verify the identity of the bidder and ensure the privacy of the bidder’s identification. In calculating the transaction price, based on the intractability of the discrete logarithm, it encrypts and packages the binary length of the auction price to ensure the secrecy and accuracy of the results of auction price. Analysis results show that the scheme is simple and has high security, and the computational efficiency relative to most of the existing electronic auction scheme has greatly improved.
e-commerce; sealed auction; anonymity; bid price confidentiality; digital signature; discrete logarithm problem
1000-3428(2014)03-0171-04
A
TP309.07
国家自然科学基金资助项目(51274078)；教育部人文社会科学科研基金资助项目“基于SMC的电子商务安全性研究”(09YJA630029)。
程文娟(1970－)，女，副教授，主研方向：信息安全，电子商务；董莹莹、韩俊光，硕士研究生。
2013-02-28
2013-04-22 E-mail：cheng@ah.edu.cn
10.3969/j.issn.1000-3428.2014.03.035
