using mobile agents
Dong-Her Shih a,*,Shin-Yi Huang a ,David C.Yen b
a
Department of Information Management,National Yunlin University of Science and Technology,123,Section 3,University Road,
Touliu,Yunlin,Taiwan,R.O.C.
b
Department of DSC and MIS,Miami University,Oxford,Ohio 45056,United States
Available online 4November 2004
Abstract
In order to get the goods,a buyer must search for the items through several auction sites in Internet.When the auction starts,the buyer needs to connect to these auction sites frequently so that he can monitor the bid states and re-bid.In this paper,we propose an automated negotiation model between two participants,for m-commerce,using collaborative mobile agents called mobile reverse auction agent system (MoRAAS),which mediates between the buyer and the sellers and executes bidding asynchronously and autonomously.This reduces the network load and offers more intelligent bidding.A new double encryption key chain technique and a new RV AP protocol are proposed to achieve unconditional bid privacy.Every losing bidder can control the privacy of their own bids while no trust is needed.Computational cost of our RV AP protocol is reduced by avoiding the costly verifiable encryption technique.D 2004Elsevier B.V .All rights reserved.
Keywords:Reverse Vickrey auction;Bid privacy;Mobile agent;M-commerce;Automated negotiation
1.Introduction
Though the technology of e-commerce has grown steadily,it is still difficult to implement the negotiation between a buyer and a seller online.The Internet auction agent system has been expanded as an alternative solution and the area of multi-agent systems [1]has achieved steadily growing interest in the past
decade.Two key problems to be addressed in this area are automated resource allocation and task assignment among the individual agents.As a solution to these problems,it has become common practice to apply well-known results and insights from auction theory (e.g.,Refs.[2,3])and well-understood auction proto-cols like the English auction,the Dutch auction,and the Vickrey auction.Among the different protocols,the Vickrey auction [4]has received particular at-tention within the multi-agent community and has been applied in e-commerce.The Vickrey auction,in its original formulation,is used for selling goods or resource allocation.In task assignment scenarios,the
0920-54/$-see front matter D 2004Elsevier B.V .All rights reserved.doi:10.1016/j.csi.2004.10.006
*Corresponding author.Tel.:+88655342601;fax:+88655312077.
E-mail addresses:shihdh@yuntech.edu.tw (D.-H.Shih)8yendc@muohio.edu (D.C.Yen).
Computer Standards &Interfaces 27(2005)383
–395
www.elsevier.com/locate/csi
Due to the growing number of cellular phones and PDAs,more and more people desire to perform activities using them.One of these activities is mobile commerce(m-commerce),where a user can buy a product or service no matter where he is.It is necessary to develop techniques and communication mechanisms for mobile commerce,which satisfy the requirements and the limitations of the mobile infrastructure.
This paper proposes an automated reverse auction agent system for mobile commerce(MoRAAS)using collaborative mobile agents based on our proposed RV AP(Reverse Vickrey Auction Protocol with bid privacy)for electronic commerce.The MoRAAS system mediates between the buyer and the seller and RV AP protocol executes bidding autonomously for the buyer.The RV AP auction is a novel protocol in which the sellers’bid agent can compete on price with bid privacy.The idea of encryption key chain is inherited and a new double encryption key chain technique is proposed,so that bid privacy for a losing bidder is achieved without any trust on other parties. Additionally,the new scheme is simpler as the third party T and the auctioneer A are removed.
2.Related works
Agent system and bid privacy of an auction are introduced in this section.
2.1.Auction agent system
Agents facilitate several auction types,including Dutch,English,Vickrey,and First-Price-Sealed-Bid auctions.At first-price open-cry English auction bidders win with and have to pay the amount of the highest bid.In descending price open-cry Dutch auctions,the auctioneer sells a single item at the first incoming bid.At a first-price sealed-bid auction,each bidder submits one bid in ignorance of all other bids and the highest bidder wins and pays the amount of his bid.Similarly,at second-price sealed-bid Vickrey auctions,the winning bidder pays the price of only the second highest bid.There are many auction sites have solutions that offer a convenience to the users.For example,eBay uses a reserve-price auction method.It allows the user to enter a reserve price.As long as the auction is open and the user’s reserve price has not been reached,the agent bids the minimum amount necessary to become the highest bidder.However,this limits the user’s choice of bidding strategy without bid privacy and may involve taking into account the effect of the d winner’s curse T.The winner’s curse is the difference between the amount the winner paid and the next lower bid.If the bidder bids the perceived valuation of the item and wins,the bidder will know that he paid too much because others valued the item less.Sandholm and Huai[5]solve this problem with the agent allowing the user to coordinate bids across multiple auctions automatically and select a bidding strategy.
Nomad[5]and Magnet[6]are auction agents using a mobile agent mechanism.A mobile agent has the unique ability to transport itself from one system to another.This ability allows mobile agents to execute asynchronously and autonomously.Also,the mobile agents communicate with one another.Because of this ability,the auction agent using a mobile agent is smarter than the reserve auction agent.Thus,the agent tracks bids in multiple auction houses in order to look for the best deal and/or coordinates the user’s bids in the different auctions.
2.2.Bid privacy of an auction
Bid privacy is a frequently desired property in auction schemes.It refers to the con?dentiality of losing bids to anybody even after the auction ends. Franklin and Reiter[7]were among the first to address electronic auction with bid privacy.They covered many basic problems,combined crypto-graphic primitives such as secret sharing,digital cash
D.-H.Shih et al./Computer Standards&Interfaces27(2005)383–395 384and multicasts,and introduced their own primitive called b verifiable signature sharing Q.There are only very few publications devoted to second-price auc-tions[8–10]and all of them relying on the security of distributed computation.The other privacy issues of the sealed-bid auction protocol are listed in Table1 [11].In current auction schemes,two methods are often applied to implement bid privacy.The first method is to trust some parties to conceal the losing bids.To strengthen bid privacy,the trust is often shared among a few auctioneers,so that bid privacy can be achieved if the number of honest parties is over a threshold.This mechanism is usually realized by sharing the capability of bid-opening among several auctioneers and requiring the cooperation of a portion of them to open the bids.Several published schemes are in this category[12–15].The disadvantages of these methods are that the bid privacy obtained is not strong enough.In some applications,stronger bid privacy is required.Therefore,the second method is unconditional bid privacy—without the cooperation of a losing bidder,his bid is confidential.A mechanism called Dutch style bid opening can be employed to achieve unconditional bid privacy.In this mechanism the bids are opened downwards from the highest biddable price.After the winning bid is found in a downward search,cooperation from the bidders is not available,so any losing bidder’s bid is kept private without trust on anybody else.Therefore,very strong absolute privacy is achieved.Prominent schemes in this category are indicated in the table[16,17].
In the reverse auction,multiple sellers compete on goods and the evaluation value shown by the buyer.A designated bidding system is one form of reverse auction.In designated bidding,the auctioneer nomi-nates a bidder based on the quality of their work.It can prevent poor companies from making a successful bid prior to bidding.The right to bid is granted only to bidders accepted by aptitude.By nominating a superior contractor,it becomes possible to assure the quality of work.The disadvantage is the increased probability of collusion,because the number of bid participants is restricted[18].It is hard for companies from other areas and new companies to join the auctions.Collusion prevents any fear of competition. In theory,the open bidding auction mechanism is better than the designated auction mechanism[19]. However,buyers can solicit nominations via Internet. Therefore,we adopted the designated auction mech-anism to the Internet auction.The Reverse Extended Vickrey(REV)auction protocol[20]is the case.In REV auction,a buyer selects sellers who have substitute goods and the buyer’s preferred goods. The nominated sellers submit sealed bids.The designated aspect of the auction can eliminate sellers who have inferior goods by preselecting a seller.The designated auction is not robust against collusion for the following reasons[21].
–The goods have common value.Rebates enable bidders to know the auctioneer’s evaluation value.
–If auction is repeated,there will be an incentive for sellers to collude.
–Retaliation from other colluding sellers prevents a seller from avoiding collusion.
Since verifiable encryption enables T(Third trusted party)to recover a secret share once he gets its encrypted value,registration information from bidders must be transmitted through a con-fidential channel.Even though the registration information is encrypted,collusion of A(Auction-eer)and T still can reveal all decryption keys and thus all losing bids.That means bid privacy is based on the following two assumptions:(1)A and the winner do not conspire;(2)A and T do not conspire.These are still strong assumptions and require strong trust.
Table1
Privacy issues of the sealed-bid auction protocol
Using technique Auctioneer(s)Hiding bids
of losers Opener of bids
Verifiable signature
sharing
Not trusted No Auctioneer(s)
Secret sharing Trusted Yes/No Auctioneer(s) (Distributed)
public-key
crypto
Trusted Yes Auctioneer(s)
Convertible
undeniable
signature
Not trusted Yes Bidder Hash chaining Not trusted Yes Bidder
Verifiable encryption Not trusted Yes Auctioneer(s)
D.-H.Shih et al./Computer Standards&Interfaces27(2005)383–395385
Therefore,we proposed a mobile auction agent system (MoRAAS)for the buyer’s mobility consid-eration in Section 3.A new auction protocol (RV AP)for bid privacy is presented in Section 4.Thus,stronger bid privacy is achieved in MoRAAS auction security.
3.MoRAAS:mobile reverse auction agent system In order to achieve the buyer’s mobility,a mobile MoRAAS system is proposed.Our proposed MoR-AAS consists of three main components:a buyer agent,a broker agent and a bid agent.The communication model with web service,as shown in Fig.1,works as follows.There is an application in the mobile device,called BuyApplication,used by the client to make purchases.Each time a mobile network user wishes to make a purchase,BuyAp-plication connects to another application called CallBuyApplication,which is hosted in a server in the fixed network,and sends information about the product,which the user wants,like its features,the desired price and the maximum price to offer.On the other hand,a broker agent chooses mobile network sellers who agree to make a sell,SelAp-plication connects to another application called CallSelApplication,which is hosted also in a server in the fixed network,and sends information about
the goods.As soon as the buyer agents have been created,they move to the host of the selected sellers to negotiate with them.At the end of the negotiation and auction,buyer agent sends its results to the user.
The proposed model for mobile commerce is divided in six sessions,which is shown in Fig.2and described below.
Connection Session :when the buyer wants to start a new auction,he sends a message to the fixed network,requesting a new auction process.This message contains the desired product and its features.When the request arrives,the applica-tion in the fixed network creates an original buyer agent responsible for performing the auction.
Call Session :in this session,the buyer agent sends a multicast message to the broker agents in order to verify which of the sellers’bid agents have the desired product.
Designation Session :in this session,the buyer selects which sellers’bid agent it will negotiate with among the sellers’bid agents that responded affirmatively in the prior session.
Auction Session :in this session,a copy of the sellers’bid agent,selected in the previous session,is sent to the buyer agent.The RV AP auction is
performed.
Fig.1.Communication in MoRAAS.
D.-H.Shih et al./Computer Standards &Interfaces 27(2005)383–395
386
The architecture of a MoRAAS is shown in Fig.3. The buyer agent offers a buyer interfaces for querying the broker agent,specifying the bid agents,and controlling the bid agents.An interface for querying the broker agent shows a recommended seller’s
list Fig.2.MoRAAS working
sessions.
Fig.3.MoRAAS architecture.
D.-H.Shih et al./Computer Standards&Interfaces27(2005)383–395387
and the expected goods through bid agent finder.An interface for specifying agents sends a bid agent creator the information for creating the bid agent.Then,the bid agent creator creates the bid agent from a template and designates the bid agent with the broker agent.An interface for buy control agent allows the user to communicate with the bid agent and controls the bid agent’s behaviors.The broker agent matches the buyers and the sellers.A sellers’bid agent registry messages come to agent register.If a buy message comes from the buyer agent and the message is a query for recommending the seller,the agent matcher will respond to matched sellers’bid agent list.The sellers’bid agents publish goods for seller through register agent interface.Bid agent is granted a response for bidding and bid control agent would take control with the bidding process.These agents collaborate with each other in order to execute an auction in a mobile agent platform.
When a new auction is created,a seller must choose a bid agent in order to publish his goods (1).A chosen bid agent registers it with a broker agent (2).The buyer submits the item’s identity and evaluation price to the buyer agent (3).The buyer agent submits the data received to the broker agent to find possible bid agent (4).The broker agent searches for a recommendable bid agent and returns the results to the buyer agent (5).The buyer agent informs the buyer (6).The buyer selects proper bid agents recommended by the broker agent (7).The buyer agent requests all the designated bid agents for bidding (8).The bid agent then dispatches it to the
seller (9).The seller grants the request (10)and bid agent dispatches it to the buyer agent (11).Finally,the buyer agent starts an auction process (12).All the bid agents read the auction information from the buyer agent’s blackboard,and execute the bidding autono-mously.The buyer agent receives the intermediate auction information from the bid agent,and controls the bid agent.When the auction ends,the bid agent sends a d win T or d fail T message to the buyer agent.The winning bid agent exchanges transaction information with buyer agent in order to transact.Fig.4presents the entire MoRAAS workflow.As can be seen from the workflow,the buyer needs to connect to the network once in order to start the bidding.From that point on,the buyer agent executes the rest autono-mously.Finally,the buyer agent notifies the buyer of the bidding and evaluation results.
4.Reverse Vickrey auction without a trusted party An encryption key chain technique by Watanabe and Imai [11]was claimed to achieve strong bid privacy non-interactively.Therefore,a new crypto-graphic tool,double encryption key chain,is proposed and employed in our RV AP protocol.The bids are opened in a bottom-up direction from the lowest biddable price until the winning bid and second lowest price are found.Further details are given below.We also assume the use of a bulletin board (BB)setting where participants read and write in authenticated
manner.
Fig.4.MoRAAS workflow.
D.-H.Shih et al./Computer Standards &Interfaces 27(2005)383–395
388
4.1.Double encryption key chain
In Ref.[11]only a finite set of prices are biddable and an encryption key chain is constructed for these prices.Our proposed double encryption key chain,in reverse Vickrey auction,is constructed in a different rule:first,a bidder is encrypted with all public key(n bidders)for the negative bid(he is not willing to sell at a price).If a bidder has a positive bid(he is willing to sell at a price)at a price,he must encrypt with all other’s public key(nÀ1bidders)for the next higher price in the auction.The public keys are generated in a special way so that the shares for the decryption key at the winning price and the second lowest price are different.There-fore,we denote it as double encryption key chain.Any decryption key at a price higher than the second lowest price cannot be reconstructed without cooperation from all bidders.The double encryption key chain for our RV AP protocol is as follows.
(1)At each price,lower than bidder’s positive bid,
all the bids are encrypted by the same public key, which is generated by all the bidders,namely the first encrypted key chain.
(2)The corresponding decrypting key is shared
among the bidders.Only when all the bidders put their shares together at a price,the bids at
that price can be opened.
(3)If a bidder is not willing to sell a price,at that
price his bidding value contains his share of the decryption key needed to open the bids at the next price.If none of the bidders are willing to sell a price,the decryption key to open the bids at the next price can be constructed from their opened bids at the price.
(4)If a bidder is willing to sell a price,his share of
the decryption key needed to open the bids at the price and at the next prices is encrypted with all other’s public key,namely the second encrypted key chain.As soon as the first encryption key chain is broken,the second encryption key chain is started and the decryption key to open the bids at the next price can be constructed by all other’s public key.
(5)When the first encryption key chain is broken by
a winning bid,the next bid is decrypted until the
second lowest price is found and the second encrypted key chain is broken also.The decryp-
tion key to open the bids after the second lowest price cannot be constructed unless others are collude together,thus the con?dentiality of the losing bids is protected.
4.2.RVAP protocol
We want unconditional bid privacy,namely no trust is needed on any other party for the confidentiality of a losing bidder’s bid.In the new scheme,when there is a winning bid and a second lowest price,the key chain is broken completely.To obtain a simpler and more effective and efficient scheme,no active auctioneer is employed and no registration phase is needed in our scheme.Nor does it need a third party or verifiable encryption.Bidders performing malicious behavior (e.g.failing to reveal correct share in a d No T bid)can be publicly identified.Notation G is a cyclic group with a generator g.There are n bidders S1,S2,...,S n and w biddable prices p1,p2,...,p w from lowest to highest.
E y(x)denotes encryption of x by a public key y.D a(b) denotes decryption of b by a private key a.Sig a(b) denotes a’s signature on b and message b.Primes p and q satisfy q|pÀ1.Our scheme includes four phases: initial phase,preparing phase,bidding phase and opening phase.
4.2.1.Initial phase
Each bidder S i chooses a secret x i,j and publishes a public key y i,j for every biddable price Pkt1i=(S i,y i,j, Sig Si(S i,y i,j))where y i,j=g xi,j for i=1,2,...,n on a bulletin board.
4.2.2.Preparing phase
Every bidder S i calculates the first encryption key chain Y j¼
Q n
k¼1
y k;j mod p and the second encryp-tion key chain R i;j¼
Q n
k¼1;k p i
y k;j mod p for every biddable price as illustrated in Table2and Table3
Table2
Public key generations for the first encryption key chain S1S2S3First encryption key
p1y1,1=g x1,1y2,1=g x2,1y3,1=g x3,1Y1=y1,1*y2,1*y3,1mod p p2y1,2=g x1,2y2,2=g x2,2y3,2=g x3,2Y2=y1,2*y2,2*y3,2mod p p3y1,3=g x1,3y2,3=g x2,3y3,3=g x3,3Y3=y1,3*y2,3*y3,3mod p p4y1,4=g x1,4y2,4=g x2,4y3,4=g x3,4Y4=y1,4*y2,4*y3,4mod p p5y1,5=g x1,5y2,5=g x2,5y3,5=g x3,5Y5=y1,5*y2,5*y3,5mod p p6y1,6=g x1,6y2,6=g x2,6y3,6=g x3,6Y6=y1,6*y2,6*y3,6mod p
(supposing there are three bidders and six biddable prices,so that n =3,w =6).The public key for price p j is either Y j or R i,j and can be calculated by anybody using the public values available on the bulletin board.4.2.3.Bidding phase
Every bidder submits an encrypted bid for each biddable price.If a bidder S i is not willing to sell p j ,his encryption key of secret key x i,j +1is Y j and his bid at p j is V i,j =E yj (x i,j +1).If bidder S i has a positive bid at price p k ,his encryption key of secret key x i,k +1is R i,k and his bid at p k is V i,k =E Ri,k (x i,k +1).At price p k
higher than his evaluation,his secret keys x i,k +2,x i,k +3,...are encrypted as E Ri,k +1(x i,k +2),E Ri,k +2(x i,k +3),...,respectively.S i publishes V i =(S i ,V i,1,V i,2,...,V i,w ,Sig Si (S i ,V i,1,V i,2,...,V i,w ))on the bulletin board.Bid format is illustrated in Table 4(supposing there are three bidders and six biddable prices).
4.2.4.Opening phase
The bidders publish Pkt 2i =(S i ,x i,1,Sig Si (S i ,x i,1))for i =1,2,...,n .Anybody can verify the validity of the shares against y i,1for i =1,2,...,n ,construct the decryption key for the first price X 1¼P n i ¼1x i ;1mod q and decrypt all the bids at p 1.The meaning of S i ’s decrypted bid v i,1can be determined by testing whether y i,2=g vi,1(v i,1is a negative bid)or y i,2p g vi,1(v i,1is a positive bid)is true.If y i,2=g vi,1,there is no bid showing willingness to sell at p 1,all the shares x i,2=v i,1for i =1,2,...,n are obtained
and X 2¼P n
i ¼1x i ;2mod q can be recovered.Then all the bids at p 2are opened.The opening continues until y i,j +1p g vi,j is met and the first key chain breaks at p j .S i is declared as the winner.The second key chain starts when the first key chain is broken,where y i,j +1p g vi,j .Then,x k,j +1,for k =1,2,...,n and k p i ,are decrypted with X j ¼P n i ¼1x i ;j mod q and x i,j +1is decrypted with x i ;j þ1¼D R i ;j V i ;j
ÀÁTable 3
Key generations for the second encryption key chain
S 1
S 2
S 3
p 1R 1,1=y 2,2*y 3,2mod p R 2,1=y 1,2*y 3,2mod p R 3,1=y 1,2*y 2,2mod p p 2R 1,2=y 2,3*y 3,3mod p R 2,2=y 1,3*y 3,3mod p R 3,2=y 1,3*y 2,3mod p p 3R 1,3=y 2,4*y 3,4mod p R 2,3=y 1,4*y 3,4mod p R 3,3=y 1,4*y 2,4mod p p 4R 1,4=y 2,5*y 3,5mod p R 2,4=y 1,5*y 3,5mod p R 3,4=y 1,5*y 2,5mod p p 5R 1,5=y 2,6*y 3,6mod p R 2,5=y 1,6*y 3,6mod p R 3,5=y 1,6*y 2,6mod p p 6
R 1,6=y 2,1*y 3,1mod p
R 2,6=y 1,1*y 3,1mod p
R 3,6=y 1,1*y 2,1mod p
Table 4
Bids data format and decryption key generation
S 1
S 2S 3First decryption key
Decryption results
p 1E Y 1(x 1,2)E Y 1(x 2,2)E Y 1(x 3,2)X 1=x 1,1+x 2,1+x 3,1mod q
x 1,2,x 2,2and x 3,2are decrypted by X 1p 2
E Y 2(x 1,3)E R 2,2(x 2,3)E Y 2(x 3,3)X 2=x 1,2+x 2,2+x 3,2mod q
x 1,3and x 3,3are
decrypted by X 2,x 2,3
is decrypted by x 1,3+x 3,3p 3
E Y 3(x 1,4)E R 2,3(x 2,4)E Y 3(x 3,4)X 3=x 1,3+x 2,3+x 3,3mod q
x 1,4and x 3,4are decrypted by X 3,x 2,4is decrypted by x 1,4+x 3,4
p 4
E R 1,4(x 1,5)
E R 2,4(x 2,5)
E Y 4(x 3,5)
X 4=x 1,4x 2,4+x 3,4mod q
x 3,5is decrypted by X 4,x 2,5and x 1,5are decrypt with each other which is
impossible.Therefore,the 2nd decryption key is broke.
p 5E R 1,5(x 1,6)E R 2,5(x 2,6)E R 3,5(x 3,6)S 1,S 2must collude to recover X 5
Decryption key has been broken.
p 6
E R 1,6(x 1,1)
E R 2,6(x 2,1)
E R 3,6(x 3,1)
All the bidders must collude to recover X 6
Decryption key has been broken.
where R i ;j ¼P n
k ¼1;k p i x k ;j þ1mod q .Then,the de-cryption of X j þ1¼P n i ¼1x i ;j þ1mod q can be recov-ered and opening continues until another y m,r +1p g V m,r is found at price p r (r N j ).Since secrets x i,r +1and x m,r +1cannot decrypted from each other,X r +1cannot be reconstructed and the second key chain is broken at contract’s price p r and opening stops.The decryption key to open the bids after price p r cannot be constructed unless others collude together,thus the confidentiality of the losing bids is protected.An example of bid format and decryption result is illustrated in Table 4.The evaluation prices of bidders
S 1,S 2and S 3are assumed to be p 4,p 2and p 5respectively.Fig.5illustrates the auction procedure.4.3.Buyer and winner’s evaluation
We assume that the buyer nominates n sellers with goods that suit the buyer’s preferences.The buyer shows an evaluation value,b ,where p 1Q b Q p w .Sellers bid for the evaluation value in the auction.In the winner determination algorithm,b 1represents the smallest bid value and b 2represents the second smallest bid value,p 1is the lowest biddable
price
Fig.5.Our proposed auction procedure.
and p w is the highest biddable price,where p 1Q b 1Q b 2Q p w .When seller S i wins,the buyer’s payment and the utility of seller and buyer are determined as follows.(1)
If b 2Q b ,the buyer pays the price,b 2,to the seller S i .We assume a quasi-linear utility.Therefore,a buyer’s utility is b Àb 2and the winner’s utility is b 2Àb 1.
(2)
If b 1Q b Q b 2,a buyer’s valuation is between the first and second prices,the buyer pays price b to the seller.Obviously,the buyer’s utility is 0,and the seller S i ’s utility is b Àb 1.(3)
If b b b 1,then this trade fails.
If there is a tie condition,the agent can choose a winner randomly.Since the second price is used to determine a successful trade’s payment,therefore,in case 1this auction is a second-price,sealed-bid double auction.If the buyer’s evaluation value is between the first and second prices,the buyer pays the successful bidder the buyer’s evaluation value.Never-theless,after the auction is stopped,the buyer and the winner can negotiate the final price with each other to avoid the failure of the Vickrey auction.Therefore,availability at any time and everywhere of mobile connection is needed.4.4.Analyses
The RV AP auction protocol is analyzed in this section.It will be shown that the protocol is correct,sound,fair,publicly verifiable and achieves uncondi-tional privacy for losing bids.We claim that the following properties described in Refs.[22,23]are achieved in our protocol.
4.4.1.Fairness
Before the opening phase,only every bidder’s public keys and bids for each price are published;no bids are revealed.Bidder S i chooses a secret key x i,j
for biddable price p j and the public key is y i,j =g xi,j
or R i ;j ¼Q n k ¼1;k p i y k ;j mod p .Since x i,j is chosen from 1,2,3,...,ord(G )randomly,y i,j and R i,j have an identical distribution over G .So no information about any bidder’s bids is revealed from the public keys.All the submitted bids are encryptions of a random integer less than ord(G ),and thus have a uniform distribution
in the ciphertext space (G in the case of ElGamal encryption)if a semantically secure encryption algorithm (e.g.ElGamal or Paillier’s [24])is employed.Therefore,before the opening phase all bids are confidential on the assumption that the encryption algorithm is semantically secure.4.4.2.Privacy of losing bid
All bidding prices,except the winner and contract’s price,are not revealed to anyone.The winner cannot take advantage over other bidders even after the auction result turns out,because to open any losing bid after contract’s price,the cooperation of other losing bidders is necessary.If the bidder S i with his bid p j is the winner and the bidder S m with his bid p j +r is the second price winner,they cannot disclose x i,j +r +1and x m,j +r +1.Since the decryption of x i ;j þr þ1¼D R i ;j þr V i ;j þr ÀÁ,where R i ;j þr ¼P n k ¼1;k p i x k ;j þr þ1mod q needs x m,j +r +1and the decryption of x m ;j þr þ1¼D R m ;j þr V m ;j þr ÀÁ,where R m ;j þr ¼P n k ¼1;k p i x k ;j þr þ1mod q ,needs x i,j +r +1also,unless they collude,the decryption key of next price x j +r +1cannot be constructed.Thus,the confidentiality of the losing bids is protected.Therefore,anybody cannot get any information and decrypt the subsequent commitments to bids unless there exists a collusion.4.4.3.Public verifiability
In our protocol,anyone can simulate the procedure to open bids using the information on the BB.All the information necessary to decide the auction result is published on the bulletin board,so anybody can verify the auction result using the contents of the bulletin board.These decryption keys are available after the execution of the opening procedure (They are published on the BB).
4.4.4.Correctness
An honest bidder S i publishes x i,1.Then,the
decryption key X 1¼P n
i ¼1x i ;1mod q can be con-structed.Therefore,the encryption key chain starts correctly and the bids at p 1can be opened.Honest bidder S i ’s bids at all the biddable prices are as follows:(a)
At a price p j lower than his evaluation,his bid is x i,j +1satisfying y i,j +1=g x i ,j +1.
(b)At a price p j equal to his evaluation,his bid is
E Ri,j (x i,j +1).
(c)
At a price p j higher than his evaluation,his bid is E Ri,k (x i,k +1)for k =j +1,j +2,...,w À1.If at a price p j lower than any bidder’s evaluation bids are opened,the decrypted bids are v i,j =x i,j +1for i =1,2,...,n ,thus X j þ1¼P n i ¼1x i ;j þ1mod q can be reconstructed.So the first encryption key chain extends correctly one step downwards and the bids at p j +1can be opened.After the execution of the opening procedure,all bidders can get convinced that winner satisfies all conditions.Consequently,bidders cannot get any information of bids higher than contracting bid unless they all collude.The winning bid is indeed the lowest bid and contracting bid is the second lowest price.
4.4.
5.Non-repudiation
Opening bids require the first decryption key (X 1)that is shared among all bidders.Therefore,no one can disclose any information of bids unless all bidders open their shares after confirming that the bidding period closes.Nevertheless,since y i,j +1and V i,j are published in initial phase and bidding phase,respectively,they cannot be changed.So bidding values cannot be changed.Besides,y i,j +1and V i,j are signed by S i ,therefore S i cannot deny his bids.No bidders can deny they submitted their bids.
4.4.6.Soundness
As the number of biddable prices is finite,encryption key chain must stop or break somewhere.(1)
The bidder publishes the signatures of all bidders in BB during the initial phase.All bidders check these signatures at the beginning of the opening phase.If the encryption key chain extends to p w and no winner is found,no bidder submits a positive bid in the auction,if the signature algorithm is secure.
(2)
If p r and S i are declared as contract’s price and winner.Since y i,j +1and V i,j for i =1,2,...,n and j =1,2,...,r are signed by S i ,they are generated by S i if the signature algorithm is secure.So p r and S i are contract’s price and winner.
(3)
If S i is declared as a cheater,y i ;j þ1p g D X j V i ;j ðÞand y i ;j þ1p g D R i ;j V i ;j ðÞ,the key chain must be broken at a price p j .Since y i,j +1and V i,j are signed by S i ,
they are generated by S i if the signature algorithm is secure.So S i is a cheater.5.Conclusions and future work
We have designed and implemented an automated reverse auction agent system whereby a mobile agent substitutes for a buyer efficiently in mobile com-merce.All the heavy computation is performed in the fixed network.A mobile agent mechanism reduces user operations and network load.The user does not need to be connected during the auction.The buyer agent serves to implement the coordination of bids across multiple sellers’bid agent sites.A new double encryption key chain technique is proposed,so that stronger bid privacy can be achieved in the proposed RV AP auction protocol.This protocol can achieve non-interaction,public verifiability and unconditional privacy for losing bids at the same time.In RV AP protocol,the dishonest bidders can be identified,unenrolled,but it is necessary to rewind the auction.The advantages of our RVAP protocol are that collusion is difficult and losing bidder can have his own bid unrevealed.In Our MoRAAS,all the heavy computations are performed in the fixed network,by the CallBuyApplication,the CallSellApplication and the agent platform,and do not overload the mobile device.It also does not overload the communication channel,because it imposes small data traffic between the mobile device and the fixed network.Due to the growing number of cellular phones and PDAs,more and more people desire to perform activities using them.One of these activities is mobile commerce (m-commerce),where a user can buy a product or service no matter where he is.In Our MoRAAS,buyer can use mobile device so the auction can take place everywhere and anytime.Therefore,deploying part of MoRAAS into wireless devices results in a greater profit than in the wire Internet environment.
In some auction sites,there are systems where buyers can evaluate sellers [25].A buyer can nominate new sellers for themselves in reverse auctions.Whenever a buyer evaluates a certain seller negatively,the seller’s utility is decreased.This evaluation function may accompany our proposed model easily.Our future work includes extending the RV AP auction protocol to cases where group buying
[1]G.Weis,Multi-agent Systems:A Modern Approach to
Distributed Artificial Intelligence,MIT Press,Cambridge, MA,1999.
[2]R.P.McAfee,J.McMillan,Auctions and bidding,Journal of
Economic Literature25(1987)699–738.
[3]P.R.Milgrom,R.J.Weber,A theory of auctions and
competitive bidding,Econometrica50(1982)10–1122. [4]W.Vickrey,Counter speculation,auctions,and competitive
sealed tenders,Journal of Finance16(1)(1961)8–37. [5]T.Sandholm,Q.Huai,Nomad:mobile-agent system for an
internet-based auction house,IEEE Internet Computing(2000) 80–86.
[6]E.Steinmetz,J.Collins,S.Jamison,R.Sundarewara, B.
Mobasher,M.Gini,Bid evaluation and selection in the MAGNET automated contracting system,First International Workshop on Agent Mediated Electronic Trading AMET-98, 1998,pp.105–125.
[7]M.K.Franklin,M.K.Reiter,The design and implementation of
a secure auction service,IEEE Transactions on Software
Engineering22(5)(1996)302–312.
[8]M.Harkavy,J.D.Tygar,H.Kikuchi,Electronic auctions with
private bids,Proceedings of the3rd USENIX Workshop on Electronic Commerce,1998,pp.61–74.
[9]H.Kikuchi,(M+1)st-price auction protocol,Proceedings of
Financial Cryptography(FC2001),2001.
[10]H.Kikuchi,S.Hotta,K.Abe,S.Nakanishi,Resolving winner
and winning bid without revealing privacy of bids,Proceed-ings of the International Workshop on Next Generation Internet(NGITA),2000,pp.307–312.
[11]Yuji Watanabe,Hideki Imai,Reducing the round complexity
of a sealed-bid auction protocol with an off-line ttp,STOC 2000,ACM,2000,pp.80–86.
[12]Masayuki Abe,Koutarou Suzuki,M+1-st price auction
using homomorphic encryption,Public Key Cryptology
2002,Lecture Notes in Computer Science,vol.2288, 2002,pp.115–124.
[13]Koji Chida,Kunio Kobayashi,Hikaru Morita,Efficient sealed-
bid auctions for massive numbers of bidders with lump comparison,Information Security,4th International Confer-ence,ISC2001,Lecture Notes in Computer Science,vol.
2200,Springer-Verlag,Berlin,2001,pp.408–419.
[14]Hiroaki Kikuchi,(m+1)st-price auction,The Fifth Interna-
tional Conference on Financial Cryptography2001,Berlin, February,Lecture Notes in Computer Science,vol.2339, 2001,pp.291–298.
[15]Kazumasa Omote,Atsuko Miyaji,A second-price sealed-bid
auction with the discriminant of the p-th root,Financial Cryptography2002,Berlin.
[16]K.Sako,An auction scheme which hides the bids of losers,
Public Key Cryptology2000,Berlin,Lecture Notes in Computer Science,vol.1880,2000,pp.422–432.
[17]Koutarou Suzuki,Kunio Kobayashi,Hikaru Morita,Efficient
sealed-bid auction using hash chain,International Confer-ence on Information Security and Cryptology2000,Lecture Notes in Computer Science,vol.2015,Springer-Verlag, 2000,pp.183–191.
[18]T.Saijo,M.Une,T.Yamaguchi,Dango experiments,Journal of
the Japanese and International Economics10(1)(1996)1–11.
[19]Y.Baba,A.Mineika,Auctions for Privatization(in Japanese),
Financial Review,Policy Research Institute of the Ministry of Finance Japan,vol.53,2000,pp.46–61.
[20]T.Matsuo,T.Ito,A designated bid reverse auction for agent-
based electronic commerce,LNAI2358(2002)460–469. [21]A.Kajii,A.Matsui,Microeconomics:strategic approaches,
Nippon Hyoronsha(2000)113–115.
[22]K.Sako,Universary verifiable auction protocol which hides
losing bids,Proc.of SCIS’99(in Japanese),1999,pp.35–39.
[23]K.Sako,An auction protocol which hides bids of losers,Proc.
of PKC’2000(2000)422–432.
[24]P.Paillier,Public key cryptosystem based on composite
degree residuosity classes,Eurocrypt’99,Lecture Notes in Computer Science,vol.1592,Springer-Verlag,Berlin,1999, pp.223–238.
[25]J.McMillan,Dango:Japan’s price-fixing conspiracies,Eco-
nomics and Politics3(1991)201–218.
Dong-Her Shih received his PhD degree in
Electrical Engineering from the National
Cheng Kung University,Taiwan,in1986.
He has been a senior Associate Professor in
the Department of Information Manage-
ment,National Yunlin University of Science
and technology,Douliu,Yunlin,Taiwan,
since1991.He is the Chair of the Depart-
ment of Information Management during
1991–1994and Director of the Computer
Center during1997–2002.His current researches include network security,intrusion detection,wireless network,neural network and peer-to-peer network.
Shin-Yi Huang received his MS degree in
Information Management from National
Yunlin University of Science and Technol-
ogy,Douliu,Yunlin,Taiwan,in2004.His
current interests include E-commerce secur-
ity and mobile agent.
David C.Yen is a professor of MIS and
Chair of the Department of Decision Scien-
ces and Management Information Systems
at Miami University.He received a PhD in
MIS and Master Sciences in Computer
Science from the University of Nebraska.
Professor Yen is active in research,he has
published three books and many articles
which have appeared in Communications of
the ACM,Decision Support Systems,Infor-
mation&Management,International Jour-nal Information Management,Information Sciences,Journal of Computer Information Systems,Interfaces,Telematics and Infor-matics,Computer Standards and Interfaces,Information Society, Omega,International Journal of Organizational Computing and Electronic Commerce,Communicaitons of AIS,and Internet Research,among others.He was also one of the co-recipients for a number of grants such as Cleveland Foundation(1987–1988),GE Foundation(19),and Microsoft Foundation
(1996–1997).
D.-H.Shih et al./Computer Standards&Interfaces27(2005)383–395395下载本文
