Brandt’s fully private auction protocol revisited

Abstract

Auctions have a long history, having been recorded as early as 500 B.C. [Auction Theory, Academic Press, San Diego, USA, 2002]. Nowadays, electronic auctions have been a great success and are increasingly used in various applications, including high performance computing [Concurrency and Computation: Practice and Experience14(13–15) (2002), 1507–1542]. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions, in particular to ensure privacy. Brandt [International Journal of Information Security5 (2006), 201–216] developed a protocol that computes the winner using homomorphic operations on a distributed ElGamal encryption of the bids. He claimed that it ensures full privacy of the bidders, i.e. no information apart from the winner and the winning price is leaked. We first show that this protocol – when using malleable interactive zero-knowledge proofs – is vulnerable to attacks by dishonest bidders. Such bidders can manipulate the publicly available data in a way that allows the seller to deduce all participants’ bids. We provide an efficient parallelized implementation of the protocol and the attack to show its practicality. Additionally we discuss some issues with verifiability as well as attacks on non-repudiation, fairness and the privacy of individual bidders exploiting authentication problems.

Keywords

Anonymity applied cryptography cryptographic protocols privacy-enhancing technology

1. Introduction

Auctions are a simple method to sell goods and services. Typically a seller offers a good or a service, and the bidders make offers. Depending on the type of auction, the offers might be sent using sealed envelopes which are opened simultaneously to determine the winner (the “sealed-bid” auction), or an auctioneer could announce prices decreasingly until one bidder is willing to pay the announced price (the “dutch auction”). Additionally there might be several rounds, or offers might be announced publicly directly (the “English” or “shout-out” auction). The winner usually is the bidder submitting the highest bid, but in some cases he might only have to pay the second highest offer as a price (the “second-price”- or “Vickrey”-Auction). In general a bidder wants to win the auction at the lowest possible price, and the seller wants to sell his good at the highest possible price. For more information on different auction methods see [20]. To address this huge variety of possible auction settings and to achieve different security and efficiency properties numerous protocols have been developed, e.g. [5,13,22–26] and references therein.

One of the many applications of auctions lies is in the context of distributed scheduling of jobs for high performance computing grids [1,7]. In this and other applications, one of the key security requirements of electronic auction (e-Auction) protocols is privacy, i.e. the bids of losing bidders remain private as they can contain sensitive information. For example, in the case of a grid shared between multiple companies, the job meta-data (length, resource requirements, as well as the offered payment) can leak sensitive information to competitors about the nature, content or importance of the computation: if the job is very important, a company might be willing to pay more even for a small job, or changes in the job types might indicate that the company is developing new computation methods. Moreover, the offered prices might leak information about the bidders’ strategies (in particular in multi-round auctions) or their financial status.

Brandt proposed a first-price sealed-bid auction protocol [3–5] and claimed that it is fully private, i.e. it leaks no information apart from the winner, the winning bid, and what can be deduced from these two facts (for example that the other bids were lower).

Our contributions. The protocol is based on an algorithm that computes the winner using bids encoded as bit vectors. In this paper we show that the implementation using the homomorphic property of a distributed ElGamal encryption proposed in the original paper suffers from a weakness. In fact, we prove that any two different inputs (i.e. different bids) result in different outcome values, which are only hidden using random values. We show how a dishonest participant can remove this random noise, if malleable interactive zero-knowledge proofs are used. The seller can then efficiently compute the bids of all bidders, hence completely breaking privacy. We provide a parallel implementation for the protocol and the attack, and show that the computations are efficient in practice. We also discuss two problems with verifiability, and how the lack of authentication enables attacks on privacy even if the above attack is prevented via non-malleable non-interactive proofs. Additionally we show attacks on non-repudiation and fairness, and propose solutions to all discovered flaws in order to recover a fully resistant protocol.

A preliminary version of this paper was presented in [14], with a theoretical attack of complexity $O (n^{2} k^{2})$ where n is the number of bidders and k the number of possible bids. In this paper we correct an error in the attack given in [14] and present an improved attack of complexity only $O (n k)$ . We also give a detailed description of the new efficient algorithm, and present a practical performance evaluation on realistic inputs: With thousands of different bids and bidders, we were able to break the privacy of the original protocol in a few seconds on a 32 cores shared memory machine.

Outline. In the next section, we recall the protocol of Brandt. Then, in the following sections, we present our attacks in several steps. In Section 3, we first study the protocol using interactive zero-knowledge proofs and without random noise. Then we show how a dishonest participant can remove the noise, thus mount the attack on the protocol with noise, and discuss countermeasures. Finally, in Section 4, we discuss verifiability and in Section 5 we discuss attacks on fairness, non-repudiation and privacy exploiting the lack of authentication.

2. The protocol

The protocol of Brandt [5] was designed to ensure full privacy in a completely distributed way. It exploits the homomorphic properties of a distributed ElGamal encryption scheme [15] for a secure multi-party computation of the winner. Then it uses zero-knowledge proofs of knowledge of discrete logarithms to ensure correctness of the bids while preserving privacy. We first give a high level description of the protocol and then present details on its main cryptographic primitives.

2.1. Informal description

The participating n bidders and the seller communicate essentially using broadcast messages. The latter can for example be implemented using a bulletin board, i.e. an append-only memory accessible to everybody. The bids are encoded as k-bit-vectors where each entry corresponds to a price. If the bidder a wants to bid the price ${bid}_{a}$ , all entries will be 1, except the entry ${bid}_{a}$ which will be Y (a public constant). Each entry of the vector is then encrypted separately using a n-out-of-n-encryption scheme set up by all bidders. The bidders use multiplications of the encrypted values to compute one value $v_{a j}$ for each price, by exploiting the homomorphic property of the encryption scheme. Each one of this values ( $v_{a j}$ ) is 1 if the bidder a wins at price j, and is a random number otherwise. The decryption of the final values takes place in a distributed way to ensure that nobody can access intermediate values.

2.2. Mathematical description (Brandt [5])

Let $G_{q}$ be a multiplicative subgroup of order q, prime, and g a generator of the group. We consider that $i, h \in {1, \dots, n}$ , $j, {bid}_{a} \in {1, \dots, k}$ (where ${bid}_{a}$ is the bid chosen by the bidder with index a), $Y \in G_{q} ∖ {1}$ . More precisely, the n bidders execute the following five steps of the Brandt’s protocol [5]:

Key generation

Each bidder a, whose bidding price is ${bid}_{a}$ among ${1, \dots, k}$ does the following:

chooses a secret $x_{a} \in Z / q Z$ ;

chooses randomly $m_{i j}^{a}$ and $r_{a j} \in Z / q Z$ for each $i \in {1, \dots, n}$ and $j \in {1, \dots, k}$ ;

publishes $y_{a} = g^{x_{a}}$ and proves the knowledge of $y_{a}$ ’s discrete logarithm;

using all the published $y_{i}$ , then computes $y = \prod_{i = 1}^{n} y_{i}$ .

Bid encryption

Each bidder a knows the public value Y and

for all $j \in {1, \dots, k}$ sets $b_{a j} = {\begin{matrix} Y & if j = {bid}_{a}, \\ 1 & otherwise; \end{matrix}$

publishes $α_{a j} = b_{a j} \cdot y^{r_{a j}}$ and $β_{a j} = g^{r_{a j}}$ for each j;

proves that for all j, ${log}_{g} (β_{a j})$ equals ${log}_{y} (α_{a j})$ or ${log}_{y} (\frac{α_{a j}}{Y})$ , and that ${log}_{y} (\frac{\prod_{j = 1}^{k} α_{a j}}{Y}) = {log}_{g} (\prod_{j = 1}^{k} β_{a j}) .$

Outcome computation

Each bidder a computes and publishes for all i and j: $\begin{matrix} γ_{i j}^{a} = {((\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} α_{h d}) \cdot (\prod_{d = 1}^{j - 1} α_{i d}) \cdot (\prod_{h = 1}^{i - 1} α_{h j}))}^{m_{i j}^{a}}, \\ δ_{i j}^{a} = {((\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} β_{h d}) \cdot (\prod_{d = 1}^{j - 1} β_{i d}) \cdot (\prod_{h = 1}^{i - 1} β_{h j}))}^{m_{i j}^{a}} \end{matrix}$ and proves its correctness.

Outcome decryption

Each bidder a sends $ϕ_{i j}^{a} = {(\prod_{h = 1}^{n} δ_{i j}^{h})}^{x_{a}}$ for each i and j to the seller and proves its correctness. After having received all values, the seller publishes $ϕ_{i j}^{h}$ for all i, j, and $h \neq i$ .

Winner determination

Everybody can now compute $v_{a j} = \frac{\prod_{i = 1}^{n} γ_{a j}^{i}}{\prod_{i = 1}^{n} ϕ_{a j}^{i}}$ for each j.

If $v_{a w} = 1$ for some w, then the bidder a wins the auction at price $p_{w}$ .

2.3. Malleable proofs of knowledge and discrete logarithms

In the original paper [5] the author suggests using zero-knowledge proofs of knowledge to protect against active adversaries. The basic protocols he proposes are interactive and malleable, but can be converted into non-interactive proofs using the Fiat–Shamir heuristic [16], as advised by the author. We first recall the general idea of such proofs, then we expose the man-in-the-middle attacks on the interactive version of the zero-knowledge proofs, which we will use as part of our first attack on Brandt’s protocol in Section 3.1.

Let PDL denote a proof of knowledge of a discrete logarithm. A first scheme for PDL was developed in 1986 by Chaum et al. [9]. In the original auction paper [5] Brandt proposes to use a non-interactive variant of PDL as developed by Schnorr [27], which are malleable. Unfortunately, interactive malleable PDL are subject to man-in-the-middle attacks [19]. Many PDL’s are obtained via three-move structure protocols (commitment, challenge and response) called Σ-protocols. We first recall the classic Σ-protocol for PDL, on a group with generator g and order q [2,6,8]: Peggy and Victor know v and g, but only Peggy knows x, so that $v = g^{x}$ . She can prove this fact, without revealing x, by executing the following protocol:

(commitment) Peggy chooses r at random and sends $z = g^{r}$ to Victor.

(challenge) Victor chooses a challenge c at random and sends it to Peggy.

(response) Peggy sends $s = (r + c \cdot x) mod q$ to Victor.

Victor checks that $g^{s} = z \cdot v^{c}$ .

2.3.1. Generalization of Katz’ man-in-the-middle attack on interactive PDL

Suppose Peggy possesses some secret discrete logarithm x. We present here first the man-in-the-middle attack of [19], and then generalize it to any affine transform of a secret discrete logarithm. In this attack, an attacker can pretend to have knowledge of any affine combination of the secret x, even providing the associated proof of knowledge, without breaking the discrete logarithm. To prove this possession to say Victor, the attacker will start an interactive proof knowledge session with Peggy and another one with Victor. The attacker will transform Peggy’s outputs and forward Victor’s challenges to her. The idea of [19] is to use the proof of possession of Peggy’s x, to prove possession of $1 - x$ to Victor. Indeed to prove for instance possession of just x to Victor, an attacker would only have to forward Peggy’s messages to Victor and Victor’s messages to Peggy. The idea of the attack is similar, except that one needs to modify the messages of Peggy. We show the example of $1 - x$ in Fig. 1 since it is used in Section 3.4 to mount our attack. Upon demand by Victor to prove knowledge of $1 - x$ , Mallory, the man-in-the-middle, simply starts a proof of knowledge of x with Peggy. Peggy chooses a random exponent r and sends the commitment $z = g^{r}$ to Mallory. Mallory simply inverts z and sends $y = z^{- 1}$ to Victor. Then Victor presents a challenge c that Mallory simply forwards without modification to Peggy. Finally Peggy sends a response s that Mallory combines with c, as $u = c - s$ , to provide a correct answer to Victor. This is summarized in Fig. 1. Victor is convinced by Mallory’s proof since we have $g^{s} = g^{r + c \cdot x} = g^{r} g^{x \cdot c} = z v^{c}$ and $g^{u} = g^{c - s} = g^{c - (r + c \cdot x)} = g^{- r} g^{(1 - x) \cdot c} = z^{- 1} {(g v^{- 1})}^{c} = y w^{c}$ .

Fig. 1.

Man-in-the-middle PDL of $1 - x$ , with x an unknown discrete logarithm [19].

Now we show in Lemma 1 that it is possible to adapt the attack to make it work in the generic settings of [6,21] or of Σ-protocols [12]. We use this generalization to prevent possible countermeasures of our first attack in Section 3.7.

We let $f : Γ \to Ω$ denote a one way homomorphic function between two commutative groups $(Γ, +)$ and $(Ω, \times)$ . For an integral value α, $α \cdot x \in Γ$ (resp. $y^{α} \in Ω$ ) denotes α applications of the group law + (resp. ×). For a secret $x \in Γ$ , and any $(h, α, β) \in Γ \times Z^{2}$ , the attacker can build a proof of possession of $α \cdot h + β \cdot x$ . In the setting of the example of Fig. 1, we used $f (x) = g^{x}$ , $h = 1$ , $α = 1$ and $β = - 1$ .

In the general case also, upon demand of proof by Victor, Mallory starts a proof with Peggy. The secret of Peggy is x, and the associated witness v is $v = f (x)$ . Then Mallory wants to prove that his witness w corresponds to any combination of x with a logarithm h that he knows. With only public knowledge and his chosen $(h, α, β) \in Γ \times Z^{2}$ , Mallory is able to compute $w = f {(h)}^{α} \cdot v^{β}$ . For the proof of knowledge, Mallory still modifies the commitment $z = f (r)$ of Peggy to $y = z^{β}$ . Mallory forwards the challenge c of Victor without modification. Finally Mallory transforms the response s of Peggy, still with only public knowledge and his chosen $(h, α, β) \in Γ \times Z^{2}$ , as $u = c \cdot (α \cdot h) + β \cdot s$ . We summarize this general attack on Fig. 2.

Fig. 2.

Man-in-the-middle attack proving knowledge of any affine transform of a secret discrete logarithm in the generic setting.

Lemma 1.

In the generalized man-in-the-middle attack described above (cf. Fig. 2) on the interactive proof of knowledge of a discrete logarithm, Victor is convinced by Mallory’s proof of knowledge of $α \cdot h + β \cdot x$ .

Proof.

Indeed, $u = c \cdot (α \cdot h) + β \cdot s = c \cdot (α \cdot h) + β \cdot (r + c \cdot x) = β \cdot r + c \cdot (α \cdot h + β \cdot x) .$ (1) Now, since $z = f (r)$ , $y = z^{β}$ , $v = f (x)$ and $f {(h)}^{α} \times v^{β} = w$ , the latter Eq. (1) proves in turn that $f (u) = f {(r)}^{β} \times f {(α \cdot h + β \cdot x)}^{c} = z^{β} \times {(f {(h)}^{α} \times f {(x)}^{β})}^{c} = y \times w^{c} .$ (2) Now Victor has to verify the commitment–challenge–response $(y, c, u)$ of Mallory for his witness w. Then Victor needs to checks whether $f (u)$ corresponds to $y \times w^{c}$ , which is the case as shown by the latter Eq. (2). □

2.3.2. Generalizations to equality of discrete logarithms

We let EQDL denote a proof of equality of several discrete logarithms. Any PDL can in general easily be transformed to an EQDL by applying it k times on the same witness. It is often more efficient to combine the application in one as in [10,11], or more generally as composition of Σ-protocols, here with two logarithms and two generators $g_{1}$ and $g_{2}$ . Peggy wants to prove that she knows x such that $v = g_{1}^{x}$ and $w = g_{2}^{x}$ :

Peggy chooses r at random and sends $λ = g_{1}^{r}$ and $μ = g_{2}^{r}$ to Victor.

Victor chooses a challenge c at random and sends it to Peggy.

Peggy computes $s = (r + c \cdot x) mod q$ and sends it to Victor.

Victor tests if $g_{1}^{s} = λ \cdot v^{c}$ and $g_{2}^{s} = μ \cdot w^{c}$ .

This protocol remains malleable, and the previous attacks are still valid since the response remains of the form

r + c \cdot x

2.3.3. Countermeasures

Direct countermeasures to the above attacks are to use non-interactive and/or non-malleable proofs:

An interactive protocol can be converted into a non-interactive one using the Fiat–Shamir heuristic [16]. In this case the challenge is computed as a cryptographic hash of all previous values, and is not submitted by the verifier. This makes it impossible for Mallory to choose the challenge according to his needs (since for him the previous values and hence the hash are different), which prevents the attack.

Also the first PDL by [9] uses bit-flipping, and more generally non-malleable protocols like [18] could be used.

We will show in the following that if the proofs proposed in the original paper are not converted into non-interactive proofs, there is an attack on privacy. Note that even if non-interactive non-malleable zero-knowledge proofs are used, a malicious attacker in control of the network can nonetheless recover any bidder’s bid as the messages are not authenticated, as we show in Section 5.

3. Attacking the fully private computations

The first attack we present uses some algebraic properties of the computations performed during the protocol execution. More precisely, it relies on the fact that the outcome computation function is invertible, apart from some added random noise. In the following, we prove that the function without random noise is injective, and give an algorithm to invert it. Then we show that an attacker can actually remove the random noise, and that this is unnoticeable to the other participants if malleable zero-knowledge proofs are used. Finally we give a detailed description of the attack, and discuss countermeasures.

3.1. Analysis of the outcome computation

The idea is to analyze the computations done in Step (3) of the protocol. Consider the following example with three bidders and three possible prices. Then the first bidder computes $\begin{matrix} γ_{11}^{1} = ( & (α_{12} \cdot α_{13} \cdot & α_{22} \cdot α_{23} \cdot & α_{32} \cdot α_{33}) & \cdot & (1) & \cdot & (1) & )^{m_{11}^{1}}, \\ γ_{12}^{1} = ( & (α_{13} \cdot & α_{23} \cdot & α_{33}) & \cdot & (α_{11}) & \cdot & (1) & )^{m_{12}^{1}}, \\ γ_{13}^{1} = ( & (1) & \cdot & (α_{11} \cdot α_{12}) & \cdot & (1) & )^{m_{13}^{1}}, \\ γ_{21}^{1} = ( & (α_{12} \cdot α_{13} \cdot & α_{22} \cdot α_{23} \cdot & α_{32} \cdot α_{33}) & \cdot & (1) & \cdot & (α_{11}) & )^{m_{21}^{1}}, \\ γ_{22}^{1} = ( & (α_{13} \cdot & α_{23} \cdot & α_{33}) & \cdot & (α_{21}) & \cdot & (α_{12}) & )^{m_{22}^{1}}, \\ γ_{23}^{1} = ( & (1) & \cdot & (α_{21} \cdot α_{22}) & \cdot & (α_{13}) & )^{m_{23}^{1}}, \\ γ_{31}^{1} = ( & (α_{12} \cdot α_{13} \cdot & α_{22} \cdot α_{23} \cdot & α_{32} \cdot α_{33}) & \cdot & (1) & \cdot & (α_{11} \cdot α_{21}) & )^{m_{31}^{1}}, \\ γ_{32}^{1} = ( & (α_{13} \cdot & α_{23} \cdot & α_{33}) & \cdot & (α_{31}) & \cdot & (α_{12} \cdot α_{22}) & )^{m_{32}^{1}}, \\ γ_{33}^{1} = ( & (1) & \cdot & (α_{31} \cdot α_{32}) & \cdot & (α_{13} \cdot α_{23}) & )^{m_{33}^{1}} . \end{matrix}$ The second and third bidder do the same computations, but using different random values $m_{i j}^{a}$ . Since each $α_{i j}$ is either the encryption of 1 or Y, for example the value $γ_{22}^{1}$ will be an encryption of 1 only if

nobody submitted a higher bid (the first block) and

bidder 2 did not bid a lower bid (the second block) and

no bidder with a lower index submitted the same bid (the third block).

If we ignore the exponentiation by

m_{i j}^{a}

, each

γ_{i j}^{a}

is the encryption of the product of several

b_{i j}

’s. Each

b_{i j}

can be either 1 or Y, hence

{(γ_{i j}^{a})}^{- m_{i j}^{a}}

will be the encryption of a value

Y^{l_{i j}}

, where

0 ⩽ l_{i j} ⩽ n

. The lower bound of

l_{i j}

is trivial, the upper bound follows from the observation that each

α_{i j}

will be used at most once, and that each bidder will encrypt Y at most once.

Assume for now that we know all $l_{i j}$ . We show next that this is sufficient to obtain all bids. Consider the function f which takes as input the following vector:1

¹
By abuse of notation we write ${log}_{s} (x_{1}, \dots, x_{n})$ for $({log}_{s} (x_{1}), \dots, {log}_{s} (x_{n}))$ .

b = {log}_{Y} ({(\begin{matrix} b_{11}, \dots, b_{1 k}, & b_{21}, \dots, b_{2 k}, & \dots, & b_{n 1}, \dots, b_{n k} \end{matrix})}^{T}),

and returns the values

l_{i j}

. The input vector is thus a vector of all bid-vectors, where 1 is replaced by 0 and Y by 1. Consider our above example with three bidders and three possible prices, then we have:

b = {log}_{Y} ({(\begin{matrix} b_{11}, b_{12}, b_{13}, & b_{21}, b_{22}, b_{23}, & b_{31}, b_{32}, b_{33} \end{matrix})}^{T}) .

A particular instance where bidder 1 and 3 submit price 1, and bidder 2 submits price 2 would then look as:

b = {(1, 0, 0, 0, 1, 0, 1, 0, 0)}^{T}

. Hence only the factors

α_{11}

α_{22}

and

α_{31}

are encryptions of Y, all other α’s are encryptions of 1. By simply counting how often the factors

α_{11}

α_{22}

and

α_{31}

show up in each equation as described above, we can compute the following result:

f (b) = {(1, 1, 1, 2, 0, 1, 2, 1, 1)}^{T}

. Note that since we chose the input of f to be a bit-vector, we have to simply count the ones (which correspond to Y’s) in particular positions in b, where the positions are determined by the factors inside

γ_{i j}^{a}

. Hence we can express f as a matrix, i.e.

f (b) = M \cdot b

for the following matrix M:

f (b) = M \cdot b = [\begin{matrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \end{matrix}] \cdot (\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}) = (\begin{matrix} 1 \\ 1 \\ 1 \\ 2 \\ 0 \\ 1 \\ 2 \\ 2 \\ 1 \end{matrix}) .

To see how the matrix M is constructed, consider for example

{(γ_{22}^{a})}^{- m_{22}^{a}} = (α_{13} \cdot α_{23} \cdot α_{33}) \cdot (α_{21}) \cdot (α_{12})

which corresponds to the second row in the second vertical block:

$α_{12}$ and $α_{13}$ ; hence the two ones at position 2 and 3 in the first horizontal block,

$α_{21}$ and $α_{23}$ ; hence the two ones at position 1 and 3 in the second horizontal block,

$α_{33}$ ; hence the one at position 3 in the third horizontal block.

More generally, we can see that each

3 \times 3

block consists of potentially three parts:

An upper triangular matrix representing all bigger bids.

On the block diagonal we add a lower triangular matrix representing a lower bid by the same bidder.

In the lower left half we add an identity matrix representing a bid at the current price by a bidder with a lower index.

This corresponds exactly to the structure of the products inside each

γ_{i j}^{a}

. It is also equivalent to formula (1) in Section 4.1.1 of the original paper [5] without the random matrix

R_{k}^{*}

. In the following we prove that the function f is injective. We then discuss how this function can be efficiently inverted (i.e. how to compute the bids when knowing all

l_{i j}

’s).

3.2. Linear algebra toolbox

Let $I_{k}$ be the $k \times k$ identity matrix; let $L_{k}$ be a lower $k \times k$ triangular matrix with zeroes on the diagonal, ones in the lower part and zeroes elsewhere; and let $U_{k}$ be an upper $k \times k$ triangular matrix with zeroes on the diagonal, ones in the upper part, and zeroes elsewhere: $I_{k} = [\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & ⋱ & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 0 \\ 0 & \dots & 0 & 1 \end{matrix}], L_{k} = [\begin{matrix} 0 & 0 & \dots & 0 \\ 1 & ⋱ & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 0 \\ 1 & \dots & 1 & 0 \end{matrix}], U_{k} = [\begin{matrix} 0 & 1 & \dots & 1 \\ 0 & ⋱ & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 1 \\ 0 & \dots & 0 & 0 \end{matrix}] .$

By abuse of notation we use I, L and U to denote respectively $I_{k}$ , $L_{k}$ and $U_{k}$ . For a $k \times k$ -matrix $M_{k}$ we define ${(M_{k})}^{r} = M_{k} \dots M_{k}$ (r times) and ${(M_{k})}^{0} = I_{k}$ . Let $(e_{1}, \dots, e_{k})$ be the canonical basis.

The matrix U (resp. L) are called strictly upper (lower) triangular and are defined such as for all $i ⩽ j$ (resp. $j ⩽ i$ ) $U_{i j} = 0$ (resp. $L_{i j} = 0$ ).

Lemma 2.
Matrices $L_{k}$ and $U_{k}$ are nilpotent, i.e. ${(U_{k})}^{k} = 0$ and ${(L_{k})}^{k} = 0$ .
Proof.
We only do the proof for a strictly upper triangular matrix U, the proof for a strictly lower triangular matrix is similar. We prove by induction that $U_{i j}^{k} = 0$ for $i > j - k$ , this implies that if U is of size $m \times m$ then for all $k ⩾ m$ we have $U^{k} = 0$ . We prove this result by induction on the exponent of U:
Base case: $U_{i j}^{1} = 0$ for all $i > j - 1$ , since by definition of U for all $i ⩽ j$ we have $U_{i j} = 0$ .

Induction step: We assume that $U_{i j}^{k - 1} = 0$ for all $i > j - (k - 1)$ , we prove that $U_{i j}^{k} = 0$ holds for all $i > j - (k - 1)$ . By definition of the matrix product we have: $\begin{array}{rcl} U_{i j}^{k} & = & {(U U^{k - 1})}_{i j} \\ = & \sum_{r = 1}^{m} U_{i r} U_{r j}^{k - 1} \\ = & \sum_{r = 1}^{i} U_{i r} U_{r j}^{k - 1} + \sum_{r = i + 1}^{m} U_{i r} U_{r j}^{k - 1} \\ = & \sum_{r = 1}^{i} 0 \cdot U_{r j}^{k - 1} + \sum_{r = i + 1}^{m} U_{i r} \cdot 0 \\ = & 0 . \end{array}$ In the first sum we have $U_{i r} = 0$ since $r ⩽ i$ and since U is strictly upper triangular. In the second sum, we apply the induction hypothesis with $r ⩾ i + 1 > (j - k) + 1 = j - (k - 1)$ to obtain $U_{r j}^{k - 1} = 0$ . □

Lemma 3.
Let $w = (w_{1}, \dots, w_{k})$ , if $\sum_{j = 1}^{k} w_{j} = 1$ then we have $L_{k} \cdot w = {(1, \dots, 1)}^{T} - (I_{k} + U_{k}) \cdot w$ .
Proof.
First note that since $\sum_{j = 1}^{k} w_{j} = 1$ , $L_{k} \cdot w = [\begin{matrix} 0 & 0 & \dots & 0 \\ 1 & ⋱ & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 0 \\ 1 & \dots & 1 & 0 \end{matrix}] \cdot [\begin{matrix} w_{1} \\ ⋮ \\ w_{k} \end{matrix}] = [\begin{matrix} 0 \\ w_{1} \\ w_{1} + w_{2} \\ ⋮ \\ \sum_{j = 1}^{k - 1} w_{j} \end{matrix}] = [\begin{matrix} 1 - \sum_{j = 1}^{k} w_{j} \\ 1 - \sum_{j = 2}^{k} w_{j} \\ ⋮ \\ 1 - w_{k} \end{matrix}] .$ On the other hand, if we let $1 = {(1, \dots, 1)}^{T}$ , we have also: $1 - (I_{k} + U_{k}) \cdot w = 1 - [\begin{matrix} 1 & 1 & \dots & 1 \\ 0 & 1 & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 1 \\ 0 & \dots & 0 & 1 \end{matrix}] \cdot [\begin{matrix} w_{1} \\ ⋮ \\ w_{k} \end{matrix}] = [\begin{matrix} 1 - \sum_{j = 1}^{k} w_{j} \\ 1 - \sum_{j = 2}^{k} w_{j} \\ ⋮ \\ 1 - w_{k} \end{matrix}] . □$
Lemma 4.
For $z = e_{i} - e_{j}$ , we have that $(L_{k} + U_{k}) \cdot z = - z$ .
Proof.
If $i = j$ , then $z = 0$ and the results is true. Suppose w.l.o.g. that $i > j$ (otherwise we just prove the result for $- z$ ). Then $U_{k} \cdot (e_{i} - e_{j}) = \sum_{s = 1}^{i - 1} e_{s} - \sum_{s = 1}^{j - 1} e_{s} = \sum_{s = j}^{i - 1} e_{s} .$ Similarly $L_{k} \cdot (e_{i} - e_{j}) = \sum_{s = i + 1}^{k} e_{s} - \sum_{s = j + 1}^{k} e_{s} = \sum_{s = j + 1}^{i} - e_{s} .$ Therefore, $(L_{k} + U_{k}) \cdot (e_{i} - e_{j}) = \sum_{s = j}^{i - 1} e_{s} - \sum_{s = j + 1}^{i} e_{s} = e_{j} - e_{i} = - z . □$

3.3. How to recover the bids when knowing the $l_{i j}$ ’s

As discussed above, we can represent the function f as a matrix multiplication. Let M be the following square matrix of size $n k \times n k$ : $M = [\begin{matrix} (U + L) & U & \dots & \dots & U \\ (U + I) & (U + L) & U & \dots & U \\ ⋮ & ⋱ & ⋱ & ⋱ & ⋮ \\ (U + I) & \dots & (U + I) & (U + L) & U \\ (U + I) & \dots & \dots & (U + I) & (U + L) \end{matrix}] . Then f (b) = M \cdot b .$ The function takes as input a vector composed of n vectors, each of k bits. It returns the $n k$ values $l_{i j}$ , $1 ⩽ i ⩽ n$ and $1 ⩽ j ⩽ k$ . As explained above, the structure of the matrix is defined by the formula that computes $γ_{i j}^{a}$ , which consists essentially of three factors: first we multiply all $α_{i j}$ which encode bigger bids (represented by the matrix U), then we multiply all $α_{i j}$ which encode smaller bids by the same bidder (represented by adding the matrix L on the diagonal), and finally we multiply by all $α_{i j}$ which encode the same bid by bidders with a smaller index (represented by adding the matrix I on the lower triangle of M). In our encoding there will be a “1” in the vector for each Y in the protocol, hence f will count how many Ys are multiplied when computing $γ_{i j}^{a}$ .

Example 5 (f in the case of two bidders and two prices).

In the case of two bidders and two possible prices, we obtain the following matrix M: $M = [\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix}] .$ In this example, we have four possible cases for the bids: $b_{0} = (\begin{matrix} 1 \\ 0 \\ 1 \\ 0 \end{matrix}), b_{1} = (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}), b_{2} = (\begin{matrix} 0 \\ 1 \\ 1 \\ 0 \end{matrix}), b_{3} = (\begin{matrix} 0 \\ 1 \\ 0 \\ 1 \end{matrix}) .$ We can compute f for all cases: $f (b_{0}) = (\begin{matrix} 0 \\ 1 \\ 1 \\ 1 \end{matrix}), f (b_{1}) = (\begin{matrix} 1 \\ 1 \\ 2 \\ 0 \end{matrix}), f (b_{2}) = (\begin{matrix} 1 \\ 0 \\ 1 \\ 2 \end{matrix}), f (b_{3}) = (\begin{matrix} 2 \\ 0 \\ 2 \\ 1 \end{matrix}) .$ In this example it is easy to see that for all $i \neq j$ we have $f (b_{i}) \neq f (b_{j})$ , even if the winner and the winning price is the same, as for example in the case of $b_{2}$ and $b_{3}$ .

In general, we can prove the following theorem stating that f is injective.

Theorem 6.
f is injective on valid bid vectors, i.e. for two different correct bid vectors $u = {[u_{1}, \dots, u_{k}]}^{T}$ and $v = {[v_{1}, \dots, v_{k}]}^{T}$ with $u \neq v$ we have $M \cdot u \neq M \cdot v$ .
Proof.
Let u and v be two correct bid vectors such that $u \neq v$ . We want to prove that $M \cdot u \neq M \cdot v$ . We make a proof by contradiction, hence we assume that $M \cdot u = M \cdot v$ or that $M \cdot (u - v) = 0$ . Because u and v are two correct bid vectors, each one of them is an element of the canonical basis $(e_{1}, \dots, e_{k})$ , i.e. $u = e_{i}$ and $v = e_{j}$ , as shown in Section 3.1. We denote $u - v$ by z, and consequently $z = e_{i} - e_{j}$ . Knowing that $M \cdot z = 0$ , we prove by induction on a that for all a the following property $P (a)$ holds: $P (a) : \forall l, 0 < l ⩽ a, diag (U^{k - l}) \cdot z = 0,$ where $diag (U^{k - x})$ is a $n k \times n k$ block diagonal matrix containing only diagonal blocks of the same matrix $U^{k - x}$ . The validity of $P (k)$ proves in particular that $diag (U^{0}) \cdot z_{l} = 0$ , i.e. $z = 0$ which contradicts our hypothesis.
Case $a = 1$ : we also prove this base case by induction, i.e. for all $b ⩾ 1$ the property $Q (b)$ holds, where: $Q (b) : \forall m, 0 < m ⩽ b, U^{k - 1} \cdot z_{m} = 0$ which gives us that $U^{k - 1} \cdot z = 0$ .

Base case $b = 1$ : We start by looking at the multiplication of the first row of M with z. We obtain: $(L + U) \cdot z_{1} + U \cdot (z_{2} + \dots + z_{k}) = 0 .$ We can multiply each side by $U^{k - 1}$ , and use Lemma 4 to obtain: $U^{k - 1} \cdot [- z_{1} + U \cdot (z_{2} + \dots + z_{k})] = 0 .$ Since U is nilpotent, according to Lemma 2 the latter gives $- U^{k - 1} \cdot z_{1} = 0$ . Hence we know $Q (1) : U^{k - 1} \cdot z_{1} = 0$ , i.e. the last entry of $z_{1}$ is 0.

Inductive step $b + 1$ : assume $Q (b)$ . Consider now the multiplication of the $(b + 1)$ th row of the matrix M: $(U + I) \cdot z_{1} + \dots + (U + I) \cdot z_{b} + (L + U) \cdot z_{b + 1} + U \cdot (z_{b + 2} + \dots + z_{k}) = 0 .$ Then by multiplying by $U^{k - 1}$ and using Lemma 4 we obtain: $U^{k - 1} \cdot [(U + I) \cdot z_{1} + \dots + (U + I) \cdot z_{b} - z_{b + 1} + U \cdot (z_{b + 2} + \dots + z_{k})] = 0 .$ Since U is nilpotent according to Lemma 2 we have $U^{k - 1} \cdot z_{1} + \dots + U^{k - 1} \cdot z_{b} - U^{k - 1} \cdot z_{b + 1} = 0 .$ Using the fact that for all $m < b$ we have $U^{k - 1} \cdot z_{m} = 0$ , the latter gives $- U^{k - 1} \cdot z_{b + 1} = 0$ .

Inductive step $a + 1$ : assume $P (a)$ . By induction on $b ⩾ 1$ we will show that $Q^{'} (b)$ holds, where $Q^{'} (b) : \forall m, 0 < m ⩽ b, U^{k - (a + 1)} \cdot z_{m} = 0$ which gives us that $U^{k - (a + 1)} \cdot z = 0$ , i.e. $P (a + 1)$ .

Base case $b = 1$ : Consider the multiplication of the first row with $U^{k - (a + 1)}$ : $U^{k - (a + 1)} \cdot [(L + U) \cdot z_{1} + U \cdot (z_{2} + \dots + z_{k})] = 0$ which can be rewritten as $- U^{k - (a + 1)} \cdot z_{1} + U^{k - a} \cdot (z_{2} + \dots + z_{k}) = 0 .$ Using $U^{k - a} \cdot z_{l} = 0$ for all l, we can conclude that $- U^{k - (a + 1)} \cdot z_{1} = 0$ , i.e. $Q^{'} (1)$ holds.

Inductive step $b + 1$ : assume $Q^{'} (b)$ . Consider now the $(b + 1)$ th row of the matrix M: $(U + I) \cdot z_{1} + \dots + (U + I) \cdot z_{b} + (L + U) \cdot z_{b + 1} + U \cdot (z_{b + 2} + \dots + z_{k}) = 0 .$ Then by multiplying by $U^{k - (a + 1)}$ and using Lemma 4 we obtain: $U^{k - (a + 1)} \cdot [(U + I) \cdot z_{1} + \dots + (U + I) \cdot z_{b} + (- z_{b + 1}) + U \cdot (z_{b + 2} + \dots + z_{k})] = 0 .$ Using $U^{k - a} \cdot z_{l} = 0$ for all l, we can conclude that $U^{k - (a + 1)} \cdot z_{1} + \dots + U^{k - (a + 1)} \cdot z_{b} - U^{k - (a + 1)} \cdot z_{b + 1} = 0 .$ Now, for all $m < b$ , we have $U^{k - (a + 1)} \cdot z_{m} = 0$ , so that $- U^{k - (a + 1)} \cdot z_{b + 1} = 0$ ; i.e. $Q^{'} (b + 1)$ holds. □

This theorem shows that if there is a constellation of bids that led to certain values $l_{i j}$ , this constellation is unique. Hence we are able to invert f on valid outputs. We will now show that this can be efficiently done.
3.3.1. Recursive formulae for the bids

Our aim is to solve the following linear system: $M \cdot x = l$ . We will use the same steps we used for the proof of injectivity to solve this system efficiently. Consider the rth block of size k of the latter system. We have $x_{r} = (x_{r, 1}, x_{r, 2}, \dots, x_{r, k})$ and the rth block of $M \cdot x$ is $\begin{array}{l} (U + I) x_{1} + \dots + (U + I) x_{r - 1} + (L + U) x_{r} + U x_{r + 1} + \dots + U x_{n} \\ = U (\sum_{i = 1}^{n} x_{i}) + (\sum_{i = 1}^{r - 1} x_{i}) + L x_{r} . \end{array}$ As the rth block of l is $l_{r}$ , we thus have: $U (\sum_{i = 1}^{n} x_{i}) + \sum_{i = 1}^{r - 1} x_{i} + L x_{r} = l_{r} .$

Using Lemma 3, with $w_{j} = x_{r, j}$ for $j = 1. . k$ , we can exchange L in the latter to get $U (\sum_{i = 1}^{n} x_{i}) + \sum_{i = 1}^{r - 1} x_{i} + (1 - (I + U) x_{r}) = l_{r} .$ Hence, $U (\sum_{i = 1}^{n} x_{i}) + \sum_{i = 1}^{r - 1} x_{i} + 1 - x_{r} - U x_{r} = l_{r},$ so that we now have: $\{\begin{matrix} x_{1} = 1 - l_{1} + U (\sum_{i = 2}^{n} x_{i}), \\ x_{r} = 1 - l_{r} + \sum_{i = 1}^{r - 1} x_{i} + U (\sum_{i = 1, i \neq r}^{n} x_{i}) if 1 < r ⩽ n . \end{matrix}$ (3)

This gives us a formula to compute the values of $x_{i, j}$ , starting with the last element of the first block $x_{1, k}$ . Then we can compute the last elements of all other blocks $x_{2, k}, \dots, x_{n, k}$ , and then the second to last elements $x_{1, k - 1}, \dots, x_{n, k - 1}$ , etc.

The idea is to project the above Eq. (3) on the tth coordinate. Then, the tth row of U has ones only starting at index $t + 1$ , and thus the tth row of $U z$ involves only the elements $z_{t + 1}, \dots, z_{k}$ . We thus have: $e_{t}^{T} U (\sum_{i = 1, i \neq r}^{n} x_{i}) = \sum_{j = t + 1}^{k} \sum_{i = 1, i \neq r}^{n} x_{i, j}$ for $t < k$ and $e_{k}^{T} U = 0$ . Now $e_{t}^{T} x_{r} = x_{r, t}$ , $e_{t}^{T} l_{r} = l_{r, t}$ and $e_{t}^{T} 1 = 1$ . Hence, we therefore get the following where at row t, the right-hand side involves only already computed values: $\{\begin{matrix} x_{1, k} = 1 - l_{1, k}, \\ x_{r, k} = 1 - l_{r, k} + \sum_{i = 1}^{r - 1} x_{i, k} & if 1 < r ⩽ n, \\ x_{1, t} = 1 - l_{1, t} + \sum_{j = t + 1}^{k} \sum_{i = 2}^{n} x_{i, j} & if 1 ⩽ t < k, \\ x_{r, t} = 1 - l_{r, t} + \sum_{i = 1}^{r - 1} x_{i, t} + \sum_{j = t + 1}^{k} \sum_{i = 1, i \neq r}^{n} x_{i, j} & if 1 ⩽ t < k and 1 < r ⩽ n . \end{matrix}$ (4)

3.3.2. Efficient algorithm

Algorithm 1.

Bids recovery

To obtain all values, we have to apply the above formula (4) for each $1 ⩽ r ⩽ n$ and $1 ⩽ t ⩽ k$ , but we know that the bids also satisfy the following constraint: there is a single non-zero value, a one, per block of x of size k. Therefore, the last Eq. (4) can be replaced by the following choice:

Either the location of the bid for the rth bidder, i.e. the non-zero value in $x_{r}$ , has already been found at step t. Then $\exists t + 1 ⩽ j_{0} ⩽ k$ , $x_{r, j_{0}} = 1$ and the remaining part of $x_{r}$ is all zeroes, so that $x_{r, t} = 0$ .

Or $\forall t + 1 ⩽ j ⩽ k$ , $x_{r, j} = 0$ . Then the $i \neq r$ can be removed in the last sum of the formula and $x_{r, t} = 1 - l_{r, t} + \sum_{i = 1}^{r - 1} x_{i, t} + \sum_{j = t + 1}^{k} \sum_{i = 1}^{n} x_{i, j} .$

From this remark, one sees that either we already know the $x_{r, t}$ value or it is just $1 - l_{r, t}$ plus the sum of all the previously computed $x_{i, j}$ . Therefore to efficiently compute all these values, it is sufficient to maintain a counter of the known values as in Algorithm 1.

Theorem 7.

Algorithm 1is correct and its arithmetic cost can be bounded by $O (n k)$ .

Proof.

The correctness follows from the analysis in the beginning of this section. Then for each entry in the output vector, we have to compute two additions, one test and potentially a counter increment. □

This is two orders of magnitude less than the number of operations required just to compute all the encrypted bids.

3.4. Attack on the random noise: How to obtain the

l_{i j}

’s

In the previous section we showed that knowing the $l_{i j}$ ’s allows us the efficiently break the privacy of all bidders. Here is how to obtain the $l_{i j}$ ’s. The seller will learn all $v_{i j} = {(Y^{l_{i j}})}^{(\sum_{h = 1}^{n} m_{i j}^{h})}$ at the end of the protocol. Since the $m_{i j}^{h}$ are randomly chosen, this will be a random value if $l_{i j} \neq 0$ . However, a malicious bidder (“Mallory”, of index a) can cancel out the $m_{i j}^{h}$ as follows: in Step (3) of the protocol each bidder will compute his $γ_{i j}^{a}$ and $δ_{i j}^{a}$ . Mallory waits until all other bidders have published their values (the protocol does not impose any synchronization or special ordering) and then computes his values $γ_{i j}^{ω}$ and $δ_{i j}^{ω}$ as: $\begin{array}{l} γ_{i j}^{ω} = ((\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} α_{h d}) \cdot (\prod_{d = 1}^{j - 1} α_{i d}) \cdot (\prod_{h = 1}^{i - 1} α_{h j})) \cdot {(\prod_{k \neq ω} γ_{i j}^{k})}^{- 1}, \\ δ_{i j}^{ω} = ((\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} β_{h d}) \cdot (\prod_{d = 1}^{j - 1} β_{i d}) \cdot (\prod_{h = 1}^{i - 1} β_{h j})) \cdot {(\prod_{k \neq ω} δ_{i j}^{k})}^{- 1} . \end{array}$ The first part is a correct encryption of $Y^{l_{i j}}$ , with $m_{i j}^{ω} = 1$ for all i and j. The second part is the inverse of the product of all the other bidders $γ_{i j}^{k}$ and $δ_{i j}^{k}$ , and thus it will eliminate the random exponents. Hence after decryption the seller obtains $v_{i j} = Y^{l_{i j}}$ , where $l_{i j} < n$ for a small n. He can compute $l_{i j}$ by simply (pre-)computing all possible values $Y^{r}$ and testing for equality. This allows the seller to obtain the necessary values and then to use the resolution algorithm to obtain each bidder’s bid. Note that although we changed the intermediate values, the output still gives the correct result (i.e. winning bid). Therefore, the attack might even be unnoticed by the other participants. Note also that choosing a different $Y_{i}$ per bidder does not prevent the attack, since all the $Y_{i}$ need to be public in order to prove the correctness of the bid in Step (2) of the protocol.

However the protocol requires Mallory to prove that $γ_{i j}^{ω}$ and $δ_{i j}^{ω}$ have the same exponent. This is obviously the case, but Mallory does not know the exact value of this exponent. Thus it is impossible for him to execute the proposed zero-knowledge protocol directly.

In the original paper [5] the malleable interactive proof of [10], presented in Section 2.3, is used to prove the correctness of $γ_{i j}^{a}$ and $δ_{i j}^{a}$ in Step (3) of the protocol. If this proof is not converted into a non-interactive proof, then Mallory is able to fake it as follows.

3.5. Proof of equality of the presented outcomes

Note that we can rewrite $γ_{i j}^{ω}$ and $δ_{i j}^{ω}$ as: $\begin{matrix} v = γ_{i j}^{ω} = {\underset{g_{1}}{\underset{︸}{((\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} α_{h d}) \cdot (\prod_{d = 1}^{j - 1} α_{i d}) \cdot (\prod_{h = 1}^{i - 1} α_{h j}))}}}^{1 - (\sum_{k \neq ω} m_{i j}^{k})}, \\ w = δ_{i j}^{ω} = {\underset{g_{2}}{\underset{︸}{((\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} β_{h d}) \cdot (\prod_{d = 1}^{j - 1} β_{i d}) \cdot (\prod_{h = 1}^{i - 1} β_{h j}))}}}^{1 - (\sum_{k \neq ω} m_{i j}^{k})} . \end{matrix}$ When Mallory, the bidder m, is asked by Victor for a proof of correctness of his values, he starts by asking all other bidders for proofs to initialize the man-in-the-middle attack of Fig. 1. Each of them answers with values $λ_{o} = g_{1}^{z_{o}}$ and $μ_{o} = g_{2}^{z_{o}}$ . Mallory can then answer Victor with values $λ = \prod_{o} λ_{o}^{- 1}$ and $μ = \prod_{o} μ_{o}^{- 1}$ , where $o \in ([1, n] ∖ m)$ . Victor then sends a challenge c, which Mallory simply forwards to the other bidders. They answer with $r_{o} = z_{o} + c \cdot m_{i j}^{o}$ , and Mallory sends $r = c - \sum_{o} r_{o}$ to Victor, who can check that $g_{1}^{r} = λ \cdot v^{c}$ and $g_{2}^{r} = μ \cdot w^{c}$ . If the other bidders did their proofs correctly, then Mallory’s proof will appear valid to Victor: $\begin{matrix} λ \cdot v^{c} = \prod_{o} λ_{o}^{- 1} \cdot {(g_{1}^{1 - (\sum_{o} m_{i j}^{o})})}^{c} = \prod_{o} g_{1}^{- z_{o}} \cdot g_{1}^{c - c (\sum_{o} m_{i j}^{o})} = g_{1}^{c - \sum_{o} (z_{o} + c m_{i j}^{o})}, \\ μ \cdot w^{c} = \prod_{o} μ_{o}^{- 1} \cdot {(g_{2}^{1 - (\sum_{o} m_{i j}^{o})})}^{c} = \prod_{o} g_{2}^{- z_{o}} \cdot g_{2}^{c - c (\sum_{o} m_{i j}^{o})} = g_{2}^{c - \sum_{o} (z_{o} + c m_{i j}^{o})} . \end{matrix}$ Hence in the case of malleable interactive zero-knowledge proofs Mallory is able to modify the values $γ_{i j}^{ω}$ and $δ_{i j}^{ω}$ as necessary, and even prove the correctness using the bidders. Hence the modifications may stay undetected and the seller will be able to break privacy.

3.6. Efficiency of the attack

In order to measure the practicability of the attack we have implemented the protocol in C++ using the Givaro library2

²
http://givaro.forge.imag.fr/.

for the large modular computations. We have used a 32 cores shared memory Intel Xeon E5-4620 to simulate several bidders, each core running at 2.2 GHz. The computations of the seller (namely the computation of the winner) and of Mallory, our attacker, have been performed on a single core of this machine.

First we report on Table 1 our timings for a different number of bidders and 8192 different possible prices. The “Set-up” column represents the total time required to set-up Brandt’s protocol on our machine with 32 cores whereas the “Set-up/bidder” column represent the time required for each bidder. On the one hand, this shows that Brandt’s protocol requires quite a lot of computing time and that as predicted by the arithmetic complexity, the set-up time can be quite resource demanding for each bidder, as well as for the seller (“Winner computation” is done by the seller). On the other hand, we see that both our attacks are even some orders of magnitude faster than just setting up the protocol and that our novel attack requires only a few seconds to break the privacy of realistic auctions (with hundreds of bidders and thousands of prices).

Table 1

Parallel Brandt for 8192 bids with OpenMP on an Intel Xeon E5-4620, 32×2.2 GHz

Bidders	Bids	Set-up (s)	Set-up/bidder (s)	Winner computation (s)	[DDL13] Attack (s)	Novel attack (s)
2	8192	80.354	80.354	0.454	0.100	0.001
4	8192	124.370	124.370	0.758	0.181	0.002
8	8192	219.641	219.641	1.768	0.594	0.004
16	8192	396.398	396.398	3.620	1.560	0.011
32	8192	1399.480	1399.480	16.945	4.601	0.043
64	8192	4181.830	2090.915	72.924	14.171	0.192
128	8192	14,559.700	3639.925	420.497	54.200	0.664
256	8192	50,546.800	6318.350	2942.650	173.255	2.910

Next we also show in the log scale Fig. 3 that the arithmetic complexity bounds given in Section 3.3.2 are indeed tight: quadratic in the number of bids and bidders for the setting-up and the previous attack; only linear for the novel attack.

Fig. 3.

Parallel Brandt for 32 bidders with OpenMP on an Intel Xeon E5-4620, 32×2.2 GHz. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-150535.)

3.7. The complete attack and countermeasures

Putting everything together, the attack works as follows:

The bidders set up the keys as described in the protocol.

They encrypt and publish their bids.

They compute $γ_{i j}^{h}$ and $δ_{i j}^{h}$ and publish them.

Mallory, who is a bidder himself, waits until all other bidders have published their values. He then computes his values as defined above, and publishes them.

If he is asked for a proof, he can proceed as explained above in Section 3.5.

The bidders (including Mallory) jointly decrypt the values.

The seller obtains all $Y^{l_{i j}}$ ’s. He can then compute the $l_{i j}$ ’s by testing at most n possibilities.

Once he has all values, he can invert the function f as explained above.

He obtains all bidders bids.

Again, note that for all honest bidders, this execution will look normal, so they might not even notice that an attack took place. To prevent this attack, one could perform the following actions:

To counteract the removal of the noise of Section 3.4, the bidders could check whether the product of the $γ_{i, j}^{a}$ for all bidders a is equal to the product of the $α_{h d}$ without any noise (exponent is 1). Unfortunately, the man-in-the-middle attack generalizes to any exponent as shown in Fig. 2. Therefore the attacker could use a randomly chosen exponent only known to him.

As mentioned above, another countermeasure is the use of non-interactive, non-malleable proofs of knowledge. In this case, we will show in Section 5 that it is still possible to attack a targeted bidder’s privacy.

4. Attacking verifiability

Brandt claims that the protocol is verifiable as the parties have to provide zero-knowledge proofs for their computations, however there are two problems.

4.1. Exceptional values

First, a winning bidder cannot verify if he actually won. To achieve privacy, the protocol hides all outputs of $v_{a j}$ except for the entry containing “1”.3

³
Note that the protocol contains a mechanism to resolve ties, i.e. there should always be exactly one entry equal to 1, even in the presence of ties.

This is done by exponentiation with random values

m_{i j}^{a}

inside all entries

γ_{i j}^{a}

and

δ_{i j}^{a}

, i.e. by computing

x_{i j}^{\sum_{a} m_{i j}^{a}}

where

x_{i j}

is the product of some

α_{i j}

as specified in the protocol. If

x_{i j} = 1

, for any k we have

x_{i j}^{k} = 1

. For any other value of

x_{i j}

x_{i j}^{k}

should be different from 1. However, the random values

m_{i j}^{a}

may add up to zero (mod q), hence the returned value will be

x_{i j}^{\sum_{a} m_{i j}^{a}} = x_{i j}^{0} = 1

and the bidder will conclude that he won, although he actually lost (

x_{i j} \neq 1

). Hence simply verifying the proofs is not sufficient to be convinced that the observed outcome is correct. For the same reason the seller might observe two or more “1”-values, even though all proofs are correct. In such a situation he is unable to decide which bidder actually won since he cannot determine which “1”s correspond to a real bids, and hence which bid is the highest real bid. If two “1”s correspond to real bids, he could even exploit such a situation to his advantage: he can tell both bidders that they won and take money from both, although there is only one good to sell – this is normally prohibited by the protocol’s tie-breaking mechanism. If the bidders do not exchange additional data there is no way for them to discover that something went wrong, since the seller is the only party having access to all values.

A solution to this problem could work as follows: when computing the $γ_{i j}^{a}$ and $δ_{i j}^{a}$ , the bidders can check if the product $x_{i j} = (\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} α_{h d}) \cdot (\prod_{d = 1}^{j - 1} α_{i d}) \cdot (\prod_{h = 1}^{i - 1} α_{h j})$ is equal to one – if yes, they restart the protocol using different keys and random values. If not, they continue, and check if $\prod_{a} γ_{i j}^{a} = 1$ . If yes, they choose different random values $m_{i j}^{a}$ and re-compute the $γ_{i j}^{a}$ and $δ_{i j}^{a}$ , otherwise they continue. Since the probability of the random values adding up to zero is low, this will rapidly lead to correct values.

4.2. Different private keys

Second, the paper does not precisely specify the proofs that have to be provided in the joint decryption phase. If the bidders only prove that they use the same private key on all decryptions and not also that it is the one they used to generate their public key, they may use a wrong one. This will lead to a wrong decryption where with very high probability no value is “1”, as they will be random. Hence all bidders will think that they lost, thus allowing a malicious bidder to block the whole auction, as no winner is determined. Hence, if we assume that the verification test consists in verifying the proofs, a bidder trying to verify that he lost using the proofs might perform the verification successfully, although the result is incorrect and he actually won – since he would have observed a “1” if the vector had been correctly decrypted.

This problem can be addressed by requiring the bidders to also prove that they used the same private key as in the key generation phase.

5. Attacks using the lack of authentication

The protocol as described in the original paper does not include any authentication of the messages. This means that an attacker in control of the network can impersonate any party, which can be exploited in many ways. However, the authors supposed in the original paper a “reliable broadcast channel, i.e. the adversary has no control of communication” [5]. Yet even under this assumption dishonest participants can impersonate other participants by submitting messages on their behalf. Additionally, this assumption is difficult to achieve in asynchronous systems [17]. In the following we consider an attacker in control of the network, however many attacks can also be executed analogously by dishonest parties (which are considered in the original paper) in the reliable broadcast setting.

5.1. Another attack on privacy

Our first attack on privacy only works in the case of malleable interactive proofs. If we switch to non-interactive non-malleable proofs, Mallory cannot ask the other bidders for proofs using a challenge of his choice.

However, even with non-interactive non-malleable zero-knowledge proofs, the protocol is still vulnerable to attacks on a targeted bidder’s privacy if an attacker can impersonate any bidder of his choice as well as the seller, which is the case for an attacker controlling the network due to the lack of authentication. In particular, if he wants to know Alice’s bid he can proceed as follows:

Mallory impersonates all other bidders. He starts by creating keys on their behalf and publishes the values $y_{i}$ and the corresponding proofs for all of them.

Alice also creates her secret keyshare and publishes $y_{a}$ together with a proof.

Alice and Mallory compute the public key y.

Alice encrypts her bid and publishes her $α_{a j}$ and $β_{b j}$ together with the proofs.

Mallory publishes $α_{i j} = α_{a j}$ and $β_{i j} = β_{a j}$ for all other bidders i and also copies Alice’s proofs.

Alice and Mallory execute the computations described in the protocol and publish $γ_{i j}^{a}$ and $δ_{i j}^{a}$ .

They compute $ϕ_{i j}^{a}$ and send it to the seller.

The seller publishes the $ϕ_{i j}^{a}$ and computes the $v_{a j}$ .

Since all submitted bids are equal, the seller (which might also be impersonated by Mallory) will obtain Alice’s bid as the winning price, hence it is not private any more. This attack essentially simulates a whole instance of the protocol to make Alice indirectly reveal a bid that was intended for another, probably real auction. To counteract this it is not sufficient for Alice to check that the other bids are different: Mallory can produce different

α_{i j} = α_{a j} y^{x}

together with

β_{i j} = β_{a j} g^{x}

which are still correct encryptions of Alice bids.

Note that the same attack also works if dishonest bidders collude with the seller: they simply re-submit the targeted bidders bid as their own bid.

5.2. Attacking fairness, non-repudiation and verifiability

The lack of authentication obviously entails that a winning bidder can claim that he did not submit his bid, hence violating non-repudiation (even in the case of reliable broadcast). Additionally, this also enables an attack on fairness: an attacker in control of the network can impersonate all bidders vis-à-vis the seller, submitting bids of his choice on their behalf and hence completely controlling the winner and winning price. This also causes another problem with verifiability: it is impossible to verify if the bids were submitted by the registered bidders, or by somebody else.

5.3. Countermeasures

The solution to these problems is simple: all the messages need to be authenticated, e.g. using signatures or Message Authentication Codes (MACs). This requires a trust anchor, for example a Public Key Infrastructure (PKI) that verifies the identities of the participants and certifies their keys.

6. Conclusion

In this paper we analyzed the protocol of Brandt [5] from various angles. We showed that the underlying computations have a weakness which can be exploited by malicious bidders to break privacy if malleable interactive zero-knowledge proofs are used. Using an implementation of the protocol and the attack we illustrated its practical efficiency. We also identified two problems with verifiability and proposed solutions. Finally we showed how the lack of authentication can be used to mount different attacks on privacy, verifiability as well as fairness and non-repudiation. Again we suggested a solution to address the discovered flaws.

So sum up, the following countermeasures have to be implemented:

Use of non-interactive or non-malleable zero-knowledge proofs.

All messages have to be authenticated, e.g. using a Public-Key Infrastructure (PKI) and signatures.

In the outcome computation step: when computing the $γ_{i j}^{a}$ and $δ_{i j}^{a}$ , the bidders can check if $x_{i j} = (\prod_{h = 1}^{n} \prod_{d = j + 1}^{k} α_{h d}) \cdot (\prod_{d = 1}^{j - 1} α_{i d}) \cdot (\prod_{h = 1}^{i - 1} α_{h j})$ is equal to one – if yes, they restart the protocol using different keys and random values. If not, they continue, and check if $\prod_{a} γ_{i j}^{a} = 1$ . If yes, they choose different random values $m_{i j}^{a}$ and re-compute the $γ_{i j}^{a}$ and $δ_{i j}^{a}$ , otherwise they continue.

In the outcome decryption step: the bidders have to prove that the value $x_{a}$ they used to decrypt is the same $x_{a}$ they used to generate their public key $y_{a}$ in the first step.

The attacks show that properties such as authentication can be necessary to achieve other properties like for instance privacy, which might appear to be unrelated at first sight. It also points out that there is a difference between computing the winner in a fully private way, and ensuring privacy for the bidders: in the second attack we use modified inputs to break privacy even though the computations themselves are secure. Additionally our analysis highlights that the choice of interactive or non-interactive, malleable or non-malleable proofs is an important decision in any protocol design.

As for possible generalizations of our attacks, of course the linear algebra part of our first attack is specific to this protocol. Yet the man-in-the-middle attack on malleable proofs as well as the need of authentication for privacy are applicable to any protocol. Similarly, checking all exceptional cases and ensuring that the same keys are used all along the process are also valid insights for other protocols.

As future work we would like to realize a full formal security proof of the fixed protocol.

Footnotes

Acknowledgments

This work was partly supported by the ANR projects ProSe (decision ANR-2010-VERS-004-01), HPAC (ANR-11-BS02-013) and the support of the “Digital Trust” Chair from the University of Auvergne Foundation. We also thank Dorian Arnaud, Jean-Baptiste Gheeraert, Maud Lefevre, Simon Moura and Jérémy Pouzet for spotting an error in the description of our first attack in [].

References

[1]

Attanasio,

Ghiani,

Grandinetti,

Guerriero and

Guerriero, Operations research methods for resource management and scheduling in a computational grid: A survey, in: Grid Computing the New Frontier of High Performance Computing,

Grandinetti, ed., Advances in Parallel Computing, Vol. 14, North-Holland, 2005, pp. 53–81.

[2]

Bangerter,

Camenisch and

U.M.

Maurer, Efficient proofs of knowledge of discrete logarithms and representations in groups with hidden order, in: Proceedings of the 8th International Conference on Theory and Practice in Public Key Cryptography, PKC’05, Springer, Berlin, Heidelberg, 2005, pp. 154–171.

[3]

Brandt, A verifiable, bidder-resolved auction protocol, in: Proceedings of the 5th AAMAS Workshop on Deception, Fraud and Trust in Agent Societies,

Falcone,

Barber,

Korba and

Singh, eds, 2002, pp. 18–25.

[4]

Brandt, Fully private auctions in a constant number of rounds, in: Financial Cryptography 2003, LNCS, Vol. 2742, Springer, 2003, pp. 223–238.

[5]

Brandt, How to obtain full privacy in auctions, International Journal of Information Security5 (2006), 201–216.

[6]

Burmester,

Desmedt,

Piper and

Walker, A general zero-knowledge scheme, in: Advances in Cryptology – EUROCRYPT’89, Houthalen, Belgium, April 1989, LNCS, Vol. 434, Springer, 1989, pp. 122–133.

[7]

Buyya,

Abramson,

Giddy and

Stockinger, Economic models for resource management and scheduling in grid computing, Concurrency and Computation: Practice and Experience14(13–15) (2002), 1507–1542.

[8]

Chaum,

J.-H.

Evertse and

van de Graaf, An improved protocol for demonstrating possession of discrete logarithms and some generalizations, in: Advances in Cryptology – EUROCRYPT’87, Amsterdam, The Netherlands, 13–15 April 1987, LNCS, Vol. 304, 1987, pp. 127–141.

[9]

Chaum,

J.H.

Evertse,

van de Graaf and

Peralta, Demonstrating possession of a discrete logarithm without revealing it, in: CRYPTO’86, LNCS, Vol. 263, Springer, 1986, pp. 200–212.

10.

[10]

Chaum and

T.P.

Pedersen, Wallet databases with observers, in: Crypto’92, LNCS, Vol. 740, Springer, California, USA, 1992, pp. 89–105.

11.

[11]

S.S.M.

Chow,

Ma and

Weng, Zero-knowledge argument for simultaneous discrete logarithms, in: COCOON,

M.T.

Thai and

Sahni, eds, LNCS, Vol. 6196, Springer, 2010, pp. 520–529.

12.

[12]

Cramer and

Damgård, Zero-knowledge proofs for finite field arithmetic, or: Can zero-knowledge be for free?, in: Advances in Cryptology – CRYPTO’98,

Krawczyk, ed., LNCS, Vol. 1462, Springer, Berlin, Heidelberg, 1998, pp. 424–441.

13.

[13]

Curtis,

Pieprzyk and

Seruga, An efficient eAuction protocol, in: ARES, IEEE Computer Society, 2007, pp. 417–421.

14.

[14]

Dreier,

J.-G.

Dumas and

Lafourcade, Brandt’s fully private auction protocol revisited, in: Proceedings of the 6th International Conference on Cryptology in Africa, AfricaCrypt’2013, Cairo, Egypt, June 2013, LNCS, Vol. 7918, 2013, pp. 88–106.

15.

[15]

ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in: Proceedings of CRYPTO 84 on Advances in Cryptology, Springer, New York, NY, USA, 1985, pp. 10–18.

16.

[16]

Fiat and

Shamir, How to prove yourself: Practical solutions to identification and signature problems, in: CRYPTO,

A.M.

Odlyzko, ed., LNCS, Vol. 263, Springer, 1986, pp. 186–194.

17.

[17]

M.J.

Fischer,

N.A.

Lynch and

Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM32(2) (1985), 374–382.

18.

[18]

Fischlin and

Fischlin, Efficient non-malleable commitment schemes, Journal of Cryptology22 (2009), 530–571.

19.

[19]

Katz, Efficient cryptographic protocols preventing “man-in-the-middle” attacks, PhD thesis, Columbia University, 2002.

20.

[20]

Krishna, Auction Theory, Academic Press, San Diego, USA, 2002.

21.

[21]

Maurer, Unifying zero-knowledge proofs of knowledge, in: Progress in Cryptology – AFRICACRYPT 2009,

Preneel, ed., LNCS, Vol. 5580, Springer, Berlin, Heidelberg, 2009, pp. 272–286.

22.

[22]

Naor,

Pinkas and

Sumner, Privacy preserving auctions and mechanism design, in: ACM Conference on Electronic Commerce, 1999, pp. 129–139.

23.

[23]

Omote and

Miyaji, A practical English auction with one-time registration, in: ACISP,

Varadharajan and

Mu, eds, LNCS, Vol. 2119, 2001, pp. 221–234.

24.

[24]

Peng,

Boyd,

Dawson and

Viswanathan, Robust, privacy protecting and publicly verifiable sealed-bid auction, in: ICICS,

R.H.

Deng,

Qing,

Bao and

Zhou, eds, LNCS, Vol. 2513, Springer, 2002, pp. 147–159.

25.

[25]

A.-R.

Sadeghi,

Schunter and

Steinbrecher, Private auctions with multiple rounds and multiple items, in: DEXA Workshops, IEEE, 2002, pp. 423–427.

26.

[26]

Sako, An auction protocol which hides bids of losers, in: Public Key Cryptography,

Imai and

Zheng, eds, LNCS, Vol. 1751, Springer, 2000, pp. 422–432.

27.

[27]

C.P.

Schnorr, Efficient signature generation by smart cards, Journal of Cryptology4 (1991), 161–174.