Skip to main content
Article
A NOVEL APPROACH TO FULLY PRIVATE AND SECURE AUCTION: A SEALED-BID KNAPSACK AUCTION
International Journal of Research and Reviews in Applied Science (2011)
  • Maged Ibrahim, Helwan University
Abstract
In an electronic auction protocol, the main participants are the seller, a set of trusted auctioneer(s) and the set of bidders. In this paper we consider the situation where there is a seller and a set of n bidders intending to come to an agreement on the selling price of a certain good. Full private or bidder-resolved auction means that this agreement is reached without the help of trusted parties or auctioneers. Therefore, only the seller and the set of bidders are involved, the role of the auctioneers becomes obsolete in this case. We propose a new – simple and secure – technique for the design of a full private sealed-bid auction protocol. We employ the well known mathematical proposition, the knapsack problem which was used by Merkle and Hellman [1] in the design of their asymmetric public-key knapsack trapdoor cryptosystem. Up to our knowledge, the knapsack problem has not been considered before in the design of electronic auctions. We also employ an efficient (1-out-of-k) oblivious transfer of strings for secure data transfer between the seller and the bidders (e.g., [2]). At the end of the protocol, the seller knows the set of prices selected by the bidders, yet he doesn't know which bid belongs to which bidder until the winning bidder announces himself and proves his case by opening a secret code corresponding to the highest price. Our protocol is a 1st price and automatically a 2nd price auction as well, since the winning bidder can pay the 2nd highest price – indicated by a flag – according to the public auction predefined rules. We give the protocol for honest but curious participants then we show how to detect malicious behavior of the participants by employing a one way function with a suitable homomorphic property.
Keywords
  • Electronic auction,
  • Sealed-bid auction,
  • Knapsack problem,
  • Secret sharing,
  • Oblivious transfer
Disciplines
Publication Date
November, 2011
Citation Information
Maged Ibrahim. "A NOVEL APPROACH TO FULLY PRIVATE AND SECURE AUCTION: A SEALED-BID KNAPSACK AUCTION" International Journal of Research and Reviews in Applied Science Vol. 9 Iss. 2 (2011) p. 260 - 269
Available at: http://works.bepress.com/maged-hamada-ibrahim/13/