Auctions have a long history and are an effective method to distributed resources. In the era of Internet and e-commerce, electronic sealed-bid auction play an important role in business. However, it is a risk to run a sealed-bid auction through the Internet, which is an open and unreliable environment. There are many security concerns about correctness and fairness of the auction and privacy of the bidders in electronic sealed-bid auctions. Cryptology seems to be the only security solution for electronic sealed-bid auction. On the other hand, a practical electronic sealed-bid auction scheme must be efficient. So efficient application of cryptographic tools to electronic sealed-bid auction is the focus of this thesis. Firstly, security requirements of sealed-bid auctions are surveyed. The auction result must be determined correctly according to the submitted bids and the pre-defined auction rule. The bidders must compete with each other in a fair play and none of them can take advantage of others. The auction must be publicly verifiable, so that the auction result is acceptable by everyone. Usually, a losing bidder hopes to keep his bid secret, so the losing bids should be kept secret. In different applications, different auction rules may be applied. So, to avoid a tie, a large number of biddable prices must be accepted in some applications. Secondly, the currently known sealed-bid auction schemes are classified. In recent years, many sealed-bid auction schemes based on various cryptographic primitives have been proposed. Nearly all of them can be classified into five models. In the Model 1, each bid is known to the auctioneers, who can find the winning bid and winner very efficiently. Bid privacy is not implemented in Model 1. In Model 2 homomorphic bid opening is employed, so that the winning bid and winner can be found while the losing bids are kept secret. In Model 3 very strong bid privacy is achieved through a Dutch-style bid opening, which is highly inefficient. In Model 4, the link between the bids and bidders instead of confidentiality of the bids is kept secret. This kind of confidentiality is weaker than normal bid privacy and called relative bid privacy in this thesis. (Complete confidentiality of the bids in the end of the auction is called absolute bid privacy.) Implementation of relative bid privacy can be very efficient if an efficient anonymous channel can be constructed. Model 5 uses secure evaluation to open the bids and find the auction result and makes it possible to achieve absolute bid privacy efficiently. Three main cryptographic primitives are explored and employed to design new auction schemes in four auction models. The first tool is batch verification, which can improve computational efficiency in auction schemes. The second is mix network, which can be used to implement anonymous channels in Model 4 and Model 5. Two new efficient mix networks are designed and used in Model 2, Model 4 and Model 5. The third is secure evaluation, which is employed in two new auction schemes in Model 5 to achieve strong bid privacy efficiently. Other cryptographic primitives employed in the auction schemes include efficient 1-out-of-w oblivious transfer in Model 2 and key chain in Model 3. Five new auction schemes are proposed. The first scheme in Model 2 batch verifies bid validity to improve efficiency. The second scheme optimises the key chain used in Model 3 to obtain a more advanced auction scheme. The third scheme implements a concrete anonymous channel in Model 4 for the first time and achieves relative bid privacy and high efficiency convincingly. The last two employ new secure evaluation techniques to achieve absolute bid privacy and high efficiency. With these five new auction schemes, better solutions are achieved in various auction applications.
