Fundamental aspects of privacy and deception in electronic auctions [Elektronische Ressource] / Felix Brandt

Felix Brandt

Sujets

• Informatik

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2003
• Nombre de lectures: 19
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Fundamental Aspects of Privacy and
Deception in Electronic Auctions
Felix BrandtInstitut fu¨r Informatik
der Technischen Universitat Munchen¨ ¨
Fundamental Aspects of Privacy and
Deception in Electronic Auctions
Felix Brandt
Vollst¨andiger Abdruck der von der Fakulta¨t fu¨r Informatik der Technischen
Universitat Munchen zur Erlangung des akademischen Grades eines¨ ¨
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr. Stefan Kramer
Prufer der Dissertation: 1. Univ.-Prof. Dr. Dr. h.c. Wilfried Brauer¨
2. Univ.-Prof. Dr. Martin Bichler
Die Dissertation wurde am 15.05.2003 bei der Technischen Universitat Mun-¨ ¨
chen eingereicht und durch die Fakult¨at fu¨r Informatik am 21.07.2003 ange-
nommen.Kurzfassung
Auktionen spielen eine wesentliche Rolle im elektronischen Handel. Regie-
rungen versteigern Lizenzen fu¨r Funkfrequenzen (wie ku¨rzlich die UMTS-
Mobilfunklizenzen), Millionen Bieter nehmen an Internet-Versteigerungen
teil und Aufgabenverteilung in Multiagentensystemen sowie Beschaffung von
WarenoderDienstleistungenfurUnternehmenerfolgenhaufigdurchAuktio-¨ ¨
nen. Diese Arbeit gliedert sich in zwei Teile. W¨ahrend sich der erste Teil mit
strategischem Bietverhalten beschaftigt, werden im zweiten Teil Aspekte der¨
Sicherheit und des Datenschutzes in Auktionen behandelt.
Es gibt Auktionsmechanismen, die bewiesenermaßen zu einer Gu¨terver-
teilung fuhren, die den Nutzen aller beteiligten Personen (Kaufer und Ver-¨ ¨
k¨aufer)maximiert,unddiestrategischesBietenu¨berflu¨ssigmachen.Umdiese
Eigenschaften zu garantieren, werden jedoch einschr¨ankende Annahmen im
zuGrundeliegendentheoretischenModellgemacht.Sowerdenbeispielsweise
Absprachen zwischen Bietern (sog. Kollusionen) oder betru¨gerische Auktio-
natoren nicht betrachtet. In der vorliegenden Arbeit wird diese Liste um
sog. antisoziale“ Agenten erg¨anzt. Das Ziel dieser Agenten ist, neben der
”
MaximierungihreseigenenNutzens,denNutzenihrerKonkurrentenzumini-
mieren.EswerdenoptimaleBietstrategienfu¨rantisozialeAgentenpr¨asentiert
unddieUnmoglichkeitderKonstruktioneinesAuktionsmechanismusgezeigt,¨
der oben genannte Grundeigenschaften in Gegenwart von mindestens einem
antisozialen Agenten aufweisen kann.
Im zweiten Teil dieser Arbeit wird der Schutz von verdeckten Geboten
¨(beispielsweise bei Ausschreibungen) untersucht. Ublicherweise wird die Ver-
traulichkeit von verdeckten Geboten durch die Zuhilfenahme eines Dritten,
demAuktionator,sichergestellt.DieRichtigkeitdesAuktionsergebnissesund
der tats¨achliche Schutz der Gebote h¨angen allerdings vollkommen von der
Vertrauenswurdigkeit dieser Instanz ab. Der Hauptbeitrag dieser Dissertati-¨
on ist die schrittweise Entwicklung von verteilten Protokollen, die Auktions-
mechanismen nachbilden ohne sich auf vertrauenswurdige Instanzen zu stut-¨ ¨
zen. Dies wird unter anderem mit ku¨rzlich entwickelten, kryptographischen
Verfahrenwie multipartycomputation“undderGrundidee,dieBestimmung
”
iii KURZFASSUNG
desAuktionsergebnissesaufdieBieterzuverteilen,erreicht.Dievorgestellten
Protokollesindsicher,unabh¨angigdavonwievieleBieterihrWissenteilen.In
einigen konnen die Gebote selbst mit unbeschranktem Rechenaufwand nicht¨ ¨
aufgedeckt werden.Acknowledgements
First of all, my sincere thanks are due to Prof. Brauer, my supervisor. With-
out the pleasant working atmosphere provided at chair VII and his uncon-
ditional support, this work would not have been possible. Moreover, his
comments greatly improved the presentation of this thesis.
I am much obliged to Prof. Bichler for interesting discussions and serving
as an additional referee. Gerhard Weiß, co-author of some joint papers and
leader of our research group, introduced me to auctions. So, in a way, he
can be made responsible for the following pages. Thanks for the exciting and
fruitful collaboration.
Many thanks have to go to my colleagues Michael Rovatsos, Klaus Stein,
and Felix Fischer for proof-reading. The most exhaustive proof-reading was
done by my girl-friend Monika. Thank you so much and sorry for countless
days (and especially nights) that I spent working on this thesis.
Thanks to my colleagues Volker Baier, Markus Holzer, Matthias Nickles,
and Stefan Romer, and former colleagues Claudia Brand, Dieter Bartmann,¨
Till Brychcy, Astrid Kiehn, Clemens Kirchmair, Barbara Ko¨nig, Alexandra
Musto, Peter Rossmanith, and Michael Sturm. They all contributed to the
convenient atmosphere mentioned above.
Moreover, I am grateful to Masayuki Abe, Ivan Damg˚ard, Hiroaki
Kikuchi, Helger Lipmaa, and James Peck for helpful emails. Further thanks
go to Marcus Martenstein from econia.
iiiiv ACKNOWLEDGEMENTSAbstract
Auctions have become a major phenomenon of electronic commerce. Gov-
ernments use auctions to sell spectrum licenses, millions of users trade goods
in Internet auctions, and task assignment in multiagent systems as well as
procurement in the “real world” is handled via auctions. The contribution
of this dissertation is two-fold. The first part addresses strategic bidding
whereas the second part deals with privacy issues.
There are auction mechanisms that have been proven to lead to alloca-
tions of goods that maximize utility among participants (bidders and sellers)
and to remove counter-speculation in the bid-preparation process. However,
the theoretical model makes several restrictive assumptions to achieve those
properties. For example, agreements between bidders (“bidder collusion”) or
untruthful auctioneers are not considered. This thesis extends this list by
adding the notion of“antisocial”agents, i.e., agents that intend to maximize
their own utility while minimizing their competitors’ utilities. We present
optimal antisocial bidding strategies and show that it is impossible to con-
struct an auction mechanism that provides the properties mentioned above
in the presence of at least one antisocial agent.
Inthesecondpartofthisthesis,theprivacyofsealed-bidauctionsisinves-
tigated. Traditionally,privacyisobtainedbyconsultingatrustedthird-party,
the auctioneer. However, the correctness of the outcome and the privacy of
bids completely depend on the trustworthiness of the auctioneer. The major
contributionofthisdissertationistheincrementaldevelopmentofdistributed
protocols that emulate auction mechanisms without relying on any trusted
party. This is achieved by applying recently developed cryptographic tech-
niques of secure multiparty computation and distributing the determination
oftheauctionoutcomeonbidders. Theproposedprotocolsaresecuredespite
any collusion of bidders. Some of them even provide partial privacy against
computationally unbounded adversaries.
vvi ABSTRACT