Privacy Preserving Auctions based on Homomorphic Encryption and Secret Sharing

Due to the popularity of auction mechanisms in real-world applications and the increase in the awareness of securing private information, auctions are in dire need of bid-privacy protection. This dissertation research covers three privacy preserving algorithms for preserving bidder's information. The first uses homomorphic encryption in a sealed first-price auction scheme, the second uses homomorphic encryption in a VCG auction, and the third uses secret sharing techniques in a combinatorial auction without an auctioneer.;In the first algorithm, this research develops a secure multi-unit sealed-bid first-price auction scheme in which the auction is processed on the bidders' encrypted bids by a server and the final output is only known by the auctioneer. As a result, neither the auctioneer nor the server can obtain the full information of the bidders. Furthermore, the auctioneer can verify whether a winner has paid its full payment in the auction. Finally, a comprehensive analysis on the performance of the auction mechanism is conducted.;The second algorithm is a Vickrey-Clarke-Groves (VCG) scheme. This is a type of sealed-bid auction of multiple items which has good economic properties. However, VCG has security vulnerabilities, e.g. it is vulnerable to auctioneer fraud. To make VCG more practical, bid prices must be well protected. This research proposes a bidder-oriented, privacy-preserving auction scheme using homomorphic encryption where the bidders can calculate the results by themselves, and the auctioneer is able to verify the results. Compared to previous research, this scheme is more trustworthy with stronger privacy.;The third algorithm presents a secret sharing mechanism for combinatorial auctions. Combinatorial auctions impact people's daily lives in many applications. In such auctions, bidders may want to submit bids for combinations of goods but keep the bid values private. The challenge is how to protect the privacy of bidding prices and ensure data security in these auctions. This approach is to represent the price in the degree of a polynomial; thus the maximum/sum of the degree of two polynomials can be obtained by the degree of the sum/product of the two polynomials based on secret sharing. This protocol hides the information of bidders (the bid price) from the auction servers. The auctioneers can obtain their secret shares from bidders without a secure channel. Since it doesn't need a secure channel, this scheme is more practical and applicable to more scenarios. This scheme provides resistance to collusion attacks, conspiracy attacks, and passive attacks.