Analysis and Design of Secure Sealed-Bid
Auction
by

Kun Peng
Bachelor of Engineering in Computer Software (Huazhong University of Science
and Technology, Wuhan, China) – 1997
Master of Engineering in Computer Software and Theory (Huazhong University
of Science and Technology, Wuhan, China) – 2000

Thesis submitted in accordance with the regulations for
Degree of Doctor of Philosophy

Information Security Research Centre
Faculty of Information Technology
Queensland University of Technology


ii


QUEENSLAND UNIVERSITY OF TECHNOLOGY
DOCTOR OF PHILOSOPHY THESIS EXAMINATION

CANDIDATE NAME:

Kun Peng

CENTRE/RESEARCH CONCENTRATION:

Information Security Research Centre

PRINCIPAL SUPERVISOR:

Associate Professor Colin Boyd

ASSOCIATE SUPERVISOR(S):

Professor Ed Dawson

THESIS TITLE:

Analysis and Design of Secure Sealed-Bid Auction

Under the requirements of PhD regulation 9.2, the above candidate was examined orally
by the Faculty. The members of the panel set up for this examination recommend that
the thesis be accepted by the University and forwarded to the appointed Committee for
examination.
Name: .Associate
. . . . . . . . . .Professor
. . . . . . . . .Colin
. . . . . .Boyd
. . . . . . . . . . . . . . . . . . Signature . . . . . . . . . . . . . . . . . . . . . . . .
Panel Chairperson (Principal Supervisor)
Name: .Professor
. . . . . . . . . xxxx
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Signature . . . . . . . . . . . . . . . . . . . . . . . .
Panel Member
Name: .Dr.
. . . .xxxxxxx
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Signature . . . . . . . . . . . . . . . . . . . . . . . .

Panel Member
Under the requirements of PhD regulation 9.15, it is hereby certified that the thesis of
the above-named candidate has been examined. I recommend on behalf of the Thesis
Examination Committee that the thesis be accepted in fulfilment of the conditions for the
award of the degree of Doctor of Philosophy.
Name .Professor
. . . . . . . . . xxxxxxxx
. . . . . . . . . . . . . . . . . . . Signature . . . . . . . . . . . . . . . . . . . . . . Date . . . . . . . . . . .
Chair of Examiners (Thesis Examination Committee)



Keywords
Electronic Sealed-Bid Auction, Bid Privacy, Relative Bid Privacy, Batch Verification, Mix Network, Secure Evaluation, High Efficiency

i


ii


Abstract
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 predefined 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
iii


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.

iv


Contents
Keywords

i

Abstract

iii

Declaration

xv

Previously Published Material


xvii

Acknowledgements

xix

Notation

xxi

1 Introduction
1.1 Aims and Objectives . . . . . . . . . . . . . . . . . . . . . . . . .

1
2

1.2 Contributions and Achievements . . . . . . . . . . . . . . . . . . .
1.3 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . .

3
4

2 Sealed-Bid Auction
2.1 What Is A Sealed-Bid E-Auction? . . . . . . . . . . . . . . . . . .

7
7

2.2 Requirements of a Sealed-Bid Auction . . . . . . . . . . . . . . .
2.2.1 Basic Requirements . . . . . . . . . . . . . . . . . . . . . .


11
11

2.2.2 Advanced Requirements . . . . . . . . . . . . . . . . . . .
2.2.3 Receipt-Freeness, A Misused Concept in Auction . . . . .
2.3 Classification of Bid Privacy . . . . . . . . . . . . . . . . . . . . .

13
14
17

2.4 Classification of Sealed-bid Auctions . . . . . . . . . . . . . . . .
2.4.1 Model 1: Auction with Simple Encryption . . . . . . . . .

19
20

2.4.2
2.4.3
2.4.4

Model 2: Auction with Homomorphic Bid-Opening . . . .
Model 3: Auction with Downward Search . . . . . . . . . .
Model 4: Auction with Relative Bid Privacy . . . . . . . .
v

21
23
25



2.4.5 Model 5: Auction by Secure Evaluation . . . . . . . . . . .
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Cryptographic Tools

26
27
31

3.1 Encryption Algorithms . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 ElGamal Encryption . . . . . . . . . . . . . . . . . . . . .

31
32

3.1.2 RSA Encryption . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Paillier’s Public Key Encryption Scheme . . . . . . . . . .
3.2 Secret Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32
32
33

3.2.1
3.2.2

Shamir’s Threshold Scheme . . . . . . . . . . . . . . . . .
Verifiable Secret Sharing . . . . . . . . . . . . . . . . . . .


33
33

3.2.3 Verifiable Secret Sharing for Auction Schemes . . . . . . .
3.3 Distributed Decryption . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Distributed ElGamal Decryption . . . . . . . . . . . . . .

34
36
36

3.3.2
3.3.3

Distributed RSA Decryption . . . . . . . . . . . . . . . . .
Distributed Paillier Decryption . . . . . . . . . . . . . . .

37
37

3.4 Knowledge Proof Techniques . . . . . . . . . . . . . . . . . . . . .
3.4.1 Three-Move Σ Proof . . . . . . . . . . . . . . . . . . . . .
3.4.2 Proof of Knowledge of Logarithm . . . . . . . . . . . . . .

38
38
40

3.4.3
3.4.4

3.4.5

Proof of Equality of Logarithms . . . . . . . . . . . . . . .
Proof of Knowledge of 1-out-of-k Logarithm . . . . . . . .
Proof of 1-out-of-k Equality of Logarithms . . . . . . . . .

40
41
41

3.4.6
3.4.7

Proof of Knowledge of Root . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .

42
42

3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4 Batch Verification Techniques
4.1 Development of Batch Verification Technology . . . . . . . . . . .
4.2 New Batch Verification Techniques . . . . . . . . . . . . . . . . .

45
45
49


4.2.1
4.2.2

Batch Verification of Knowledge of Logarithm . . . . . . .
Batch Verification of Equality of Logarithms of Common

50
52

4.2.3

Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Batch Verification of Equality of Logarithms of Common
Exponent . . . . . . . . . . . . . . . . . . . . . . . . . . .
Batch Verification with Strict Assumption . . . . . . . . .
Batch Verification with Loose Assumption . . . . . . . . .

54
55

vi

53


4.2.4 Batch Verification of Knowledge of Root . . . . . . . . . .
4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Mix Networks


61

5.1 Definition of Mix Network . . . . . . . . . . . . . . . . . . . . . .
5.2 Classification of Mix Networks . . . . . . . . . . . . . . . . . . . .
5.2.1
5.2.2
5.2.3

57
59

62
63

Decryption Chain or Re-encryption . . . . . . . . . . . . .
General or Separate Verification . . . . . . . . . . . . . . .
Tag Attached to Input . . . . . . . . . . . . . . . . . . . .

63
65
68

5.2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 A New Mix Network with General Validity Verification . . . . . .

68
69

5.3.1
5.3.2

5.3.3

The Current Mix Networks with General Validity Verification 70
The New Mix Network . . . . . . . . . . . . . . . . . . . . 72
Analysis and Summary . . . . . . . . . . . . . . . . . . . . 74

5.4 A New Mix Network with Separate Verification . . . . . . . . . .
5.4.1 The Current Mix Networks with Separate Verification . . .
5.4.2
5.4.3

76
77

Improvement on the Naive Verification Technique . . . . .
A New Mix Network with Separate Verification . . . . . .
Group Shuffling . . . . . . . . . . . . . . . . . . . . . . . .

78
81
82

Batched Group-shuffling Mix Network . . . . . . . . . . .
Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Correctness Analysis . . . . . . . . . . . . . . . . . . . . .

86
88
88


Other Properties . . . . . . . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .

90
93

5.5 Batch Verification of Decryption Validity in Mix Networks . . . .
5.5.1 Batch Verification of ElGamal Decryption . . . . . . . . .
5.5.2 Batch Verification of Distributed RSA Decryption . . . . .

94
94
95

5.4.4

5.5.3
5.5.4

Batch Verification of Distributed Paillier Decryption . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .

97
98

5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

6 Secure Evaluation

101
6.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.2 Preliminary Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.1

Verification of Paillier Encryption . . . . . . . . . . . . . . 105
Proof of Knowledge of N th Root modZN∗ 2 . . . . . . . . . 105
vii


6.2.2

Proof of Knowledge of 1-out-of-2 N th Root modZN∗ 2 . . . . 107
Modified ElGamal Encryption . . . . . . . . . . . . . . . . 108

6.3 A New General Purpose Secure Evaluation: SE-1 . . . . . . . . . 109
6.3.1 A Building Block — Zero Test . . . . . . . . . . . . . . . . 110

6.3.2

Simple Zero Test . . . . . . . . . . . . . . . . . . . . . . . 110
Complex Zero Test . . . . . . . . . . . . . . . . . . . . . . 112
New Secure Evaluation Technique . . . . . . . . . . . . . . 113
Two Special Formats . . . . . . . . . . . . . . . . . . . . . 114
Secure Evaluation in F-1 . . . . . . . . . . . . . . . . . . . 116

6.3.3

Secure Evaluation in F-2 . . . . . . . . . . . . . . . . . . . 116
Application of SEF-1 and SEF-2 . . . . . . . . . . . . . . . 117

Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.3.4 An Application Example . . . . . . . . . . . . . . . . . . . 119
6.4 A New Special Purpose Secure Evaluation Technique — SE-2 . . 121
6.4.1
6.4.2

6.4.3

Proof Primitive . . . . . . . . . . . . . . . . . . . . . . . . 122
Ciphertext Comparison . . . . . . . . . . . . . . . . . . . . 125
Bit Encryption and its Validity Verification . . . . . . . . 126
The Comparison Function . . . . . . . . . . . . . . . . . . 127
Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

6.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7 Auction with Homomorphic Bid-Openings
135
7.1 Homomorphic Bid Opening . . . . . . . . . . . . . . . . . . . . . 135
7.2 Verification of Bid Validity — Inefficient but Necessary . . . . . . 136
7.3 Implementation of Verification of Bid Validity . . . . . . . . . . . 138
7.3.1 A Special Bid Format Suitable for Verification . . . . . . . 138
7.3.2
7.3.3

Validity verification with homomorphic secret sharing . . . 139
Validity verification with ElGamal encryption . . . . . . . 140

7.3.4 Validity verification with Paillier encryption . . . . . . . . 141

7.4 Batch Verification of Bid Validity . . . . . . . . . . . . . . . . . . 141
7.4.1 1-out-of-w Oblivious Transfer . . . . . . . . . . . . . . . . 143
7.4.2

Batch Verification of Bid Validity in Homomorphic Secret
Sharing Auction . . . . . . . . . . . . . . . . . . . . . . . . 145

7.4.3
7.4.4

Batch Validity Verification with ElGamal Encryption . . . 146
Batch Validity Verification with Paillier Encryption . . . . 147
viii


7.4.5
7.4.6

Security Analysis . . . . . . . . . . . . . . . . . . . . . . . 148
Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . . 149

7.4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
8 Auction with Downward Search

153

8.1 Bid Privacy in Dutch-style Sealed-bid Auction . . . . . . . . . . . 153
8.2 Key Chain and its Application to Protect Bid Privacy . . . . . . . 154
8.2.1 Key chain . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

8.2.2
8.2.3

The Scheme by Watanabe and Imai . . . . . . . . . . . . . 155
Problems in the Scheme by Watanabe and Imai . . . . . . 156

8.3 A Modified Key Chain and its Application to Auction . . . . . . . 158
8.4 Analysis of the New Auction Scheme . . . . . . . . . . . . . . . . 162
8.4.1 Security of the New Auction Scheme . . . . . . . . . . . . 162
8.4.2 Efficiency Comparison . . . . . . . . . . . . . . . . . . . . 165
8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
9 Auctions with Relative Bid Privacy
167
9.1 A Trade-off between Bid Privacy and Other Properties in Auction 167
9.2 Implementation of the auction scheme . . . . . . . . . . . . . . . 169
9.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
9.3.1
9.3.2
9.3.3

Security Analysis . . . . . . . . . . . . . . . . . . . . . . . 172
Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . . 173
Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 174

9.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
10 Auctions by Secure Evaluation
177
10.1 A New Auction Scheme in Model 5 — Auction 4 . . . . . . . . . . 178
10.1.1 The Auction Protocol . . . . . . . . . . . . . . . . . . . . 178
10.1.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

10.2 Another New Auction Scheme in Model 5 — Auction 5 . . . . . . 181
10.2.1 The auction Protocol . . . . . . . . . . . . . . . . . . . . . 181
10.2.2 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . 183
10.3 Efficiency Optimisation . . . . . . . . . . . . . . . . . . . . . . . . 185
10.3.1 Binary Mix . . . . . . . . . . . . . . . . . . . . . . . . . . 185
10.3.2 The Bid Validity Verification Function . . . . . . . . . . . 186

ix


10.4 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
10.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11 Conclusion and Future Directions

191

11.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . 191
11.1.1 Results of the Survey of Sealed-bid Auction . . . . . . . . 192
11.1.2 Original Cryptographic Primitives . . . . . . . . . . . . . . 193
11.1.3 New Auction Schemes . . . . . . . . . . . . . . . . . . . . 194
11.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Bibliography

198

x


List of Figures
2.1 Auction with Simple Encryption . . . . . . . . . . . . . . . . . . .

2.2 Auction Homomorphic Bid-Opening . . . . . . . . . . . . . . . . .

21
22

2.3 Auction with Downward Search . . . . . . . . . . . . . . . . . . .
2.4 Auction with Relative Bid Privacy . . . . . . . . . . . . . . . . .
2.5 Auction by Secure Evaluation . . . . . . . . . . . . . . . . . . . .

24
25
27

4.1 Bellare’s Batch Verification of Exponentiations with a Common Base 48
5.1 Mix Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

5.2 Decryption-chain Mix Network . . . . . . . . . . . . . . . . . . . .
5.3 Re-encryption Mix Network . . . . . . . . . . . . . . . . . . . . .
5.4 General Verification Mix Network . . . . . . . . . . . . . . . . . .

64
64
66

5.5 Separate Verification Mix Network . . . . . . . . . . . . . . . . .
5.6 Grouping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

84

6.1 Proof of Knowledge of N th Root . . . . . . . . . . . . . . . . . . . 106
6.2 Proof of Knowledge of 1-out-of-2 N th Root . . . . . . . . . . . . . 108
6.3 Combined Proof of Equality of Exponent and Knowledge of N th
Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.1 Simple Batch Verification with Secret Sharing . . . . . . . . . . . 142
7.2 Batch Verification with Secret Sharing . . . . . . . . . . . . . . . 145
7.3 Batch Verification with ElGamal Encryption . . . . . . . . . . . . 147
7.4 Batch Verification of Validity with Paillier Encryption . . . . . . . 148
8.1 Modified key chain . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.2 Optimistic auction procedure . . . . . . . . . . . . . . . . . . . . 161

xi


xii


List of Tables
1
2

Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii
Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii

2.1 Trust and bid privacy . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Properties and efficiency of current auction schemes . . . . . . . .

19

28

4.1 Efficiency improvenment by batch verification . . . . . . . . . . .

60

5.1 Classification of mix networks . . . . . . . . . . . . . . . . . . . .
5.2 comparison of mix networks . . . . . . . . . . . . . . . . . . . . .

69
76

5.3 Comparison of the new mix network against other mix networks .
5.4 Comparison of computation cost of shuffling verification in mix
networks in full-length exponentiations . . . . . . . . . . . . . . .

91

5.5 Example of cost of shuffling verification in mix networks . . . . .
5.6 Cost of Validity Verification . . . . . . . . . . . . . . . . . . . . .

93
98

93

6.1 Drawbacks of the currently existing secure evaluation schemes . . 105
6.2 The truth table for the example function . . . . . . . . . . . . . . 114
6.3 Partial information revelation from m1 − m2 . . . . . . . . . . . . 130
6.4 Efficiency of secure evaluation . . . . . . . . . . . . . . . . . . . . 132

7.1 Comparison of Computation Efficiency . . . . . . . . . . . . . . . 150
7.2 Comparison of Computation Efficiency . . . . . . . . . . . . . . . 151
7.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
8.1 Key generation in the scheme by Watanabe and Imai . . . . . . . 156
8.2 Bids in the scheme by Watanabe and Imai . . . . . . . . . . . . . 157
8.3 Key generation in our scheme . . . . . . . . . . . . . . . . . . . . 159
8.4 Bids in our scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.5 Efficiency comparison . . . . . . . . . . . . . . . . . . . . . . . . . 166
xiii


9.1 Comparison of Properties . . . . . . . . . . . . . . . . . . . . . . 174
9.2 Comparison of Efficiency . . . . . . . . . . . . . . . . . . . . . . . 175
9.3 Comparison of Efficiency with Example Values . . . . . . . . . . . 176
10.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
10.2 Comparison of properties . . . . . . . . . . . . . . . . . . . . . . . 187
10.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.1 Five Auction Models . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.2 Properties of the new auction schemes . . . . . . . . . . . . . . . 194
11.3 Efficiency Comparison . . . . . . . . . . . . . . . . . . . . . . . . 196

xiv


Declaration
The work contained in this thesis has not been previously submitted for a degree
or diploma at any higher education institution. To the best of my knowledge and
belief, the thesis contains no material previously published or written by another
person except where due reference is made.


Signed:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Date:. . . . . . . . . . . . . . . . . . . . . .

xv


xvi


Previously Published Material
The following papers have been published or presented contain material based on
the content of this thesis.
[1] Kun Peng, Colin Boyd, Ed Dawson, and Kapali Viswanathan. Robust, privacy protecting and publicly verifiable sealed-bid auction. In Robert H. Deng,
Sihan Qing, Feng Bao, and Jianying Zhou, editors, Information and Communications Security, 4th International Conference, ICICS 2002, Singapore,
December 9-12, 2002, Proceedings,ICICS, volume 2513 of Lecture Notes in
Computer Science, pages 147 – 159. Springer, 2002.
[2] Kun Peng, Colin Boyd, Ed Dawson, and Kapali Viswanathan. Non-interactive
auction scheme with strong privacy. In Pil Joong Lee and Chae Hoon Lim,
editors, Information Security and Cryptology - ICISC 2002, 5th International
Conference Seoul, Korea, November 28-29, 2002, Revised Papers,ICISC, volume 2587 of Lecture Notes in Computer Science, pages 407 – 420. Springer,
2003.
[3] Kun Peng, Colin Boyd, Edward Dawson, and Kapali Viswanathan. Five
sealed-bid auction models. In Australia Workshop of Information Security
2003, pages 77 – 86, 2003.
[4] Kun Peng, Colin Boyd, Edward Dawson, and Kapali Viswanathan. Efficient
implementation of relative bid privacy in sealed-bid auction. In The 4th International Workshop on Information Security Applications, WISA2003, volume
2908 of Lecture Notes in Computer Science, pages 244 – 256, Berlin, 2003.
Springer-Verlag.
[5] Kun Peng, Colin Boyd, Edward Dawson, and Kapali Viswanathan. A correct,
private and efficient mix network. In 7th International Workshop on Theory
xvii



and Practice in Public Key Cryptography, Singapore, March 1-4, PKC 2004,
volume 2656 of Lecture Notes in Computer Science, pages 439–454, Berlin,
2004. Springer-Verlag.
[6] Riza Aditya, Kun Peng, Colin Boyd, and Ed Dawson. Batch verification for
equality of discrete logarithms and threshold decryptions. In Second conference of Applied Cryptography and Network Security, ACNS 04, volume 3089
of Lecture Notes in Computer Science, pages 494–508, Berlin, 2004. SpringerVerlag.

xviii


Acknowledgements
After studying IT for ten years and learning more than sixty units in it, I suddenly
found most of the units I learnt during my bachelor and master courses have
nothing to do with my Ph.D. thesis. On the contrary, the basic knowledge about
number theory and probability theory I learnt in middle school and high school
are very helpful. Especially, the special training for the national mathematics
contest during my high school study affects my research work in the past three
years greatly. So I would firstly like to thank the excellent mathematics education
in middle school and high school in China. Especially, I have to thank my high
school mathematics teacher Li Hegui.
During my seven-year-study of computer science at HUST, several professors
taught me knowledge useful in this thesis. Professor Hong Fan taught discrete
mathematics (including set theory, group theory, ring theory, graphics theory and
logics) and an introduction unit to cryptology (which is not so systematic and
comprehensive as Introduction to Cryptology at QUT). Professor Cui Guohua
taught two units about algorithm design and analysis, which are useful in protocol design and efficiency analysis in this thesis. Associate Professor Hu Lunjun
adviced me to choose information security as my research field during my master
course. Unfortunately I forget the names of the professors teaching linear algebra

and probability theory.
During my study at ISRC, QUT, I learnt a lot of useful knowledge in cryptology in two units — Introduction to Cryptology and Advanced cryptology —
taught by Professor Ed Dawson, Dr Lauren May and Associate Professor Colin
Boyd. Another unit, Security Topics by Associate Professor Colin Boyd is also
helpful to my research.
Most importantly, I would like to thank my four supervisors. They have been
always supported me and helped me even when I made mistakes. My principal
supervisor, Associate Professor Colin Boyd is an expert in secure protocols. His
xix


direction is essential to the design and analysis of secure auction protocols in
this thesis. He can always find attacks to my original protocols and help me to
optimise them. He also taught me the basic skills for research and professional
English writing. My associate supervisor, Professor Ed Dawson is an excellent
director. He can always find promising research direction and the best way to
organise an academic paper. Dr Kapali Viswanathan gave me a lot of concrete
help in study, research and life. He did a very successful Ph.D. study at ISRC not
a long time ago. His experience in Ph.D. study is so helpful to me, that I always
regard him an a good example to follow. After Dr Viswanathan returned to India,
Dr B Lee took his place. Dr Byoungcheon Lee is an experienced researcher and
gave me many constructive advices in my research.
In the last three months of thesis writing, my parents came from China and
stayed with me. With their support and help, I can focus on my thesis. Many
other members of ISRC and IT Faculty at QUT gave me a lot of help. Dr
Greg Maitland helped me to master the usage of LATEX for academic writing.
Ms Elizabeth Hansford, Ms Christine Orme and Ms Elizabeth Lipowitz gave me
great support in my work. Mr Riza Aditya and Ms Minna Yao are good partners
in work and life.


xx


Notation
The following parameters in Table 1 are used in this thesis.
The notations used in this thesis are listed In Table 2.

xxi