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.

Voting is a fundamental decision making instrument in any consensus-based society. It is employed in various applications from student body elections, reality television shows, shareholder meetings, to national elections. With the motivation of better eciency, scalability, speed, and lower cost, voting is currently shifting from paper-based to the use of electronic medium. This is while aiming to achieve better security, such that voting result reflects true opinions of the voters. Our research focuses on the study of cryptographic voting protocols accommodating a flexible ballot structure as a foundation for building a secure electronic voting system with acceptable voting results. In particular, we search for a solution suitable for the preferential voting system employed in the Australian Federal Election. The outcomes of the research include: improvements and applications of batch proof and verication theorems and techniques, a proposed alternative homomorphic encryption based voting scheme, a proposed Extended Binary Mixing Gate (EBMG) mix-network scheme, a new threshold randomisation technique to achieve receipt-freeness property in voting, and the application of cryptographic voting protocol for preferential voting. The threats and corresponding requirements for a secure secret-ballot voting scheme are rst discussed. There are significant security concerns about the conduct of electronic voting, and it is essential that the voting results re ect the true opinions of the voters - especially in political elections. We examine and extend batch processing proofs and verifications theorems and proposed applications of the theorems useful for voting. Many instances of similar operations can be processed in a single instance using a batch technique based on one of the batch theorems. As the proofs and verications provide formal assurances that the voting process is secure, batch processing offers great efficiency improvements while retaining the security required in a real-world implementation of the protocol. The two main approaches in cryptographic voting protocols, homomorphic encryption based voting and mix-network based voting, are both studied in this research. An alternative homomorphic voting scheme using multiplicative homomorphism property, and a number of novel mix-network schemes are proposed. It is shown that compared to the mix-network approach, homomorphic encryption schemes are not scalable for straight-forward adaptation of preferential systems. One important requirement of secret-ballot voting is receipt-freeness. A randomisation technique to achieve receipt-freeness in voting is examined and applied in an ecient and practical voting scheme employing an optimistic mix-network. A more general technique using threshold randomisation is also proposed. Combination of the primitives, both the homomorphic encryption and mixnetwork approach, yields a hybrid approach producing a secure and ecient secret-ballot voting scheme accommodating a exible ballot structure. The resulting solution oers a promising foundation for secure and practical secret-ballot electronic voting accommodating any type of counting system.