Affiliations: [a] Université de Lorraine, Loria, UMR 7503, Vandoeuvre-lès-Nancy, France | [b] Inria, Villers-lès-Nancy, France | [c] CNRS, Loria, UMR 7503, Vandoeuvre-lès-Nancy, France. E-mail: jannik.dreier@loria.fr | [d] Université Grenoble Alpes, CNRS, Laboratoire Jean Kuntzmann, Grenoble Cedex 9, France. E-mail: jean-guillaume.dumas@imag.fr | [e] University Clermont Auvergne, LIMOS, Aubière Cedex, France. E-mail: pascal.lafourcade@udamail.fr
Correspondence:
[*]
Corresponding author: Jannik Dreier, Université de Lorraine, Loria, UMR 7503, F-54506 Vandoeuvre-lès-Nancy, France. E-mail: jannik.dreier@loria.fr.
Abstract: Auctions have a long history, having been recorded as early as 500 B.C. [Auction Theory, Academic Press, San Diego, USA, 2002]. Nowadays, electronic auctions have been a great success and are increasingly used in various applications, including high performance computing [Concurrency and Computation: Practice and Experience 14(13–15) (2002), 1507–1542]. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions, in particular to ensure privacy. Brandt [International Journal of Information Security 5 (2006), 201–216] developed a protocol that computes the winner using homomorphic operations on a distributed ElGamal encryption of the bids. He claimed that it ensures full privacy of the bidders, i.e. no information apart from the winner and the winning price is leaked. We first show that this protocol – when using malleable interactive zero-knowledge proofs – is vulnerable to attacks by dishonest bidders. Such bidders can manipulate the publicly available data in a way that allows the seller to deduce all participants’ bids. We provide an efficient parallelized implementation of the protocol and the attack to show its practicality. Additionally we discuss some issues with verifiability as well as attacks on non-repudiation, fairness and the privacy of individual bidders exploiting authentication problems.
