# Hawk and Aucitas: e-auction schemes from the Helios and Civitas e-voting schemes Adam McCarthy, Ben Smyth, Elizabeth A. Quaglia ## Abstract The cryptographic foundations of e-auction and e-voting schemes are similar, for instance, seminal works in both domains have applied mixnets, homomorphic encryption, and trapdoor bit-commitments. However, these developments have appeared independently – for example, the adoption of mixnets in e-voting preceded a similar adoption in e-auctions by over two decades – and the two research communities are disjoint. In this paper, we demonstrate a relation between e-auction and e-voting: we present Hawk and Aucitas, two e-auction schemes derived from the Helios and Civitas e-voting schemes. Our results make progress towards the unification of the e-auction and e-voting domains, thereby paving the way for developments in e-voting to be capitalised upon in the development of e-auctions. #### Keywords. Aucitas, auction, bid secrecy, Civitas, collusion resistance, Hawk, Helios, price flexibility, privacy, sealed-bid, verifiability, voting. # Introduction An *e-auction* is a process for the trade of goods and services from *sellers* to *bidders* (or *buyers*), with the aid of an *auctioneer*. We study *sealed-bid auctions* (see Brandt (Brandt 2010) for discussion of other types of auctions), which are defined as follows. First, each bidder submits a *bid* which encapsulates the *price* that the bidder is willing to pay. Secondly, the bids are *opened* to derive the *winning price*. Finally, the *winner* is *revealed*. The winning price and winner are derived in accordance with the auction’s policy, for example, in *first-price sealed-bid auctions* the winning price is the highest price bid and the winner is the bidder who bid at the winning price. We shall focus on *$M$th price sealed-bid auctions*, which generalise first-price sealed-bid auctions to sell $M$ identical items at the highest price that $M$ bidders are mutually willing to pay. For instance, in the case $M=6$, six identical items will be sold at the sixth highest price that is bid, because six bidders are mutually willing to pay this price. Such auctions are used to auction telecoms spectrum (Garside 2013), vehicles (US Government 2013b) and land (US Government 2013a), for example. An *election* is a decision-making process by which *voters* choose a *representative* from some *candidates*. We study *secret ballot elections* (see Saalfeld (Saalfeld 1995, sec. 2) for discussion of other types of election), which are defined as follows. First, each voter submits a *ballot* which encapsulates the voter’s chosen candidate (i.e., the voter’s *vote*). Secondly, all ballots are *tallied* to derive the *distribution of votes*. Finally, the representative is derived in accordance with the election’s policy, e.g., in *first-past-the-post elections* (see Lijphart & Grofman (Lijphart and Grofman 1984) for discussion of other types of policy) the representative is the candidate with the most votes. In this paper, we shall demonstrate that it is possible to derive e-auction schemes from e-voting schemes. #### Constructing e-auction schemes from e-voting schemes. Our translation from an e-voting scheme to an e-auction scheme assumes that prices can be represented as candidates, for example, an e-auction with a *starting price* of $10$, *price increments* of $5$ and a *price ceiling*[^1] of $30$ can be represented by the following five candidates: $10$, $15$, $20$, $25$ and $30$ (we refer to these values as *biddable prices*). In this setting, an e-auction proceeds as follows. First, to bid for a particular price, bidders “vote" for the candidate that represents the price that the bidder is willing to pay, for example, a bid at price $20$ is captured by a “vote" for the third candidate. Secondly, the bids are “tallied" to determine the distribution of “votes" and the winning price is derived from this distribution: the winning price is the largest price in $(10, 15, 20, 25, 30)$ for which at least $M$ bidders “voted" at or above. Finally, we link the winning price to winning bidders. This final step distinguishes our e-auction scheme from the underlying e-voting scheme and we shall see that this can be achieved in the context of secret ballot elections. ## Security properties Bidders should be able to bid in auctions without fear of repercussions; this property is known as *privacy*. Formulations of privacy depend on the environment and *bid secrecy* has emerged as a *de facto* standard privacy requirement of e-auction schemes in collusion-free environments. - **Bid secrecy**: A losing bidder cannot be linked to a price. A stronger formalisation of bid secrecy is *bidder anonymity*. - **Bidder anonymity**: Bidder identities are not revealed. Bidder anonymity is useful to hide the identities of bidders and, hence, helps prevent *bid suppression* (that is, a situation in which a conspirator asks a bidder not to submit a bid, perhaps in an attempt to eliminate competing bidders). Intuitively, bidder anonymity is stronger than bid secrecy, since losing bidders cannot be linked to prices in auctions where bidder identities are not revealed. We are also interested in *receipt freeness* and *collusion resistance*[^2] (to help prevent *bid rigging* (Zhou and Zheng 2010; Ji and Liu 2008; Hendricks and Porter 1989) by conspiring bidders), which provide privacy in hostile environments. - **Receipt freeness**: A losing bidder does not gain information which can be used to prove, to a conspirator, how they bid. - **Collusion resistance**: A losing bidder cannot collaborate with a conspirator to gain information which can be used to prove how they bid. Roughly speaking, the above properties correspond to the following properties of e-voting schemes: bid secrecy corresponds to *ballot secrecy*, bidder anonymity corresponds to a notion of *invisible absenteeism*, receipt freeness corresponds to a property with the same name, and collusion resistance corresponds to *coercion resistance* (Smyth and Bernhard 2013; Smart 2012; Backes, Hriţcu, and Maffei 2008; Delaune, Kremer, and Ryan 2009). *Verifiability* allows bidders and observers to verify that bids have been recorded and tallied correctly without trusting the system running the e-auction. The concept is intended to avoid situations whereby systems are trusted and, subsequently, discovered to be untrustworthy, thus bringing auctions into disrepute. We distinguish the following three aspects of verifiability. - **Outcome verifiability**: A bidder can check that their bid is included in the e-auction and anyone can check that the winning price is valid. - **Eligibility verifiability**: Anyone can check that all bids were submitted by registered bidders. - **Non-repudiation**: Anyone can check the winners’ identities. Outcome verifiability is a *de facto* standard requirement of e-auction schemes and eligibility verifiability is important if bidding should be restricted to registered bidders. However, eligibility verifiability typically increases complexity and reduces usability – for instance, an infrastructure for bidders’ credentials is assumed by Peng *et al.* (Peng et al. 2003) – and has been largely neglected by existing e-auction schemes. Non-repudiation prevents winners from claiming that they did not win. Roughly speaking, outcome verifiability corresponds to *individual* and *universal verifiability* properties of e-voting, and *eligibility verifiability* corresponds to a property with the same name  (Smyth 2011; Kremer, Ryan, and Smyth 2010). There is no corresponding property for non-repudiation. We are also interested in the following functional requirement. - **Price flexibility**: Bidders can submit any price. Price flexibility avoids restricting the bidding amount (although, for practical purposes, we typically assume a starting price of 1, price increments of 1, and the price ceiling to be bounded by the security parameter). Roughly speaking, price flexibility corresponds to the *write-in* property of e-voting. ## Our contribution and motivation There is an abundance of rich e-voting research which can be capitalised upon to advance e-auctions. Indeed, this statement can be justified with hindsight: Chaum (D. L. Chaum 1981) exploited mixnets in e-voting schemes twenty three years before Peng *et al.* (Peng et al. 2004) made similar advances in e-auctions (Jakobsson & Juels (Jakobsson and Juels 2000) use mixnets in a distinct manner from Chaum and Peng *et al.*), Benaloh & Fischer (Cohen and Fischer 1985) proposed the use of homomorphic encryption seventeen years before Abe & Suzuki (Abe and Suzuki 2002a), and Okamoto (Okamoto 1996) demonstrated the use of trapdoor bit-commitments six years before Abe & Suzuki (Abe and Suzuki 2002b). In this paper, we demonstrate that e-voting schemes can be used to construct e-auction schemes, thereby paving the way for developments in e-voting to be followed by advances in e-auctions. More concretely, we construct the Hawk and Aucitas $M$th price sealed-bid e-auction schemes from the Helios (Adida et al. 2009) and Civitas (Clarkson, Chong, and Myers 2008; Juels, Catalano, and Jakobsson 2005) e-voting schemes. (In addition, Appendix 7 adapts Hawk to second-price sealed-bid e-auctions.) The Helios and Civitas schemes are particularly significant, since they have both been implemented. Moreover, Helios has been used in real-world elections (e.g., (IACR 2013; Princeton 2012; Adida et al. 2009)) and Civitas is the only e-voting scheme to satisfy coercion resistance and individual, universal and eligibility verifiability. #### Hawk. In the Hawk scheme, prices are encapsulated as bids using an additively homomorphic encryption scheme and the winning price is revealed by decrypting the homomorphic combination of bids. Since individual prices are never decrypted, we have bid secrecy. Moreover, since bidders can ensure that their bid is included in the homomorphic combination and observers can check that the winning price is revealed correctly, we also have outcome verifiability. Bidder anonymity and non-repudiation are conflicting properties: non-repudiation allows the winner’s identity to be checked, whereas, bidder anonymity demands that the winner’s identity cannot be revealed. Accordingly, we propose two variants of our e-auction scheme, one satisfying non-repudiation and the other satisfying bidder anonymity. Furthermore, we implement the variant satisfying bidder anonymity. #### Aucitas. In the Aucitas scheme, prices are encrypted, mixed, and decrypted. Each encrypted price is authenticated by a bidder’s credential, however, authenticity is only checked after mixing; this facilitates the use of dummy credentials and prevents a bidder collaborating with a conspirator to prove how they bid (in essence, this is due to the indistinguishability of an encrypted price authenticated by a bidder’s credential and an encrypted price authenticated by a dummy credential, which will be rejected after mixing), thereby ensuring collusion resistance. Moreover, the credential system ensures eligibility verifiability and non-repudiation. Furthermore, outcome verifiability is derived from the mixnet. In addition, we achieve price flexibility by defining the biddable prices as $1,2,\dots,|\mathfrak m|$, where $\mathfrak m$ is the encryption scheme’s message space. Our results make progress towards the unification of e-auctions and e-voting. # Cryptographic preliminaries We adopt standard notation for the application of probabilistic algorithms $A$, namely, $A(x_1,\dots,x_n;\allowbreak r)$ is the result of running $A$ on input $x_1,\dots,x_n$ and coins $r$. Moreover, $A(x_1,\dots,x_n)$ denotes $A(x_1,\dots,x_n;r)$, where $r$ is chosen at random. We write $x\leftarrow\alpha$ for the assignment of $\alpha$ to $x$. Vectors are denoted using boldface, for example, ${\bf x}$. We write $|{\bf x}|$ to denote the length of a vector ${\bf x}$ and ${\bf x}[i]$ for the $i$th component of the vector, where ${\bf x} = ({\bf x}[1],\dots,{\bf x}[|{\bf x}|])$. We extend set membership notation to vectors: we write $x\in{\bf x}$ (respectively, $x\not\in{\bf x}$) if $x$ is an element (respectively, $x$ is not an element) of the set $\{ {\bf x}[i] : 1 \leq i \leq |{\bf x}| \}$. Let us recall the syntax for *asymmetric encryption schemes*.
An *asymmetric encryption scheme* consists of the following algorithms: - The *key generation algorithm* $\mathsf{Gen}$ takes as input the security parameter $1^k$ and outputs a public key $\mathit{pk}$, private key $\mathit{sk}$, and message space $\mathfrak{m}$. - The *encryption algorithm* $\mathsf{Enc}$ takes as input a public key $\mathit{pk}$ and message $m \in \mathfrak{m}$. It outputs a ciphertext $c$. - The *decryption algorithm* $\mathsf{Dec}$ takes as input a public key $\mathit{pk}$, a private key $\mathit{sk}$, and ciphertext $c$. It outputs a message $m$ or the special symbol $\perp$ denoting failure. Moreover, the scheme must be correct: for all $(\mathit{pk},\mathit{sk},\mathfrak{m}) \leftarrow\mathsf{Gen}(1^k)$, messages $m\in\mathfrak{m}$ and ciphertexts $c\leftarrow \mathsf{Enc}(\mathit{pk},m)$ we have $\mathsf{Dec}(\mathit{pk},\mathit{sk},c) = {m}$ with overwhelming probability. We say an encryption scheme is *homomorphic* if there exists binary operators $\oplus$, $\otimes$ and $\odot$ such that for all $(\mathit{pk},\mathit{sk},\mathfrak{m}) \leftarrow\mathsf{Gen}(1^k)$, messages $m_1,m_2\in\mathfrak{m}$ and coins $r_1$ and $r_2$, we have $\mathsf{Enc}(\mathit{pk},m_1;r_1)\otimes\mathsf{Enc}(\mathit{pk}, m_2;r_2) = \mathsf{Enc}(\mathit{pk}, m_1 \odot m_2;r_1 \oplus r_2)$. The scheme is *additive homomorphic* if $\odot$ is the addition operator or *multiplicative homomorphic* if $\odot$ is the multiplication operator.
We abbreviate the standard security notion of *indistinguishability under chosen plaintext attacks* as IND-CPA. An interactive proof system is a two party protocol between a prover and a verifier on some common input, which allows a claim of membership to be evaluated. Formally, we capture such proof systems as *sigma protocols* (Definition [def:sigmaProtocol]) and assume sigma protocols satisfy *special soundness* and *special honest-verifier zero-knowledge* (see (Bernhard, Pereira, and Warinschi 2012) for details), in addition to the standard completeness property.
A *sigma protocol* for an $\mathcal N \mathcal P$ language $\mathcal L_R$, where $\mathcal L_R=\{ s \ |\ \exists \ w \ \text{such that} \ (s,w) \in R\}$, is a tuple of algorithms $(\mathsf{Comm},\mathsf{Chal},\allowbreak\mathsf{Resp},\mathsf{Verify})$ such that: - The *commitment algorithm* $\mathsf{Comm}$ takes a statement $s$ and witness $w$ as input, and outputs a commitment comm and some state information $t$. - The *challenge algorithm* $\mathsf{Chal}$ outputs a challenge chal selected from a fixed challenge space. - The *response algorithm* $\mathsf{Resp}$ takes a challenge chal and some state information $t$ as input, and outputs a response resp. - The *verification algorithm* $\mathsf{Verify}$ takes a statement $s$ and transcript $(\textsf{comm},\allowbreak\textsf{chal},\textsf{resp})$ as input, and outputs $\top$ or $\perp$.
Our e-auction schemes are dependent upon the sigma protocols given in Definition [def:usefulSigma].
Given an asymmetric encryption scheme $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ and a sigma protocol $\Sigma$ for the language $\mathcal L_R$, we say $\Sigma$: - *proves correct key construction* if $((1^k,\mathit{pk}',\mathfrak m'),(\mathit{sk}',r)) \in R \Leftrightarrow (pk', sk',\mathfrak m') = \mathsf{Gen}(1^k;r)$ - *proves plaintext knowledge in $\mathfrak M$* if $\mathfrak M\subseteq \mathfrak m$ and $((\mathit{pk},c,\mathfrak M),(m,r)) \in R \Leftrightarrow c =\mathsf{Enc}(pk,m;r)\wedge m\in\mathfrak M$ - *proves correct ciphertext construction* if $((\mathit{pk},c_1,\dots,c_\ell),(m_1,r_1,\dots,m_\ell,r_\ell)) \in R \Leftrightarrow \bigwedge_{1\leq i \leq \ell}\allowbreak c_i =\mathsf{Enc}(\mathit{pk},m_i;r_i)$ - is a *plaintext equality test* (PET) if $((\mathit{pk},c,c',i),\mathit{sk}) \in R \wedge\allowbreak i\in\{0,1\}\Leftrightarrow ((i = 0 \wedge\allowbreak \mathsf{Dec}(\mathit{pk},\mathit{sk},c) \not=\mathsf{Dec}(\mathit{pk},\mathit{sk},c')) \vee\allowbreak (i = 1 \wedge\allowbreak \mathsf{Dec}(\mathit{pk},\mathit{sk},c) =\mathsf{Dec}(\mathit{pk},\mathit{sk},c'))) \wedge\allowbreak \mathsf{Dec}(\mathit{pk},\mathit{sk},c)\neq {\perp}$ - *proves decryption* if $((\mathit{pk},c,m),\mathit{sk}) \in R \Leftrightarrow m=\mathsf{Dec}(\mathit{pk}, \mathit{sk}, c)$ where $(\mathit{pk},\mathit{sk},\mathfrak m)\leftarrow\mathsf{Gen}(1^k)$.
We can derive *proofs of knowledge* from sigma protocols using the *Fiat-Shamir heuristic* (Fiat and Shamir 1987), which replaces the verifier’s challenge with a hash of the prover’s commitment, optionally concatenated with the prover’s statement (Bernhard, Pereira, and Warinschi 2012) and a message.
Given a sigma protocol $\Sigma = (\mathsf{Comm}_\Sigma,\mathsf{Chal}_\Sigma,\allowbreak\mathsf{Resp}_\Sigma,\mathsf{Verify}_\Sigma)$ and a hash function $\mathcal H$, the Fiat-Shamir transformation $\mathsf{FS}(\Sigma,\mathcal H) = (\mathsf{Prove}, \mathsf{Verify})$, where $\mathsf{Prove}$ and $\mathsf{Verify}$ are the algorithms defined as follows: - The *proof algorithm* $\mathsf{Prove}$ takes a statement $s$, witness $w$, and (optionally) message $m$ as input. The algorithm proceeds as follows. First, compute $(\textsf{comm},t) \leftarrow \mathsf{Comm}_\Sigma(s,w)$. Secondly, derive $\textsf{chal}$ as follows: if $m$ is defined, then $\textsf{chal} \leftarrow\mathcal H(s,\textsf{comm},m)$, otherwise, $\textsf{chal} \leftarrow\mathcal H(s,\textsf{comm})$. Thirdly, compute $\textsf{resp}\leftarrow\mathsf{Resp}_\Sigma(\textsf{chal},t)$. Finally, output $\sigma = (\textsf{comm},\textsf{resp})$. - The *verification algorithm* $\mathsf{Verify}$ takes a statement $s$, candidate proof $(\textsf{comm},\allowbreak \textsf{resp})$ and (optionally) message $m$ as input and outputs $\mathsf{Verify}_\Sigma(s,(\textsf{comm},\allowbreak \textsf{chal},\textsf{resp}))$, where $\textsf{chal}$ is derived as follows: if $m$ is defined, then $\textsf{chal} \leftarrow\mathcal H(s,\textsf{comm},m)$, otherwise, $\textsf{chal} \leftarrow\mathcal H(s,\textsf{comm})$.
# Syntax for e-auction schemes Based upon Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012; Smyth and Bernhard 2013), we formalise *e-auction schemes* as a tuple of algorithms $(\mathsf{Setup},\mathsf{BB},\mathsf{Open},\mathsf{Reveal})$ which are executed by an auctioneer and bidders as follows. (We consider a single auctioneer for simplicity and note that schemes can be generalised to several auctioneers to distribute trust, if necessary.) The $\mathsf{Setup}$ algorithm is run by the auctioneer to initialise a key pair and bulletin board. The $\mathsf{Bid}$ algorithm is used by bidders to generate their bids and the $\mathsf{BB}$ algorithm is used by the auctioneer to process bids, in particular, the algorithm adds correctly formed bids to the bulletin board. Once all of the bids have been collected, the auctioneer runs $\mathsf{Open}$ to find the winning price, which is announced by the auctioneer. Finally, the $\mathsf{Reveal}$ algorithm is used to identify winners; the $\mathsf{Reveal}$ algorithm uses private data ${\bf s}$ to reveal the winners, for example, ${\bf s}$ could be a private key which is used to decrypt bids. We define the inputs and outputs of our algorithms below:
$\mathsf{Setup}{(1^k)} \rightarrow (\mathit{pk}, \mathit{sk}, \mathfrak{bb}, \mathit{aux}\textrm{-}\mathit{pk}).$The *setup algorithm* $\mathsf{Setup}$ takes the security parameter $1^k$ as input and outputs a public key $\mathit{pk}$, private key $\mathit{sk}$, bulletin board $\mathfrak{bb}$ and auxiliary data $\mathit{aux}\textrm{-}\mathit{pk}$, where $\mathfrak{bb}$ is a set. $\mathsf{Bid}{(\mathit{pk}, \mathit{aux}\textrm{-}\mathit{pk}, {\bf P}, p)} \rightarrow b$. The *bid algorithm* $\mathsf{Bid}$ takes as input a public key $\mathit{pk}$, auxiliary data $\mathit{aux}\textrm{-}\mathit{pk}$, vector of biddable prices ${\bf P}$ and price $p$, where $1 \leq p \leq |{\bf P}|$. It outputs a bid $b$ such that $b={\perp}$ upon failure. $\mathsf{BB}{(\mathit{pk}, {\bf P}, \mathfrak{bb}, b)} \rightarrow \mathfrak{bb}'$. The *bulletin board algorithm* $\mathsf{BB}$ takes as input a public key $\mathit{pk}$, vector of biddable prices ${\bf P}$, bulletin board $\mathfrak{bb}$ and bid $b$, where $\mathfrak{bb}$ is a set. It outputs $\mathfrak{bb}\cup\{b\}$ if successful or $\mathfrak{bb}$ to denote failure. $\mathsf{Open}{(\mathit{pk}, \mathit{sk}, {\bf P}, \mathfrak{bb}, M)} \rightarrow (p, \mathit{aux}\textrm{-}\mathit{open})$. The *opening algorithm* $\mathsf{Open}$ takes as input a public key $\mathit{pk}$, private key $\mathit{sk}$, vector of biddable prices ${\bf P}$, bulletin board $\mathfrak{bb}$ and parameter $M$ denoting the number of items to be sold, where $\mathfrak{bb}$ is a set and $M>0$. It outputs the winning price $p$ and auxiliary data $\mathit{aux}\textrm{-}\mathit{open}$ such that $p = 0$ if no winning price is found and $p = {\perp}$ upon failure. $\mathsf{Reveal}{(\mathit{pk}, {\bf s}, \mathit{aux}\textrm{-}\mathit{pk},{\bf P}, \mathfrak{bb}, M, p, \mathit{aux}\textrm{-}\mathit{open})} \rightarrow (w,\mathit{aux}\textrm{-}\mathit{reveal})$. The *reveal algorithm* $\mathsf{Reveal}$ takes as input a public key $\mathit{pk}$, private data ${\bf s}$, auxiliary data $\mathit{aux}\textrm{-}\mathit{pk}$, a vector of biddable prices ${\bf P}$, bulletin board $\mathfrak{bb}$, parameter $M$ denoting the number of items to be sold, winning price $p$ and auxiliary data $\mathit{aux}\textrm{-}\mathit{open}$, where $M>0$ and $1 \leq p \leq |{\bf P}|$. It outputs a vector of winners $w$ and auxiliary data $\mathit{aux}\textrm{-}\mathit{reveal}$ such that $w={\perp}$ upon failure.
Our definition assumes that a vector of biddable prices ${\bf P}$ has been published and a bid for price ${\bf P}[p]$ is identified by price index $p$, where ${\bf P}[1]<\dots<{\bf P}[|{\bf P}|]$ and $1\leq p \leq |{\bf P}|$. For ease of understanding, we sometimes refer to $p$ as a price. # Hawk: An e-auction scheme based on Helios Hawk is an e-auction scheme derived from the Helios e-voting scheme (Adida et al. 2009) (see Cortier & Smyth (Cortier and Smyth 2013, sec. 2) for a cryptographic description of Helios). ## Informal description An auction is created by naming an auctioneer. The auctioneer generates a key pair and a proof of correct construction. The auctioneer publishes the public key, proof, biddable prices, and number of items to be sold. The bidding phase proceeds as follows.
**Bidding.** The bidder creates a bid by encrypting her price with the auctioneer’s public key and proving that the ciphertext contains a biddable price. The bidder sends her bid to the auctioneer. The auctioneer authenticates the bidder, checks that she is eligible to bid, and verifies the bidder’s proof; if these checks succeed, then the auctioneer publishes the bid on the bulletin board.
After some predefined deadline, the opening and revealing phases commence.
**Opening.** The auctioneer homomorphically combines the bids, decrypts the homomorphic combination, proves that decryption was performed correctly, and announces the winning price. **Revealing.** The auctioneer identifies bids for prices greater than or equal to the winning price, decrypts these bids, and proves that decryption was performed correctly.
Intuitively, every phase of the auction is verifiable. Bidders can check that their bid appears on the bulletin board and, by verifying bidders’ proofs, observers are assured that bids represent valid prices. Moreover, anyone can check that the homomorphic combination of bids and decryption were correctly computed. Furthermore, anyone can verify that the decrypted bids contain prices greater than or equal to the winning price. It follows that outcome verifiability is satisfied. In addition, our scheme satisfies bid secrecy, since bids for prices less than the winning price are not decrypted, and also provides non-repudiation, assuming that the auctioneer authenticates the relation between bidders and bids. ## Cryptographic construction We derive Hawk (Auction Scheme [auc:hawk]) from our informal description using an additively homomorphic encryption scheme satisfying IND-CPA, proofs of correct key construction, proofs of plaintext knowledge, and proofs of decryption. The $\mathsf{Setup}$ algorithm generates the auctioneer’s key pair, proves correct key construction, and initialises the bulletin board. The $\mathsf{Bid}$ algorithm outputs ciphertexts $c_1,\dots,c_{|{\bf P}|}$, such that ciphertext $c_p$ contains plaintext $1$ and the remaining ciphertexts contain plaintext $0$, where ${\bf P}[p]$ is the price that the bidder is willing to pay. The algorithm also outputs proofs $\sigma_1, ..., \sigma_{|{\bf P}|}$ so that this can be verified. Moreover, it outputs a proof $\sigma_{|{\bf P}|+1}$ that the bidder bid for at most one price. The $\mathsf{BB}$ algorithm adds correctly formed ballots to the bulletin board. The $\mathsf{Open}$ algorithm homomorphically combines ciphertexts representing bids at the highest price and decrypts the homomorphic combination, the algorithm repeats this process for ciphertexts at lower prices, until the sum of the decrypted ciphertexts is equal to or greater than the number of items to be sold, i.e., $M$. (The sum of the decrypted ciphertexts may be greater than $M$, since bidders may bid at the same price and, hence, the number of bids eligible to win may be greater than $M$. Nonetheless, the $\mathsf{Reveal}$ algorithm will identify exactly $M$ winning bids.) The $\mathsf{Reveal}$ algorithm homomorphically combines a bidder’s ciphertexts at or above the winning price, and decrypts the homomorphic combination. The bidder is a winner if the decryption reveals plaintext $1$. (We remark that Hawk’s open and reveal algorithms are both executed by the auctioneer and could be combined into a single function, however, the separation will be useful in Section 4.3.)  We demonstrate an execution of Hawk in Figure 1.
Suppose $\Pi = (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is an additively homomorphic asymmetric encryption scheme satisfying IND-CPA, $\Sigma_1$ proves correct key construction, $\Sigma_2$ proves plaintext knowledge in $\{0,1\}$ and $\Sigma_3$ proves decryption, where $\Pi$’s message space is $\{0,1\}^*$. Further suppose $\mathcal H$ is a hash function and let $\mathsf{FS}(\Sigma_1,\mathcal H) = (\mathsf{ProveKey}, \mathsf{VerKey})$, $\mathsf{FS}(\Sigma_2,\mathcal H) = (\mathsf{ProveCiph}, \mathsf{VerCiph})$, and $\mathsf{FS}(\Sigma_3,\mathcal H) = (\mathsf{ProveDec}, \mathsf{VerDec})$. We define *Hawk* as $\Gamma(\Pi,\Sigma_1, \Sigma_2, \Sigma_3, \mathcal H) = (\mathsf{Setup},\mathsf{Bid},\mathsf{BB},\mathsf{Open},\mathsf{Reveal})$.
$\mathsf{Setup}{(1^k)}$. Select coins $r$, compute $(\mathit{pk},\mathit{sk},\mathfrak m) \leftarrow \mathsf{Gen}(1^k;r);\rho \leftarrow \mathsf{ProveKey}((1^k,\mathit{pk},\mathfrak m),\allowbreak (\mathit{sk},r));{\bf aux}\textrm{-}{\bf pk}\leftarrow(1^k,\mathfrak m,\rho);\mathfrak{bb}\leftarrow \emptyset$ and output $(\mathit{pk},\mathit{sk},\mathfrak{bb}, {\bf aux}\textrm{-}{\bf pk})$. . $\mathsf{Bid}{(\mathit{pk},{\bf aux}\textrm{-}{\bf pk}, {\bf P}, p)}$. Parse ${\bf aux}\textrm{-}{\bf pk}$ as $(1^k,\mathfrak m,\rho)$, outputting $\perp$ if parsing fails or $\mathsf{VerKey}((1^k,\mathit{pk},\mathfrak m),\rho) \not= {\top}$. Select coins $r_1, \dots, r_{|{\bf P}|}$ and compute:
  $c_i \leftarrow \mathsf{Enc}(\mathit{pk},m_i;r_i)$; $\sigma_i \leftarrow \mathsf{ProveCiph}{((\mathit{pk}, c_i,\{0,1\}), (m_i, r_i),i)}$ $c\leftarrow c_1 \otimes \dots \otimes c_{|{\bf P}|}$; $m\leftarrow m_1 \odot \dots \odot m_{|{\bf P}|}$; $r\leftarrow r_1 \oplus \dots \oplus r_{|{\bf P}|}$ $\sigma_{|{\bf P}|+1} \leftarrow \mathsf{ProveCiph}{((\mathit{pk},c,\{0,1\}),(m, r), |{\bf P}|+1)}$
Output the bid $b = (c_1,\dots,c_{|{\bf P}|},\sigma_1,\dots,\sigma_{|{\bf P}|+1})$. $\mathsf{BB}{(\mathit{pk}, {\bf P}, \mathfrak{bb}, b)}$. Parse $b$ as a vector $(c_1,\dots,c_{|{\bf P}|},\sigma_1,\dots,\sigma_{|{\bf P}|+1})$. If parsing succeeds and $\bigwedge_{i \mathop = 1}^{|{\bf P}|+1} \mathsf{VerCiph}((\mathit{pk},c_i,\{0,1\}),\sigma_i, i) =\top$, where $c_{|{\bf P}|+1} \leftarrow c_1 \otimes \dots \otimes c_{|{\bf P}|}$, then output $\mathfrak{bb}\cup \{b\}$, otherwise, output $\mathfrak{bb}$. $\mathsf{Open}{(\mathit{pk}, \mathit{sk}, {\bf P}, \mathfrak{bb}, M)}$. Parse $\mathfrak{bb}= \{b_1, \dots, b_n\}$ as a set of vectors of length $2\cdot|{\bf P}|+1$, outputting $({\perp}, {\perp})$ if parsing fails. Initialise index $p \leftarrow |{\bf P}|+1$ and vector ${\bf aux}\textrm{-}{\bf open}\leftarrow ({\perp},\dots,{\perp})$ of length $|{\bf P}|$, and compute:
Output $p$ and auxiliary data ${\bf aux}\textrm{-}{\bf open}$. $\mathsf{Reveal}{(\mathit{pk}, \mathit{sk}, {\bf aux}\textrm{-}{\bf pk},{\bf P}, \mathfrak{bb}, M, p, {\bf aux}\textrm{-}{\bf open})}$. Parse $\mathfrak{bb}= \{b_1, \dots, b_n\}$ as a set of vectors of length $2\cdot|{\bf P}|+1$, outputting $({\perp}, {\perp})$ if parsing fails. Initialise a set $w \leftarrow \emptyset$, vector ${\bf aux}\textrm{-}{\bf reveal}\leftarrow ({\perp},\dots,{\perp})$ of length $n$ and integer $j\leftarrow 1$, and compute:
Output $(w,{\bf aux}\textrm{-}{\bf reveal})$.

Suppose a seller wants to sell two items (M = 2) using biddable prices ${\bf P} = (10, 15, 20, 25,30)$. Further suppose that Alice, Bob, Charlie and Daniel bid at prices 25, 20, 10 and 15. An execution of the Hawk auction scheme proceeds as follows.

Bidding. At the end of the bidding phase, the bulletin board is defined as follows. $$\mathfrak{bb}= \left\{ \begin{array}{l} (\mathsf{Enc}(\mathit{pk},0;r_{A,1}), \mathsf{Enc}(\mathit{pk},0;r_{A,2}), \mathsf{Enc}(\mathit{pk},0;r_{A,3}), \mathsf{Enc}(\mathit{pk},1;r_{A,4}), \mathsf{Enc}(\mathit{pk},0;r_{A,5})),\\ (\mathsf{Enc}(\mathit{pk},0;r_{B,1}), \mathsf{Enc}(\mathit{pk},0;r_{B,2}), \mathsf{Enc}(\mathit{pk},1;r_{B,3}), \mathsf{Enc}(\mathit{pk},0;r_{B,4}),\mathsf{Enc}(\mathit{pk},0;r_{B,5})),\\ (\mathsf{Enc}(\mathit{pk},1;r_{C,1}), \mathsf{Enc}(\mathit{pk},0;r_{C,2}), \mathsf{Enc}(\mathit{pk},0;r_{C,3}), \mathsf{Enc}(\mathit{pk},0;r_{C,4}), \mathsf{Enc}(\mathit{pk},0;r_{C,5})),\\ (\mathsf{Enc}(\mathit{pk},0;r_{D,1}), \mathsf{Enc}(\mathit{pk},1;r_{D,2}), \mathsf{Enc}(\mathit{pk},0;r_{D,3}), \mathsf{Enc}(\mathit{pk},0;r_{D,4}),\mathsf{Enc}(\mathit{pk},0;r_{D,5})) \end{array} \right\}$$ We omit proofs for brevity and assume that the auctioneer authenticates the relation between bidders and bids to derive non-repudiation. This assumption could be dropped, in the presence of a public key infrastructure, by signing bids.

Opening. The opening phase performs the following decryptions: $$\begin{array}{lcl} \mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 0\odot 0\odot 0;r_{A,5}\oplus r_{B,5} \oplus r_{C,5}\oplus r_{D,5})) & = & 0\\ \mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},1\odot 0\odot 0\odot 0;r_{A,4}\oplus r_{B,4} \oplus r_{C,4}\oplus r_{D,4})) & = & 1\\ \mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 1\odot 0\odot 0;r_{A,3}\oplus r_{B,3}\oplus r_{C,3}\oplus r_{D,3})) & = & 1 %\\ % %\DDecSymb(\pk,\sk,\EEncSymb(\pk,1;r_{A,2}\oplus r_{B,2}\oplus r_{C,2}\oplus r_{D,2})) & = & 1 \end{array}$$ Thereby revealing two bids at the winning price 20. The ciphertexts representing bids at prices 15 and 10 are not decrypted, because the sum of the decrypted ciphertexts (i.e., 0 + 2) are equal to M.

Revealing. The reveal phase performs the following decryptions:

$$\begin{array}{lcl} \mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 1\odot 0; r_{A,3} \oplus r_{A,4} \oplus r_{A,5})) & = & 1\\ \mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},1\odot 0\odot 0; r_{B,3} \oplus r_{B,4} \oplus r_{B,5})) & = & 1\\ \mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 0\odot 0; r_{C,3} \oplus r_{C,4} \oplus r_{C,5})) & = & 0\\ \mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 0\odot 0; r_{D,3} \oplus r_{D,4} \oplus r_{D,5})) & = & 0 \end{array}$$ Alice and Bob are declared winners.

An execution of the Hawk auction scheme
#### A comparison of Helios and Hawk. In terms of functionality, the new contribution of Hawk is the introduction of its reveal algorithm, which can be used to link a price to a bidder, given the auctioneer’s private key. In addition, we improve efficiency: Hawk’s opening algorithm modifies Helios’s tallying algorithm, in particular, Hawk only decrypts homomorphic combinations of ciphertexts until the sum of the decrypted ciphertexts is equal to or greater than the number of items to be sold, whereas Helios decrypts all homomorphic combinations of ciphertexts. ## Hawk$^*$: A variant of Hawk with bidder anonymity Hawk does not satisfy bidder anonymity, since this property conflicts with non-repudiation. However, we can sacrifice non-repudiation in favour of bidder anony-mity, as shown by Hawk$^*$ (Auction Scheme [reveal-ba]). In this variant, a winning bidder identifies her ballot $b$ on the bulletin board $\mathfrak{bb}$, computes $r$ such that $b[p] \otimes \cdots \otimes b[|{\bf P}|] = \mathsf{Enc}(\mathit{pk},1; r)$ – that is, $r$ is a partial homomorphic combination of the coins used by the bidder to construct her bid – and provides $b$ and $r$ as input to the reveal algorithm. Unlike Hawk’s reveal algorithm, Hawk$^*$’s reveal algorithm does not take the auctioneer’s private key as input and it follows that the algorithm can be executed by the seller, rather than the auctioneer. This introduces the possibility of an e-auction scheme in which the seller learns the winning bidders’ identities, but not the auctioneer. We demonstrate an execution of Hawk$^*$ in Figure 2. Intuitively, Hawk$^*$’s reveal algorithm can be optimised by omitting ciphertexts, from the homomorphic combination, for which no bid was made and the corresponding coins can be omitted from the bidders’ input (a similar optimisation can be made to Hawk’s reveal algorithm). For instance, in our example (Figure 2), the last ciphertext in each bid can be omitted from the homomorphic combination, because the opening phase has shown that no bids were cast at price $30$, and the bidders will omit $r_{A,5}$ and $r_{B,5}$ from their partial homomorphic combinations of coins. ### Implementation. We implement Hawk$^*$. Our implementation[^3] exploits the additive homomorphic (Cramer, Damgård, and Schoenmakers 1994; Cramer, Gennaro, and Schoenmakers 1997) and distributed decryption (Pedersen 1991; D. Chaum and Pedersen 1993) properties of ElGamal (ElGamal 1985), and proofs of knowledge demonstrating disjunctive proofs of equality between discrete logarithms (Bernhard, Pereira, and Warinschi 2012; Adida et al. 2009; Cramer, Damgård, and Schoenmakers 1994). (Note that our implementation distributes trust amongst several auctioneers.) The implementation builds upon the Helios code base, adding approximately 900 lines of Javascript and Python code to ensure that: 1) the coins used to construct the bid are revealed to bidders (the coins are not revealed by Helios to provide some practical resistance against vote selling), enabling bidders to disclose the coins during the reveal phase; 2) auctioneers only provide partial decryptions if the sum of the decrypted ciphertexts is equal to or greater than $M$.
Suppose $\Gamma(\Pi, \Sigma_1, \Sigma_2, \Sigma_3,\mathcal H) = (\mathsf{Setup},\mathsf{Bid},\mathsf{BB},\mathsf{Open},\mathsf{Reveal})$, where $\Pi$, $\Sigma_1$, $\Sigma_2$, $\Sigma_3$ and $\mathcal H$ satisfy the preconditions of Auction Scheme [auc:hawk]. We define *Hawk$^*$* as $\Gamma^*(\Pi,\Sigma_1, \Sigma_2, \Sigma_3,\mathcal H) = (\mathsf{Setup},\mathsf{Bid},\mathsf{BB},\mathsf{Open},\mathsf{Reveal}^*)$, where $\mathsf{Reveal}^*{(\mathit{pk}, {\bf s}, \rho, {\bf P}, \mathfrak{bb}, M, p, {\bf aux}\textrm{-}{\bf open})}$ is defined as follows. If $\mathsf{VerKey}(pk,\rho)= {\perp}$, then output $(\perp, \perp)$. Otherwise, parse $\mathfrak{bb}$ as a set of vectors of length $2\cdot|{\bf P}|+1$ and ${\bf s}$ as a vector $(b_1, r_1, \dots, b_M, r_M)$, outputting $({\perp},{\perp})$ if parsing fails. Compute:
$w\leftarrow \emptyset$ $c \leftarrow \mathsf{Enc}(\mathit{pk},1; r_i)$
Output $(w,{\perp})$.

Suppose the bidding and opening phases of a Hawk* auction are given in Figure 1. The reveal phase proceeds as follows.

Revealing. Alice and Bob reveal rA, 3 ⊙ rA, 4 and rB, 3 ⊙ rB, 4, and the reveal phase checks that Enc(pk, 1; rA, 3) ⊗ Enc(pk, 0; rA, 4) = Enc(pk, 1; rA, 3 ⊙ rA, 4) and Enc(pk1; rB, 3) ⊗ Enc(pk, 0; rB, 4) = Enc(pk, 1; rB, 3 ⊙ rB, 4).

We assume that the bidders’ coins are not revealed for bidder anonymity. This assumption could be dropped using designated verifier proofs that demonstrate knowledge of coins.

An execution of the Hawk* auction scheme
## Security analysis Since cryptographic security definitions have not been proposed in the literature (Dreier *et al.* (Dreier, Lafourcade, and Lakhnech 2013; Dreier, Jonker, and Lafourcade 2013) propose definitions in the symbolic model), we present an informal security analysis and leave formal analysis as a direction for future work. #### Bid secrecy. Hawk and Hawk$^*$ derive bid secrecy from the ballot secrecy (i.e., *voters’ votes cannot be revealed*) property of Helios. Informally, this can be witnessed up until the reveal phase as follows: by contradiction, suppose a losing bidder can be linked to a price before the winners are revealed; since Hawk and Hawk$^*$ are constructed from Helios as per our description in Section 1, it follows immediately that actions in an auction can be mapped to actions in an election and, hence, the link between a losing bidder and a price can be mapped to a relation between a voter and a vote, that is, a voter’s vote is revealed, thereby deriving a contradiction. Moreover, it follows from our definition of the $\mathsf{Reveal}$ algorithm that the reveal phase only leaks the winners, hence, we conclude that our schemes satisfies bid secrecy: a losing bid cannot be linked to a bidder. We stress that the existence of the reveal algorithm is not prohibited by Helios’s ballot secrecy property, because ballot secrecy asserts that an adversary cannot derive the private key[^4] and, hence, the reveal algorithm cannot be used by the adversary to obtain an advantage. #### Outcome verifiability. Hawk and Hawk$^*$ derive outcome verifiability from the individual verifiability (i.e., *a voter can check that her own ballot is published on the election’s bulletin board*) and universal verifiability (i.e., *anyone can check that all the votes in the election outcome correspond to ballots published on the election’s bulletin board and at most one vote is tallied per ballot*) properties of Helios, in particular, we have “a bidder can check that their bid is included in the e-auction" from the individual verifiability property and “anyone can check that the winning price is valid" from the universal verifiability property. #### Bidder anonymity/non-repudiation. Hawk satisfies non-repudiation and Hawk$^*$ satisfies bidder anonymity. We derive non-repudiation in Hawk under the assumption that the auctioneer authenticates the relation between bidders and bids, hence, a winner’s identity can be checked by verifying if the corresponding bid contains plaintext $1$ in the homomorphic combination of ciphertexts at or above the winning price. We derive bidder anonymity in Hawk$^*$ under the assumption that coins supplied by the winners are not leaked and the auctioneer does not reveal bidder identities, since, in this case, bidder anonymity follows immediately from bid secrecy. Our assumptions can be relaxed using digital signatures for non-repudiation and designated verifier proofs that demonstrate knowledge of coins. # Aucitas: An e-auction scheme based on Civitas Aucitas is an e-auction scheme derived from the Civitas e-voting scheme (Clarkson, Chong, and Myers 2008, 2007), which extends the e-voting scheme by Juels, Catalano & Jakobsson (Juels, Catalano, and Jakobsson 2002, 2005, 2010). ## Informal description An auction is created by naming an auctioneer and registrar. The auctioneer generates a key pair and a proof of correct key construction. The auctioneer publishes the public key, proof, biddable prices, and number of items to be sold. The registration phase proceeds as follows.
**Registration.** For each eligible bidder, the registrar constructs a (private) credential, sends the credential to the bidder, and derives the public credential by encrypting the credential with the auctioneer’s public key.
The registrar authentically publishes the public credentials ${\bf L}$ and the bidding phase proceeds as follows.
**Bidding.** The bidder produces two ciphertexts under the auctioneer’s public key: the first contains her price and the second contains her credential. In addition, the bidder proves plaintext knowledge of both ciphertexts. The bidder sends the bid – namely, the ciphertexts and proof – to the auctioneer. The auctioneer verifies the bidder’s proof and if verification succeeds, then the auctioneer publishes the bid on the bulletin board.
After some predefined deadline, the opening and revealing phases commence.
**Opening.** The auctioneer proceeds as follows. - *Eliminating duplicates:* The auctioneer performs pairwise plaintext equality tests on the ciphertexts containing credentials and discards any bids for which a test holds, that is, bids using the same credential are discarded. - *Mixing:* The auctioneer mixes the ciphertexts in the bids (i.e., the ciphertexts containing prices and the ciphertexts containing credentials), using the same secret permutation for both mixes, hence, the mix preserves the relation between encrypted prices and credentials. Let $\bf C_1$ and $\bf C_2$ be the outputs of these mixes. The auctioneer also mixes the public credentials published by the registrar and assigns the output to $\bf C_3$. - *Checking credentials:* The auctioneer discards ciphertexts ${\bf C_1}[i]$ from ${\bf C_1}$ if there is no ciphertext $c$ in ${\bf C_3}$ such that a PET holds for $c$ and ${\bf C_2}[i]$, that is, bids cast using ineligible credentials are discarded. - *Decrypting:* The auctioneer decrypts the remaining encrypted prices in ${\bf C_1}$ and proves that decryption was performed correctly. The auctioneer identifies the winning price from the decrypted prices. **Revealing.** The auctioneer identifies ciphertexts ${\bf C_1}[i]$ containing prices greater than or equal to the winning price, and performs PETs between ${\bf C_2}[i]$ and ${\bf L}$ to reveal the identities of winning bidders.
Intuitively, every phase of the auction is verifiable and, hence, outcome and eligibility verifiability, and non-repudiation are derived from the individual, universal and eligibility verifiability properties of Civitas. Moreover, we shall define biddable prices from a starting price of 1 using price increments of 1 and a price ceiling equal to the size of the encryption scheme’s message space, hence we have price flexibility. Furthermore, we derive collusion resistance from the coercion resistance property of Civitas. ## Cryptographic construction For our cryptographic construction of Aucitas, we extend the syntax for e-auctions schemes to include a registration algorithm, hence, an e-auction scheme is a tuple of algorithms $(\mathsf{Setup}, \mathsf{Register},\allowbreak \mathsf{Bid}, \mathsf{BB}, \allowbreak\mathsf{Open}, \mathsf{Reveal})$ such that $\mathsf{Register}{(\mathit{pk}, \mathit{aux}\textrm{-}\mathit{pk})} \rightarrow (d,pd)$, where $\mathit{pk}$ is the auctioneer’s public key, $\mathit{aux}\textrm{-}\mathit{pk}$ is auxiliary data, $d$ is a (private) credential, and $pd$ is a public credential. Moreover, we modify the input parameters of $\mathsf{Bid}$, $\mathsf{Open}$ and $\mathsf{Reveal}$, namely, $\mathsf{Bid}{(d,\mathit{pk}, \mathit{aux}\textrm{-}\mathit{pk}, {\bf P}, p)} \rightarrow b$, $\mathsf{Open}{(\mathit{pk}, \mathit{sk}, \mathit{aux}\textrm{-}\mathit{pk}, {\bf P}, \mathfrak{bb}, M, {\bf L})} \rightarrow (p, \mathit{aux}\textrm{-}\mathit{open})$ and $\mathsf{Reveal}{(\mathit{pk}, \mathit{sk}, \mathit{aux}\textrm{-}\mathit{pk}, {\bf P}, \mathfrak{bb}, p, \mathit{aux}\textrm{-}\mathit{open}, {\bf L})}\allowbreak \rightarrow ({\bf L'},\mathit{aux}\textrm{-}\mathit{reveal})$, where $d$ is a bidder’s credential, ${\bf L}$ and ${\bf L'}$ are vectors of public credentials, and the remaining inputs and outputs are as per Section 3. We define a mixnet as $\mathsf{Mix}({\bf c})\rightarrow ({\bf c}',\rho)$ such that ${\bf c}'$ contains a permutation of the ciphertexts in ${\bf c}$ after re-encryption and $\rho$ is a proof that the mix has been performed correctly. For brevity, we omit a formal definition and refer the reader to Jakobsson, Juels & Rivest (Jakobsson, Juels, and Rivest 2002). We present Aucitas in Auction Scheme [auc:aucitas]. The $\mathsf{Setup}$ algorithm generates the auctioneer’s key pair using an asymmetric encryption scheme, proves that the key has been correctly constructed, and initialises the bulletin board. The scheme is price flexible using biddable prices ${\bf P}=(1,2,\dots,|\mathfrak m|)$, where $\mathfrak m$ is the encryption scheme’s message space. The $\mathsf{Register}$ algorithm generates bidders’ credentials and we assume that the auctioneer provides the bidder with a credential $d$ corresponding to a public credential $\mathsf{Enc}(\mathit{pk},d)$; this assumption can be dropped using designated verifier proofs, for example. The specification of the $\mathsf{Bid}$, $\mathsf{BB}$, $\mathsf{Open}$ and $\mathsf{Reveal}$ algorithms follow from our informal description in Section 5.1. We demonstrate an execution of Aucitas in Figure 3.
Suppose $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is a homomorphic asymmetric encryption scheme satisfying IND-CPA, $\Sigma_1$ proves correct key construction, $\Sigma_2$ proves correct ciphertext construction, $\Sigma_3$ proves decryption, $\Sigma_4$ is a PET, and $\mathcal H$ is a hash function. Let $\mathsf{FS}(\Sigma_1,\mathcal H) = (\mathsf{ProveKey}, \mathsf{VerKey})$, $\mathsf{FS}(\Sigma_2,\mathcal H) = (\mathsf{ProveBind}, \mathsf{VerBind})$, $\mathsf{FS}(\Sigma_3,\mathcal H) = (\mathsf{ProveDec}, \mathsf{VerDec})$, and $\mathsf{FS}(\Sigma_4,\mathcal H) = (\mathsf{ProvePET}, \mathsf{VerPET})$. We define *Aucitas* below.
$\mathsf{Setup}{(1^k)}$. Select coins $r$, compute $(\mathit{pk}, \mathit{sk}, \mathfrak{m}) \leftarrow \mathsf{Gen}(1^k;r);\rho \leftarrow \mathsf{ProveKey}((1^k,\mathit{pk},\mathfrak m),\allowbreak (\mathit{sk},r)); \mathfrak{bb}\leftarrow \emptyset; {\bf aux}\textrm{-}{\bf pk}\leftarrow (1^k,\mathfrak{m},\rho)$ and output $(\mathit{pk}, \mathit{sk}, \mathfrak{bb},{\bf aux}\textrm{-}{\bf pk})$. $\mathsf{Register}{(\mathit{pk},{\bf aux}\textrm{-}{\bf pk})}$. Parse ${\bf aux}\textrm{-}{\bf pk}$ as $(1^k,\mathfrak{m},\rho)$, outputting $(\perp,\perp)$ if parsing fails. Assign a random element from $\mathfrak{m}$ to $d$ and compute $pd \leftarrow\mathsf{Enc}(\mathit{pk},d)$ and output $(d,pd)$. $\mathsf{Bid}{(d,\mathit{pk}, {\bf aux}\textrm{-}{\bf pk}, {\bf P}, p)}$. Parse ${\bf aux}\textrm{-}{\bf pk}$ as $(1^k,\mathfrak{m},\rho)$, outputting $\perp$ if parsing fails or $\mathsf{VerKey}((1^k,\mathfrak{m},\rho),\rho)\not= {\top}$. Suppose $\mathfrak{m}= \{m_1,\dots,m_{|\mathfrak{m}|}\}$ such that $m_1 < \cdots < m_{|\mathfrak{m}|}$. Select coins $r_1$ and $r_2$, compute $c_1 \leftarrow \mathsf{Enc}(\mathit{pk}, m_p; r_1);c_2 \leftarrow \mathsf{Enc}(\mathit{pk},d; r_2); %\textrm{\sout{$\sigma_1 \leftarrow \SignCiphSymb((\pk, c_1), (p, r_1));$}}\allowbreak \sigma \leftarrow \mathsf{ProveBind}((\mathit{pk},c_1,c_2),( m_p,r_1,d,r_2)); b \leftarrow (c_1, c_2, \sigma)$ and output bid $b$. $\mathsf{BB}{(\mathit{pk}, {\bf P}, \mathfrak{bb}, b)}$. Parse $b$ as $(c_1, c_2,\sigma)$. If parsing succeeds and $\mathsf{VerBind}((\mathit{pk},c_1,c_2),\sigma) = \top$, then output $\mathfrak{bb}\cup\{b\}$, otherwise, output $\mathfrak{bb}$. $\mathsf{Open}{(\mathit{pk}, \mathit{sk}, {\bf aux}\textrm{-}{\bf pk}, {\bf P}, \mathfrak{bb}, M, {\bf L})}$. Parse ${\bf aux}\textrm{-}{\bf pk}$ as $(1^k,\mathfrak{m},\rho)$ and $\mathfrak{bb}= \{b_1,\dots,b_n\}$ as a set of vectors of length $3$, outputting $({\perp},{\perp})$ if parsing fails. Proceed as follows. - Eliminating duplicates: Let ${\bf aux\textrm{-}dupl}$ be a vector of length $n$ and ${\bf BB}$ be the empty vector. For each $1\leq i \leq n$, if there exists $\sigma$ and $j\in\{1,\allowbreak\dots,\allowbreak{i-1},\allowbreak{i+1},\allowbreak\dots,\allowbreak n\}$ such that $\sigma \leftarrow \mathsf{ProvePET}((\mathit{pk},b_i[2],b_j[2],1),\allowbreak \mathit{sk})$ and $\mathsf{VerPET}((\mathit{pk},b_i[2],b_j[2],1),\allowbreak\sigma) = {\top}$, then assign ${\bf aux\textrm{-}dupl}[i] \leftarrow \sigma$, otherwise, compute $\sigma_j \leftarrow \mathsf{ProvePET}((\mathit{pk},\allowbreak b_i[2],\allowbreak b_j[2],\allowbreak 0),\allowbreak \mathit{sk})$ for each $j\in\{1,\allowbreak\dots,\allowbreak{i-1},\allowbreak{i+1},\allowbreak\dots,\allowbreak n\}$ and assign ${\bf aux\textrm{-}dupl}[i] \leftarrow (\sigma_1,\dots,\sigma_{i-1},\sigma_{i+1},\dots,\sigma_n); {\bf BB} \leftarrow {\bf BB}\parallel (b_i)$, where ${\bf BB}\parallel (b_i)$ denotes the concatenation of vectors ${\bf BB}$ and $(b_i)$, i.e., ${\bf BB}\parallel (b_i) = ({\bf BB}[1],\dots,{\bf BB}[|{\bf BB}|],b_i)$. - Mixing: Suppose ${\bf BB} = (b'_1,\dots,b'_\ell)$, select coins $r$, and compute $({\bf C_1},{\bf aux\textrm{-}mix}_{\bf 1}) \leftarrow \mathsf{Mix}((b'_1[1],\dots,b'_\ell[1]);r); ({\bf C_2},{\bf aux\textrm{-}mix}_{\bf 2}) \leftarrow \mathsf{Mix}((b'_1[2],\dots,b'_\ell[2]);r); ({\bf C_3},{\bf aux\textrm{-}mix}_{\bf 3}) \leftarrow \mathsf{Mix}({\bf L})$. - Checking credentials: Let ${\bf aux\textrm{-}cred}$ be a vector of length $|{\bf C_2}|$. For each $1\leq i \leq |{\bf C_2}|$, if there exists $\sigma$ and $c\in \bf C_3$ such that $\sigma \leftarrow \mathsf{ProvePET}((\mathit{pk},{\bf C_2}[i],c,1), \mathit{sk})$ and $\mathsf{VerPET}((\mathit{pk},{\bf C_2}[i],c,1),\sigma) = {\top}$, then assign ${\bf aux\textrm{-}cred}[i] \leftarrow \sigma$, otherwise, compute $\sigma_j \leftarrow \mathsf{ProvePET}((\mathit{pk},{\bf C_2}[i],{\bf C_3}[j],0),\mathit{sk})$ for each $j\in\{1,\dots,|{\bf C_3}|\}$ and assign ${\bf aux\textrm{-}cred}[i] \leftarrow (\sigma_1,\dots,\sigma_{|{\bf C_3}|})$. - Decrypting: Let ${aux\textrm{-}dec}$ be the empty set. For each $1 \leq i \leq |{\bf C_1}|$ such that $|{\bf aux\textrm{-}cred}[i]| = 1$ assign ${aux\textrm{-}dec}\leftarrow {aux\textrm{-}dec}\cup \{(({\bf C_1}[i],{\bf C_2}[i]),\sigma,m)\}$, where $m\leftarrow\mathsf{Dec}(\mathit{pk}, \mathit{sk}, {\bf C_1}[i])$ and $\sigma \leftarrow \mathsf{ProveDec}((\mathit{pk},{\bf C_1}[i],m),\mathit{sk})$. If $|{aux\textrm{-}dec}| < M$, then output $(0,{\perp})$. Otherwise, output $(p,{\bf aux}\textrm{-}{\bf open})$, where $p\in\{1,\dots,|\mathfrak{m}|\}$ is the largest integer such that $M$ integers in the set $\{m \mid (b,\sigma,m)\in {aux\textrm{-}dec}\}$ are greater than or equal to $m_p$, and ${\bf aux}\textrm{-}{\bf open}\leftarrow ({\bf aux\textrm{-}dupl},{\bf aux\textrm{-}mix}_{\bf 1},{\bf aux\textrm{-}mix}_{\bf 2},{\bf aux\textrm{-}mix}_{\bf 3},{\bf aux\textrm{-}cred},{aux\textrm{-}dec})$. $\mathsf{Reveal}{(\mathit{pk}, \mathit{sk}, {\bf aux}\textrm{-}{\bf pk}, {\bf P}, \mathfrak{bb}, M, p, {\bf aux}\textrm{-}{\bf open}, {\bf L})}$. Let ${aux\textrm{-}dec}\leftarrow {\bf aux}\textrm{-}{\bf open}[6]$. Parse ${\bf aux}\textrm{-}{\bf pk}$ as $(1^k,\mathfrak{m},\rho)$ and ${aux\textrm{-}dec}$ as a set of vectors of length $3$, outputting $({\perp}, \perp)$ if parsing fails. Suppose $\mathfrak{m}= \{m_1,\dots,m_{|\mathfrak{m}|}\}$ such that $m_1 < \cdots < m_{|\mathfrak{m}|}$. If there exist $M$ distinct triples $(b_1,\sigma_1,m'_1),\dots,(b_M,\sigma_M,m'_M) \in {aux\textrm{-}dec}$ and ciphertexts $c_1,\dots,c_M\in {\bf L}$ such that for each $1 \leq i \leq M$ we have $\mathsf{VerPET}((\mathit{pk},b_i[2],c_i,1),\tau_i) = {\top} \wedge m'_i \geq m_p$, where $\tau_i \leftarrow \mathsf{ProvePET}((\mathit{pk},b_i[2],c_i,1), \mathit{sk})$, then output $((c_1,\dots,c_M),(\tau_1,\dots,\tau_M))$, otherwise, output $({\perp}, \perp)$.

Suppose a seller wants to sell one item (M = 1) using biddable prices ${\bf P}=(1,2,\dots,|\mathfrak m|)$, where 𝔪 = {1, …, |𝔪|} is the encryption scheme’s message space. Further suppose that Alice, Bob and Charlie bid at prices 25, 20 and 15. In addition, let us suppose that an adversary instructs Charlie to bid 20. An execution of the Aucitas auction scheme proceeds as follows.

Registration. The registration phase results in the publication of public credentials ${\sf L} =\left( \mathsf{Enc}(\mathit{pk},d_A; r_1),\mathsf{Enc}(\mathit{pk},d_B; r_2),\mathsf{Enc}(\mathit{pk},d_C; r_3)\right)$.

Bidding. At the end of the bidding phase, the bulletin board is defined as follows.

$$\mathfrak{bb}= \left\{ \begin{array}{l} (\mathsf{Enc}(\mathit{pk},25; r_A), \mathsf{Enc}(\mathit{pk},d_A; \hat r_A)),\\ (\mathsf{Enc}(\mathit{pk},20; r_B), \mathsf{Enc}(\mathit{pk},d_B; \hat r_B)),\\ (\mathsf{Enc}(\mathit{pk},20; r), \mathsf{Enc}(\mathit{pk},d; \hat r)),\\ (\mathsf{Enc}(\mathit{pk},15; r_C), \mathsf{Enc}(\mathit{pk},d_C; \hat r_C)) \end{array} \right\}$$ We omit proofs for brevity. The ballot (Enc(pk, 20; r), Enc(pk, d; r̂)) is constructed by Charlie to avoid coercion.

Opening. The opening phase proceeds as follows.

The auctioneer identifies the winning price as 25.

Revealing. The auctioneer performs pairwise PETs between Enc(pk, dA; r̂′A) and ${\sf L}$ to reveal Enc(pk, dA; r1) as the winning bidder’s identity.

An execution of the Aucitas auction scheme
Intuitively, collusion resistance is satisfied if a bidder can convince a conspirator that they behaved as instructed, when they actually behaved differently. In Aucitas, this condition is satisfied as follows: given an instruction, a bidder generates a fake credential and follows the instruction using the fake credential. For instance, if the bidder is instructed to bid for a particular price, then the bidder constructs a bid for the price using the fake credential. It follows from the description of Aucitas that this bid will be removed during credential checking, however, the adversary will be unable to detect this, assuming at least one bidder bids at the adversary’s price. We acknowledge that price flexibility and collusion resistance are conflicting properties – allowing bidders to submit any price decreases the probability that at least one bidder bids the price instructed by an adversary – and we can balance the degree of price flexibility and collusion resistance by restricting the prices. #### A comparison of Civitas and Aucitas. Similarly to Hawk, in terms of functionality, the new contribution of Aucitas is the introduction of its reveal algorithm, which can be used to link a price to a bidder, given the auctioneer’s private key. In addition, we improve efficiency: Aucitas’s bid algorithm modifies Civitas’s vote algorithm by dropping the proof that demonstrates that ciphertext $c_1$ contains a biddable price. This proof is needed in the election setting to prevent the following attack (Juels, Catalano, and Jakobsson 2010, sec. 2.1): an adversary coerces a voter to cast a vote for a random string, this ensures that the adversary can verify if the voter followed instructions by checking that the random string is output by the tallying algorithm and ensures that this vote is not counted, since random strings do not correspond to legitimate candidates. However, this attack is not possible in the e-auction setting, because every message in the encryption scheme’s message space corresponds to a price. # Related work Magkos, Alexandris & Chrissikopoulos (Magkos, Alexandris, and Chrissikopoulos 2002) and Her, Imamot & Sakurai (Her, Imamoto, and Sakurai 2005) also study the relation between e-auction and e-voting schemes. Magkos, Alexandris & Chrissikopoulos remark that e-voting and e-auction schemes have a similar structure and share similar security properties. Her, Imamot & Sakurai contrast privacy properties of e-voting and e-auctions, and compare the use of homomorphic encryption and mixnets between domains. Our work is distinguished from these earlier works, since we *demonstrate* a relation between e-auction and e-voting schemes. Lipmaa, Asokan & Niemi (Lipmaa, Asokan, and Niemi 2002) propose an e-auction scheme, based upon homomorphic encryption, which is similar to the e-voting scheme proposed by Damgård, Jurik & Nielsen (Damgård, Jurik, and Nielsen 2010; Damgård and Jurik 2001) (although the similarities are not explicitly discussed) and Hawk. In essence, their scheme is defined as follows: 1) encrypted bids are sent to the seller during the bidding phase, 2) these encrypted bids are homomorphically combined by the seller in the opening phase and the homomorphic combination is decrypted by the auctioneer, and 3) bidders demonstrate to sellers that they are winning bidders during the reveal phase. Their scheme satisfies bid secrecy under the assumption that either the seller or auctioneer is trusted; by comparision, Hawk assumes that the auctioneer is trusted. This suggests that Hawk requires a stronger trust assumption, however, as we have discussed (Section 3), we can mitigate against the possibility that the auctioneer is dishonest by distributing trust amongst several auctioneers and, hence, the trust assumptions of Hawk and the scheme by Lipmaa, Asokan & Niemi are similar in the case that the seller is also an auctioneer. In addition, Lipmaa, Asokan & Niemi claim that their e-auction scheme could be used to construct an e-voting scheme (Lipmaa, Asokan, and Niemi 2002, sec. 9); by comparision, we focus on the inverse, i.e., the construction of e-auction schemes from e-voting schemes. Abe & Suzuki (Abe and Suzuki 2002a) propose an e-auction scheme based upon homomorphic encryption. Their scheme satisfies bid secrecy and a complimentary privacy property: with the exception of the winning price, prices are not revealed (this property helps protect bidding strategies, for example). The scheme is similar to Hawk until the opening phase, but differs thereafter, using Jakobsson & Juels’s *mix and match* technique (Jakobsson and Juels 2000) to find the winning price, for instance. By contrast, Hawk and Hawk$^*$ are conceptually simpler, and Hawk$^*$ has the additional property that allows the seller, rather than the auctioneer, to learn the winning bidders’ identities. Peng *et al.* (Peng et al. 2004) propose an e-auction schemes based upon mixnets, however, unlike Aucitas, they focus on bid secrecy rather than collusion resistance. Abe & Suzuki (Abe and Suzuki 2002b) introduce an e-auction scheme using trapdoor bit-commitments and Chen, Lee & Kim (Chen, Lee, and Kim 2003) introduce a scheme using mixnets; these two schemes satisfy collusion resistance. However, Abe & Suzuki assume the existence of a *bidding booth*, where the bidder must bid and cannot communicate with a conspirator, and Chen, Lee & Kim assume the seller is trusted. By comparision, Aucitas achieves collusion resistance without such assumptions. ### Acknowledgements. We are particularly grateful to Florian Kerschbaum and the anonymous reviewers who read earlier versions of this paper and provided useful guidance. This work has been partly supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC project *CRYSP* (259639), the ANR-09-VERS-016 BEST project, and Campus France. # Second-price sealed-bid e-auctions This paper focuses on first-price sealed-bid e-auctions in which the winning price is the highest price bid and the winner is the bidder who bid at the winning price. Vickrey (Vickrey 1961) has shown that first-price auctions motivate bidders to adopt strategies such as *bid shading* (i.e., bidding below their valuation of the item) to maximise their expected utility. *Second-price sealed-bid e-auctions* (also known as *Vickrey auctions*) overcome this problem by defining the winning price as the second-highest price bid, which incentivises bidders to bid their valuation of the item. In this appendix, we show how Hawk can be adapted to second-price e-auctions. #### A variant of Hawk for second-price e-auctions We can derive a variant of Hawk to construct second-price auctions by announcing the second-highest price bid, rather than the highest, which can be achieved by re-running the open algorithm with $M=2$. Since the open algorithm reveals the number of bidders that bid at a particular price, rather than the identities of bidders that bid at a particular price, bid secrecy is preserved. We demonstrate an execution of our variant as follows. Suppose the bidding phase of an auction is given in Figure 1. The initial execution of the open algorithm (parametrised with $M=1$) performs the first two decryptions given in the opening phase of Figure 1 and the re-run performs the remaining decryption to identify $20$ as the winning price (i.e., the second-highest price bid). Finally, the reveal algorithm computes the decryptions $\mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},1\odot 0; r_{A,4} \oplus r_{A,5}) = 1$, $\mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 0; r_{B,4} \oplus r_{B,5}) = 0$, $\mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 0; r_{C,4} \oplus r_{C,5}) = 0$ and $\mathsf{Dec}(\mathit{pk},\mathit{sk},\mathsf{Enc}(\mathit{pk},0\odot 0; r_{D,4} \oplus r_{D,5}) = 0$, and announces Alice as the winner. # References
Abe, Masayuki, and Koutarou Suzuki. 2002a. “M + 1-St Price Auction Using Homomorphic Encryption.” In *PKC’02: 5th International Workshop on Practice and Theory in Public Key Cryptography*, 2274:115–24. LNCS. Springer.
———. 2002b. “Receipt-Free Sealed-Bid Auction.” In *Information Security*, 2433:191–99. LNCS. Springer.
Adida, Ben, Olivier de Marneffe, Olivier Pereira, and Jean-Jacques Quisquater. 2009. “Electing a University President Using Open-Audit Voting: Analysis of Real-World Use of Helios.” In *EVT/WOTE’09: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections*. USENIX Association.
Backes, Michael, Cătălin Hriţcu, and Matteo Maffei. 2008. “Automated Verification of Remote Electronic Voting Protocols in the Applied Pi-calculus.” In *CSF’08: 21st Computer Security Foundations Symposium*, 195–209. IEEE Computer Society.
Bernhard, David, Véronique Cortier, Olivier Pereira, Ben Smyth, and Bogdan Warinschi. 2011. “Adapting Helios for provable ballot privacy.” In *ESORICS’11: 16th European Symposium on Research in Computer Security*, 6879:335–54. LNCS. Springer.
Bernhard, David, Olivier Pereira, and Bogdan Warinschi. 2012. “How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios.” In *ASIACRYPT’12: 18th International Conference on the Theory and Application of Cryptology and Information Security*, 7658:626–43. LNCS. Springer.
Brandt, Felix. 2010. “Auctions.” In *Handbook of Financial Cryptography and Security*, edited by Burton Rosenberg, 49–58. CRC Press.
Chaum, David L. 1981. “Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms.” *Communications of the ACM* 24: 84–90.
Chaum, David, and Torben P. Pedersen. 1993. “Wallet Databases with Observers.” In *CRYPTO’92: 12th International Cryptology Conference*, 740:89–105. LNCS. Springer.
Chen, Xiaofeng, Byoungcheon Lee, and Kwangjo Kim. 2003. “Receipt-Free Electronic Auction Schemes Using Homomorphic Encryption.” In *ICISC’03: 6th International Conference on Information Security and Cryptology*, 2971:259–73. LNCS. Springer.
Clarkson, Michael R., Stephen Chong, and Andrew C. Myers. 2007. “Civitas: Toward a Secure Voting System.” 2007-2081. Cornell University; .
———. 2008. “Civitas: Toward a Secure Voting System.” In *S&p’08: 29th Security and Privacy Symposium*, 354–68. IEEE Computer Society.
Cohen, Josh Daniel, and Michael J. Fischer. 1985. “A Robust and Verifiable Cryptographically Secure Election Scheme.” In *FOCS’85: 26th Symposium on Foundations of Computer Science*, 372–82. IEEE Computer Society.
Cortier, Véronique, and Ben Smyth. 2013. “Attacking and fixing Helios: An analysis of ballot secrecy.” *Journal of Computer Security* 21 (1): 89–148.
Cramer, Ronald, Ivan Damgård, and Berry Schoenmakers. 1994. “Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols.” In *CRYPTO’94: 14th International Cryptology Conference*, 839:174–87. LNCS. Springer.
Cramer, Ronald, Rosario Gennaro, and Berry Schoenmakers. 1997. “A Secure and Optimally Efficient Multi-Authority Election Scheme.” In *EUROCRYPT’97: 16th International Conference on the Theory and Applications of Cryptographic Techniques*, 1233:103–18. LNCS. Springer.
Damgård, Ivan, and Mads Jurik. 2001. “A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System.” In *PKC’01: 4th International Workshop on Practice and Theory in Public Key Cryptography*, 1992:119–36. LNCS. Springer.
Damgård, Ivan, Mads Jurik, and Jesper Buus Nielsen. 2010. “A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting.” *International Journal of Information Security* 9 (6): 371–85.
Delaune, Stéphanie, Steve Kremer, and Mark D. Ryan. 2009. “Verifying privacy-type properties of electronic voting protocols.” *Journal of Computer Security* 17 (4): 435–87.
Dreier, Jannik, Hugo Jonker, and Pascal Lafourcade. 2013. “Defining Verifiability in e-Auction Protocols.” In *ASIA CCS’13: 8th ACM SIGSAC Symposium on Information, Computer and Communications Security*, 547–52. ACM Press.
Dreier, Jannik, Pascal Lafourcade, and Yassine Lakhnech. 2013. “Formal Verification of e-Auction Protocols.” In *POST’13: 2nd Conference on Principles of Security and Trust*, 7796:247–66. LNCS. Springer.
ElGamal, Taher. 1985. “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.” *IEEE Transactions on Information Theory* 31 (4): 469–72.
Fiat, Amos, and Adi Shamir. 1987. “How To Prove Yourself: Practical Solutions to Identification and Signature Problems.” In *CRYPTO’86: 6th International Cryptology Conference*, 263:186–94. LNCS. Springer.
Garside, Juliette. 2013. “4G Spectrum Bidders to Be Confirmed as Auction Begins.” ; Guardian.
Hendricks, Kenneth, and Robert H Porter. 1989. “Collusion in Auctions.” *Annales d’Economie Et de Statistique* 15/16: 217–30.
Her, Yong-Sork, Kenji Imamoto, and Kouichi Sakurai. 2005. “Analysis and Comparison of Cryptographic Techniques in e-Voting and e-Auction.” 10(2). Information Science; Electrical Engineering, Kyushu University.
IACR. 2013. “IACR Elections.” (accessed 3 April 2013).
Jakobsson, Markus, and Ari Juels. 2000. “Mix and Match: Secure Function Evaluation via Ciphertexts.” In *Advances in Cryptology—ASIACRYPT 2000*, 162–77. Springer.
Jakobsson, Markus, Ari Juels, and Ronald L. Rivest. 2002. “Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking.” In *11th USENIX Security Symposium*, 339–53.
Ji, Zhu, and KJ Ray Liu. 2008. “Multi-Stage Pricing Game for Collusion-Resistant Dynamic Spectrum Allocation.” *IEEE Journal on Selected Areas in Communications* 26 (1): 182–91.
Juels, Ari, Dario Catalano, and Markus Jakobsson. 2002. “Coercion-Resistant Electronic Elections.” Cryptology ePrint Archive, Report 2002/165.
———. 2005. “Coercion-Resistant Electronic Elections.” In *WPES’05: 4th Workshop on Privacy in the Electronic Society*, 61–70. ACM Press.
———. 2010. “Coercion-Resistant Electronic Elections.” In *Towards Trustworthy Elections: New Directions in Electronic Voting*, edited by David Chaum, Markus Jakobsson, Ronald L. Rivest, and Peter Y. A. Ryan, 6000:37–63. LNCS. Springer.
Kremer, Steve, Mark D. Ryan, and Ben Smyth. 2010. “Election verifiability in electronic voting protocols.” In *ESORICS’10: 15th European Symposium on Research in Computer Security*, 6345:389–404. LNCS. Springer.
Lijphart, Arend, and Bernard Grofman. 1984. *Choosing an electoral system: Issues and Alternatives*. Praeger.
Lipmaa, Helger, N. Asokan, and Valtteri Niemi. 2002. “Secure Vickrey Auctions without Threshold Trust.” In *FC’02: 6th International Conference on Financial Cryptography and Data Security*, 2357:87–101. LNCS. Springer.
Magkos, Emmanouil, Nikos Alexandris, and Vassilis Chrissikopoulos. 2002. “A Common Security Model for Conducting e-Auctions and e-Elections.” CSCC’02: 6th WSEAS International Multiconference on Circuits, Systems, Communications and Computers .
Okamoto, Tatsuaki. 1996. “An Electronic Voting Scheme.” In *Advanced IT Tools: IFIP World Conference on IT Tools*, 21–30. IFIP Advances in Information and Communication Technology.
Pedersen, Torben P. 1991. “A Threshold Cryptosystem without a Trusted Party.” In *EUROCRYPT’91: 10th International Conference on the Theory and Applications of Cryptographic Techniques*, 522–26. LNCS 547. Springer.
Peng, Kun, Colin Boyd, Ed Dawson, and Kapalee Viswanathan. 2004. “Efficient Implementation of Relative Bid Privacy in Sealed-Bid Auction.” In *Information Security Applications*, 2908:244–56. LNCS. Springer.
Peng, Kun, Colin Boyd, Ed Dawson, and Kapali Viswanathan. 2003. “Five Sealed-Bid Auction Models.” In *ACSW’03: 21st Australasian Information Security Workshop*, 77–86. Australian Computer Society.
Princeton. 2012. “Helios Princeton Elections.” (accessed 8 February 2013).
Saalfeld, Thomas. 1995. “On Dogs and Whips: Recorded Votes.” In *Parliaments and Majority Rule in Western Europe*, edited by Herbert Döring. St. Martin’s Press.
Smart, Matthew James. 2012. “Anonymity vs. traceability: revocable anonymity in remote electronic voting protocols.” PhD thesis, School of Computer Science, University of Birmingham.
Smyth, Ben. 2011. “Formal verification of cryptographic protocols with automated reasoning.” PhD thesis, School of Computer Science, University of Birmingham.
Smyth, Ben, and David Bernhard. 2013. “Ballot secrecy and ballot independence coincide.” In *ESORICS’13: 18th European Symposium on Research in Computer Security*, 8134:463–80. LNCS. Springer.
US Government. 2013a. “2013 Alaska State Land Offering Auction \#472.” .
———. 2013b. “Auctions; Vehicles and Surplus Property.” .
Vickrey, William. 1961. “Counterspeculation, Auctions, and Competitive Sealed Tenders.” *The Journal of Finance* 16 (1): 8–37.
Zhou, Xia, and Haitao Zheng. 2010. “Breaking Bidder Collusion in Large-Scale Spectrum Auctions.” In *MobiHoc’10: 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing*, 121–30. ACM Press.
[^1]: A price ceiling – that is, an upper bound on the price that may be offered by bidders – is common in e-auctions. [^2]: Dreier *et al.* (Dreier, Lafourcade, and Lakhnech 2013) refer to collusion resistance as *coercion resistance*, we dislike this terminology, since it is suggestive of coercion rather than collusion. [^3]: Our implementation is available from the following URL: . [^4]: Formally, we can witness that ballot secrecy asserts that the adversary cannot derive the private key from (Smyth and Bernhard 2013, Definitions 3 & 5), since the tally algorithm can be used to reveal votes encapsulated inside individual ballots, given the private key.