Electronic Auction ------------------ Slide 1 (Example 1 - flight ticket) Electronic auctions are taking place over the Internet. In July 1997, Lufthansa Airline auctioned air tickets over the Internet, interactively, and in real-time. Slide #2 (Example 2 - Wine) In May 1996, a wine seller in California auctioned wines electronically. One consideration is to prevent the bidders's credit card numbers from being stolen. Slide #3 (Goods sold in Online Auction) 91 auction servers have been found on the Net, and the slide shows the goods they sell. Most of the auction servers hold auctions weekly, monthly, or bimonthly. Slide #4 (Model) To discuss the issues concerning online auctions, let's consider a simple model of auction, where we have several bidders, an auctioneer, and a seller. The auctioneer is sometimes called the auction house or the auction server. In some examples, the seller can also be the auctioneer. But in our model, we want to distinguish them. Slide #5 (Problems in Online Auction) There are many issues in online auctions. Here we only point out two of them. The first problem is the iteration cost. Most auctions use the English style auction, where the auctioneer takes bids and bidders can send multiple bids until the auction is closed. It takes very long time. We call this the iteration cost. The second problem is active attacks over the Internet. Attackers can interfere the communication: they can intercept packets, and replace bids, so that they can win. Slide #6 (Sealed-bid Auction) To reduce the iteration problem, the solution is sealed-bid auction. It is a well-known technique where each bidder is allowed to bid only one time (so it can take place quickly). Also, the bid is sealed cryptographically. This slide shows an implementation of a sealed-bid auction. Three bidders have their bids. Each of them digitally signs his or her bid, encrypts it with the auctioneer's public key, and sends it to the auctioneer. The auctioneer keeps these sealed bids, and at the closing of the auction, he decrypts all of them, checks their signatures, and declares the winner. Slide #7 (Problems in Sealed-bid Auction) There are several problems with sealed-bid auctions. First of all, they depend too much on the auctioneer. The auctioneer has the advantage of knowing each bid before the closing of the auction. The question is ``Can we trust the auctioneer?'' Slide #8 (Inside Cheating) This slide shows a real example where an auctioneer was bribed to release information to other bidders. This shows that we should minimize the information the auctioneer can obtain. Slide #9 (The Sergey and Andy Attack) Sergey and Andy attack is another interesting attack. It relies on the assumption that a bidder can register multiple keys. In the case shown in the slide, Alice submits two bids using two different keys. Depending on the values of other bidders's bids, she can claim one or the other. Slide #10 (The 100-friends Attack) Let us consider another attack where a bidder is allowed to cancel his or her bid. A professor who has 100 students can have each of them bid a different value, covering, say, all possible 100 values. Let us say now that some external bidder bids $96. All the professor has to do is to tell some of his students (those that bid higher values) to cancel their bids, and tell the one that bid $97 to claim the goods. Using this strategy, he can always win. Slide #11 (Dividing Approach) Here is a checklist of desirable properties for auctions. We have seen that we should not trust an auctioneer. In addition, we would like non-repudiation to be achieved. And validity and privacy are also important. The first proposal for sealed-bid auctions is due to Franklin and Reiter. We call it the dividing approach. The realization that a single auctioneer is problematic led them to use several independent auctioneers. Their approach uses several cryptographic primitives: secret sharing, off-line digital cash, and verifiable signature sharing. Unfortunately, their solution only achieves limited anonymity. Slide #12 (Secret Sharing) This slide shows an example of a secret sharing scheme. We have three bidders and three servers. For the purpose of this discussion, let us consider bidder two. He has his bid b_2, and he also has a secret second order polynomial f_2, where his secret is used as a constant. He then sends f_2(1) to server one, f_2(2) to server two, and f_2(3) to server three. Unless all three servers cooperate, the secret can not be obtained. Slide #13 (Digital Cash - non cancelable) To achieve non-repudiation, their proposal has bidders send digital cash to the auctioneers. <$n, S_Bank($n), B_i> is the general form of a digital cash: it has a value $n, a signature made by the bank, and an identity, which will be used to prevent double spending. In the example on the slide, bidder two wins, so his payment is automatically collected through the collaboration of all three servers. Non-repudiation is achieved in this scheme, because the payment can be obtained without any assistance of the bidder. Slide #14 (Verifiable Signature Sharing) The next primitive they use is verifiable signature sharing. Let us consider a bidder with a signature s, and an auctioneer i. The bidder computes f(i), using his secret polynomial, where s, a_1 and a_2 are coefficients. And without revealing any parameters of his polynomial, he publishes g^s, g^(a_1), g^(a_2), where g is a number known by everybody. Server i can verify his share, using the identity shown in the slide, the public information, and the information he receives from the bidder. None of the parameters of the secret polynomial is needed for this verification. What we saw in slide #12 was the standard secret sharing. The difference between it and verifiable signature sharing is that the secret is a signature here. In our auction protocol, the bidder needs to divide the money in three pieces, send them to the auctioneers, and then have the pieces put together later by the auctioneers. Verifiable secret sharing allows us to do this cryptographically. But we omit the details here. Slide #15 (Our Approach - not published) Next, we would like to present our own approach. It uses multi-party computation, secret identity, and zero-knowledge interactive proofs. Slide #16 (2. Dividing 3. Multi-party) What is the difference between our approach and the previous approach? There are three differences. The biggest one is that the bids in our system are never revealed, even after the opening of the bids. Second, the style of auction. The previous approach implemented sealed-bid auctions; in our approach, we allow multiple styles. The third difference is the use of trusted auctioneers. In Franklin and Reiter's approach, multiple auctioneers are used. In our approach, we do not use trusted auctioneers; instead we use multi-party computation. Slide #17 (Overview) This slide shows the overview of our approach. First, each bidder picks their secret identity, s_A, s_B, and s_C. Then they commit their identity using a random value and a one-way function. They also participate in a multi-party computation, which will generate the identity of the winner. Nobody knows who wins, but everybody agrees the value of the highest bid. Only the winner knows he or she won. And he or she can claim the goods by secretly sending his or her identity and the random number that committed it. Slide #18 (Average Salary Problem) Now, let us examine a multi-party computation, which can be used to solve the average salary problem: how do you compute the average salary of n professors, without revealing any particular salary? Slide #19 (Mean Protocol) Let us consider three bidders. Each bidder picks three random numbers, a_1, a_2, and a_3, so that the sum is the bidder's secret identity. Bidder A sends a_2 to B, and a_3 to C. B sends b_1 to A, and b_3 to C. And so on. After this exchange, bidder A computes the subtotal of a_1, b_1, and c_1, and publishes d_1. Thus everybody knows the subtotals, and can obtain the total, by just computing the sum of d_1, d_2, and d_3. This is the mean protocol. We will extend this to yield the maximum value. Slide #20 (Willingness to Pay) The first extension is willingness to pay. It works as follows. A bidder can be asked several prices. Now let's say that he is being asked $k. If he is willing to pay, he picks three random numbers so that the sum is equal to his secret identity. Otherwise, the sum is equal to zero. Slide #21 (Basic Protocol (MAX)) Using this extension, we have a slightly modified mean protocol. The only difference is that the participants pick random numbers such that the sum is either their identity s_i or 0. Thus, the sum of all the subtotals yields the sum of the identities of those who are willing to pay that price. Slide #22 (Number of bidders) This slide shows a typical example of the behavior of the bidders. Axis y represents number of bidders, and axis x gives asking prices. Generally, the number of bidders decreases as the price gets higher. At the highest price w_3, there is no bidder to take that price, so the total must be 0. But there must be a value w_2 different from 0, where at least one bidder is willing to pay. In the graph, in the interval w_1 - w_2, there is only one bidder willing to bid. The value computed by the above algorithm must be equal to the winner's secret identity. Now, what about if there are several bidders bidding the same highest price? We will discuss this later in the presentation. Slide #23 (Validity) There is another problem: the accountability of the bidders. Any bidder can disrupt auctions by violating the protocol. There are two possibilities. For example, a bidder can pick numbers whose sum is neither 0 nor his or her identity. He or she can also give a wrong subtotal. To prevent this from happening, we develop a zero knowledge interactive proof method. Slide #24 (Zero-knowledge Interactive Proof of bidding - ZKIP) We will not present the details today, but the idea is that everybody can verify the correctness of behavior of everybody else, without revealing the bids.