WIXLIB

I. Ray et al. / Decision Support Systems 39 (2005) 267–292create a customer profile. Such a profile can be usedlater for profit by the merchant or the financialinstitution in conjunction with the merchant, and thecustomer may not really want this to occur. Finally,the customer may just want his/her purchasing habitsbe not available to others (for example, the customermay be purchasing adult content over the Internet).These factors motivate us to propose an anonymousprotocol that allows the customer to use a pseudoidentity for a transaction and pay for the product insuch a manner that the merchant is prevented fromlinking a transaction to its source and the financialinstitution is prevented from linking a customer’stransaction to the corresponding product and/or themerchant.The protocol we propose has application in ecommerce environments where the products exchanged are digital in nature. The merchant sells adigital product that can be delivered to the customer inthe form of a message over a network. Some examplesof such products are daily news reports, stock quotesand trading information, digital music and movies(Apple Computer recently announced the formationof such a service for selling music over the Internet—see http://www.apple.com/music/). The customer paysfor the product also by sending a message; themessage contains some kind of a fund transfer information from one financial institution to another—forexample, electronic checks, credit cards information,etc. As mentioned earlier, fairness can be compromised very easily in such environments. This isbecause none of the participants need to have aphysically identifiable place to conduct the businessfrom. Our protocol is perfectly suitable in suchscenarios. No other protocol that we know of satisfiesall these goals.The proposed protocol is based on some of ourprevious work reported elsewhere [21]. The currentprotocol significantly extends the earlier work. Itaddresses the problem of anonymity of the customerand optionally that of the merchant by incorporating anew payment protocol. Also, it addresses the problemof failure and compromise of the trusted third party bydistributing the functionality of the third party acrossseveral entities. We organize the rest of the paper asfollows. In Section 2, we discuss some of the previousworks in fair-exchange protocols and compare themwith our approach. Section 3 lays the theoretical269foundation on which our protocol is built. We presentthe initial protocol in Section 4. The handling ofmisbehaving players is addressed in Section 5. Section 6 provides an analysis of how the protocolsatisfies the fundamental properties of e-commerceprotocols. Next, in Section 7, we describe how we canincrease the robustness of the protocol by using a setof trusted third parties rather than one single trustedthird party. Section 8 addresses the issue of anonymityof the customer. To achieve anonymity, we borrow thenotion of untraceable electronic cash from the Digicash protocol [8] and integrate the payment-by-digital-coin feature of Digicash into our protocol. Wedemonstrate in Section 10 that the new protocolsatisfies all the desirable properties of e-commerceprotocols and additionally provides anonymity to thecustomer. Finally, we conclude the paper in Section10 by addressing some of the limitations of theprotocol and describing the work in progress toaddress those issue.2. Related workPrevious work on fair-exchange schemes can beclassified under two categories: (i) gradual exchangeprotocols and (ii) third party protocols. In this section,we briefly describe some of the important works andcompare them with our work.2.1. Gradual exchange protocolsGradual exchange protocols like the ones proposedby various researchers [4,5,11,22], gradually increasethe probability of fair exchange over several rounds ofmessage exchanges. These protocols have extensivecommunication requirements and majority of the protocols assume that both the players have equal computational power.The protocol presented by Blum [5] provides amechanism by which two players can exchangesecrets. The secrets are such that they are primefactors of the players’ publicly announced compositenumbers. The two players exchange their respectivesecrets bit by bit, alternately. For each bit provided tothe adversary, a player has to prove that the bit isgood, that is, it is part of the secret. The author showshow the protocol can be used in conjunction with

270I. Ray et al. / Decision Support Systems 39 (2005) 267–292digital signatures to sign contracts and send certifiedemails.Even et al. [11] propose the notion of a 1-out-of-2oblivious transfer protocol. The authors define amessage to be a ‘‘recognizable secret message’’ if,although the receiver cannot compute the message,he/she can authenticate it once received. An oblivioustransfer of a recognizable secret message is a protocolby which a sender transfers a message to the receiverso that the latter gets the message with a probability of0.5, while for the sender, the a posteriori probabilitythat the receiver got the message is 0.5. A special caseof the oblivious transfer protocol is the 1-out-of-2oblivious transfer protocol by which the sender is ableto transfer exactly one secret out of two recognizablesecrets. Using the 1-out-of-2 protocol as the basis, theauthors propose protocols for contract signing, certified mail and coin flipping. In this protocol, like theone by Blum [5], the two the players exchange theitems one bit at a time.Ben-Or et al. [4] provide an approach in whicheach party gradually releases information that incrementally increases the probability that a fair exchangeis valid. This probability approaches one after severalrounds of message exchanges. This protocol, unlikethat proposed by Blum [5], does not require bothplayers to have equal computational power.One of the major shortcomings of the protocolsdescribed by researchers [4,5,11] is that they lack insimultaneity of the exchange, and consequently, theyare not suitable for electronic commerce systems thatexchange some value over the network—for example, digital money. If midway through the executionof any of these protocols, one of the players decide tostop the exchange, then it is possible that that playerwill hold an unfair advantage over the other player.Such midway, unilateral termination of an exchangemay be quite possible in real life. For example, thetransaction may seem profitable to a player whenviewed ex ante. However, during the course of thetransaction, some event occurs that modifies theperception of the player about the transaction. Ourprotocol, on the other hand, ensures fair exchangeeven if a player aborts midway through the transaction. Although we propose the protocol in the contextof exchange of value, the protocol can equally wellbe used for fair exchange of any other digitalcommodity.Sandholm and Lesser [22] choose a game theoreticapproach in the context of automated negotiationsystems, to motivate the players to behave fairly inthe transaction. The authors propose a leveled commitment contracting protocol that allows any player topay a penalty and withdraw from a contract due tosome unexpected event happening in the course of thetransaction. This ensures that no player has unfairadvantage over the other player at any point in theprotocol. However, the problem with this approach isthat the protocol assumes that both players behaverationally during the protocol execution. For e-commerce transactions over the Internet, this is, webelieve, too strong a requirement. Our protocol imposes no such requirement.2.2. Third party protocolsThe third party protocols, as proposed by theresearchers [9,10,13,26], each uses a trusted on-linethird party. The idea of using a trusted on-line thirdparty to obtain non-repudiation of origin and deliveryof an email message was proposed by Deng et al. [10]and Zhou and Gollmann [26]. These protocols areessentially similar. They differ in what information isexchanged and how the information gets transferredfrom one party to the other. The basic idea is asfollows. When A wants to send a message to B, Aencrypts the message with a key, and sends B theencrypted message and a trusted third party the key. Bafter submitting his proof of delivery can get the keyand read the message. In these protocols, the disputeresolution is outside the scope of the protocol. However, the protocols do specify what evidence must bestored and how they must be collected for the disputeto be resolved in a fair manner. Our work, whichaddresses the fair-exchange problem in the context ofelectronic transactions, automatically does the disputeresolution within the scope of the protocol itself andwithout requiring any human intervention.The NetBill system [9] is one of the earliest protocols to provide a complete solution to the problem ofselling and delivering electronic goods. Our approachis quite similar to the NetBill system and so we discussit in some details here. The NetBill system uses atrusted third party called the NetBill server. The NetBillserver maintains accounts for both the customer and themerchants, and is linked with conventional financial

I. Ray et al. / Decision Support Systems 39 (2005) 267–292institutions. The basic NetBill protocol is as follows.The customer requests the merchant for the price of anitem. The merchant sends the price quote. The customer then requests the merchant for the goods. Themerchant sends the goods encrypted with a key. Uponreceipt of this encrypted product, the customer suppliesthe merchant with a signed electronic purchase order.The electronic purchase order contains a segment thathas payment information. This portion is readable onlyby the NetBill server. The merchant endorses theelectronic purchase order, and forwards it to the NetBillserver together with the decrypting key. The NetBillserver debits the customer’s account and credits themerchant’s account and then sends a signed message tothe merchant that includes the result of the transactionand an encrypted receipt intended for the customer. Theencrypted receipt contains the decrypting key, and thestatus of the customer’s account after the transaction.The receipt can be read only by the customer. Themerchant forwards the encrypted message to the customer to complete the transaction. If, for some reason,the merchant does not deliver the receipt, the customergets it from the NetBill server.The goal of our protocol is similar to that of NetBill.In NetBill, a merchant who has provided a worthlessgood is detected only after the exchange occurs. Theprotocol gathers evidence during protocol execution;any dispute resolution is handled manually and isoutside the scope of the protocol. With our protocol,on the other hand, the customer can verify whether themerchant is delivering the product promised, before thecustomer actually makes the payment. The customer isguaranteed to receive the product for which he ispaying; the merchant is guaranteed to receive paymentfor the product he has sold. Thus, fair exchange isensured. Further, any dispute resolution can be handledautomatically by the trusted third party without resorting to manual intervention. The dispute resolutioninvolves both player receiving each other’s product.A fair-exchange protocol that ensures the consistency of the document has been proposed by Ketchpel[17]. The basic protocol is as follows. After agreeingupon the product and the price, the customer and themerchant sign a contract which is forwarded to thethird party. The customer sends the payment to thethird party and the merchant sends the requiredproduct to the third party. The third party verifies thatthe product and payment satisfy the terms of the271contract and then forwards the product to the customerand the payment to the merchant. Thus, the third partyplays an active role in this protocol. Our protocol, incontrast, reduces the involvement of the third party.Further, the third party in our protocol is not a sourceof bottleneck. We use multiple third parties, a coterieof which can resolve disputes and ensure fairness.Franklin and Reiter [13] also propose a set of fairexchange protocols that verify the consistency of adocument before the exchange takes place. Theseprotocols require a semi-trusted third party. A semitrusted third party is one that can misbehave on itsown but will not collude with any of the participatingparties. The protocols use a one-way function f whichhas the additional property that there exists anotherefficiently computable function F such that F(x,( f( y)) f (xy). The function, f, is known by both theparties, and F is known by the third party.The basic protocol is as follows. Suppose X and Ywish to exchange some secret information KX and KY.Before the protocol is initiated, it is assumed that Xand Y know f (KY) and f (KX), respectively. The firststep involves X sending a random number x1 (whichis in the domain of f ) to Y, and Y sending a similarrandom number y1 to X. In the second step, X sendsthe following to the third party: f (KX), f (KY), KXx1 1and f ( y1) and Y also sends the corresponding components to the third party. The third party makes somecomparisons to ascertain that each is sending thecorrect components, and then forwards KXx1 1 to Yand KY y1 1 to X. Y and X can multiply these by x1and y1 respectively to get the respective keys.One contribution of this paper is that the third partyis semi-trusted and the information that X and Y aretrying to exchange is never revealed to the third party.Our protocol, in contrast, requires the third party to betrusted. Franklin’s protocol requires an active involvement of the third party for all scenarios. We resort tothe third party only when no one misbehaves oraborts.Three fair-exchange protocols that do not require theinvolvement of the third party unless there is a problemhave been proposed by Bao et al. [3]. The first oneexchanges digital signatures on some document, thesecond one exchange signatures on two documents,and the third one exchanges a document and a signatureon the document. The important contribution of thispaper is that the authors provide a theory based on

272I. Ray et al. / Decision Support Systems 39 (2005) 267–292which each party is able to verify that the signature he isabout to receive is indeed the correct signature, beforeactually receiving the signature. However, the protocolis not general, and does not apply when both the partieswant to exchange items of some value over the networkother than digital signatures. Asokan et al. [2] alsoprovides an optimistic protocol that deals with the fairexchange of digital signatures.A more general protocol that allows exchange ofany two digital items has been proposed by Asokanet al. [1]. This protocol does not involve the thirdparty unless one of the parties behaves unfairly oraborts. The protocol begins by the two partiespromising each other an exchange of items. If theydo not agree on the terms of the exchange, theprotocol is aborted. Otherwise, the exchange takesplace. The items as well as non-repudiation tokensare exchanged. In case of any failure or any partymisbehaving, the recovery phase is initiated. Theauthors assume there is a reliable communicationchannel between each party and the third party.Hence, all the messages exchanged in the recoveryphase uses these reliable channels via the thirdparty. When any party misbehaves, the third partycan issue an affidavit which can be used in a courtof law in case of a dispute. Non-repudiation oforigin and non-repudiation of receipt is guaranteedby these protocols. The protocol always guaranteesweak fairness, that is, an honest party can prove hiscase in case of a dispute.The main similarity with our work is that the thirdparty is not invoked unless there is a problem.However, there are a number of significant differences with our work. The most significant differenceis that our protocol always ensures strong fairness,whereas the protocol proposed by Asokan et al.ensures only weak fairness. The other significantdifference is that dispute resolution is outside thescope of Asokan et al.’s protocol. The honest partycan prove his case, but how he gets compensated orthe dishonest party punished is not elaborated. In ourprotocol, the honest party is always compensated byreceiving the correct item. This is taken care of bythe protocol itself—no manual intervention is necessary. A third difference is that in Asokan’s protocolboth the parties exchange descriptions of the itembefore exchanging the items. Once an item is received, the receiving party checks whether the itemmatches the description or not. In our work, eachparty is able to verify that the item he is about toreceive is the one he expects, before exchanging theitems. Another significant difference is that anonymity of the customer is not preserved in Asokan’sprotocol. Our protocol does so. Last but not the least,in Asokan’s protocol, the third party is a source ofbottleneck; in ours, it is not.3. Theory of cross validationOur protocol uses a novel approach based on‘‘RSA like’’ cryptography to provide fair exchange.We term this approach ‘‘cross validation’’. In thissection, we establish the theory.We begin by assuming that the customer buys adigital product and pays the merchant using a digitalpayment token. (Later on, in Section 8, we show howwe modify the protocol so as to replace the paymenttoken with electronic cash.) For confidentiality as wellas integrity purposes, the digital product is encryptedwhile in transit. The customer needs to get a decryptionkey in order to decipher the encrypted product. Theencryption is assumed to be sufficiently strong that,without the decryption key, the encrypted product isuseless to the customer. The customer receives thedecryption key if and only if the merchant receivespayment for the product. Thus, in order to validate theproduct, the customer should be able to recognize thecontents of the encrypted product, without requiring todecrypt it. Note that using cryptographic checksumsdoes not solve the problem of validation. There can betwo ways checksums can be added to the deliveredproduct.1. The merchant sends a cryptographic checksum ofthe actual product (i.e. the cryptographic checksumcomputed before encryption). In this case, thecustomer has no way of ascertaining that thechecksum corresponds to the actual product without first obtaining the actual product.2. The merchant sends a cryptographic checksum ofthe encrypted product. This can at most guaranteethat the customer has received the encryptedproduct correctly, without any error. This doesnot provide any protection if the merchant sendsthe wrong product.

I. Ray et al. / Decision Support Systems 39 (2005) 267–292273With the above background information, we nowpresent the theory of cross validation.number theory (see, for example, Ref. [19]) or oncryptography (for example, Ref. [24]).5Definition 1. The set of messages M is the set of nonnegative integers m that are less than an upper boundN, i.e.Corollary 1. If 0 m N and N N1N2 . . . Nk andN1, N2, . . ., Nk are primes, then mx/(N) 1 u m mod N.MfmA0Vm N gð1ÞDefinition 2. Given an integer a and a positive integerN, the following relationship holds,a ¼ qN þ r where 0Vr N and q ¼ ta N bð2Þwhere t x b denotes the largest integer less than equal tox. The value q is referred to as the quotient and r isreferred to as the remainder. The remainder r, denoteda mod N, is also referred to as the least positiveresidue of a mod N.Definition 3. For positive integers a, b and N, we saya is equivalent to b, modulo n, denoted by a u b modn, if a mod n b mod n.Definition 4. For positive integers a, x, n and n 1, ifgcd(a, n) 1 and a.x u 1 mod n, then x is referred toas the multiplicative inverse of a modulo n.Definition 5. Two integers a, b are said to berelatively prime if their only common divisor is 1, thatis, gcd(a, b) 1.Definition 6. The integers n1, n2, . . ., nk are said to bepairwise relatively prime, if gcd(ni, nj) 1 for i p j.Definition 7. The Euler’s totient function /(N) isdefined as the number of integers that are less than Nand relatively prime to N. Below we give someproperties of totient functions that we need in thispaper.1. /(N) N 1 if N is prime.2. /(N) /(N1)/(N2). . ./(Nk) if N N1N2. . .Nk andN1, N2,. . ., Nk are pairwise relatively prime.Definition 8. A key K is defined to be the ordered pairhe, Ni, where N is a product of distinct primes, N z Mand e is relatively prime to /(N); e is the exponent andN is the base of the key K.Definition 9. The encryption of a message m with thekey K he, Ni, denoted as [m, K], is defined as½m; he; N i ¼ me mod Nð3ÞDefinition 10. The inverse of a key K he, Ni,denoted by K 1, is an ordered pair hd, Ni, satisfyinged u 1 mod /(N).Theorem 2. For any message m,½½m; K ; K 1 ¼ ½½m; K 1 ; K ¼ mwhere K he, Ni and K 1 hd, Ni.Proof of Theorem 2. We first show that½½m; K ; K 1 ¼ mL:H:S: ¼ ½½m; K ; K 1¼ ½me mod N ; K 1ðfrom Definition 9Þ¼ ðme mod N Þd mod N ðfrom Definitions 9and 10Þ¼ med mod NarithmeticÞðfrom laws of modular¼ mðx/ðNÞþ1Þ mod N ðfrom Definitions 2and 10; ed ¼ x/ðN Þ þ 1Þ¼ m mod Nðfrom Corollary 1ÞTheorem 1. Euler’s theorem states that for every aand N that are relatively prime,¼ma/ðNÞ u1 mod N N ; see Definition 1Þ¼ R:H:S:Proof of Theorem 1. We omit the proof of Euler’stheorem and refer the interested reader to any book onð4Þðsince we assume mBy symmetry [[m, K 1], K] m.5

274I. Ray et al. / Decision Support Systems 39 (2005) 267–292Corollary 2 . An encryption, [m, K], is one-to-one if itsatisfies the relationK1[If part] Given m m̂, we have to prove that [m,K2] u [m̂, K1] mod N1, that is,K2 mod N1 ¼ ½m̂; K1 mod N1½m; K1½½m; K ; K 1 ¼ ½½m; K 1 ; K ¼ mL:H:S: ¼ ½m; K1Definition 11 . Two keys K1 he1, N1i and K2 he2,N2i are said to be compatible if e1 e2 and N1 and N2are relatively prime.Definition 12

An anonymous and failure resilient fair-exchange e-commerce protocol Indrajit Raya,*, Indrakshi Raya, Narasimhamurthi Natarajanb aComputer Science Department, Colorado State University, 217 USC, 601 S Howes Street, Fort Collins, CO 80523-1873, USA bElectrical and Computer Engineering Department, University of Michigan-De