Slide #1 (Goals the System)
  We would like our system to achieve standard security properties
  (ensure correct determination  of the winning bidder, ensure
  accountability), support 
  anonymity, and support privacy (we are willing to reveal the winning
  bid, but nothing else). With respect to the identities of the bidders,
  they can use pseudonyms. We would also like to support
  alternative auction styles. Franklin and Reiter's proposal supported
  first price sealed-bid auctions. But there are other styles:
  English, Dutch (a 
  descendent version of English, where somebody stands up and says
  "I will take it", as the price descends), and second price
  sealed-bid auction, which is closer to what we are doing. 

Slide #2 (Overview of Structure)
  In our proposal, bidders can use pseudonyms. Also, we have a
  collection of auctioneers, with distributed trust. This is similar,
  in many ways, to the Franklin and Reiter proposal, or other
  electronic commerce protocols. The bids are simply "yes" or "no" to
  proposed values. 

  In our proposal, many rounds may be aggregated as a batch, for
  efficiency reasons. 

Slide #3 (Submitting Bids)
  Bidders can submit their bids via 
  Shamir-style secret sharing or some slight modification of that. The
  auctioneers, as before, would compute the sums, and would need to
  cooperate to get the bids. At any point, if there is only one
  bidder, then he or she can claim the goods; if there are multiple
  bidders, then none of them can. And of course, ties are possible. 

Slide #4 (Breaking Ties 1)
  All bidders submit bids and anti-bids. An anti-bid is the opposite
  of a bid. It is 0 if you are not bidding, and non-zero if you
  are. The reason we have the anti-bids is efficiency. 

  As before, one can submit zero or non-zero bids, and a submission
  can be verified: nobody can submit inconsistent bids and anti-bids. 

  And in the case of breaking ties, we are going to do a binary search
  on an array of values, representing bidders, some of whom want the
  goods, and some of whom don't. (The auctioneers are the only ones
  that know about a tie; the bidders themselves do not necessarily
  know about it.)

  (Slide #7 shows concretely what is being referred to. The aquamarine
  color represents bidders that are not interested in bidding, and
  blue represents those that are. And we do a binary search to find
  the winner.)

  We randomly permute the array of bidders, so that there is a
  fairness condition. 

Slide #5 (Breaking Ties 2)
  Given a permutation of the array of bidders, we find the winning
  bidder the following way. Let A be the sum of the bids of first
  half, B be the product of the anti-bids of the second half (we are
  simply permuting simple logic 
  gates), and C be the distributed coin. C is a shared secret, just
  as A and B are, and is zero half of the time, and non-zero the other
  half of the time. We compute A + BC. Again, we are simply
  performing very simple logic, but we are doing it in a secret
  sharing environment. 

Slide #6 (Breaking Ties 3)
  Since A is the sum of the bids of the first half, it is zero when no
  one in the first half bids. And B is zero when someone in the second
  half bids. In case B is non-zero, AC + B is also non-zero (with
  very high probability). There is a chance that AC might be equal to
  B, but since we are working with enormous numbers, that probability
  is negligible. In this case, we will select the first half. And that
  is exactly what we want to do because no one in the second half
  wanted the object. 

  If B is zero, then AC + B is just AC. And if A is zero, then AC is
  zero, and we select the second half. Note that we have to select the
  second half, in this case, because (A = 0) means that no one in the
  first half wants the object. 

  And if A is different from zero, then AC is zero exactly when C is
  zero. This corresponds to our coin flipping. 

Slide #7 (Searching for a Bidder)
  This slide shows that if both halves have non-zero bidders, then the
  protocol select either one with equal probability. The reason we are
  doing this is that 
  we want to reveal as little information as possible about, for
  example, the number of bidders who are tied. 

Slide #8 (Bidder Accountability)
  We made the bidders's shares non-repudiable, and the collection of
  shares will prove the bid. So once we decide who is supposed to win,
  we can verify if he or she actually bid on the object. The
  bids and tie-breaks use the same information, but you can not submit
  the bid and decide to do something else with the tie-break. You need
  to be consistent. 

  We would like to apply some of the same ideas to verifiable secret
  sharing, and possibly verifiable signature sharing. 

Slide #9 (Current and Future Work)
  Future work includes implementation details, improving efficiency,
  achieving perfect zero-knowledge for ties (currently, it is
  extremely limited knowledge), and implementing verifiable and/or
  threshold secret sharing.