# An Efficient Electronic English Auction System with a Secure On-Shelf Mechanism and Privacy Preserving

Authors: Hong Zhong; Song Li; Ting-Fang Cheng; Chin-Chen Chang
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

With the rapid development of the Internet, electronic commerce has become more and more popular. As an important element of e-commerce, many Internet companies such as Yahoo! and eBay have launched electronic auction systems. However, like most electronic commerce products, safety is an important issue that should be addressed. Many researchers have proposed secure electronic auction mechanisms, but we found that some of them do not exhibit the property of unlinkability, which leads to the leakage of users’ privacy. Considering the importance of privacy preservation, we have designed a new auction mechanism. Through symmetrical key establishment in the registration phase, all messages transmitted over the Internet would be protected and, meanwhile, achieve the property of unlinkability. The security analysis and performance analysis show that our protocol fulfills more security properties and is more efficient for implementation compared with recent works.


---

## Body

## 1. Introduction

With the development of network technology, more and more people are searching for information on the Internet. In 2013, the number of Internet users of the whole world reached 2.92 billion [1]. Now, people not only read the news and search for information on the Internet but also do business with others. Not surprisingly, e-commerce has grown rapidly in recent decades. As the founder and CEO of China’s most famous e-commerce company Alibaba, Jack Ma was ranked as the second richest man in China in 2014. Many famous Internet companies launched electronic auction products several years ago such as Yahoo! and eBay. On these websites, users can play the role of not only auctioneer but also bidder after they register their accounts successfully. They can participate in the auction anytime and anywhere when their devices have access to the Internet.Auctions can be classified into many types [2]. According to numbers of sellers and buyers, auctions can be classified as forward auctions and reverse auctions; according to the determinant of the winner, auctions can be classified as single attribute auctions and multiattribute auctions; and according to whether the bidding price is made open, we can classify auctions as sealed-bid auctions and open auctions. The sealed-bid auctions can be subdivided into sealed-bid first-price auctions and sealed-bid second-price auctions. In the first mode, all bidders submit their sealed bids to the auctioneer of an auction at the same time, and the auctioneer or arbiter of the auction secretly calculates the highest price. After that, the auctioneer or arbiter announces the winner as the owner with the highest price bid. In a sealed-bid second-price auction (also called Vickrey auction), the highest price bidder wins the auction but only needs to pay the second highest price. The designer of the sealed-bid second price auction thinks that everyone will submit their bidding price rationally in this mode; however, this method confronts a lot of problems in practice, such as bidder collusion. Open auctions can be further classified into English auctions and Dutch auctions. In an English auction, the auctioneer changes the current price dynamically, with the bidding price increasing. This means that, if one bidder’s bid price is higher than the current price, then the auctioneer uses this price as the new current price and waits for someone to offer a higher price than the current price. If someone submits a higher price, the current price is changed simultaneously; if no one offers a higher price when the auction is closed, the owner of the current price bid wins the auction. A Dutch auction is bidding process contrary to the English auction. In a Dutch auction, the auctioneer decreases the current price until one bidder can afford it and is the winner of the auction.A lot of problems arise when we introduce the auction process in reality on the Internet. An important issue is the information security of the system. As an Internet product is connected with money and goods, users are concerned with the safety of the online auction. Many researchers have proposed their protocols to solve security problems in auction systems. In 1999, based on millionaires’ problem, Cachin [3] proposed a private bidding and auction scheme with an oblivious third party. In 2000, Nguyen and Traoré [4] used a group signature to protect bidders’ anonymity. However, the huge computational cost and the special authority of group managers still cannot be resolved. In 2001, Omote and Miyaji [5] applied a bulletin board to overcome these problems, but their scheme does not publish the winner’s information at the end. In 2003, C.-C. Chang and Y.-F. Chang [6] proposed an anonymous English auction protocol to ensure that bidders can bid arbitrarily. In 2005, Jiang et al. [7] considered that the scheme in [6] cannot protect against man-in-the-middle attacks. In 2006, Y.-F. Chang and C.-C. Chang [8] proposed another anonymous auction scheme to resolve the problem in [6]. In 2005, Suzuki and Yokoo proposed safety problem in the multiattribute auction systems [9]. In 2007, Shih et al. proposed a privacy preserving multi-item auction mechanism with a shared key chain [10]. In 2008, Parkes et al. used a homomorphic cryptograph to achieve bid privacy in multi-item auction [11]. In 2009, Xiong et al. [12] proposed an anonymous auction scheme based on the ring signature. However, like the group signature-based protocol in [4], huge computational cost is an essential problem that should be resolved. In 2012, Xiong et al. [13] proposed another protocol based on revocable ring signature to solve the problem of high computational cost in [12] and added a dispute section.In 2013, Chang et al. [14] pointed out that [13] is vulnerable to denial of service attacks and designed an ECC-based protocol which provides a secure on-shelf phase. Unfortunately, we found that Chang et al.’s proposal [14] does not provide unlinkability. In [14], users’ privacy can be leaked by monitoring the communication of system and linking the captured information. Although some important data such as public key and certificate are encrypted before transmission, unencrypted messages such as on-shelf information can link different packets together. For example, in the on-shelf phase, although attackers cannot calculate the true public key of the auctioneer using an encrypted message transmitted from the auctioneer and the published anonymous public key on website, attackers still can link transmitted packets and website information together through on-shelf information. This is because the on-shelf information is transmitted in plaintext. On the other hand, bidders’ privacy is in more serious danger during the bidding phase. At the end of the bidding phase, the agent center (AC) publishes the information with the bidder’s true public key on its website. Attackers can link this public key with a certain IP address and know what the user bids on. Then, attackers can trace this public key owner’s transaction history.Until now, many researchers have stressed the importance of privacy preservation in online auctions [15–17]. Hence, in order to overcome the privacy problem in [14], in this paper, we provide a new English auction system with privacy preservation. The overview of the auction system architecture is shown in Figure 1. Using the same system mode with Chang et al.’s proposal [14], our system has 5 phases: the registration phase, on-shelf phase, bidding phase, product-claim phase, and dispute phase. We utilize a trusted third party as theAC of our system, a well-meaning role that will not initiate attacks. However, the safety of theAC’s database cannot be completely guaranteed. We do not consider the case of hackers controlling theAC, but hackers may get access to read data in theAC. The only data we consider to be completely safe is the private key ofAC. Besides this, any leaked data cannot do serious harm to the safety of the whole system. In addition, we built our protocol on Elliptic Curve Cryptosystem. According to the analysis in Section 8, our proposal has an efficiency advantage over the original proposal. In our scheme, messages transmitted between any two entities are encrypted with a symmetrical encryption algorithm such as AES. By utilizing this method, monitors cannot link different messages together. Security analysis shows that our proposal provides more security properties than the original one.Figure 1
Privacy problem in electronic auction system.The rest of this paper is organized as follows. In Section2, we introduce the Elliptic Curve Cryptosystem and ECDLP (elliptic curve discrete logarithm problem). Subsequently, we briefly review Chang et al.’s auction protocol [14] in Section 3. In Section 4, we talk about network model, adversary model, and properties that an auction mechanism needed. We describe our proposal in detail and use BAN logic to analyze authentication accuracy of on-shelf phase and bidding phase in Sections 5 and 6, respectively. In Sections 7 and 8, we compare the security and efficiency of our protocol with related schemes.


## 2. Preliminaries

In this part, we introduce some basic ideas of Elliptic Curve Cryptosystem including the definition of elliptic curve, basic operations on the Elliptic Curve, and ECDLP on ECC that can be used to construct cryptographic algorithms.


### 2.1. Elliptic Curve Cryptosystem

Elliptic Curve Cryptosystem (ECC) is an asymmetrical cryptosystem. It was independently proposed by Miller [19] and Koblitz [20] in 1985 and 1987. Compared to RSA, ECC can achieve the same security requirement with a shorter key-length [21]. Hence, it has been widely used in many cryptographic schemes recently.An elliptic curve [22, 23] is defined over a finite field Fp by equation Ep(a,b):y2=x3+ax+b, where p is a large prime and 4a3+27b2≠0mod⁡p. The points on this elliptic curve form a cyclic group. Addition in this group is defined as if points P,Q,R∈Ep(a,b) on one line, and then P+Q+R=O (O is infinite point). Given an integer s∈Fp∗ and a point P∈Ep(a,b), the multiplication operation s·P over Ep(a,b) is defined as P+P+⋯+P in s times. If P is symmetrical with P′ on the x-axis, then P+P′=O. Furthermore, point P is a base point with an order n if and only if n·P=O.


### 2.2. ECDLP

Every cryptosystem has its own difficult problem, such as the integer factorization used in RSA. The most important difficult problem in ECC is the elliptic curve discrete logarithm problem (ECDLP) [24]. Based on ECDLP, we can develop many other difficult problems, such as the computational Diffie-Hellman problem (CDLP) and the elliptic curve factorization problem (ECFP). In our scheme, we will use ECDLP.Definition 1 (elliptic curve discrete logarithm problem (ECDLP)).
Given two pointsP and Q over Ep(a,b), it is very hard to find an integer s∈Fp∗ such that Q=sP.


## 2.1. Elliptic Curve Cryptosystem

Elliptic Curve Cryptosystem (ECC) is an asymmetrical cryptosystem. It was independently proposed by Miller [19] and Koblitz [20] in 1985 and 1987. Compared to RSA, ECC can achieve the same security requirement with a shorter key-length [21]. Hence, it has been widely used in many cryptographic schemes recently.An elliptic curve [22, 23] is defined over a finite field Fp by equation Ep(a,b):y2=x3+ax+b, where p is a large prime and 4a3+27b2≠0mod⁡p. The points on this elliptic curve form a cyclic group. Addition in this group is defined as if points P,Q,R∈Ep(a,b) on one line, and then P+Q+R=O (O is infinite point). Given an integer s∈Fp∗ and a point P∈Ep(a,b), the multiplication operation s·P over Ep(a,b) is defined as P+P+⋯+P in s times. If P is symmetrical with P′ on the x-axis, then P+P′=O. Furthermore, point P is a base point with an order n if and only if n·P=O.


## 2.2. ECDLP

Every cryptosystem has its own difficult problem, such as the integer factorization used in RSA. The most important difficult problem in ECC is the elliptic curve discrete logarithm problem (ECDLP) [24]. Based on ECDLP, we can develop many other difficult problems, such as the computational Diffie-Hellman problem (CDLP) and the elliptic curve factorization problem (ECFP). In our scheme, we will use ECDLP.Definition 1 (elliptic curve discrete logarithm problem (ECDLP)).
Given two pointsP and Q over Ep(a,b), it is very hard to find an integer s∈Fp∗ such that Q=sP.


## 3. Related Work

In this part, we describe Chang et al.’s proposal [14] briefly and analyze the security and privacy preserving in it.Chang et al.’s protocol includes five phases: registration phase, on-shelf phase, bidding phase, product claiming phase, and dispute phase. A new user should register to an agent center (AC) andAC will issue a certificate for him/her such that he/she can play the role of both auctioneer and bidder. If a registered user wants to initiate an auction, he/she should send some basic information about auction (i.e., product identity, basic price of the auction, and deadline) toAC via the on-shelf phase. Upon checking the legality of user’s identity and the information of the new auction,AC publishes an advertisement on its website (BBAC) such that anyone can read it after the auction has started. If someone wants to bid for the product of this auction via the bidding phase, he/she can send bidding information toAC. AfterACchecked the legality of bidder’s identity and the bidding price is higher than current price,AC should change the value of current price to the bidding price and publish the bidder’s public key and bidding price onBBAC; else,AC ignores this bid and waits for new bid. After the auction deadline,AC selects the bidder with highest price as the winner, sends a receipt to the winner, and publishes final result onBBAC such that anyone can read and verify it. After getting the receipt, the winner can claim the product from the auctioneer by showing the receipt via the product claiming phase. Then, the auctioneer can verify the correctness of this receipt and send the product to the user. With regard to the dispute phase, if a user takes action illegally, the user trading with him/her can submit dispute information toACand wait for the arbitration ofAC. If illegal action existed,AC can trace the identity of malicious user and punish him/her.The notations used in Chang et al.’s protocol are as follows and the details of their protocol are described in the following except of the dispute phase:AC: a trusted agent center.BZ: a Bidder Z.AZ: an auctioneer Z.IDZ: the identity of Z.SKAC: AC’s private key.PKZ: Z’s public key.PWZ: Z’s password.CERTZ: the certificate of PKZ signed byAC.BBAC: the Bulletin board ofAC.P: the base point of ECC group over a finite field Fp with order p, where p is a large prime.(·)x: an operation using x-coordinate in ECC.(·)y: an operation using y-coordinate in ECC.Ek[·]/Dk[·]:AES-based encryption/decryption with key k.f(·): a secure one-way hash function.


### 3.1. Registration Phase

If a user wants to play the role of an auctioneer or a bidder in the auction, he/she should register an account atAC by the following steps.(1)
User choosesIDu, PWu∈Zp∗ and a random number ru∈Zp∗, and computes his/her public key PKu=PWu·Pmod⁡p. Then, the user calculates R0=ru·Pmod⁡p, R1=IDu+(ru·PKAC)xmod⁡⁡p, and R2=PKu+ru·PKACmod⁡⁡p and sends (R0,R1,R2) toAC.(2)
AC retrieves user’s identity IDu=R1-(SKAC·R0)xmod⁡⁡p and public key PKu=R2-SKAC·R0modp. Subsequently,AC chooses a random number rAC∈Zq∗ calculates R0′=rAC·Pmod⁡p and CERTu=rAC+PKux·SKAC·IDumod⁡⁡p, and sends them to the user. User checks the correctness of equation CERTu·P-R0′?≡(PKu)x·IDu·PKAC(modp) to verify the validation of this certificate. If valid, then user stores it with R0′.


### 3.2. On-Shelf Phase

If a registered user wants to host an auction, then he/she becomes an auctioneerAj and performs the following.(1)
Aj chooses a random number r1∈Zp∗ and a nonce n1∈Zp∗ and calculates O0=r1·Pmodp, O1=(PKAj+r1·PKAC)mod⁡p, Kaa=(PWAj·PKAC·n1)xmod⁡p, and O2=EKaa(R0′∥CERTAj). Aj generates auction information AI=(pidk∥BasicPrice∥Deadline), that is, the identity of a product, basic price of this auction, and the deadline of this auction. Finally, Ajcomputes Sig=(r1+AI·PWAj·n1)mod⁡p and sends (IDAj,n1,O0,O1,O2,AI,Sig) toAC.(2)
AC retrieves Aj’s public key PKAj=O1-SKAC·O0. Then,AC computes the symmetrical key shared with Aj:Kaa=(SKAC·PKAj·n1)xmod⁡p.AC can decryptO2 with Kaa to extract Aj’s certificate.AC should check the correctness of the certificate by verifying if equation CERTAj·P-R0′≡(PKAj)x·IDAj·PKAC(mod⁡p) holds and the integrity of AI by verifying if equation Sig·P-O0≡PKAj′·AI(mod⁡p) holds where PKAj′=n1·PKAjmod⁡p. If both are valid,AC generates a uniquegid for Aj’s product.AC then computes a verifier V=h(gid∥Kaa) and sends (V,gid) to Aj.(3)
AfterAj received message fromAC, he/she computes and checks if V=h(gid∥Kaa). If the equation holds, Aj respondsApprovalmessage toAC. Upon receivingApproval from Aj,AC publishes (gid,IDAj,AI,O0,PKAj′,Sig,N1) on BBAC and anyone can verify this message by checking equation SigP-O0≡PKAj′·AI(modp).


### 3.3. Bidding Phase

If someone is interested in this auction, he/she could play the role of a bidderBi and send bidding message toAC by the following.(1)
Bi chooses a random number r2∈Zq∗ and computes D0=r2·Pmodp, D1=(PKBi+r2·PKACmod⁡⁡p, Kba=PWBi·PKAC·D0yxmod⁡p, and D2=EKba(R0′∥CERTBi∥IDBi). Bi generates bidding message BM=(gid∥price) and signs it as BSigBi=(r2+BM·PWBi)mod⁡p. Bi sends (D0,D1,D2,BM,BSigBi) toAC.(2)
Upon receiving these messages,AC retrieves Bi’s public key PKBi=D1-D0·SKACmod⁡p and computes Kba=(SKAC·PKBi·(D0)y)x. Then,AC decrypts D2 using Kba to extract Bi’s certificate.AC can verify the correctness of CERTBi by checking equation CERTBi·P-R0′?≡(PKBi)x·IDBi·PKAC(modp). If it is valid,AC checks the correctness ofBM by checking equation BSigBi·P-D0?≡PKBi·BM(modp). If it is valid too,AC further checksDeadlineandBasicPrice of the auction by usinggid to search the corresponding information on its website. If the auction has closed or theprice is not larger thanBasicPrice,AC rejects this bid; otherwise,AC generates a unique transaction identitytid forBi and chooses a random number r3∈Zq∗.AC then computes D3=r3·Pmod⁡p, BM′=(tid∥BM), Rec=r3+(BM′·SKAC)xmod⁡p, and D4=EKba(tid∥D3∥Rec). Finally,AC updatesBasicPrice=price, publishes (tid,price,date) on BBAC, stores (tid,price,date,D0,BM,BSigBi,PKBi,D2) in database, and sends D4 to bidder.(3)
AfterBi received the message fromAC, Bi can extract the transaction information (tid∥D3∥Rec) from D4. Then, Bi checks the validation of receipt Rec by verifying Rec·P-D3?≡(tid∥BM)·PKACmod⁡⁡p. If the equation holds, Bi stores Rec and D3.(4)
After deadline,AC sets the winner as the bidder with the highest price.AC then publishes the winner’s information onBBAC including several items (tid,price,date,D0,bid,BSigBi,PKBi,D2) such that anyone can verify its validity by checking BSigBi·P-D0?≡PKBi·BM(mod⁡p).


### 3.4. Product Claiming Phase

After the auction deadline, the winner can claim the product from the auctioneer by showing his/her receipt and performing the following steps. After the auctioneer checked the correctness of receipt, the auctioneer should send the product to the winner.(1)
Bi selects a random number rc and a nonce n2 from Zq∗, computes C0=rc·Pmod⁡⁡p, C1=(Rec+rc·n2·PKAj′)mod⁡p, and C2=(D3+rc·n2·PKAj′)mod⁡p, and sends (gid,C1,C2,C0,n2) to Aj.(2)
Once receivingBi’s claiming request, Aj retrieves Rec=(C1-(C0·n2·n1·PWAj)x)mod⁡p and D3=(C2-C0·n2·n1·PWAj)mod⁡p. Then, Aj verifies Rec·P-D3?≡(tid∥gid∥price)·PKACmod⁡⁡p. If the verification holds, Aj is convinced that Bi is the actual winner and sends the product to Bi.


### 3.5. Security Defect of Chang et al.’s Protocol

According to our analysis, we found that Chang et al.’s protocol meets most of the security requirements of an auction protocol except for unlinkability. In Chang et al.’s protocol, although some important data such as users’ public keys and certificates are encrypted before being transferred, unencrypted messages such as the on-shelf information still can be linked together with different packets. Figures2 and 3 show the linkage between transferred messages and published messages onAC’s website. The solid border represents the message transferred on the Internet, and the dotted border represents the message published onAC’s website.Figure 2
Linkage of messages in on-shelf phase.Figure 3
Linkage of messages in bidding phase.From Figures2 and 3, we can see that these messages can be linked together through certain parameters. For example, in the on-shelf phase (Figure 2), although attackers cannot calculate the public key or certificate of an auctioneer Aj from the encrypted message (solid border) based on the definition of ECDLP and the security assumption of underlying AES algorithms, attackers can still find the relevance of transferred messages (solid message) and published messages (dotted message) to analyze the specific user’s privacy. As shown in Figure 2, we find that IDAj, n1, AI, O0, and Sig are linkable. Obviously, an adversary can link the captured message on the Internet with the published message if they have the same parameters IDAj, n1, AI, O0, andSig. Furthermore, the adversary can decide that if these messages come from the specific IP address. If so, the adversary obtained this IP address owner’s identity IDAj.On the other hand, as mentioned previously, bidders’ privacy is in more serious danger in the bidding phase. At the end of the bidding phase, theAC publishes the information with the winner’s true public key onAC’s website. As shown in Figure 3, similar to Figure 2, attackers have the ability to determine the IP addresses of captured messages on the Internet and to link the specific transferred encrypted bidding information with the published message (the winner’s information). Consequently, attackers would find the relevance of the winner’s public key and the specific IP address. If this user continues to anticipate other auctions, his/her transaction history will be traced. For example, an adversary used Sniffer (a network tool to capture the packets transferred in local network) to capture packets transferred in the local network of his/her office environment and found that some packets are transferred to the auction server (AC). After analyzing the important parts of these packets and comparing them with the messages published onAC’s website, the adversary can know what the specific IP address owner had bidden for or sold out. Obviously, the adversary can easily know who uses the IP address in this office if he/she wishes.According to the aforementioned analyses, we can see that the main problem that results in privacy disclosure is that some published data is transferred in plaintext before such that an adversary can easily link them together. Hence, in our proposal, we establish a shared symmetrical key between each user and theAC to encrypt the message transferred on the Internet to avoid linkability. By using symmetrical encryptions and fewer ECC operations, our proposal can not only improve the security but also reduce the system cost. In the registration phase, we connect a user’s identity and the corresponding symmetrical key so that theAC can compute the shared symmetrical key easily with the user’s identity. Besides, each user’s identity is encrypted with theAC’s public key so it cannot be revealed without the knowledge ofAC’s private key. In our proposal, we fulfill the verifiability of all messages published on theAC’s website; however, Chang et al.’s proposal only partially achieved this feature.


## 3.1. Registration Phase

If a user wants to play the role of an auctioneer or a bidder in the auction, he/she should register an account atAC by the following steps.(1)
User choosesIDu, PWu∈Zp∗ and a random number ru∈Zp∗, and computes his/her public key PKu=PWu·Pmod⁡p. Then, the user calculates R0=ru·Pmod⁡p, R1=IDu+(ru·PKAC)xmod⁡⁡p, and R2=PKu+ru·PKACmod⁡⁡p and sends (R0,R1,R2) toAC.(2)
AC retrieves user’s identity IDu=R1-(SKAC·R0)xmod⁡⁡p and public key PKu=R2-SKAC·R0modp. Subsequently,AC chooses a random number rAC∈Zq∗ calculates R0′=rAC·Pmod⁡p and CERTu=rAC+PKux·SKAC·IDumod⁡⁡p, and sends them to the user. User checks the correctness of equation CERTu·P-R0′?≡(PKu)x·IDu·PKAC(modp) to verify the validation of this certificate. If valid, then user stores it with R0′.


## 3.2. On-Shelf Phase

If a registered user wants to host an auction, then he/she becomes an auctioneerAj and performs the following.(1)
Aj chooses a random number r1∈Zp∗ and a nonce n1∈Zp∗ and calculates O0=r1·Pmodp, O1=(PKAj+r1·PKAC)mod⁡p, Kaa=(PWAj·PKAC·n1)xmod⁡p, and O2=EKaa(R0′∥CERTAj). Aj generates auction information AI=(pidk∥BasicPrice∥Deadline), that is, the identity of a product, basic price of this auction, and the deadline of this auction. Finally, Ajcomputes Sig=(r1+AI·PWAj·n1)mod⁡p and sends (IDAj,n1,O0,O1,O2,AI,Sig) toAC.(2)
AC retrieves Aj’s public key PKAj=O1-SKAC·O0. Then,AC computes the symmetrical key shared with Aj:Kaa=(SKAC·PKAj·n1)xmod⁡p.AC can decryptO2 with Kaa to extract Aj’s certificate.AC should check the correctness of the certificate by verifying if equation CERTAj·P-R0′≡(PKAj)x·IDAj·PKAC(mod⁡p) holds and the integrity of AI by verifying if equation Sig·P-O0≡PKAj′·AI(mod⁡p) holds where PKAj′=n1·PKAjmod⁡p. If both are valid,AC generates a uniquegid for Aj’s product.AC then computes a verifier V=h(gid∥Kaa) and sends (V,gid) to Aj.(3)
AfterAj received message fromAC, he/she computes and checks if V=h(gid∥Kaa). If the equation holds, Aj respondsApprovalmessage toAC. Upon receivingApproval from Aj,AC publishes (gid,IDAj,AI,O0,PKAj′,Sig,N1) on BBAC and anyone can verify this message by checking equation SigP-O0≡PKAj′·AI(modp).


## 3.3. Bidding Phase

If someone is interested in this auction, he/she could play the role of a bidderBi and send bidding message toAC by the following.(1)
Bi chooses a random number r2∈Zq∗ and computes D0=r2·Pmodp, D1=(PKBi+r2·PKACmod⁡⁡p, Kba=PWBi·PKAC·D0yxmod⁡p, and D2=EKba(R0′∥CERTBi∥IDBi). Bi generates bidding message BM=(gid∥price) and signs it as BSigBi=(r2+BM·PWBi)mod⁡p. Bi sends (D0,D1,D2,BM,BSigBi) toAC.(2)
Upon receiving these messages,AC retrieves Bi’s public key PKBi=D1-D0·SKACmod⁡p and computes Kba=(SKAC·PKBi·(D0)y)x. Then,AC decrypts D2 using Kba to extract Bi’s certificate.AC can verify the correctness of CERTBi by checking equation CERTBi·P-R0′?≡(PKBi)x·IDBi·PKAC(modp). If it is valid,AC checks the correctness ofBM by checking equation BSigBi·P-D0?≡PKBi·BM(modp). If it is valid too,AC further checksDeadlineandBasicPrice of the auction by usinggid to search the corresponding information on its website. If the auction has closed or theprice is not larger thanBasicPrice,AC rejects this bid; otherwise,AC generates a unique transaction identitytid forBi and chooses a random number r3∈Zq∗.AC then computes D3=r3·Pmod⁡p, BM′=(tid∥BM), Rec=r3+(BM′·SKAC)xmod⁡p, and D4=EKba(tid∥D3∥Rec). Finally,AC updatesBasicPrice=price, publishes (tid,price,date) on BBAC, stores (tid,price,date,D0,BM,BSigBi,PKBi,D2) in database, and sends D4 to bidder.(3)
AfterBi received the message fromAC, Bi can extract the transaction information (tid∥D3∥Rec) from D4. Then, Bi checks the validation of receipt Rec by verifying Rec·P-D3?≡(tid∥BM)·PKACmod⁡⁡p. If the equation holds, Bi stores Rec and D3.(4)
After deadline,AC sets the winner as the bidder with the highest price.AC then publishes the winner’s information onBBAC including several items (tid,price,date,D0,bid,BSigBi,PKBi,D2) such that anyone can verify its validity by checking BSigBi·P-D0?≡PKBi·BM(mod⁡p).


## 3.4. Product Claiming Phase

After the auction deadline, the winner can claim the product from the auctioneer by showing his/her receipt and performing the following steps. After the auctioneer checked the correctness of receipt, the auctioneer should send the product to the winner.(1)
Bi selects a random number rc and a nonce n2 from Zq∗, computes C0=rc·Pmod⁡⁡p, C1=(Rec+rc·n2·PKAj′)mod⁡p, and C2=(D3+rc·n2·PKAj′)mod⁡p, and sends (gid,C1,C2,C0,n2) to Aj.(2)
Once receivingBi’s claiming request, Aj retrieves Rec=(C1-(C0·n2·n1·PWAj)x)mod⁡p and D3=(C2-C0·n2·n1·PWAj)mod⁡p. Then, Aj verifies Rec·P-D3?≡(tid∥gid∥price)·PKACmod⁡⁡p. If the verification holds, Aj is convinced that Bi is the actual winner and sends the product to Bi.


## 3.5. Security Defect of Chang et al.’s Protocol

According to our analysis, we found that Chang et al.’s protocol meets most of the security requirements of an auction protocol except for unlinkability. In Chang et al.’s protocol, although some important data such as users’ public keys and certificates are encrypted before being transferred, unencrypted messages such as the on-shelf information still can be linked together with different packets. Figures2 and 3 show the linkage between transferred messages and published messages onAC’s website. The solid border represents the message transferred on the Internet, and the dotted border represents the message published onAC’s website.Figure 2
Linkage of messages in on-shelf phase.Figure 3
Linkage of messages in bidding phase.From Figures2 and 3, we can see that these messages can be linked together through certain parameters. For example, in the on-shelf phase (Figure 2), although attackers cannot calculate the public key or certificate of an auctioneer Aj from the encrypted message (solid border) based on the definition of ECDLP and the security assumption of underlying AES algorithms, attackers can still find the relevance of transferred messages (solid message) and published messages (dotted message) to analyze the specific user’s privacy. As shown in Figure 2, we find that IDAj, n1, AI, O0, and Sig are linkable. Obviously, an adversary can link the captured message on the Internet with the published message if they have the same parameters IDAj, n1, AI, O0, andSig. Furthermore, the adversary can decide that if these messages come from the specific IP address. If so, the adversary obtained this IP address owner’s identity IDAj.On the other hand, as mentioned previously, bidders’ privacy is in more serious danger in the bidding phase. At the end of the bidding phase, theAC publishes the information with the winner’s true public key onAC’s website. As shown in Figure 3, similar to Figure 2, attackers have the ability to determine the IP addresses of captured messages on the Internet and to link the specific transferred encrypted bidding information with the published message (the winner’s information). Consequently, attackers would find the relevance of the winner’s public key and the specific IP address. If this user continues to anticipate other auctions, his/her transaction history will be traced. For example, an adversary used Sniffer (a network tool to capture the packets transferred in local network) to capture packets transferred in the local network of his/her office environment and found that some packets are transferred to the auction server (AC). After analyzing the important parts of these packets and comparing them with the messages published onAC’s website, the adversary can know what the specific IP address owner had bidden for or sold out. Obviously, the adversary can easily know who uses the IP address in this office if he/she wishes.According to the aforementioned analyses, we can see that the main problem that results in privacy disclosure is that some published data is transferred in plaintext before such that an adversary can easily link them together. Hence, in our proposal, we establish a shared symmetrical key between each user and theAC to encrypt the message transferred on the Internet to avoid linkability. By using symmetrical encryptions and fewer ECC operations, our proposal can not only improve the security but also reduce the system cost. In the registration phase, we connect a user’s identity and the corresponding symmetrical key so that theAC can compute the shared symmetrical key easily with the user’s identity. Besides, each user’s identity is encrypted with theAC’s public key so it cannot be revealed without the knowledge ofAC’s private key. In our proposal, we fulfill the verifiability of all messages published on theAC’s website; however, Chang et al.’s proposal only partially achieved this feature.


## 4. System and Adversary Model

In this section, we describe the definitions of our network model, adversary model, and requirements as follows before introducing our proposed scheme.


### 4.1. Network Model

We consider a network composed of an agent center (AC) and users. TheAC is a trusted third party that undertakes most tasks of system running, such as user registration, generation of users’ certificates, and product on-shelf. With regard to the application of the trusted third party, it is widespread in e-commerce systems [25–28]. TheAC is also an arbiter of an auction and has the right to determine who the winner is or punish the illegal user’s identity. Hence, we think that theAC has large capability of computation and storage. TheAC should maintain a database on its machine to store users’ data. Herein, we do not consider this database to be completely secure. Hackers may have methods to access it, but such actions will not destroy the security of the whole system. Furthermore, theAC’s private key should be kept in a trusted place such as a bank security box.On the other hand, users use their devices such as computers or mobile devices to communicate with theAC through the Internet. When a user wants to connect with theAC, he/she should type in a password or insert a smart card with a password into the machine. The client in the user’s machine erases the password after the user goes offline.


### 4.2. Adversary Model

In this paper, we assume that an adversary can launch a passive attack to monitor the communication channel of the system. The adversary has knowledge of the format of a packet, so he/she can analyze what content is included in the packet. We also think that the adversary has the ability to access the database stored in theAC and can read theAC’s website as the other users. In addition, some registered users may attack the system jointly.


### 4.3. Security Requirements

In order to provide a secure auction scheme, the following security properties are critical [29].Anonymity. User’s identification should be kept secret as the system is running. No one can obtain the user’s identification from messages transmitted or published.Easy Revocation. A user’s right should be easily and correctly revoked in the auction system by theAC.Fairness. All bidders should have the ability to verify whether their bids have indeed been included in the auction.Nonrepudiation. Users including bidders and auctioneers cannot deny the actions that have been taken before. For example, if an auctioneer puts a product on-shelf, he/she cannot deny that he/she did it and off-shelf this product arbitrarily.Onetime Registration. Any registered user can host or participate in any auction without reregistration at theAC.Traceability. If some illegal actions are taken such as a nonpaying bid (NPB), theAC should have the ability to identify and publish the dishonest user’s true identity anytime.Unforgeability. No one can forge a valid message or impersonate any legal users to do illegal things.Unlinkability. No one can link different messages together to trace a specific user’s transaction history even if he/she does not know the true identification of the user.Verifiability. All winning bids and product information published on a bulletin board should be publicly verifiable without revealing the bidders’ identities.


## 4.1. Network Model

We consider a network composed of an agent center (AC) and users. TheAC is a trusted third party that undertakes most tasks of system running, such as user registration, generation of users’ certificates, and product on-shelf. With regard to the application of the trusted third party, it is widespread in e-commerce systems [25–28]. TheAC is also an arbiter of an auction and has the right to determine who the winner is or punish the illegal user’s identity. Hence, we think that theAC has large capability of computation and storage. TheAC should maintain a database on its machine to store users’ data. Herein, we do not consider this database to be completely secure. Hackers may have methods to access it, but such actions will not destroy the security of the whole system. Furthermore, theAC’s private key should be kept in a trusted place such as a bank security box.On the other hand, users use their devices such as computers or mobile devices to communicate with theAC through the Internet. When a user wants to connect with theAC, he/she should type in a password or insert a smart card with a password into the machine. The client in the user’s machine erases the password after the user goes offline.


## 4.2. Adversary Model

In this paper, we assume that an adversary can launch a passive attack to monitor the communication channel of the system. The adversary has knowledge of the format of a packet, so he/she can analyze what content is included in the packet. We also think that the adversary has the ability to access the database stored in theAC and can read theAC’s website as the other users. In addition, some registered users may attack the system jointly.


## 4.3. Security Requirements

In order to provide a secure auction scheme, the following security properties are critical [29].Anonymity. User’s identification should be kept secret as the system is running. No one can obtain the user’s identification from messages transmitted or published.Easy Revocation. A user’s right should be easily and correctly revoked in the auction system by theAC.Fairness. All bidders should have the ability to verify whether their bids have indeed been included in the auction.Nonrepudiation. Users including bidders and auctioneers cannot deny the actions that have been taken before. For example, if an auctioneer puts a product on-shelf, he/she cannot deny that he/she did it and off-shelf this product arbitrarily.Onetime Registration. Any registered user can host or participate in any auction without reregistration at theAC.Traceability. If some illegal actions are taken such as a nonpaying bid (NPB), theAC should have the ability to identify and publish the dishonest user’s true identity anytime.Unforgeability. No one can forge a valid message or impersonate any legal users to do illegal things.Unlinkability. No one can link different messages together to trace a specific user’s transaction history even if he/she does not know the true identification of the user.Verifiability. All winning bids and product information published on a bulletin board should be publicly verifiable without revealing the bidders’ identities.


## 5. Proposed Scheme

In this section, we propose a secure English auction system with privacy preservation. Our proposal consists of six phases: the system setup phase, registration phase, on-shelf phase, bidding phase, product claiming phase, and dispute phase. There are two kinds of participants in this system: theAC and the users. In the system setup phase, theAC inputs a security parameter and generates a set of system parameters. TheAC then requests a certificate from an acknowledged certificate authority and publishes these data on its website. Anyone can get these data from theAC’s website. If a new user wants to register an account, he/she can connect with theAC during the registration phase. After registration, the user can either host or participate in an auction. If he/she wants to host an auction, he/she can on-shelf his/her products in the on-shelf phase; if he/she wants to bid for some on-shelved products, he/she can send the bidding information to theAC during the bidding phase. TheAC should publish every bidder’s bidding information except for the bidder’s identity on its website such that anyone can read it. If a bidder wins the auction, he/she will receive a receipt and a session key shared with the auctioneer from theAC. Then, the winning bidder can obtain his/her product from the auctioneer during the product claiming phase. In our proposal, theAC has the capability of tracing the whole transaction and identifying the participants in an auction if necessary. If a dispute has occurred, anyone participating in an auction can submit the dispute request to theAC in the dispute phase. The notations used in our proposal are as follows and the details of our proposal are described in the following subsections:Bi: a bidder i.Aj: an auctioneer j.AC:a trusted agent center.κ: the system security parameter chosen byAC.Fq: finite filed of order q.E/Fq: an elliptic curve based on q order finite field.Gq: a cyclic group of the elliptic curve.P: the base point of ECC group.(·)x: an operation using x-coordinate in ECC.SKAC:AC’s private key.PKAC:AC’s public key.CertAC: the certificate of PKAC signed by the certificate authority.idU: the identity of a user U.pwU: U’s password.Nn: a nonce.PU: U’s partial key used for computing symmetrical key shared withAC.KAU: the symmetrical key ofAC and a user.KAB: the symmetrical key ofAC and a bidder.KAA: the symmetrical key ofAC and an auctioneer.EK(·): an AES-based encryption with key K.DK(·): an AES-based decryption with key K.H(·): a secure one-way hash function.BBAC: the bulletin board ofAC.


### 5.1. System Setup Phase

Before the system is running, theAC chooses SKAC∈RZq∗ as the private key. TheAC then inputs a security parameter κ∈Zq∗ and generates a set of system parameters Ω={Fq,E/Fq,Gq,P,PKAC,CertAC,H(·)} through the steps below:(1)
Choose aκ-bit prime q.(2)
Determine the tuple{Fq,E/Fq,Gq,P}; Fq is a finite filed modular q, E/Fq is an elliptic curve defined over Fq, Gq is a cyclic group defined over Fq, and P is the generator of Gq.(3)
Compute theAC’s public key PKAC=SKAC·Pmod⁡q.(4)
Choose a cryptographic hash functionH(·).(5)
Request a certificateCertAC of PKAC from the certificate authority.Then, theAC publishes Ω on its online BBAC and keeps SKAC secret.


### 5.2. Registration Phase

If a user wants to host or participate in an auction, he/she must perform the following steps to register an account at theAC.(1)
The user obtains system parameters onBBAC and checks the validation of theAC’s public key by CertAC. If PKAC is invalid, he/she terminates the subsequent operations; otherwise, he/she chooses his/her password pwU∈Zq∗ and identity idU∈Zq∗ and generates a random number r0 and a nonce N1. Afterwards, he/she computes R0=r0·Pmod⁡⁡q, PU=pwU·Pmod⁡⁡q, C=(r0·PKAC+PU)mod⁡q, and C0=(r0·PKACx+M)mod⁡q and sends (C,C0,R0) to AC, where M=(idU,N1).(2)
Upon the receipt of the message sent from the user, theAC can extract PU and M by computing PU=C-SKAC·R0mod⁡q and =(idU,N1)=C0-SKAC·R0xmod⁡q. TheAC then checks the freshness of N1. If N1 is valid, the AC chooses a nonce N2 and computes RESPONSE=((success,N2)+SKAC·PUx)mod⁡q. TheAC then sendsRESPONSE to the user and stores (idU,vU) in its database, where vU=PU⊕H(SKAC).(3)
After receivingRESPONSE, the user retrieves (success,N2)=(RESPONSE-PKAC·pwUx)mod⁡q and checks ifsuccess is contained in it. If so, the user checks the freshness of N2. If both are valid, the user ascertains that he/she has registered successfully and then can either host or participate in an auction.Note that each registered user has a partial keyPU and can share a key KAU≡pwU·PKACx≡SKAC·PUx(mod⁡q) with theAC. For convenience, in the following, we use KAA to imply the key shared between theAC and a user who plays as an auctioneer Aj, and Aj’s partial key is PAj. In contrast, the keys of a user who plays as a bidder Bi are KAB and PBi.


### 5.3. On-Shelf Phase

If a registered user wants to host an auction to sell some products, he/she becomes an auctioneerAj and performs the following steps.(1)
Aj generates on-shelf information γ=(IDproduct∥Basic_price∥Deadline) firstly, where IDproduct refers to the identity of a product, Basic_price indicates the basic price of this auction (every bidder’s bidding price should not be less than this value), andDeadline represents the deadline of this auction. Then, Aj computes KAA=(pwAj·PKAC)xmod⁡q. After that, Aj randomly chooses a nonce N3 and calculates e1=EKAA(γ,N3,idAj), h1=H(e1,KAA), C1=(h1·PKAC)x+idAjmod⁡q, and R1=h1·Pmod⁡q. Then, Aj sends (C1,R1,e1) to the AC.(2)
TheAC retrieves idAj from C1 by computing idAj=C1-(R1·SKAC)xmod⁡q. Then, the AC searches its database to extract the corresponding PAj (PAj=H(SKAC)⊕vAj) of idAj and calculates KAA=(SKAC·PAj)xmod⁡q. TheAC extracts (γ,N3,idAj) by decrypting operation DKAA(e1). TheAC checks whether the identity idAj in e1 is equal to that retrieved from C1. If they are not equal, theAC may confront a replay attack, and theAC should terminate sequent operations immediately; otherwise, theAC checks the freshness of N3. If both are valid, theAC generates a unique on-shelf identity IDon-shelf for Aj and sends EKAA(IDon-shelf,idAj,N4) to Aj, where N4 is a nonce.(3)
After receiving the message from theAC, Aj retrieves (IDon-shelf,idAj,N4) by decryption with key KAA. Aj checks the integrity of the message by checking if a correct idAj is in it and checks the freshness of this message by checking N4. If both are valid, the auctioneer then sendsAPPROVAL toAC.(4)
Upon receivingAPPROVAL from Aj, theAC chooses a random number r1∈RZq∗ and computes R2=r1·Pmod⁡q and S1=r1-1·(M1-SKAC·R2x)mod⁡q, where M1=(γ,IDon-shelf,idAj). Waiting τ minutes (τ∈R(0,t)), theAC publishes (M1,R2,S1) on BBAC. Once theAC publishes the on-shelf information, the auction has been held, and anyone can verify the validation of the auction information by checking the correctness of equation S1·R2+(R2)x·PKAC?≡M1·Pmod⁡q.


### 5.4. Bidding Phase

If a bidderBi wants to bid for an on-shelved product, he/she should send the bidding information to theAC, including the corresponding identity IDon-shelf of the product and a bidding price price. We denote (IDon-shelf∥price) as η here.(1)
Bi computes KAB=pwBi·PKACmod⁡q firstly. Then, Bi computes e2=EKAB(η,N5,idBi),h2=H(e2,KAB), C2=((h2·PKAC)x+idBi)mod⁡q, and R3=h2·Pmodq, where N5 is a nonce. Then, Bi sends (C2,R3,e2) to theAC.(2)
After receiving the bid sent fromBi, theAC can retrieve idBi from C2 by computing idBi=C2-(R3·SKAC)xmod⁡q. Then, theAC searches the idBi in the database. If the idBi does not exist, theAC terminates the sequent operation; otherwise, theAC retrieves the corresponding PBi by computing PBi=H(SKAC)⊕vBi and computes the symmetrical key shared with Bi as KAB=SKAC·PBimod⁡q. TheAC decrypts e2 with KAB to extract (η,N5,idBi). TheAC can check the integrity of this bid by seeing if idBi is equal to the one retrieved from C2. If they are not equal, theAC may confront a replay attack, and theAC should terminate the sequent operations; otherwise, theAC checks the freshness of N5. If both are valid, theACuses IDon-shelf in η to search the corresponding auction information in BBAC.(3)
After finding the corresponding auction, theAC compares price in η with Basic_price of the auction. If price is not larger than Basic_price, theAC ignores this bid and returns to the waiting state; otherwise, theAC updates Basic_price=price and generates a unique identity IDtrans for this transaction. Then, theAC generates a nonce N6 and computes kdis=H(SKAC∥N6) and dis=Ekdis(C2,R3). Let (IDtrans,date,price,dis,N6) be M2; theAC then generates r2∈RZq∗ and computes R4=r2·Pmod⁡q and S2=r2-1·(M2-SKAC·(R4)x)mod⁡q. Waiting τ minutes, τ∈R(0,t), theAC publishes (M2,R4,S2) on BBAC such that anyone can verify it by checking if equation S2·R4+R4x·PKAC≡M2·Pmod⁡q holds.(4)
TheAC then finds out the corresponding PAj of the auctioneer’s idAj of this auction in the database. TheAC computes the symmetrical key shared with Aj:KAA=SKAC·PAjmod⁡q. Then, theAC generates a session key shared between Bi and Aj as Ksession=H(IDtrans,price,date,KAAx). TheAC generates a receipt for Bi as RECEIPT=KAAx+H(SKAC∥N6)·M2 and sends EKAB(RECEIPT,Ksession,idBi,N7,IDtrans) to Bi, where N7 is a nonce.(5)
Upon receiving the message from theAC, Bi decrypts it with KAB and checks the idBi and N7 in it. If idBi is correct and the nonce is fresh, Bi stores (RECEIPT,Ksession,IDtrans).(6)
After theDeadLine arrives, theAC closes the auction and determines the bidder with the highest price as the winner. TheAC determines from the corresponding winning bid information on BBAC whoseprice of the bid is equal toBasic_price. Let M3=(IDtrans,price,date,H(SKAC∥N6)·P,dis,N6); theAC chooses r3∈RZq∗ and computes R5=r3·Pmod⁡q and S3=r3-1·(M3-SKAC·(R5)x)mod⁡q. Then, theAC publishes the winning information (M3,R5,S3) on BBAC. Anyone can verify the winner’s information by checking S3·R5+(R5)x·PKAC?≡M3·P(mod⁡q).


### 5.5. Product Claiming Phase

After theACpublishes the auction result, every bidder can check whether he/she is a winner by checking whether his/her transaction identity IDtrans is equal to the winner’s IDtrans. If a bidder Bi wins the auction, then he/she can claim the product from the auctioneer Aj using the following.B
i computes EKsession(RECEIPT·Pmod⁡q,N8) and sends it to Aj, where N8 is a nonce. Upon receiving the claiming request, Aj computes KAA=pwAj·PKAC firstly. Then, he/she browses the BBAC and computes the session key Ksession=H(IDtrans,price,date,KAAx) shared with the winner and extracts (RECEIPT·Pmod⁡q,N8) by decrypting the ciphertext sent from Bi using Ksession. Then, Aj checks the freshness of N8. If N8 is fresh, Aj verifies the validity ofRECEIPT by checking RECEIPT·P-(KAA)x·P?≡M2·H(SKAC∥N6)·Pmod⁡q. Note that M2 and H(SKAC∥N6)·P can be found in the winner’s information on BBAC. If the equation holds, Aj is convinced that Bi is the winner and sends the product to him/her.


### 5.6. Dispute Phase

In our proposal, theAC has the capability of tracing the whole transaction and identifying the participants in an auction if necessary. If a dispute has occurred, anyone who participates in an auction can submit a dispute request to theAC in this phase. In the following, we consider two situations to explain the dispute phase.Situation 1 (auctioneer appeals toAC).
If a nonpaying auction happened, which means that the winnerBi did not contact the auctioneer Aj after he/she won the auction, Aj can appeal to theAC and theAC will trace the transaction to deal with this dispute.
A
j browses BBAC and finds the winner’s IDtrans firstly. Then, Aj selects a nonce N9 and computes KAA=pwAj·PKAC, e3=EKAA(IDtrans,idAj,N9), h3=H(e3,KAA), C3=(h3·PKAC)x+idAjmod⁡q, and R6=h3·Pmod⁡q. Subsequently, Aj sends (C3,R6,e3) toAC. Once receiving the dispute request from Aj, theAC retrieves idAj=C3-(R6·SKAC)xmod⁡q and checks the validation of idAj in the database. If it is valid, then theAC computes KAA=(H(SKAC)⊕vAj)·SKACmod⁡q and decrypts e3 to extract IDtrans, idAj, and N9. TheAC checks the freshness of N9. If the nonce is fresh, theAC checks if idAj in C3 equals idAj in e3. If they are not equal, theAC terminates operation immediately; otherwise, theAC searches the IDtrans on BBAC and traces the transaction history to determine whether the problem really exists. If theAC ascertains that the problem claimed by Aj is true, theAC then finds out the correspondingdisand N6 among the winner’s information from BBAC. Afterwards, theAC computes kdis=H(SKAC∥N6) and extracts (C2,R3) fromdis. Finally, theAC can retrieve the dishonest winner’s identity as idBi=C2-(R3·SKAC)xmodq and publish it.Situation 2 (bidder appeals toAC).
If the auctioneerAj of an auction refuses to send the product to the winner Bi, Bi also can appeal to theAC.
Firstly,Bi computes KAB=pwBi·PKACmod⁡q, e4=EKAB(RECEIPT∥IDtrans∥N10∥idBi), h4=H(e4,KAB), C4=(h4·PKAC)x+idBimod⁡q, and R7=h4·Pmod⁡q, where N10 is a nonce. Bi then sends (C4,R7,e4) to the AC. Upon receiving the dispute request from Bi, the AC retrieves idBi=C4-(R7·SKAC)xmod⁡q and checks if idBi exists in the database. If it exists, the AC then computes KAB=(H(SKAC)⊕vBi)·SKACmod⁡q and decrypts e4 to extract RECEIPT, IDtrans, N10, and idBi. The AC checks the freshness of N10. If the nonce is fresh, the AC checks if idBi in C4 equals idBiin e4. If they are not equal, the AC terminates the operation immediately; otherwise, the AC then finds the corresponding N6 and idAj of IDtrans on BBAC and the corresponding vAj of idAj in the database. Then, the AC calculates PAj=H(SKAC)⊕vAj and KAA=PAj·SKACmod⁡q. The AC checks the validation of RECEIPT by verifying RECEIPT?=KAAx+H(SKAC∥N6)·M2. Note that M2 and N6 can be found in the winner’s information on BBAC. If RECEIPT is valid, the AC traces the transaction history to determine whether the problem really exists. If the AC ascertains that the problem claimed by Bi is true, the AC publishes the identity of the dishonest auctioneer Aj.


## 5.1. System Setup Phase

Before the system is running, theAC chooses SKAC∈RZq∗ as the private key. TheAC then inputs a security parameter κ∈Zq∗ and generates a set of system parameters Ω={Fq,E/Fq,Gq,P,PKAC,CertAC,H(·)} through the steps below:(1)
Choose aκ-bit prime q.(2)
Determine the tuple{Fq,E/Fq,Gq,P}; Fq is a finite filed modular q, E/Fq is an elliptic curve defined over Fq, Gq is a cyclic group defined over Fq, and P is the generator of Gq.(3)
Compute theAC’s public key PKAC=SKAC·Pmod⁡q.(4)
Choose a cryptographic hash functionH(·).(5)
Request a certificateCertAC of PKAC from the certificate authority.Then, theAC publishes Ω on its online BBAC and keeps SKAC secret.


## 5.2. Registration Phase

If a user wants to host or participate in an auction, he/she must perform the following steps to register an account at theAC.(1)
The user obtains system parameters onBBAC and checks the validation of theAC’s public key by CertAC. If PKAC is invalid, he/she terminates the subsequent operations; otherwise, he/she chooses his/her password pwU∈Zq∗ and identity idU∈Zq∗ and generates a random number r0 and a nonce N1. Afterwards, he/she computes R0=r0·Pmod⁡⁡q, PU=pwU·Pmod⁡⁡q, C=(r0·PKAC+PU)mod⁡q, and C0=(r0·PKACx+M)mod⁡q and sends (C,C0,R0) to AC, where M=(idU,N1).(2)
Upon the receipt of the message sent from the user, theAC can extract PU and M by computing PU=C-SKAC·R0mod⁡q and =(idU,N1)=C0-SKAC·R0xmod⁡q. TheAC then checks the freshness of N1. If N1 is valid, the AC chooses a nonce N2 and computes RESPONSE=((success,N2)+SKAC·PUx)mod⁡q. TheAC then sendsRESPONSE to the user and stores (idU,vU) in its database, where vU=PU⊕H(SKAC).(3)
After receivingRESPONSE, the user retrieves (success,N2)=(RESPONSE-PKAC·pwUx)mod⁡q and checks ifsuccess is contained in it. If so, the user checks the freshness of N2. If both are valid, the user ascertains that he/she has registered successfully and then can either host or participate in an auction.Note that each registered user has a partial keyPU and can share a key KAU≡pwU·PKACx≡SKAC·PUx(mod⁡q) with theAC. For convenience, in the following, we use KAA to imply the key shared between theAC and a user who plays as an auctioneer Aj, and Aj’s partial key is PAj. In contrast, the keys of a user who plays as a bidder Bi are KAB and PBi.


## 5.3. On-Shelf Phase

If a registered user wants to host an auction to sell some products, he/she becomes an auctioneerAj and performs the following steps.(1)
Aj generates on-shelf information γ=(IDproduct∥Basic_price∥Deadline) firstly, where IDproduct refers to the identity of a product, Basic_price indicates the basic price of this auction (every bidder’s bidding price should not be less than this value), andDeadline represents the deadline of this auction. Then, Aj computes KAA=(pwAj·PKAC)xmod⁡q. After that, Aj randomly chooses a nonce N3 and calculates e1=EKAA(γ,N3,idAj), h1=H(e1,KAA), C1=(h1·PKAC)x+idAjmod⁡q, and R1=h1·Pmod⁡q. Then, Aj sends (C1,R1,e1) to the AC.(2)
TheAC retrieves idAj from C1 by computing idAj=C1-(R1·SKAC)xmod⁡q. Then, the AC searches its database to extract the corresponding PAj (PAj=H(SKAC)⊕vAj) of idAj and calculates KAA=(SKAC·PAj)xmod⁡q. TheAC extracts (γ,N3,idAj) by decrypting operation DKAA(e1). TheAC checks whether the identity idAj in e1 is equal to that retrieved from C1. If they are not equal, theAC may confront a replay attack, and theAC should terminate sequent operations immediately; otherwise, theAC checks the freshness of N3. If both are valid, theAC generates a unique on-shelf identity IDon-shelf for Aj and sends EKAA(IDon-shelf,idAj,N4) to Aj, where N4 is a nonce.(3)
After receiving the message from theAC, Aj retrieves (IDon-shelf,idAj,N4) by decryption with key KAA. Aj checks the integrity of the message by checking if a correct idAj is in it and checks the freshness of this message by checking N4. If both are valid, the auctioneer then sendsAPPROVAL toAC.(4)
Upon receivingAPPROVAL from Aj, theAC chooses a random number r1∈RZq∗ and computes R2=r1·Pmod⁡q and S1=r1-1·(M1-SKAC·R2x)mod⁡q, where M1=(γ,IDon-shelf,idAj). Waiting τ minutes (τ∈R(0,t)), theAC publishes (M1,R2,S1) on BBAC. Once theAC publishes the on-shelf information, the auction has been held, and anyone can verify the validation of the auction information by checking the correctness of equation S1·R2+(R2)x·PKAC?≡M1·Pmod⁡q.


## 5.4. Bidding Phase

If a bidderBi wants to bid for an on-shelved product, he/she should send the bidding information to theAC, including the corresponding identity IDon-shelf of the product and a bidding price price. We denote (IDon-shelf∥price) as η here.(1)
Bi computes KAB=pwBi·PKACmod⁡q firstly. Then, Bi computes e2=EKAB(η,N5,idBi),h2=H(e2,KAB), C2=((h2·PKAC)x+idBi)mod⁡q, and R3=h2·Pmodq, where N5 is a nonce. Then, Bi sends (C2,R3,e2) to theAC.(2)
After receiving the bid sent fromBi, theAC can retrieve idBi from C2 by computing idBi=C2-(R3·SKAC)xmod⁡q. Then, theAC searches the idBi in the database. If the idBi does not exist, theAC terminates the sequent operation; otherwise, theAC retrieves the corresponding PBi by computing PBi=H(SKAC)⊕vBi and computes the symmetrical key shared with Bi as KAB=SKAC·PBimod⁡q. TheAC decrypts e2 with KAB to extract (η,N5,idBi). TheAC can check the integrity of this bid by seeing if idBi is equal to the one retrieved from C2. If they are not equal, theAC may confront a replay attack, and theAC should terminate the sequent operations; otherwise, theAC checks the freshness of N5. If both are valid, theACuses IDon-shelf in η to search the corresponding auction information in BBAC.(3)
After finding the corresponding auction, theAC compares price in η with Basic_price of the auction. If price is not larger than Basic_price, theAC ignores this bid and returns to the waiting state; otherwise, theAC updates Basic_price=price and generates a unique identity IDtrans for this transaction. Then, theAC generates a nonce N6 and computes kdis=H(SKAC∥N6) and dis=Ekdis(C2,R3). Let (IDtrans,date,price,dis,N6) be M2; theAC then generates r2∈RZq∗ and computes R4=r2·Pmod⁡q and S2=r2-1·(M2-SKAC·(R4)x)mod⁡q. Waiting τ minutes, τ∈R(0,t), theAC publishes (M2,R4,S2) on BBAC such that anyone can verify it by checking if equation S2·R4+R4x·PKAC≡M2·Pmod⁡q holds.(4)
TheAC then finds out the corresponding PAj of the auctioneer’s idAj of this auction in the database. TheAC computes the symmetrical key shared with Aj:KAA=SKAC·PAjmod⁡q. Then, theAC generates a session key shared between Bi and Aj as Ksession=H(IDtrans,price,date,KAAx). TheAC generates a receipt for Bi as RECEIPT=KAAx+H(SKAC∥N6)·M2 and sends EKAB(RECEIPT,Ksession,idBi,N7,IDtrans) to Bi, where N7 is a nonce.(5)
Upon receiving the message from theAC, Bi decrypts it with KAB and checks the idBi and N7 in it. If idBi is correct and the nonce is fresh, Bi stores (RECEIPT,Ksession,IDtrans).(6)
After theDeadLine arrives, theAC closes the auction and determines the bidder with the highest price as the winner. TheAC determines from the corresponding winning bid information on BBAC whoseprice of the bid is equal toBasic_price. Let M3=(IDtrans,price,date,H(SKAC∥N6)·P,dis,N6); theAC chooses r3∈RZq∗ and computes R5=r3·Pmod⁡q and S3=r3-1·(M3-SKAC·(R5)x)mod⁡q. Then, theAC publishes the winning information (M3,R5,S3) on BBAC. Anyone can verify the winner’s information by checking S3·R5+(R5)x·PKAC?≡M3·P(mod⁡q).


## 5.5. Product Claiming Phase

After theACpublishes the auction result, every bidder can check whether he/she is a winner by checking whether his/her transaction identity IDtrans is equal to the winner’s IDtrans. If a bidder Bi wins the auction, then he/she can claim the product from the auctioneer Aj using the following.B
i computes EKsession(RECEIPT·Pmod⁡q,N8) and sends it to Aj, where N8 is a nonce. Upon receiving the claiming request, Aj computes KAA=pwAj·PKAC firstly. Then, he/she browses the BBAC and computes the session key Ksession=H(IDtrans,price,date,KAAx) shared with the winner and extracts (RECEIPT·Pmod⁡q,N8) by decrypting the ciphertext sent from Bi using Ksession. Then, Aj checks the freshness of N8. If N8 is fresh, Aj verifies the validity ofRECEIPT by checking RECEIPT·P-(KAA)x·P?≡M2·H(SKAC∥N6)·Pmod⁡q. Note that M2 and H(SKAC∥N6)·P can be found in the winner’s information on BBAC. If the equation holds, Aj is convinced that Bi is the winner and sends the product to him/her.


## 5.6. Dispute Phase

In our proposal, theAC has the capability of tracing the whole transaction and identifying the participants in an auction if necessary. If a dispute has occurred, anyone who participates in an auction can submit a dispute request to theAC in this phase. In the following, we consider two situations to explain the dispute phase.Situation 1 (auctioneer appeals toAC).
If a nonpaying auction happened, which means that the winnerBi did not contact the auctioneer Aj after he/she won the auction, Aj can appeal to theAC and theAC will trace the transaction to deal with this dispute.
A
j browses BBAC and finds the winner’s IDtrans firstly. Then, Aj selects a nonce N9 and computes KAA=pwAj·PKAC, e3=EKAA(IDtrans,idAj,N9), h3=H(e3,KAA), C3=(h3·PKAC)x+idAjmod⁡q, and R6=h3·Pmod⁡q. Subsequently, Aj sends (C3,R6,e3) toAC. Once receiving the dispute request from Aj, theAC retrieves idAj=C3-(R6·SKAC)xmod⁡q and checks the validation of idAj in the database. If it is valid, then theAC computes KAA=(H(SKAC)⊕vAj)·SKACmod⁡q and decrypts e3 to extract IDtrans, idAj, and N9. TheAC checks the freshness of N9. If the nonce is fresh, theAC checks if idAj in C3 equals idAj in e3. If they are not equal, theAC terminates operation immediately; otherwise, theAC searches the IDtrans on BBAC and traces the transaction history to determine whether the problem really exists. If theAC ascertains that the problem claimed by Aj is true, theAC then finds out the correspondingdisand N6 among the winner’s information from BBAC. Afterwards, theAC computes kdis=H(SKAC∥N6) and extracts (C2,R3) fromdis. Finally, theAC can retrieve the dishonest winner’s identity as idBi=C2-(R3·SKAC)xmodq and publish it.Situation 2 (bidder appeals toAC).
If the auctioneerAj of an auction refuses to send the product to the winner Bi, Bi also can appeal to theAC.
Firstly,Bi computes KAB=pwBi·PKACmod⁡q, e4=EKAB(RECEIPT∥IDtrans∥N10∥idBi), h4=H(e4,KAB), C4=(h4·PKAC)x+idBimod⁡q, and R7=h4·Pmod⁡q, where N10 is a nonce. Bi then sends (C4,R7,e4) to the AC. Upon receiving the dispute request from Bi, the AC retrieves idBi=C4-(R7·SKAC)xmod⁡q and checks if idBi exists in the database. If it exists, the AC then computes KAB=(H(SKAC)⊕vBi)·SKACmod⁡q and decrypts e4 to extract RECEIPT, IDtrans, N10, and idBi. The AC checks the freshness of N10. If the nonce is fresh, the AC checks if idBi in C4 equals idBiin e4. If they are not equal, the AC terminates the operation immediately; otherwise, the AC then finds the corresponding N6 and idAj of IDtrans on BBAC and the corresponding vAj of idAj in the database. Then, the AC calculates PAj=H(SKAC)⊕vAj and KAA=PAj·SKACmod⁡q. The AC checks the validation of RECEIPT by verifying RECEIPT?=KAAx+H(SKAC∥N6)·M2. Note that M2 and N6 can be found in the winner’s information on BBAC. If RECEIPT is valid, the AC traces the transaction history to determine whether the problem really exists. If the AC ascertains that the problem claimed by Bi is true, the AC publishes the identity of the dishonest auctioneer Aj.


## 6. BAN Logic Analysis

In this part, we will use BAN logic to analyze the authentication accuracy. Burrows-Abadi-Needham logic (also known as the BAN logic) is a set of rules for defining and analyzing information exchange protocols. Specifically, BAN logic helps its users to determine whether exchanged information is trustworthy, secured against eavesdropping, or both [30]. The notations of BAN logic are as follows:P∣≡X: P believes X.P⊲X: P sees X.P∣~X: P once said X.|→PKP: P has PKas a public key.#(X): the formula X is fresh.P∣⇒X: Phas jurisdiction over X.P↔KQ: P and Q have a shared key K for communication.{X}K: the formula X encrypted under key K.We mainly focus on the proof of on-shelf phase and bidding phase.


### 6.1. On-Shelf Phase

We idealized the on-shelf phase as below:(I1)
Aj→AC:{idAj}PKAC,{γ,N3,idAj}KAA.(I2)
AC→Aj:{IDon-shelf,N4,idAj}KAA.In this phase, we want to ensure thatAC believes in the on-shelf information γ and Aj believes in the IDon-shelf transferred fromAC, so we can conclude the two goals below:(G1)
AC∣≡γ.(G2)
Aj∣≡IDon-shelf.We need to assume thatAC believes the nonce N3 is fresh and Aj believes the nonce N4 is fresh;AC believes that Aj does not send fake γ and idAj, so if Aj believes γ and idAjare true thenAC will believe them too;KAA is computed byAC self, so Aj believes that KAA is shared between him/her andAC; and Aj believes thatAC does not send fake IDon-shelf, so ifAC believes IDon-shelf is true then Aj will believe them too. All 6 assumptions are listed as below:(A1)
AC∣≡#(N3).(A2)
AC∣≡Aj∣⇒γ.(A3)
AC∣≡Aj∣⇒idAj.(A4)
Aj∣≡(AC↔KAAAj).(A5)
Aj∣≡#(N4).(A6)
Aj∣≡AC⇒IDon-shelf.Proof.
For goal (G1), our deduction is shown as the following formulas:(F1)
AC⊲{idAj}PKAC.(F2)
AC⊲idAj (message decryption rule).(F3)
AC∣≡idAj(our hypothesis, we will prove that it is true later).(F4)
AC∣≡(AC↔KAA=SKAC·PAjAj) ((F3), the computing property of believing in operator).(F5)
AC⊲{γ,N3,idAj}KAA.(F6)
AC∣≡Aj∣~{γ,N3,idAj} ((F4), (F5), message meaning rule).(F7)
AC∣≡#({γ,N3,idAj}) ((A1), freshness propagation rule).(F8)
AC∣≡Aj∣≡{γ,N3,idAj} ((F6), (F7), nonce verification rule).(F9)
AC∣≡Aj∣≡idAj ((F8), believing rule).(F10)
AC∣≡idAj ((F9), (A3), jurisdiction rule, our hypothesis in (F3) is proved).(F11)
AC∣≡Aj∣≡γ ((F8), believing rule).(F12)
AC∣≡γ ((F11), (A3), jurisdiction rule).
According to formula (F12), the proof of (G1) is completed.
For goal (G2), our deduction is shown as following formulas:(F13)
Aj⊲{IDon-shelf,N4,idAj}KAA.(F14)
Aj∣≡AC∣~{IDon-shelf,N4,idAj} ((F13), (A4), message meaning rule).(F15)
Aj∣≡#({IDon-shelf,N4,idAj}) ((A5), freshness propagation rule).(F16)
Aj∣≡AC∣≡{IDon-shelf,N4,idAj} ((F14), (F15), nonce verification rule).(F17)
Aj∣≡AC∣≡IDon-shelf ((F16), believing rule).(F18)
Aj∣≡IDon-shelf ((F16), (A6), jurisdiction rule).
According to formula (F18), the proof of (G2) is completed.


### 6.2. Bidding Phase

Our bidding phase can be idealized as below:(I3)
Bi→AC:{idBi}PKAC,{η,N5,idBi}KBA.(I4)
AC→Bi:{RECEIPT,Ksession,N7,idBi}KAB.In bidding phase, we want to ensure thatAC can be convinced that bidding information η transferred from Bi is true; additionally, Bi should be convinced thatRECEIPT and Ksession transferred fromAC are true. So the three goals below can be concluded:(G3)
AC∣≡η.(G4)
Bi∣≡RECEIPT.(G5)
Bi∣≡Ksession.We need to assume thatAC believes N5 is fresh and Bi believes N7 is fresh; if Bi believes η and idBi are true,AC believes in them too because they are generated by Bi; similarly, ifAC believes inRECEIPTand Ksession then Bi believes in them too; because KAB is generated by Bi, Bi believes that he/she shared KAB withAC. All assumptions are listed as below:(A7)
AC∣≡#(N5).(A8)
AC∣≡Bi∣⇒η.(A9)
AC∣≡Bi∣⇒idBi.(A10)
Bi∣≡(AC↔KABBi).(A11)
Bi∣≡#(N7).(A12)
Bi∣≡AC⇒RECEIPT.(A13)
Bi∣≡AC⇒Ksession.Proof.
For goal (G3), our deduction is shown as the following formulas:(F19)
AC⊲{idBi}PKAC.(F20)
AC⊲idBi (message decryption rule).(F21)
AC∣≡idBi (our hypothesis, we will prove that it is true later).(F22)
AC∣≡(AC↔KAB=SKAC·PBiBi) ((F21), operator believes in property).(F23)
AC⊲{η,N5,idBi}KBA.(F24)
AC∣≡Bi∣~{η,N5,idBi} ((F22), (F23), message meaning rule).(F25)
AC∣≡#({η,N5,idBi}) ((A7), freshness propagation rule).(F26)
AC∣≡Bi∣≡{η,N5,idBi} ((F24), (F25), nonce verification rule).(F27)
AC∣≡Bi∣≡idBi ((F26), believing rule).(F28)
AC∣≡idBi ((F27), (A9), jurisdiction rule, our hypothesis in (F21) is proved).(F29)
AC∣≡Bi∣≡η ((F26), believing rule).(F30)
AC∣≡η ((F29), (A8), jurisdiction rule).
According to formula (F30), the proof of (G3) is completed.
For goal (G4), our deduction is shown as the following formulas.(F31)
Bi⊲{RECEIPT,Ksession,N7,idBi}KAB.(F32)
Bi∣≡AC∣~{RECEIPT,Ksession,N7,idBi} ((F31), (A10), message meaning rule).(F33)
Bi∣≡#({RECEIPT,Ksession,N7,idBi}) ((A11), freshness propagation rule).(F34)
Bi∣≡AC∣≡{RECEIPT,Ksession,N7,idBi} ((F32), (F33), nonce verification rule).(F35)
Bi∣≡AC∣≡RECEIPT ((F34), believing rule).(F36)
Bi∣≡RECEIPT ((F34), (A12), jurisdiction rule).
According to formula (F36), the proof of (G4) is completed. Finally, the goal of (G5) is deduced by the following formulas:(F37)
Bi∣≡AC∣≡Ksession ((F34), believing rule).(F38)
Bi∣≡RECEIPT ((F37), (A13), jurisdiction rule).
The proof of (G5) is completed.According to our proofs, we can see that our protocol completes the mutual authentication between users andAC. In on-shelf phase,AC can be sure that on-shelf information is sent from legal user and auctioneer can be sure that IDon-shelf is transmitted fromAC; in bidding phase,AC can be sure that bidding information is sent from legal user and bidder can be sure that receipt and session key are generated and sent byAC. As the results, our protocol achieves authentication accuracy.


## 6.1. On-Shelf Phase

We idealized the on-shelf phase as below:(I1)
Aj→AC:{idAj}PKAC,{γ,N3,idAj}KAA.(I2)
AC→Aj:{IDon-shelf,N4,idAj}KAA.In this phase, we want to ensure thatAC believes in the on-shelf information γ and Aj believes in the IDon-shelf transferred fromAC, so we can conclude the two goals below:(G1)
AC∣≡γ.(G2)
Aj∣≡IDon-shelf.We need to assume thatAC believes the nonce N3 is fresh and Aj believes the nonce N4 is fresh;AC believes that Aj does not send fake γ and idAj, so if Aj believes γ and idAjare true thenAC will believe them too;KAA is computed byAC self, so Aj believes that KAA is shared between him/her andAC; and Aj believes thatAC does not send fake IDon-shelf, so ifAC believes IDon-shelf is true then Aj will believe them too. All 6 assumptions are listed as below:(A1)
AC∣≡#(N3).(A2)
AC∣≡Aj∣⇒γ.(A3)
AC∣≡Aj∣⇒idAj.(A4)
Aj∣≡(AC↔KAAAj).(A5)
Aj∣≡#(N4).(A6)
Aj∣≡AC⇒IDon-shelf.Proof.
For goal (G1), our deduction is shown as the following formulas:(F1)
AC⊲{idAj}PKAC.(F2)
AC⊲idAj (message decryption rule).(F3)
AC∣≡idAj(our hypothesis, we will prove that it is true later).(F4)
AC∣≡(AC↔KAA=SKAC·PAjAj) ((F3), the computing property of believing in operator).(F5)
AC⊲{γ,N3,idAj}KAA.(F6)
AC∣≡Aj∣~{γ,N3,idAj} ((F4), (F5), message meaning rule).(F7)
AC∣≡#({γ,N3,idAj}) ((A1), freshness propagation rule).(F8)
AC∣≡Aj∣≡{γ,N3,idAj} ((F6), (F7), nonce verification rule).(F9)
AC∣≡Aj∣≡idAj ((F8), believing rule).(F10)
AC∣≡idAj ((F9), (A3), jurisdiction rule, our hypothesis in (F3) is proved).(F11)
AC∣≡Aj∣≡γ ((F8), believing rule).(F12)
AC∣≡γ ((F11), (A3), jurisdiction rule).
According to formula (F12), the proof of (G1) is completed.
For goal (G2), our deduction is shown as following formulas:(F13)
Aj⊲{IDon-shelf,N4,idAj}KAA.(F14)
Aj∣≡AC∣~{IDon-shelf,N4,idAj} ((F13), (A4), message meaning rule).(F15)
Aj∣≡#({IDon-shelf,N4,idAj}) ((A5), freshness propagation rule).(F16)
Aj∣≡AC∣≡{IDon-shelf,N4,idAj} ((F14), (F15), nonce verification rule).(F17)
Aj∣≡AC∣≡IDon-shelf ((F16), believing rule).(F18)
Aj∣≡IDon-shelf ((F16), (A6), jurisdiction rule).
According to formula (F18), the proof of (G2) is completed.


## 6.2. Bidding Phase

Our bidding phase can be idealized as below:(I3)
Bi→AC:{idBi}PKAC,{η,N5,idBi}KBA.(I4)
AC→Bi:{RECEIPT,Ksession,N7,idBi}KAB.In bidding phase, we want to ensure thatAC can be convinced that bidding information η transferred from Bi is true; additionally, Bi should be convinced thatRECEIPT and Ksession transferred fromAC are true. So the three goals below can be concluded:(G3)
AC∣≡η.(G4)
Bi∣≡RECEIPT.(G5)
Bi∣≡Ksession.We need to assume thatAC believes N5 is fresh and Bi believes N7 is fresh; if Bi believes η and idBi are true,AC believes in them too because they are generated by Bi; similarly, ifAC believes inRECEIPTand Ksession then Bi believes in them too; because KAB is generated by Bi, Bi believes that he/she shared KAB withAC. All assumptions are listed as below:(A7)
AC∣≡#(N5).(A8)
AC∣≡Bi∣⇒η.(A9)
AC∣≡Bi∣⇒idBi.(A10)
Bi∣≡(AC↔KABBi).(A11)
Bi∣≡#(N7).(A12)
Bi∣≡AC⇒RECEIPT.(A13)
Bi∣≡AC⇒Ksession.Proof.
For goal (G3), our deduction is shown as the following formulas:(F19)
AC⊲{idBi}PKAC.(F20)
AC⊲idBi (message decryption rule).(F21)
AC∣≡idBi (our hypothesis, we will prove that it is true later).(F22)
AC∣≡(AC↔KAB=SKAC·PBiBi) ((F21), operator believes in property).(F23)
AC⊲{η,N5,idBi}KBA.(F24)
AC∣≡Bi∣~{η,N5,idBi} ((F22), (F23), message meaning rule).(F25)
AC∣≡#({η,N5,idBi}) ((A7), freshness propagation rule).(F26)
AC∣≡Bi∣≡{η,N5,idBi} ((F24), (F25), nonce verification rule).(F27)
AC∣≡Bi∣≡idBi ((F26), believing rule).(F28)
AC∣≡idBi ((F27), (A9), jurisdiction rule, our hypothesis in (F21) is proved).(F29)
AC∣≡Bi∣≡η ((F26), believing rule).(F30)
AC∣≡η ((F29), (A8), jurisdiction rule).
According to formula (F30), the proof of (G3) is completed.
For goal (G4), our deduction is shown as the following formulas.(F31)
Bi⊲{RECEIPT,Ksession,N7,idBi}KAB.(F32)
Bi∣≡AC∣~{RECEIPT,Ksession,N7,idBi} ((F31), (A10), message meaning rule).(F33)
Bi∣≡#({RECEIPT,Ksession,N7,idBi}) ((A11), freshness propagation rule).(F34)
Bi∣≡AC∣≡{RECEIPT,Ksession,N7,idBi} ((F32), (F33), nonce verification rule).(F35)
Bi∣≡AC∣≡RECEIPT ((F34), believing rule).(F36)
Bi∣≡RECEIPT ((F34), (A12), jurisdiction rule).
According to formula (F36), the proof of (G4) is completed. Finally, the goal of (G5) is deduced by the following formulas:(F37)
Bi∣≡AC∣≡Ksession ((F34), believing rule).(F38)
Bi∣≡RECEIPT ((F37), (A13), jurisdiction rule).
The proof of (G5) is completed.According to our proofs, we can see that our protocol completes the mutual authentication between users andAC. In on-shelf phase,AC can be sure that on-shelf information is sent from legal user and auctioneer can be sure that IDon-shelf is transmitted fromAC; in bidding phase,AC can be sure that bidding information is sent from legal user and bidder can be sure that receipt and session key are generated and sent byAC. As the results, our protocol achieves authentication accuracy.


## 7. Security Analysis

In this part, we analyze the security of our proposal. We assume that an adversary can eavesdrop on public communications on the Internet and read the information onBBAC; however, he/she cannot read ciphertexts without getting the encrypting keys. Of course, the adversary cannot calculate the keys from ciphertexts. All roles in the system except for theAC can conspire to do something illegally for their benefit. In the following, we provide different scenarios to explain our security defense.(1) Impersonation Attack. It is impossible for an adversary to impersonate a user. When a user wants to communicate with theAC, he/she should send his/her identity ciphertext (Cn,Rn,en) to theAC. TheAC retrieves and checks the user’s identity from this message. We can see that the adversary cannot generate a legal (Cn,Rn,en) to pass this verification without the knowledge of theAC’s private key SKAC and the key KAU shared between theAC and the user. Even if the adversary eavesdrops on the other users’ communications and stores their (Cn,Rn,en), he/she still cannot use these to do anything because theAC will check if the identity included in Cn equals that in en. The only method for the adversary is to replay the whole (Cn,Rn,en); however, this will not work because theAC can check the freshness of the nonce in en.(2) Collusion Attack. In some cases, bidders and auctioneers may conspire to break the secret of theAC. For example, a bidder may sendRECEIPT instead of RECEIPT·P to an auctioneer. However, with this knowledge, they can only compute H(SKAC∥N6)=(RECEIPT-(KAA)x)/M2, where KAA can be computed by the auctioneer and M2 can be found in BBAC. Even obtaining H(SKAC∥N6), they cannot compute SKAC because H(·) is a one-way hash function.(3) Forging Receipt. Firstly, we consider the case that a malicious bidder wants to forge a receipt to impersonate the winner of an auction by himself/herself. Because RECEIPT=(KAA)x+H(SKAC∥N6)·M2, the malicious bidder obviously cannot forge a valid receipt without knowing theAC’s private key SKAC and the key KAA shared between theAC and the auctioneer. Secondly, it is also impossible for the winner and auctioneer to conspire and create the receipt of another auction. As mentioned in the Collusion Attack, they only can compute H(SKAC∥N6). However, for different bidders, N6’s are different, so H(SKAC∥N6) are different in different auctions. Obviously, they cannot create a useful receipt of the other auction with H(SKAC∥N6) by collusion. Besides, it is meaningless for the winner and auctioneer of an auction to forge a receipt of the auction.(4) Denial of Service Attack. If an adversary wants to mount a deny of service attack on a bidder (Bi) such that he/she cannot claim the product in the product claiming phase when he/she wins an auction, the adversary should generate a fake receipt and send it to the bidder during the bidding phase. However, the receipt transmitted to Bi needs to be encrypted with Bi’s identity by the symmetrical key shared between Bi and theAC as EKAB(RECEIPT,Ksession,idBi,N7,IDtrans). After receiving the ciphertext, the bidder should decrypt it and check if his identity idBi is correct. So it is impossible for an adversary to deceive a bidder to accept a fake receipt.(5) Publishing Fake Information. In our proposal, all published information, including new auction information in the on-shelf phase and bidding information and winner information in the bidding phase are signed by the private key ofAC, so anyone can verify the published information withAC’s public key. Let us consider a situation: if a bidder wants to win an auction, he/she may try to publish a fake bidding message with a very high bidding price on BBAC so that no one else wants to compete with him/her. However, he/she cannot be successful without knowing the private key of theAC, because every user can check the signature of theAC on this message.(6) Privacy Preserving. In our scheme, an adversary cannot link any information together to analyze a user’s privacy. Only auctioneers’ identities need to be published in BBAC for enhancing users’ willingness to bid. All packets transmitted in the public channel are encrypted, so the adversary cannot know whether these packets can be linked to certain information published on BBAC even if they captured these packets. It is noteworthy that, in our schemes, we use a delay operation in bidding and on-shelf phases for increasing difficulty of linkage of different messages. For example, if the adversary detects that Alice sends an on-shelf message to theAC and theAC publishes an auction advertisement on the website including the auctioneer’s identity immediately, the adversary would ascertain that Alice is the auctioneer and obtain Alice’s identity. If we delay publishing the auction message several minutes later (i.e., theAC publishes it with other auction information together), then the adversary cannot distinguish a specific user from them. The larger the τ we use, the stronger the privacy preserving function is. However, we should balance the privacy preserving and user experience. Moreover, in the bidding phase, a bidder’s identity can be retrieved by idBi=C2-(R3·SKAC)xmod⁡q, where C2 and R3 are involved in the information published on BBAC. However, these parameters are protected byAC’s private key as dis=Ekdis(C2,R3) before being published on BBAC, where kdis=H(SKAC∥N6), such that no one can extract idBi except for theAC. In the product claiming phase, an auctioneer cannot know the winner’s identity from RECEIPT·P but can only know the validity of the receipt. As indicated in the results, our scheme indeed achieves privacy preserving.(7) Accessing to the Database of the AC. In the definition of a network model (Section 4), we have mentioned that we do not consider the database of theAC to be completely secure in our proposal. An adversary may access the messages stored in it by certain methods. However, accessing the database would not destroy the security of the whole system. Furthermore, theAC’s private key should be kept in a trusted place, such as a bank. There are mainly four data sets maintained in theAC: the first is (idU,vU) generated in the registration phase, the second is (IDproduct,Basic_price,Deadline,IDon-shelf,idAj,R2,S1) generated in the on-shelf phase, and the final are (IDtrans,date,price,dis,N6,R4,S2) and (IDtrans,price,date,H(SKAC∥N6)·P,dis,N6) generated in the bidding phase. Only the first data set is unpublished, so we only consider the safety of the first data set here. If a hacker reads the content of the first data set, he/she only can obtain all users’ identities and their partial keys (PUs) which have been protected byAC’s private key as the form vU=PU⊕H(SKAC). With only protected partial keys, the hacker cannot compute the symmetrical key KAU (KAU=pwu·PKACmod⁡q=SKAC·PUmod⁡q) shared between users and theAC, because the private key of theAC is kept secret. Furthermore, he/she cannot retrieve a user’s password from the partial key based on ECDLP. So we can see that accessing the database does not destroy the safety of the whole system.(8) Password Guessing Attack. In our scheme, users’ passwords are needed to protect system security. However, because the user’s password is not very long and there is a certain routine mode, attackers may try to mount the password guessing attack to the password-based communication schemes. To prevent this attack, in our scheme, users’ passwords will not be transmitted or stored in plaintext. As mentioned in the registration phase (Section 5.2), the password related information PU is transformed to ciphertext C=(r0·PKAC+PU)mod⁡q before transferring and is stored as the format of vU=PU⊕H(SKAC) inAC’s database. Obviously, even an attacker collects ciphertext or vU by eavesdropping the whole communication channel or intrudingAC’s database; he/she can not obtain any user’s password by password guessing attack without the knowledge ofAC’s secret key SKAC.Table1 (“○” means fully achieved, “△” means partially achieved, and “×” means not achieved) shows the security comparison among our proposal and three other schemes: Chang et al.’s [14], Xiong et al.’s [13], and Chung et al.’s [18]. As shown in Table 1, our scheme fulfills the most secure properties of an electronic auction system. In the analysis of “privacy preserving,” our scheme can achieve the properties of anonymity and unlinkability; in the analysis of “Publishing Fake Information,” our scheme can achieve the properties of fairness and verifiability; and in the analyses of “Impersonation Attack,Forging Receipt, andDenial of Service Attack,” our scheme can achieve the property of unforgeability. Similar to [13, 14, 18], the bidding information should be published on an open website, so the bidder can check if his/her bid appeared on it to ensure fairness. Based on the digital signature, bidders cannot deny their bids so nonrepudiation is achieved in four proposals. By providing the dispute mechanism, our scheme achieves the properties of easy revocation, nonrepudiation, and traceability. Furthermore, our scheme overcomes the security problem (leakage of unlinkability) and meanwhile inherits the advantage of without a secure channel in Chang et al.’s scheme [14]. It is noteworthy that, compared to [14], our protocol needs to store a little of the verification table in the server side. However, as we analyzed before, leakage of these verification tables will not influence system security, so we say that our protocol achieves partial property of no verification table.Table 1
Comparison in security properties of the three schemes.
Property
Proposal
Our proposal
Chang et al.’s proposal [14]
Xiong et al.’s proposal [13]
Chung et al.’s proposal [18]
Anonymity
○
○
○
○
Easy revocation
○
○
△
△
Fairness
○
○
○
○
Nonrepudiation
○
○
○
○
Onetime registration
○
○
○
○
Traceability
○
○
○
○
Unforgeability
○
○
○
○
Unlinkability
○
×
○
○
Verifiability
○
△
×
○
On-shelf mechanism
○
○
×
×
Without secure channel
○
○
×
×
Password guessing attack defending
○
○
○
○With regard to verifiability, in the bidding phase of Chang et al.’s proposal [14], only the winner’s bidding information will be signed by theAC and can be publicly verified, which may lead attackers to modify any new bidding information with a higher price such that no one else wants to bid for it further. So verifiability is not fully achieved in [14]. As [14] analyzed, the designed revocation function in [13, 18] only partially achieved easy revocation. Our protocol and [14] have a secure on-shelf phase compared to [13, 18]. Our protocol does not need a secure channel to achieve verification in any phase similar to [14]. However, in [13, 18], a secure channel is needed to assist in the completion of the whole protocol.


## 8. Performance Analysis

In this section, we compare the cost of our scheme with the other three schemes [13, 14, 18] with regard to computational cost, traffic, and communication rounds.Table2 shows the comparison of computational cost, where “PM” means a point multiplication operation of ECC, “BM” means a bilinear mapping which can be implemented on ECC such as Weil pairing, “E” means a symmetrical encryption, “D” means a symmetrical decryption, “H” means a hash function, and “n” means the number of bidders in an auction.Table 2
Comparison in computational cost of the three schemes.
Property
Proposal
Our proposal
Chang et al.’s proposal [14]
Xiong et al.’s proposal [13]
Chung et al.’s proposal [18]
Registration phase
8PM + H
9PM
4PM + 2H
5PM + 3H
On-shelf phase
7PM + 2E + 2D + 2H
10PM + 2E + 2D + 2H
×
×
Bidding phase
(10n + 2)PM + 3nE + 2nD + 5nH
12nPM + 2nE + 2nD
(4n + 1)PM + 3BM + 2H
(8n + 2)PM + (3n + 1)H
Product claiming phase
2PM + E + D + 1H
6PM
×
×
Dispute phase (bidder/auctioneer)
6PM + E + 1D + 3H/6PM + E + 2D + 3H
3PM + 2H/3PM + E + D
0.5nBM/×
×As we know, a bilinear map is an expensive operation; the more it is used, the more computation cost is needed. Compared with point multiplication, the hash function only consumes negligible computation cost. Symmetrical cryptographic operation is also cheaper than point multiplication. From the comparison in Table2, we can see that our proposal needs less computation cost compared with Chang et al.’s proposal [14] in each phase, except for the dispute phase. However, in reality, the first four phases are more frequently executed.To make the traffic comparison, we determine the elliptic curve operation as NistP 192 [24], hash function as SHA-256 [31], and symmetrical encryption/decryption as AES-256 [32]. The length of the user’s identity is 4 bytes, product identity is 5 bytes, transaction identify is 5 bytes,GID in [14] is 5 bytes,price is 5 bytes, andDeadline is 4 bytes. Note that we ignore the length of nonce transmitted in communications. As shown in Table 3, we can see that our protocol has a traffic advantage compared with related works [13, 14, 18], except for dispute phase of Chang et al.’s scheme [14]. The main reason for this is that our scheme finished the key establishment in the registration phase for saving the traffic cost of public keys and certificates. Comparing with Chang et al.’s proposal, though our dispute phase needs more traffic, this phase is not often used compared with the other four phases. As a result, we believe that our proposal has traffic advantages still. Finally, we compare the communication rounds of our scheme and the related schemes in Table 4. As shown in this table, our protocol needs the same communication rounds as those in Chang et al.’s protocol [14].Table 3
Comparison in traffic of the three schemes (B: bytes).
Property
Proposal
Our proposal
Chang et al.’s proposal [14]
Xiong et al.’s proposal [13]
Chung et al.’s proposal [18]
Registration phase
82 B
192 B
108 B
128 B
On-shelf phase
144 B
266 B
×
×
Bidding phase
176n B
290n B
(96n + 120) B
(119n + 248) B
Product claiming phase
48 B
149 B
×
×
Dispute phase(auctioneer/bidder)
112 B/128 B
37 B/85 B
48 B/×
×Table 4
Comparison in communication rounds of the three schemes.
Property
Proposal
Our proposal
Chang et al.’s proposal [14]
Xiong et al.’s proposal [13]
Chung et al.’s proposal [18]
Registration phase
2
2
1
1
On-shelf phase
3
3
×
×
Bidding phase
2
n
2
n
1
n
+
2
Product  claiming phase
1
1
×
×
Dispute phase (auctioneer/bidder)
1/1
1/1
1
×


## 9. Conclusions

In this paper, we pointed out that Chang et al.’s protocol does not fulfill the unlinkability such that users’ privacy will be leaked by linking different messages together. Considering the importance of privacy preservation, we proposed a novel electronic English auction system. By using symmetrical encryptions and fewer ECC operations, our protocol can not only improve the security but also reduce the system cost. In the registration phase, we connect a user’s identity and the corresponding symmetrical key so that theAC can compute the shared symmetrical key easily with the user’s identity. Furthermore, each user’s identity is encrypted with theAC’s public key so it cannot be revealed without the knowledge of theAC’s private key. In the bidding phase, we improve the efficiency of generating bidding receipts. In our proposal, we fulfill the verifiability of all messages published on theAC’s website; however, Chang et al.’s proposal only achieved this feature partially. We used BAN logic to prove that our protocol indeed realizes mutual authentication. The security analysis and performance analysis show that our protocol fulfills more security properties and is more efficient for implementation compared with recent works.



---

*Source: 6567146-2016-05-04.xml*