Hawk and Aucitas: e-auction schemes from the
Helios and Civitas e-voting schemes
Adam McCarthy1 , Ben Smyth1 , and Elizabeth A. Quaglia2
1

INRIA Paris-Rocquencourt, France
2
ENS, Paris, France

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 and the two
communities are disjoint. In this paper, we demonstrate a relation between e-auction and e-voting: we present Hawk and Aucitas, two eauction schemes derived from the Helios and Civitas e-voting schemes.
Our results make progress towards the unification of the e-auction ande-voting domains.

Keywords. Aucitas, auction, bid secrecy, Civitas, collusion resistance,
Hawk, Helios, price flexibility, privacy, sealed-bid, verifiability, voting.

1

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,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 winnerare derived in accordance with the auction’s policy, for example, in first-pricesealed-bid auctions the winning price is the highest price bid and the winner isthe 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, inthe case M = 6, six identical items will be sold at the sixth highest price thatis bid, because six bidders are mutually willing to pay this price. Such auctions
are used to auction telecoms spectrum, vehicles and land, for example.
An election is a decision-making process by which voters choose a representative from some candidates. We study secret ballot elections, which are defined asfollows. 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 withthe election’s policy, e.g., in first-past-the-post elections the representative is thecandidate with the most votes. In this paper, we shall demonstrate that it ispossible to derive e-auction schemes from e-voting schemes.
?

See [16] for the long version of this paper.

Constructing e-auction schemes from e-voting schemes. Our translation from ane-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 incrementsof 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 topay, 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 thewinning 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.
1.1

Security properties

Bidders should be able to bid in auctions without fear of repercussions. This
property is known as privacy and bid secrecy has emerged as a de facto standard
privacy requirement.
– Bid secrecy: A losing bidder cannot be linked to a price.
We are also interested in collusion resistance (to help prevent bid rigging [19] byconspiring bidders).
– Collusion resistance: A losing bidder cannot collaborate with a conspirator to gain information which can be used to prove how they bid.
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 byregistered bidders.
– Non-repudiation: Anyone can check the winners’ identities.
We are also interested in the following functional requirement, which avoids
restricting the bidding amount.
– Price flexibility: Bidders can submit any price.
1

A price ceiling – that is, an upper bound on the price that may be offered by bidders– is common in e-auctions.

2

Cryptographic preliminaries

We adopt standard notation for the application of probabilistic algorithms A,
namely, A(x1 , . . . , xn ; r) is the result of running A on input x1 , . . . , xn and coinsr. Moreover, A(x1 , . . . , xn ) denotes A(x1 , . . . , xn ; r), where r is chosen at random.
We write x ← α for the assignment of α to x. Vectors are denoted using boldface,for example, x. We write |x| to denote the length of a vector x and x[i] forthe ith component of the vector, where x = (x[1], . . . , x[|x|]). We extend set
membership notation to vectors: we write x ∈ x (respectively, x 6∈ x) if x is anelement (respectively, x is not an element) of the set {x[i] : 1 ≤ i ≤ |x|}.
An asymmetric encryption scheme is a tuple of algorithms (Gen, Enc, Dec)
satisfying the standard correctness property (see the long version [16, Def 1] of
this paper for a formal definition). We say an encryption scheme is homomorphic if there exists binary operators ⊕, ⊗ and such that for all (pk , sk , m) ←Gen(1k ), messages m1 , m2 ∈ m and coins r1 and r2 , we have Enc(pk , m1 ; r1 ) ⊗Enc(pk , m2 ; r2 ) = Enc(pk , m1 m2 ; r1 ⊕ r2 ). The scheme is additive homomorphic if
is the addition operator or multiplicative homomorphic if
is themultiplication operator.
An interactive proof system is a two party protocol between a prover anda verifier on some common input, which allows a claim of membership to beevaluated. Formally, we capture such proof systems as sigma protocols (see thelong version [16, Def 2] of this paper for a formal definition). A sigma protocol
for an N P language LR , where LR = {s | ∃ w such that (s, w) ∈ R}, is a tupleof algorithms (Comm, Chal, Resp, Verify) satisfying special soundness and special
honest-verifier zero-knowledge (see [5] for details), in addition to the standard
completeness property. Our e-auction schemes are dependent upon the sigma
protocols given in Definition 1.
Definition 1. Given an asymmetric encryption scheme (Gen, Enc, Dec) and asigma protocol Σ for the language LR , we say Σ:– proves correct key construction if ((1k , pk 0 , m0 ), (sk 0 , r)) ∈ R ⇔ (pk 0 , sk 0 , m0 ) =Gen(1k ; r)
– proves plaintext knowledge in M if M ⊆ m and ((pk , c), (m, r)) ∈ R ⇔ c =Enc(pk, m; r) ∧ m ∈ M– provesVcorrect ciphertext construction if ((pk , c1 , . . . , c` ), (m1 , r1 , . . . , m` , r` )) ∈R ⇔ 1≤i≤` ci = Enc(pk , mi ; ri )– is a plaintext equality test (PET) if ((pk , c, c0 , i), sk ) ∈ R∧i ∈ {0, 1} ⇔ ((i =0∧Dec(pk , sk , c) 6= Dec(pk , sk , c0 ))∨(i = 1∧Dec(pk , sk , c) = Dec(pk , sk , c0 )))∧
Dec(pk , sk , c) 6= ⊥– proves decryption if ((pk , c, m), sk ) ∈ R ⇔ m = Dec(pk , sk , c)where (pk , sk , m) ← Gen(1k ).
We can derive proofs of knowledge from sigma protocols using the FiatShamir heuristic [9], which replaces the verifier’s challenge with a hash of theprover’s commitment, optionally concatenated with the prover’s statement [5]and a message.

Definition 2 (Fiat-Shamir transformation). Given a sigma protocol Σ =(CommΣ , ChalΣ , RespΣ , VerifyΣ ) and a hash function H, the Fiat-Shamir transformation FS(Σ, H) = (Prove, Verify), where Prove and Verify are the algorithms
defined as follows:– The proof algorithm Prove takes a statement s, witness w, and (optionally) message m as input. The algorithm proceeds as follows. First, compute(comm, t) ← CommΣ (s, w). Secondly, derive chal as follows: if m is defined,
then chal ← H(s, comm, m), otherwise, chal ← H(s, comm). Thirdly, compute resp ← RespΣ (chal, t). Finally, output σ = (comm, resp).
– The verification algorithm Verify takes a statement s, candidate proof (comm,resp) and (optionally) message m as input and outputs VerifyΣ (s, (comm,chal, resp)), where chal is derived as follows: if m is defined, then chal ←H(s, comm, m), otherwise, chal ← H(s, comm).

3

Syntax for e-auction schemes

Based upon Bernhard et al. [4, 5, 18], we formalise e-auction schemes as a tupleof algorithms (Setup, BB, Open, Reveal) which are executed by an auctioneer andbidders 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 Setup algorithm is run by the auctioneer to initialise a key pair andbulletin board. The Bid algorithm is used by bidders to generate their bids andthe BB algorithm is used by the auctioneer to process bids, in particular, thealgorithm adds correctly formed bids to the bulletin board. Once all of the bids
have been collected, the auctioneer runs Open to find the winning price, which
is announced by the auctioneer. Finally, the Reveal algorithm is used to identify winners; the Reveal algorithm uses private data s to reveal the winners, forexample, s could be a private key which is used to decrypt bids. We define theinputs and outputs of our algorithms below:
Setup(1k ) → (pk , sk , bb, aux -pk ).The setup algorithm Setup takes the security
parameter 1k as input and outputs a public key pk , private key sk , bulletinboard bb and auxiliary data aux -pk , where bb is a set.
Bid(pk , aux -pk , P, p) → b. The bid algorithm Bid takes as input a public key
pk , auxiliary data aux -pk , vector of biddable prices P and price p, where1 ≤ p ≤ |P|. It outputs a bid b such that b = ⊥ upon failure.
BB(pk , P, bb, b) → bb0 . The bulletin board algorithm BB takes as input a public
key pk , vector of biddable prices P, bulletin board bb and bid b, where bb
is a set. It outputs bb ∪ {b} if successful or bb to denote failure.
Open(pk , sk , P, bb, M ) → (p, aux -open). The opening algorithm Open takes as
input a public key pk , private key sk , vector of biddable prices P, bulletinboard bb and parameter M denoting the number of items to be sold, wherebb is a set and M > 0. It outputs the winning price p and auxiliary dataaux -open such that p = 0 if no winning price is found and p = ⊥ upon
failure.

Reveal(pk , s, aux -pk , P, bb, M, p, aux -open) → (w, aux -reveal ). The reveal algorithm Reveal takes as input a public key pk , private data s, auxiliary dataaux -pk , a vector of biddable prices P, bulletin board bb, parameter M denoting the number of items to be sold, winning price p and auxiliary dataaux -open, where M > 0 and 1 ≤ p ≤ |P|. It outputs a vector of winners w
and auxiliary data aux -reveal such that w = ⊥ upon failure.
Our definition assumes that a vector of biddable prices P has been publishedand a bid for price P[p] is identified by price index p, where P[1] < · · · < P[|P|]and 1 ≤ p ≤ |P|. For ease of understanding, we sometimes refer to p as a price.

4

Hawk: An e-auction scheme based on Helios

Hawk is an e-auction scheme derived from the Helios e-voting scheme [3]. 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 phaseproceeds 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 thebidder, 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 bulletinboard.
After some predefined deadline, the opening and revealing phases commence.
Opening. The auctioneer homomorphically combines the bids, decrypts thehomomorphic combination, proves that decryption was performed correctly,
and announces the winning price.
Revealing. The auctioneer identifies bids for prices greater than or equal to thewinning price, decrypts these bids, and proves that decryption was performed
correctly.
Intuitively, every phase of the auction is verifiable. Bidders can check that theirbid appears on the bulletin board and, by verifying bidders’ proofs, observers
are assured that bids represent valid prices. Moreover, anyone can check thatthe homomorphic combination of bids and decryption were correctly computed.
Furthermore, anyone can verify that the decrypted bids contain prices greaterthan 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. (Aninformal security analysis appears in the long version [16, §4.4] of this paper.)4.1

Cryptographic construction

We derive Hawk (Auction Scheme 1) 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
Setup algorithm generates the auctioneer’s key pair, proves correct key construction, and initialises the bulletin board. The Bid algorithm outputs ciphertexts
c1 , . . . , c|P| , such that ciphertext cp contains plaintext 1 and the remaining ciphertexts contain plaintext 0, where P[p] is the price that the bidder is willingto pay. The algorithm also outputs proofs σ1 , ..., σ|P| so that this can be verified.
Moreover, it outputs a proof σ|P|+1 that the bidder bid for at most one price.
The BB algorithm adds correctly formed ballots to the bulletin board. The Openalgorithm homomorphically combines ciphertexts representing bids at the highest price and decrypts the homomorphic combination, the algorithm repeats thisprocess 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
Reveal algorithm homomorphically combines a bidder’s ciphertexts at or above
the winning price, and decrypts the homomorphic combination. The bidder is awinner if the decryption reveals plaintext 1. In the long version [16] of this paper
we demonstrate an execution of Hawk and implement2 a variant which provides
a stronger notion of privacy.
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 tolink 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 numberof items to be sold, whereas Helios decrypts all homomorphic combinations ofciphertexts.

5

Aucitas: An e-auction scheme based on Civitas

Aucitas is an e-auction scheme derived from the Civitas e-voting scheme [7],which extends the e-voting scheme by Juels, Catalano & Jakobsson [13]. 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.
2

Our implementation is available from the following URL: http://bensmyth.com/
publications/2014-Hawk-and-Aucitas-auction-schemes/.

Auction Scheme 1 Hawk
Suppose Π = (Gen, Enc, Dec) is an additively homomorphic asymmetric encryption
scheme satisfying IND-CPA, Σ1 proves correct key construction, Σ2 proves plaintext knowledge in {0, 1} and Σ3 proves decryption, where Π’s message space is{0, 1}∗ . Further suppose H is a hash function and let FS(Σ1 , H) = (ProveKey, VerKey),
FS(Σ2 , H) = (ProveCiph, VerCiph), and FS(Σ3 , H) = (ProveDec, VerDec). We define
Hawk as Γ (Π, Σ1 , Σ2 , Σ3 , H) = (Setup, Bid, BB, Open, Reveal).
Setup(1k ). Select coins r, compute (pk , sk , m) ← Gen(1k ; r); ρ ← ProveKey((1k , pk , m),(sk , r)); aux-pk ← (1k , m, ρ); bb ← ∅ and output (pk , sk , bb, aux-pk). .
Bid(pk , aux-pk, P, p). Parse aux-pk as (1k , m, ρ), outputting ⊥ if parsing fails or
VerKey((1k , pk , m), ρ) 6= >. Select coins r1 , . . . , r|P| and compute:for 1 ≤ i ≤ |P| do
if i = p then mi ← 1 else mi ← 0
ci ← Enc(pk , mi ; ri ); σi ← ProveCiph((pk , ci ), (mi , ri ), i)c ← c1 ⊗ · · · ⊗ c|P| ; m ← m1 · · · m|P| ; r ← r1 ⊕ · · · ⊕ r|P| ;σ|P|+1 ← ProveCiph((pk , c), (m, r), |P| + 1)
Output the bid b = (c1 , . . . , c|P| , σ1 , . . . , σ|P|+1 ).
BB(pk , P, bb, b). Parse b as a vector (c1 , . . . , c|P| , σ1 , . . . , σ|P|+1 ). If parsing succeeds
Vand |P|+1
i = 1 VerCiph((pk , ci ), σi , i) = >, where c|P|+1 ← c1 ⊗ · · · ⊗ c|P| , then output
bb ∪ {b}, otherwise, output bb.
Open(pk , sk , P, bb, M ). Parse bb = {b1 , . . . , bn } as a set of vectors of length 2 · |P| + 1,
outputting (⊥, ⊥) if parsing fails. Initialise index p ← |P| + 1 and vector
aux-open ← (⊥, . . . , ⊥) of length |P|, and compute:dop ← p − 1;c ← b1 [p] ⊗ · · · ⊗ bn [p];m ← Dec(pk , sk , c); aux-open[p] ← ProveDec((pk , c, m), sk );M ←M −mwhile M > 0 ∧ p > 0;
if M > 0 then p ← 0
Output p and auxiliary data aux-open.
Reveal(pk , sk , aux-pk, P, bb, M, p, aux-open). Parse bb = {b1 , . . . , bn } as a set of vectors of length 2 · |P| + 1, outputting (⊥, ⊥) if parsing fails. Initialise a set w ← ∅,vector aux-reveal ← (⊥, . . . , ⊥) of length n and integer j ← 1, and compute:doc ← bj [p] ⊗ · · · ⊗ bj [|P|];m ← Dec(pk , sk , c); aux-reveal[j] ← ProveDec((pk , c, m), sk );if m = 1 then w ← w ∪ {bj }j ←j+1
while M > |w| ∧ j ≤ n;
Output (w, aux-reveal).

The registrar authentically publishes the public credentials 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, thenthe 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, i.e., 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 C1 andC2 be the outputs of these mixes. The auctioneer also mixes the publiccredentials published by the registrar and assigns the output to C3 .
– Checking credentials: The auctioneer discards ciphertexts C1 [i] from C1
if there is no ciphertext c in C3 such that a PET holds for c and C2 [i],that is, bids cast using ineligible credentials are discarded.
– Decrypting: The auctioneer decrypts the remaining encrypted prices in
C1 and proves that decryption was performed correctly.
The auctioneer identifies the winning price from the decrypted prices.
Revealing. The auctioneer identifies ciphertexts C1 [i] containing prices greaterthan or equal to the winning price, and performs PETs between C2 [i] and
L to reveal the identities of winning bidders.
Intuitively, every phase of the auction is verifiable and, hence, outcome andeligibility verifiability, and non-repudiation are derived from the individual, universal and eligibility verifiability properties of Civitas. Moreover, we shall definebiddable 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 thecoercion resistance property of Civitas.
5.1

Cryptographic construction

For our cryptographic construction of Aucitas, we extend the syntax for eauctions schemes to include a registration algorithm, hence, an e-auction scheme is a tuple of algorithms (Setup, Register, Bid, BB, Open, Reveal) such that
Register(pk , aux -pk ) → (d, pd), where pk is the auctioneer’s public key, aux -pk
is auxiliary data, d is a (private) credential, and pd is a public credential.
Moreover, we modify the input parameters of Bid, Open and Reveal, namely,
Bid(d, pk , aux -pk , P, p) → b, Open(pk , sk , aux -pk , P, bb, M, L) → (p, aux -open)
and Reveal(pk , sk , aux -pk , P, bb, p, aux -open, L) → (L0 , aux -reveal ), where d is abidder’s credential, L and L0 are vectors of public credentials, and the remaininginputs and outputs are as per Section 3. We define a mixnet as Mix(c) → (c0 , ρ)such that c0 contains a permutation of the ciphertexts in c after re-encryptionand ρ 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 [12].
We present Aucitas in Auction Scheme 2. The Setup algorithm generates
the auctioneer’s key pair using an asymmetric encryption scheme, proves thatthe key has been correctly constructed, and initialises the bulletin board. The
scheme is price flexible using biddable prices P = (1, 2, . . . , |m|), where m is theencryption scheme’s message space. The Register algorithm generates bidders’credentials and we assume that the auctioneer provides the bidder with a credential d corresponding to a public credential Enc(pk , d); this assumption can be
dropped using designated verifier proofs, for example. The specification of theBid, BB, Open and Reveal algorithms follow from our informal description. We
demonstrate an execution of Aucitas in the long version [16, Fig 3] of this paper.
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 thebidder constructs a bid for the price using the fake credential. It follows fromthe 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 andcollusion resistance are conflicting properties – allowing bidders to submit any
price decreases the probability that at least one bidder bids the price instructedby an adversary – and we can balance the degree of price flexibility and collusion
resistance by restricting the prices.

6

Related work

Magkos, Alexandris & Chrissikopoulos [15] and Her, Imamot and Sakurai [10]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 distinguishedfrom these earlier works, since we demonstrate a relation between e-auction ande-voting schemes.
Lipmaa, Asokan & Niemi [14] propose an e-auction scheme, based upon homomorphic encryption, which is similar to the e-voting scheme proposed by
Damgård, Jurik & Nielsen [8] (although the similarities are not explicitly discussed) and Hawk. In essence, their scheme is defined as follows: 1) encryptedbids are sent to the seller during the bidding phase, 2) these encrypted bids arehomomorphically combined by the seller in the opening phase and the homomorphic combination is decrypted by the auctioneer, and 3) bidders demonstrateAuction Scheme 2 Aucitas
Suppose (Gen, Enc, Dec) is a homomorphic asymmetric encryption scheme satisfying IND-CPA, Σ1 proves correct key construction, Σ2 proves correct ciphertext
construction, Σ3 proves decryption, Σ4 is a PET, and H is a hash function. Let
FS(Σ1 , H) = (ProveKey, VerKey), FS(Σ2 , H) = (ProveBind, VerBind), FS(Σ3 , H) =(ProveDec, VerDec), and FS(Σ4 , H) = (ProvePET, VerPET). We define Aucitas below.
Setup(1k ). Select coins r, compute (pk , sk , m) ← Gen(1k ; r); ρ ← ProveKey((1k , pk , m),(sk , r)); bb ← ∅; aux-pk ← (1k , m, ρ) and output (pk , sk , bb, aux-pk).
Register(pk , aux-pk). Parse aux-pk as (1k , m, ρ), outputting (⊥, ⊥) if parsing fails.
Assign a random element from m to d and compute pd ← Enc(pk , d) and output(d, pd).
Bid(d, pk , aux-pk, P, p). Parse aux-pk as (1k , m, ρ), outputting ⊥ if parsing fails or
VerKey((1k , m, ρ), ρ) 6= >. Suppose m = {m1 , . . . , m|m| } such that m1 < · · · < m|m| .
Select coins r1 and r2 , compute c1 ← Enc(pk , mp ; r1 ); c2 ← Enc(pk , d; r2 ); σ ←ProveBind((pk , c1 , c2 ), (mp , r1 , d, r2 )); b ← (c1 , c2 , σ) and output bid b.
BB(pk , P, bb, b). Parse b as (c1 , c2 , σ). If parsing succeeds and VerBind((pk , c1 , c2 ), σ) =>, then output bb ∪ {b}, otherwise, output bb.
Open(pk , sk , aux-pk, P, bb, M, L). Parse aux-pk as (1k , m, ρ) and bb = {b1 , . . . , bn }as a set of vectors of length 3, outputting (⊥, ⊥) if parsing fails. Proceed as follows.
– Eliminating duplicates: Let aux-dupl be a vector of length n and BB be
the empty vector. For each 1 ≤ i ≤ n, if there exists σ and j ∈ {1,. . . , i − 1, i + 1, . . . , n} such that σ ← ProvePET((pk , bi [2], bj [2], 1), sk ) and
VerPET((pk , bi [2], bj [2], 1), σ) = >, then assign aux-dupl[i] ← σ, otherwise,compute σj ← ProvePET((pk , bi [2], bj [2], 0), sk ) for each j ∈ {1, . . . , i − 1,
i + 1, . . . , n} and assign aux-dupl[i] ← (σ1 , . . . , σi−1 , σi+1 , . . . , σn ); BB ←BB k (bi ), where BB k (bi ) denotes the concatenation of vectors BB and(bi ), i.e., BB k (bi ) = (BB[1], . . . , BB[|BB|], bi ).
– Mixing: Suppose BB=(b01 , . . . , b0` ), select coins r, and compute (C1 , aux-mix1 ) ← Mix((b01 [1], . . . , b0` [1]); r); (C2 , aux-mix2 ) ←Mix((b01 [2], . . . , b0` [2]); r); (C3 , aux-mix3 ) ← Mix(L).
– Checking credentials: Let aux-cred be a vector of length |C2 |. For each 1 ≤ i ≤|C2 |, if there exists σ and c ∈ C3 such that σ ← ProvePET((pk , C2 [i], c, 1), sk )and VerPET((pk , C2 [i], c, 1), σ) = >, then assign aux-cred[i] ← σ, otherwise,compute σj ← ProvePET((pk , C2 [i], C3 [j], 0), sk ) for each j ∈ {1, . . . , |C3 |}and assign aux-cred[i] ← (σ1 , . . . , σ|C3 | ).
– Decrypting: Let aux-dec be the empty set. For each 1 ≤ i ≤ |C1 | such that|aux-cred[i]| = 1 assign aux-dec ← aux-dec ∪ {((C1 [i], C2 [i]), σ, m)}, wherem ← Dec(pk , sk , C1 [i]) and σ ← ProveDec((pk , C1 [i], m), sk ).
If |aux-dec| < M , then output (0, ⊥). Otherwise, output (p, aux-open), wherep ∈ {1, . . . , |m|} is the largest integer such that M integers in the set {m |(b, σ, m) ∈ aux-dec} are greater than or equal to mp , and aux-open ←(aux-dupl, aux-mix1 , aux-mix2 , aux-mix3 , aux-cred, aux-dec).
Reveal(pk , sk , aux-pk, P, bb, M, p, aux-open, L). Let aux-dec ← aux-open[6]. Parse
aux-pk as (1k , m, ρ) and aux-dec as a set of vectors of length 3, outputting (⊥, ⊥)if parsing fails. Suppose m = {m1 , . . . , m|m| } such that m1 < · · · < m|m| . If there
exist M distinct triples (b1 , σ1 , m01 ), . . . , (bM , σM , m0M ) ∈ aux-dec and ciphertexts
c1 , . . . , cM ∈ L such that for each 1 ≤ i ≤ M we have VerPET((pk , bi [2], ci , 1), τi ) => ∧ m0i ≥ mp , where τi ← ProvePET((pk , bi [2], ci , 1), sk ), then output((c1 , . . . , cM ), (τ1 , . . . , τM )), otherwise, output (⊥, ⊥).

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. Thissuggests that Hawk requires a stronger trust assumption, however, as we havediscussed (Section 3), we can mitigate against the possibility that the auctioneer
is dishonest by distributing trust amongst several auctioneers and, hence, thetrust assumptions of Hawk and the scheme by Lipmaa, Asokan & Niemi aresimilar 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 [14, §9]; by comparision, we focus on the inverse, i.e., theconstruction of e-auction schemes from e-voting schemes.
Abe & Suzuki [1] 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 [11] to find the winning price, for instance. By contrast,
Hawk is conceptually simpler.
Peng et al. [17] propose an e-auction schemes based upon mixnets, however,unlike Aucitas, they focus on bid secrecy rather than collusion resistance. Abe &Suzuki [2] introduce an e-auction scheme using trapdoor bit-commitments andChen, Lee & Kim [6] introduce a scheme using mixnets. These are the only eauction scheme satisfying 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 andthe 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.

References
1. Abe, M., Suzuki, K.: M + 1-st price auction using homomorphic encryption.
In: PKC’02: 5th International Workshop on Practice and Theory in Public Key
Cryptography. Volume 2274 of LNCS., Springer (2002) 115–124
2. Abe, M., Suzuki, K.: Receipt-free sealed-bid auction. In: Information Security.
Volume 2433 of LNCS. Springer (2002) 191–199
3. Adida, B., Marneffe, O., Pereira, O., Quisquater, J.: 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 (2009)

4. Bernhard, D., Cortier, V., Pereira, O., Smyth, B., Warinschi, B.: Adapting Helios for provable ballot privacy. In: ESORICS’11: 16th European Symposium on
Research in Computer Security. Volume 6879 of LNCS., Springer (2011) 335–354
5. Bernhard, D., Pereira, O., Warinschi, B.: How Not to Prove Yourself: Pitfallsof the Fiat-Shamir Heuristic and Applications to Helios. In: ASIACRYPT’12:
18th International Conference on the Theory and Application of Cryptology andInformation Security. Volume 7658 of LNCS., Springer (2012) 626–643
6. Chen, X., Lee, B., Kim, K.: Receipt-Free Electronic Auction Schemes Using Homomorphic Encryption. In: ICISC’03: 6th International Conference on Information
Security and Cryptology. Volume 2971 of LNCS., Springer (2003) 259–273
7. Clarkson, M.R., Chong, S., Myers, A.C.: Civitas: Toward a Secure Voting System.
In: S&P’08: 29th Security and Privacy Symposium, IEEE Computer Society (2008)
354–368
8. Damgård, I., Jurik, M., Nielsen, J.B.: A Generalization of Paillier’s Public-Key
System with Applications to Electronic Voting. International Journal of Information Security 9(6) (2010) 371–385
9. Fiat, A., Shamir, A.: How To Prove Yourself: Practical Solutions to Identificationand Signature Problems. In: CRYPTO’86: 6th International Cryptology Conference. Volume 263 of LNCS., Springer (1987) 186–194
10. Her, Y.S., Imamoto, K., Sakurai, K.: Analysis and comparison of cryptographic
techniques in e-voting and e-auction. Technical Report 10(2), Information Scienceand Electrical Engineering, Kyushu University (September 2005)
11. Jakobsson, M., Juels, A.: Mix and match: Secure function evaluation via ciphertexts. In: Advances in CryptologyASIACRYPT 2000. Springer (2000) 162–177
12. Jakobsson, M., Juels, A., Rivest, R.L.: Making Mix Nets Robust for Electronic
Voting by Randomized Partial Checking. In: 11th USENIX Security Symposium.
(2002) 339–353
13. Juels, A., Catalano, D., Jakobsson, M.: Coercion-Resistant Electronic Elections.
In Chaum, D., Jakobsson, M., Rivest, R.L., Ryan, P.Y., eds.: Towards Trustworthy
Elections: New Directions in Electronic Voting. Volume 6000 of LNCS. Springer(2010) 37–63
14. Lipmaa, H., Asokan, N., Niemi, V.: Secure Vickrey Auctions without Threshold
Trust. In: FC’02: 6th International Conference on Financial Cryptography andData Security. Volume 2357 of LNCS., Springer (2002) 87–101
15. Magkos, E., Alexandris, N., Chrissikopoulos, V.: A Common Security Model for
Conducting e-Auctions and e-Elections. CSCC’02: 6th WSEAS International Multiconference on Circuits, Systems, Communications and Computers http://www.
wseas.us/e-library/conferences/crete2002/papers/444-766.pdf (2002)
16. McCarthy, A., Smyth, B., Quaglia, E.A.: Hawk and Aucitas: e-auction schemes from the Helios and Civitas e-voting schemes. http://bensmyth.com/
publications/2014-Hawk-and-Aucitas-auction-schemes/ (2014)17. Peng, K., Boyd, C., Dawson, E., Viswanathan, K.: Efficient implementation ofrelative bid privacy in sealed-bid auction. In: Information Security Applications.
Volume 2908 of LNCS. Springer (2004) 244–256
18. Smyth, B., Bernhard, D.: Ballot secrecy and ballot independence coincide. In: ESORICS’13: 18th European Symposium on Research in Computer Security. Volume8134 of LNCS., Springer (2013) 463–480
19. Zhou, X., Zheng, H.: Breaking bidder collusion in large-scale spectrum auctions.
In: MobiHoc’10: 11th ACM international symposium on Mobile ad hoc networking
and computing, ACM Press (2010) 121–130