Home/Magazine Archive/February 2014 (Vol. 57, No. 2)/Cryptography Miracles, Secure Auctions, Matching Problem.../Full Text

Contributed articles
# Cryptography Miracles, Secure Auctions, Matching Problem Verification

In this article, we extend the methods of Rabin et al.^{10,11} in a major way and provide a solution to the long-standing important problem of preventing collusion in second-price (Vickrey) auctions. The new tools presented are deniable revelation of a secret value and uncontrollable deniable bidding. In Rabin et al.,^{10,11} new highly efficient methods for proving correctness of announced results of computations were introduced. These proofs completely conceal input values and intermediate results of the computation. One application was to enable an Auctioneer to announce outcome of a sealed bid auction and provide verification of correctness of the outcome, while keeping bid values information-theoretically secret. We quickly survey these methods for completeness of the discussion and because of their wide applicability. Another example of an application is to prove to participants of a stable matching process such as the assignment residents to hospitals, of the correctness of the announced assignment without revealing any preferences of residents with respect to hospitals and vice-versa.

By way of motivation, let us outline the main application given in this article for the extended method for secrecy preserving proofs of correctness. We consider Vickrey auctions where bidders *B*_{1}, ..., *B*_{n} submit sealed bids *b*_{1}, ..., *b*_{n} for a single item IT to a seller/auctioneer AU. At an announced end of bidding time *T*_{1}, the AU opens the bids and determines that, say, *b*_{w} was the highest bid value and *b*_{s} was the second highest bid. Bidder *B*_{w} will get the item IT and pay to AU the second-highest bid value *b*_{s}.

This bidding mechanism, absent collusion, makes it worth while for every bidder to bid his true value for the item IT. It thus assures the AU a return of the second highest private true value for the IT.^{14}

When setting up the auction, AU specifies a reserve price *r*. If none of the bids is *r*, then the IT is not sold. If the second price is smaller than *r*, then the winner (if there is one) pays *r* for the IT.

The possibility of collusion completely subverts the above advantage to the AU from the second price auction. Assume that all bidders form a Cartel to collude against AU. They determine ahead of closing time *T* that *B*_{1}'s true value *b*_{1} (as claimed by him) for the item IT is the largest among all true values as claimed by bidders. They agree that in the actual auction, *B*_{1} will bid *b*_{1} and each of the other bidders *B*_{2}, ..., *B*_{n} will bid *r*. They also agree that if *B*_{1} gets the IT, then he will make certain side payments to Cartel members *B*_{2}, ..., *B*_{n}. They also specify fines to be paid by cartel members who deviate from the agreement. Now, if all Cartel members keep to their agreement, then *B*_{1} will get the IT and pay *r* to the AU. Thus, all of the seller's potential gain from conducting the auction is wiped out. Because of possibility of collusion, second-price auctions are rarely used despite their theoretical advantage.^{5,6,12,13}

We shall show how the use of cryptography enables prevention of collusion in *one-time* second-price auctions by making cartel agreements unenforceable and making it worthwhile for colluders to break those agreements. In repeated auctions involving the same bidders, the participants have an incentive to voluntarily keep collusion agreements so as to gain in the long run. The extent to which our methods can be applied to these cases and to other auctions is under study.

Using the methods of Rabin et al.^{10,11} and the new tools of *deniable revelation of a secret value and uncontrollable deniable bidding*, we design an auction mechanism with the following properties.

- Bidders submit sealed bids
*b*_{1}, ...,*b*_{n}to AU in an uncontrollable and deniable manner. This means that a bidder cannot be compelled by anybody to submit a specified bid value. Also, he cannot be compelled to reveal any information about his submitted bid. - The AU assigns to every bidder
*B*_{i}a secret identifier*id*_{i}. Identifiers are known to AU but NOT known to bidders. - After the closing time of the auction, the AU determines that bidder
*B*_{w}is the highest/winning bidder and that*B*_{s}is the second highest bidder with bid value*b*_{s}. - AU proves to the bidders, referring only to identifiers, that the bid by the bidder with identifier value
*id*_{w}(say identifier value 10325) is the highest bid. Also that the bid by the bidder with identifier value*id*_{s}(say identifier value 21131) is the second highest bid. - The proof in 4 is information-theoretic hiding with respect to all bid values and with respect to the correlation between identifiers and bidders. Thus at this stage, bidders know nothing about who bid what and even the winner and second highest bidder do not know about their status as such.
- The AU proves to
*B*_{w}that his identifier is the above-mentioned*id*_{w}, that is, that he is the winner of the IT. AU proves to*B*_{w}that the bid value associated with the above-mentioned identifier*id*_{s}is*b*_{s}. AU collects from the winner*B*_{w}the price*b*_{s}. That is, the winner gets IT and pays to the AU the second highest bid value*b*_{s}(Vickrey). These proofs to*B*_{w}are again secrecy preserving with respect to the actual identity of*B*_{s}and any other bid value except*b*_{s}. - The AU proves to
*B*_{s}that his identifier is*id*_{s}. The AU proves to every bidder*B*_{j}*, j**s*, that his identifier is different from*id*_{s}. - The proofs of 67 are again secrecy preserving and deniable by the bidders involved.
- Every bidder
*B*_{i}, if he so desires, can arrange that if he wins the item IT, then the fact he won will remain secret/unknown to the other bidders. This assumption holds, for example, for digital goods but may be difficult to implement for some physical goods such as radio spectrum. This issue is fully discussed later.

We shall prove that these properties 19 enable the Auctioneer to prevent collusion by promising, when announcing the auction, a kickback payment to the second highest bidder, whoever he may turn out to be.

The implementation of properties 18 requires of the Auctioneer proofs of correctness of announced results of computations while keeping input values and intermediate results secret. A new highly efficient tool for doing this was presented in Rabin et al.^{10,11}

A new construct of a deniable proof of value presented in this paper is employed in implementing the properties 1 and 8.

In this article, we assume that the Auctioneer employs an electronic Secure Bulletin Board (SBB) with the following properties. The SBB is controllable by the AU who can post data. Posted data is time stamped and signed by the AU. Data cannot be erased. The SBB is viewable by all participants in the auction and they are assured that they all view the same content. Detailed implementations of a SBB use standard algorithmic tools and are not discussed herein.

Much of the data posted on the SBB will be in "sealed envelopes" created by bidders or by the AU. In Definition 3, we specify the Pedersen Commitment function which will be used in detailed proofs of the secrecy properties of our bidding mechanism. In practice, we implement sealed envelopes and commitments by an encryption function *E*(,), say a 128-bit AES (Advanced Encryption Standard) used in authenticated encryption mode such as GCM.

The method of value-secrecy preserving proofs of correctness in Rabin et al.^{10,11} and in the present work was motivated by the ground-breaking methodology of Zero Knowledge Proofs (ZKP) innovated in Goldreich et al.^{3} and Goldwasser et al.,^{4} and the subject of thousands of subsequent papers. ZKP and other methods of verification of truth of claimed statements are, however, not sufficiently efficient for providing practical solutions for the auction-verification problems treated in Rabin et al.^{10,11} and herein.

By way of example, in Parkes et al.^{8} a method using Paillier homomorphic encryption^{7} was employed for verification of claimed results of an auction while keeping bid values secret. Verification of a hundred-bidder second-price auction required several hundred minutes. By comparison, the new method of Rabin et al.^{10} verifies a hundred-bidder second-price auction in two milliseconds. The use of multi-party computations (see Ben-David et al.^{1}) provides secrecy of bids but no verification of correctness of announced results. It is also by far slower than that of Rabin et al.^{10,11} and that presented in the present work.

We show how the use of cryptography enables prevention of collusion in one-time second-price auctions by making cartel agreements unenforceable and making it worthwhile for colluders to break those agreements.

The main innovation of Rabin et al.^{10,11} is to work directly with the input values to a computation and its intermediate results as numbers rather than going down to the bit level. Furthermore, numbers are randomly represented by two-coordinate vectors.

The papers by Rabin et al.^{10,11} consider a generalized form of straight line computations on elements of a finite field *F*_{p}. For our applications, a 128-bit prime *p* is completely adequate. Thus, the field operations (*x* + *y*) mod *p* and (*x* × *y*) mod *p* are rapidly executable on an ordinary 64-bit processor.

A number of players *P*_{1}, ..., *P*_{n} secretly submit to an *Evaluator Prover* EP input values *x*_{1}, ..., *x*_{n} taken from *F*_{p} (i.e., *x* {0, 1, ..., *p* 1}). The EP performs a computation on these inputs and announces the results of that computation.

DEFINITION 1. *A Generalized Straight Line Computation (GSLC) on inputs x*_{1}, ..., *x*_{n} *F*_{p} *with K outputs x*_{L+1}, ..., *x*_{L+K} *is a sequence*

where for all *m* > *n* there exist *i, j* < *m, L*, such that *x*_{m} = (*x*_{i} + *x*_{j}) mod *p*, or *x*_{m} = (*x*_{i} × *x*_{j}) mod *p*, or *x*_{m} = *x*_{i}, or *x*_{m} = TruthValue (*x*_{i} *x*_{j}).

An example of a GSLC for the output *x*_{(2n 1)} = *x*_{1} + ··· + *X*_{n} is

**Random vector representations of values x**

DEFINITION 2. *Let x* *F*_{p} *be a value. A random vector representation* RR(*x*) *of x is a vector X* = (*u, v) where u, v* *F*_{p}*; u was chosen randomly (notation u F*_{p}*) and x = (u + v)* mod *p. For a vector X = (u, v) we denote* val(*X*) = (*u* + *v*) mod *p*.

The method for creating a RR(*x*) = (*u, v*) of *x* is to randomly choose *u* *F*_{p} and set *v = (x u) mod p*. Note that from *u* (or *v*) by itself, no information about *x* can be deduced.

**Commitment functions**. We shall use the Pedersen commitment function^{9} for values *u* *F*_{p}. Let *G* be a group of prime order *q > p* for which computing the discrete log function is intractable. Let *g, h* in *G* be two generators such that log_{g}(*h*) = *e* (i.e., *g*^{e} *= h*) is not known and by the intractability assumption not computable in, say, a thousand years.

DEFINITION 3. *Let u* *F*_{p}*, the commitment* COM(*u, r) to u, using the help value r* [0, *q* 1], *is* COM(*u, r*) = *g*^{u} × *h*^{r}.

Note that under a random choice of the help value *r*, COM(*u, r*) is a random element of *G*. Consequently, the commitment function COM(*u, r*) is *information-theoretically hiding*. Since computation of log _{g} (*h*) = *e* is intractable, the commitment function is *computationally binding*. The latter means that for no commitment value *C* is it possible to compute two different pairs (*u, r*) (*v, s*) such that *C* = COM(*u, r)* = COM(*v, s*). The reason is that log_{g} (*h*) = *e* is efficiently computable from the equation *g*^{u} × *h*^{r} *= g*^{v} × *h*^{s}. Consequently, a player who has created and posted a commitment COM(*u, r*) can open it only in one way to reveal the original value *u*.

Even the above strong binding property of the Pedersen commitment leaves it exposed to an attack by imitation. Assume that one bidder in an auction has committed to his bid using a value *u* committed to as *C* = COM(*u, r*) = *g*^{u} × *h*^{r}. Another bidder who sees the posted *C* will post *D* = *C* × *g* × *h*^{s}. When the first bidder decommits the value *u* by revealing *u* and *r*, the second bidder will open *D* by revealing *u* + 1 and *r* + *s*, thus decommitting the value *u* + 1 and raising the bid by 1. In the following, such an attack will be enabled if there is collusion between the auctioneer and the second bidder.

To counter exposure to imitation, we assume that an independent agent, such as NIST, has created and signed randomly chosen pairs (*g*_{i}*, h*_{i}), *i* = 0, 1, ..., of generators of the group G. When setting up the auction, the AU and every participant are assigned a different pair of generators from the above list to be used for their commitments.

**Proving claimed correctness of an addition x + y = z**. We can now show how the EP can prove to a Verifier correctness of an equation

if and only if there exists a *w* *F*_{p} such that *X* + *Y* = *Z* + (*w*, *w*).

The EP prepares commitments

The EP posts the commitments (4) or sends them to the Verifier VER and claims that the hidden vectors *X, Y, Z* satisfy (3).

When challenged by VER to prove this claim, the EP posts or sends to Verifier the above value *w*. The Verifier now presents to EP a randomly chosen challenge *c* {1, 2}.

Assume that *c* = 1. The EP decommits/reveals to Verifier *u*_{j}*, r*_{j}*, j* = 1, 2, 3. The Verifier checks the commitments, that is, computes COM(*u*_{j}*, r*_{j}), *j* = 1, 2, 3, and compares to the posted first coordinates of COM(*X*), COM(*Y*), COM(*Z*).

The Verifier next checks that *u*_{1} + *u*_{2} = *u*_{3} + *w*. If *c* = 2 was chosen, then the Verifier asks for the second coordinates of *X, Y, Z*, and checks that *u*_{1} + *u*_{2} = *u*_{3} *w*. The following two theorems are immediately obvious.

THEOREM 1. *If (3) is not true for the vectors committed in* COM(*X*), COM(*Y*), COM(*Z), then Verifier will accept with probability at most 1/2 the claim that (3) holds*.

PROOF. Under our assumption about the COM function being computationally binding, the EP can open the commitments for *u*_{j}*, v*_{j}*, j* = 1, 2, 3, in only one way. Now, if (3) does not hold, then at least one of the equations *u*_{1} + *u*_{2} = *u*_{3} + *w*, or *v*_{1} + *v*_{2} = *v*_{3} *w* is not true. So the probability that a random challenge *c* {1, 2} will not uncover the falsity of the claim (3) is less than 1/2.

THEOREM 2. *The above interactive proof between EP and Verifier reveals nothing about the values val(X), val(Y), val(Z) beyond, if successful, that the claim that (3) is true (subject to probability at most 1/2 of Verifier accepting a false claim*).

PROOF. We note that the interactive proof involves only the revelation of either all the first coordinates or all the second coordinates of *X, Y, Z*. Assume that Verifier's challenge was *c* = 1. The only revealed values were random *u*_{1}, *u*_{2}, *u*_{3}, *w* which satisfy *u*_{1} + *u*_{2} = *u*_{3} + *w*. Because the commitment function *C*(,) is information-theoretically hiding, the un opened second coordinates in the commitments (3) of COM(*X*), COM(*Y*), COM(*Z*) are consistent with any three values *v*_{1,1}, *v*_{2,2}, *v*_{3,3}, satisfying *v*_{1,1} + *v*_{2,2} = *v*_{3,3} *w*. Thus, the interactive proof is consistent with any three vectors *X*_{1}, *Y*_{1}, *Z*_{1} satisfying the sum equality (3).

A probability of 1/2 of the Verifier being cheated is of course not acceptable. The probability of being cheated is exponentially reduced by simultaneously employing *k* repetitions of the process.

**Simultaneous verification of several additions**. Consider the GSLC (2) which involves *n* inputs *x*_{1}, ..., *x*_{n}, and has as output their sum *x*_{1} + ··· + *x*_{n}. The EP will present to Verifier 2*n* 1 commitments COM(*X*_{j}), 1 *j* 2*n* 1, for random representation for the values *x*_{j}, 1 *j* 2*n* 1. The interactive proofs for correctness of all *n* 1 claimed equalities val(*X*_{n+1}) = val(*X*_{1}) + val(*X*_{2}), val(*X*_{n+2}) = val(*X*_{n+1}) + val(*X*_{3}), etc., will be done simultaneously for all equations. The EP will present to Verifier *n* 1 values *w*_{1}, ..., *w*_{n1}. The Verifier will then randomly choose a challenge *c* {1, 2}. The same challenge *c* will be used by EP and Verifier to check all the *n* 1 equalities. It is clear that if not all *n* 1 claimed equations are true, then the probability that Verifier will accept is at most 1/2. Also, the argument of Theorem 2 that the interactive proof is information-theoretic value-hiding holds without change.

**Proving claimed correctness of multiplications**. For proving correctness of the operations of multiplication *x*_{m} = *x*_{i} × *x*_{j} in the SLC (1), the EP will have posted on the SBB for the Verifier commitments COM(*X*_{m}), COM(*X*_{i}), COM(*X*_{j}) for random representations of the values *x*_{m}*, x*_{i}*, x*_{j}. The EP has to prove to Verifier that

Let *X*_{i} = (*u*_{1}, *v*_{1}), *X*_{j} = (*u*_{2}, *v*_{2}), and *X*_{m} = (*u*_{3}, *v*_{3}). The EP prepares auxiliary vectors *Z*_{0} = (*u*_{1}*u*_{2}, *v*_{1}*v*_{2}), *Z*_{1} = (*u*_{1}*v*_{2} + *w*_{1}, *p w*_{1}), *Z*_{2} = (*u*_{2}*v*_{1} + *w*_{2}, *p w*_{2}), where *w*_{1}, *w*_{2} are randomly chosen values. The EP augments the commitments presented to Verifier into:

Clearly (5) holds if the following Aspects 04 hold true for the vectors committed in (6):

In the interactive proof/verification, either Aspects 0 and 4 are checked together, or Aspect 1 or Aspect 2 is separately checked. The Veifier randomly chooses with probability 1/2 to verify Aspect 0 and the addition in Aspect 4. He randomly chooses *c* {1, 2}. Say *c* = 1. The EP reveals the first coordinates of *X*_{m}*, X*_{i}*, X*_{j} and *Z*_{0}. Aspect 0 is verified. Aspect 4 is verified in the manner of verification of additions. If the EP's claim is false with respect to Aspect 0 or Aspect 4, then the probability of Verifier accepting is at most 3/4 = 1 (1/2) × (1/2).

The Verifier chooses to check either Aspect 1 or Aspect 2, each with probability 1/4. Say Aspect 1 was chosen by Verifier. The EP reveals the first coordinate *u*_{1} of *X*_{i} and the second coordinate *v*_{2} *of X*_{j} and both coordinates of *Z*_{1} and checks the equality of Aspect 1. Note that if Aspect 1 is false and is chosen for verification, then Verifier will never accept. Similarly for Aspect 2. Consequently, if (5) is false and the proof of correctness (6) presented by EP to Verifier is false in Aspect 1, or Aspect 2, then the probability that Verifier will accept is at most 3/4. Altogether we have:

THEOREM 3. *If the product claim (5) is false then the probability that the Verifier will accept EP's proof of correctness is at most 3/4*.

REMARK. To achieve the information-theoretic value hiding property of the above interactive proof of correctness, we require an additional step in EP's construction of the posted proof (6). We note that the same *x*_{i} can appear in the GSLC (1) as left factor and as right factor. One example arises if the GSLC has an operation *x*_{m} *= x*_{i} × *x*_{i}. In this case, verifying Aspect 1 will reveal both coordinates of *X*_{i} and hence reveal the value *x*_{i} = val(*X*_{i}). When preparing a proof of correctness of the GSLC (1), the EP creates for every *x*_{i} involved in multiplications two random vector representations and .

The proof of correctness of the multiplication *x*_{m} *= x*_{i} × *x*_{j} will be:

where now = (*u*_{1}, *v*_{1}), = (*u*_{2}, *v*_{2}). It is clear that even if *i = j*, and Aspect 1 is checked, *u*_{1} and *v*_{2} are independent random values from *F*_{p}. Similarly if SLC contains another multiplication *x*_{k} *= x*_{s} × *x*_{i}, it, as well as *x*_{m} *= x*_{i} × *x*_{j}, is verified with respect to Aspect 1. For the first multiplication, will be employed, and for the second multiplication, will be used. Thus again independent random first coordinate of and second coordinate of *are* revealed.

**Proving claimed inequalities x _{m} = TruthValue(x_{i} x_{j})**. Such inequalities

So the EP can prove correctness of inequalities if he can, when true, prove for a commitment COM(*X*) *that* val(*X*) < *p*/2.

In Rabin et al.,^{10, 11} Lagrange's theorem that every integer *x* is the sum of four squares of integers: is employed to enable the EP to create a Value Hiding Proof of the GSLC (1) by use of which he can achieve [Rabin et al.,^{10,11} Theorem 1]:

THEOREM 4. *Let commitments COM*(*X*_{1}), ..., *COM*(*X*_{n}) *to input values x*_{1}, ..., *x*_{n} *be posted and let the EP perform the GSLC (1) and post the K output values x*_{(L+1)}, ..., *x*_{(L+k)}. *The claimed correctness of the output values can be interactively proven by the EP and a Verifier while keeping all inputs and intermediate values information-theoretically secret. If the Prover's claim is true then the Verifier will always accept the claim. If the Prover's claim is false then the probability that Verifier will accept the claim is at most 3/4*.

In the previous section, we saw how the EP has expanded the GSLC (1) into a sequence of commitments to be called a Value Hiding Proof (VHP-GSLC). The *Value Hiding Proof* is employed by EP and VER in an input and intermediate value-hiding interactive proof of correctness of the output values of the GSLC as claimed by the EP. We have shown that the probability of the VER to accept a false claim is at most 3/4. In applications, a 3/4 probability of being cheated is of course unacceptable. The solution is of course duplication of the interactive proof in *k* translations of the GSLC (1). A successful verification of correctness of all *k* translations by VER will assure him that the probability of him having been cheated by the EP is smaller than (3/4)^{k}.

In practice, the EP may be called upon to interactively prove correctness of announced results to different Verifiers upon *K* different occasions. So, what is needed is for the EP to prepare and post *K* × *k* Value Hiding Proofs of the GSLC. Next we give an algorithm for doing that.

**Making multiple copies of a sequence of hidden values**. The reader who is mainly interested in the overall structure of our results may skip the details of this section and just take for granted its conclusion that many copies of posted hidden values can be made and their value consistency can be proved without revelation of actual values.

In the general case, as well as in the application to securing Vickrey auctions, the EP will have a sequence of *m* hidden input values *y*_{1}, ..., *y*_{m}. Some of these inputs were supplied by players *P*_{1}, ..., *P*_{n} (in the case of auctions by bidders) and some of these inputs are created by the EP as part of the GSLC computation and proofs that he will conduct.

To begin with, the AU posts on the Secure Bulletin Board 3*k* rows:

Each of these 3*k* rows consists of *m* commitments to vector representations of the *m* values val() = *y*_{i}, 1 *i* *m*. For some column indices *i*, the 3*k* commitments COM(), 1 *j* 3*k*, to vector representations of the value *y*_{i} were provided by one of the players *P*_{1}, ..., *P*_{n}. For the other column indices *i*, the 3*k* commitments were supplied by the EP. For a proof of correctness of announced output results, the question arises: How can the EP prove to a Verifier that for each column index *i* the posted commitments COM(), 1 *j* 3*k*, all contain vector representations of the same value. That is, how can the EP prove that the rows in (7) are *pairwise value consistent* in the following sense.

DEFINITION 4: *Two rows of commitments*

are called *value consistent* if val(*X*_{i}) = val(*Y*_{i}), 1 *i* *m*.

Assume that the EP wants to prove for two posted commitments COM(*X*) and COM(*Y*), where *X* = (*u*_{1}, *v*_{1}) and *Y* = (*u*_{2}, *v*_{2}), a claim that val(*X*) = val(*Y*). He reveals to VER the pair (*w*, *w*) such that *X* = *Y* + (*w*, *w*). As in the verification of addition, the Verifier now presents to EP a randomly chosen challenge *c* {1, 2}. If *c* = 1, then the EP reveals to VER the first coordinates *u*_{1} and *u*_{2}. The VER checks that *u*_{1} = *u*_{2} + *w*. Similarly if *c* = 2. Clearly, if the EP's claim is false, then the probability that VER will accept the claim is at most 1/2.

The same procedure will apply to proving/verifying a claim that the two rows (8) are value consistent. Here, EP posts *m* vectors (*w*_{i}, *w*_{i}), 1 *i* *m*. The VER uses one random challenge *c* {1, 2} to require from the EP to either reveal/open all first coordinates in all commitments or to reveal/open all second coordinates.

We now come to the procedure whereby the EP proves to a VER the value consistency of the initially posted 3*k* rows of commitments (7) and creates additional *N* rows of commitments to be used in multiple proofs of correctness of announced results of the GSLC.

THEOREM 5. (*Rabin et al*.,^{10,11} *Theorem 8*) *Let the EP choose an L* (*say L = 10*) *and prepare and post M* = 10 × *k* × *L new rows* (*9*):

so that each row of (9) is pairwise value consistent with every one of the 3*k* rows (7). That is, for every input index *i*, val() = *y*_{i}, 1 *j* *M*.

Upon demand, EP can conduct an information-theoretic value-hiding interactive proof convincing a Verifier that:

- Among the initially posted 3
*k*rows (7) at least a majority of 2*k*rows are pairwise value consistent. By definition, the*m*values*y*_{1},*..., y*_{m}of the vectors committed to in that 2*k*majority are the input values to the process. - In the additional
*M*rows (9) posted by EP, at least (1 1/*L*)*M*rows are pairwise value consistent with at least 2*k*pairwise value consistent rows of (7). - The probability that the Verifier will accept claims 12 when not both are true is at most (1/2 + 1/
*e*^{2})^{k}+ (1/2 + 1/*e*^{2})^{3k}< 2(1/2 + 1/*e*^{2})^{k}.

The interactive proof involves EP opening one coordinate in every one of the 3 *km* pairs (7) and opening one coordinate in each commitment in 6 *kL* rows of (9). Thus this interactive proof leaves 4 *kL* untouched rows of (9) with the assurance that at least (1 1/*L*)4 *kl* of these rows are pairwise value consistent with the *m* values initially committed to in (7). The untouched rows can be employed in *N* = 4*L* = 40 proofs of correctness of outputs, where each proof uses *k* rows extended to Value Hiding Proofs. Every such interactive proof employing *k* rows reduces probability of Verifier being cheated to (1/10 + 3/4)^{k}.

In practice, the EP may be called upon to interactively prove correctness of announced results to different Verifiers upon K different occasions.

In the following treatment of Vickrey auctions, we shall assume the availability of any needed number of value-consistent rows of commitments to input values without repeating the details as to how these rows were obtained from the initial input rows.

We want to show that the EP can post commitments COM(*X*) to vector presentations of a value *x* and reveal the value *x* to a player *P* in a manner that *P* can subsequently deny knowledge of the value *x*. Furthermore, even though the commitments are publicly posted on the SBB and viewable by other players, *P* cannot open any of these commitments. Consequently, the value *x* remains information-theoretically hidden from everybody except for the EP and *P*.

Our algorithm requires a step where *P privately* meets with the EP in a manner unobserved by anybody else and that *P* does not carry away from the meeting a record of the value *x*. The question whether this private meeting can be replaced by exchanges of encrypted messages is a topic for further research.

THEOREM 6. *Assume that the EP has posted on the SBB 20k commitments*:

where *P* is a name of a player, to random representations of a value *x*, that is, val(*X*^{(j)}) = *x*, 1 *j* 20*k*. Note that these posted commitments are publicly associated with the player *P*.

The EP reveals the value *x* to *P* and claims to him that the posted commitments (10) are to vector representations of this *x*. The EP can prove to *P* that the commitments are to random representations of the value *x* in a manner that (a) If more than 2*k* of the above 20*k* commitments are *not* to vector representations of *x*, then the probability that *P* will accept the false claim is at most *d*^{k}; (*b*) *P* cannot be compelled to reveal that value *x* to another party or prove to another party that the commitments are to the value *x*.

PROOF. Player *P* meets privately with the EP. The EP claims to *P* that the hidden value is *x*. Player P randomly chooses 10*k* commitments out of the 20*k* commitments (*P*, COM(*X* ^{(i))}).

For each of the 10*k* commitment (*P*, COM(*X* ^{(i)})) chosen by *P*, the EP privately claims to *P* that *X*^{(i)} = (*u*^{(i)}, *v*^{(i)}). Note that this is what EP claims, without opening the commitment COM(*X*^{(i)}).

Player *P* checks that for every claimed value of a vector *X*^{(i)}, (*u*^{(i)} + *v*^{(i)}) *mod p = x*.

Next, *P* chooses, for each of the 10*k* selected COM(*X*^{(i)}), independently a random challenge *c*_{i} {1, 2} and presents *c*_{i} to EP. If *c*_{i} = 1, then EP opens/reveals to *P* the first commitment of the chosen pair COM(*X*^{(i)}). Player *P* checks that for COM(*X*^{(i)}), the revealed coordinate value matches the above value *u*^{(i)} as claimed by EP. Similarly for the case *c*_{i} = 2. Player *P* accepts that (10) are 20*k* commitments to representations of the value *x* only if all the above 10*k* checks are true.

The opening of the commitment to the coordinate *c*_{i} is done by EP on the *SBB* so that the identity of the opened commitment is publicly known.

Why is knowledge of the value *x* deniable by *P*? Player *P* was privately shown both coordinates, *u*^{(i)} and *v*^{(i)}, of 10*k* vectors *X*^{(i)}. Thus he has deniability of what he saw. For each of these vectors, the EP publicly opened just one of the two posted commitments COM(*u*^{(i)}), COM(*v*^{(i)})), where COM(*X*^{(i)})) = (COM(*u*^{(i)}), COM(*v*^{(i)})). Hence, nobody except for the EP can open the other coordinate and the value *x* remains information-theoretically hidden.

We turn to the probability that the player *P* will accept a false claim. For brevity of discussion, we present a heuristic argument that if, say, *k* > 30 then the value *d* in the above bound *d*^{k} on the probability of *P* being cheated is close to , *e* being the natural log base 2.71. ... Namely, if more than 2*k* of the 20*k* vectors *X*^{(i)} have val(*X*^{(i)}) *x*, then the probability for a randomly chosen *X*^{(i)} to lead *P* to find that EP is cheating is >(1/10) × 1/2. Consequently, the probability of accepting EP's claim for a randomly chosen *X*^{(i)} that val(*X*^{(i)}) = *x* is < 11/20. For 10*k* choices, the probability of accepting is smaller than (11/20)^{10k}. But (11/20)^{10} approximates .

We turn to describe the method implementing uncontrollable, deniable bidding by use of deniable revelation of a value. In the following sections, the auctioneer AU will play the role of an evaluator prover EP vis-à-vis the bidders in the auction. The terms AU and EP will be used interchangeably.

**Step 6.1** Assume a one-time single-item Vickrey auction. The auctioneer AU, who will later also act as a prover, announces the auction and a reserve price *r* below which the item will not be sold. AU announces a time *T* for closing of the auction participation phase. AU also announces a time *T*_{1} > *T* for completion of submission of bids.

**Step 6.2** Assume that bidders *B*_{1}, ..., *B*_{n} have decided to participate in the auction. As each bidder *B*_{i} declares to AU prior to time *T* his intention to participate in the auction, the AU assigns to *B*_{i} a randomly chosen identification number *id*_{i} *F*_{p} and a randomly chosen value *x*_{i} *F*_{p}. The value *x*_{i} will be subsequently used to enable *B*_{i} to submit his bid in an uncontrollable, deniable way.

The EP posts for every *B*_{i} 20*k* pairs (*B*_{i}, COM(*X*_{i}^{(j)})), 1 *j* 20*k*, to random vector representations of the value *x*_{i}, that is, val(*X*_{i}^{(j)}) = *x*_{i}, 1 *j* 20*k*.

In a private meeting, EP reveals to *B*_{i} the value *x*_{i} in a deniable way as discussed earlier.

**Step 6.3** To bid the value *b*_{i}, bidder *B*_{i} computes, while still privately meeting with EP, the *z*_{i} *F*_{p} such that *x*_{i} + *z*_{i} = *b*_{i} mod *p*.

Bidder *B*_{i} prepares 3*k* commitments COM(), 1 *j* 3*k*, to random vector representations of the value *z*_{i}, that is, val() = *z*_{i}, 1 *j* 3*k*. He digitally signs these commitments and hands them over to EP who posts them on the SBB.

Now *B*_{i} erases from his device the values *x*_{i} and *b*_{i} but retains the value *z*_{i} and the data required for opening/decommitting COM(), 1 *j* 3*k*.

Note that at this point in time, before the closing of the auction, *B*_{i} has made his chosen bid *b*_{i}, but the EP does not know what that bid value is because he does not know the value *z*_{i}.

THEOREM 7. *The above process implements a sealed-bid uncontrollable and deniable submission of a bid by bidder B*_{i}.

PROOF. The bid value *b*_{i} equals the sum *x*_{i} + *z*_{i}. While EP knows the value *x*_{i}, he will know the value *z*_{i} only after bidder *B*_{i} will reveal it to the EP at the closing of the auction at time *T*_{1}. Thus we have a sealed-bid auction.

Bidder *B*_{i} cannot be compelled to make a specified bid because until his private meeting with the EP he does not know the value *x*_{i}. After he made his bid he can perhaps be made, or volunteer, to reveal the value *z*_{i}. But the value *x*_{i} was revealed to *B*_{i} in a deniable way. As shown earlier and in Theorem 6, *B*_{i} can claim anything about that value but can prove nothing about it. Thus this deniability extends to his bid value *x*_{i} + *z*_{i} = *b*_{i}.

The purpose of the following procedure is to enable the EP to prove to bidders who won and what price the winner should pay by referring only to id numbers assigned by the EP to bidders. The procedure keeps bid values information-theoretically secret as well as the correlation between id numbers and actual bidders.

**Step 7.1** The EP chooses for every bidder *B*_{i} a random identifier *id*_{i}. The identifiers are known only to the EP. At time *T*, the announced end of auction participation phase, the AU will post on the Secure Bulletin Board (SBB) the following data:

where *ID*_{1}^{(j)} is the *j*th random vector representation of the identifier *id*_{1}; COM(*Y*_{1}^{(j)}) is the *j*th random vector representation of the value *x*_{1} chosen as explained at the end of of the section "Deniable Revelation of a Value"; and is the *j*th random vector representation of the value *z*_{1}. Similarly for the other subscripts 2, ..., *n*.

**Step 7.2** After time *T* of closing the submission of sealed-bid auction and posting of the 3*k* rows (11), every bidder *B*_{i} opens his 3*k* commitments COM(), for the EP.

The EP chooses *M* = 10 *kL, L* = 10, and randomly chooses *M* permutations of the indexes {1, ..., *n*}. The EP creates for every bidder *B*_{i} *M* commitments COM(*VB*_{i}) to random vector representations *VB*_{i} of the value *B*_{i} (the names of the bidders are ASCII code words reduced to numbers).

The EP now creates and posts *M new rows R*_{3k+h}, 1 *h* *M* each row *R*_{3k+h}, a random permutation _{h} of the *n* quadruples:

Each of the rows (12) contains *m* = 4*n* commitments and, before being permuted, is pairwise value consistent with each of the rows (11) viewed as a sequence of *m* = 4*n* commitments to vector representations of values.

**Step 7.3** The EP acting as Prover and all bidders *B*_{1}, ..., *B*_{n} jointly acting as Verifier, now conduct the secrecy preserving proof noted earlier confirming that out of the 3*k* rows (11) at least 2*k* are pairwise value consistent and out of the new *M* rows (12) no more than *M/L* are not value consistent with at least 2*k* majority of the rows (11).

The only new point in this interactive proof is that whenever a row *R*_{3k+h} is chosen by the Verifier, the EP/Prover opens all the *n* commitments COM(*VB*_{i}^{(3k+h)}) revealing the names *B*_{1}, ..., *B*_{n} and ordering the quadruples according to the names.

As mentioned, 4 *kL* of the rows *R*_{3k+h} remain untouched at the end of this Step 7.3.

**Step 7.4** Now the EP proves which identifier number *id*_{w} had highest bid and which identifier number *id*_{s} had the second highest bid. Without revealing bid values and without revealing names of the bidders associated with these identifier numbers, this is done as follows:

The Verifiers *B*_{1}, ..., *B*_{n} randomly choose *k* rows *R*_{3k+h} out of the 4 *kL* remaining untouched rows in Step 7.3. Slightly abusing notations, call these rows *R*_{1}, ..., *R*_{k}.

The EP orders the identifier numbers *id*_{1}, ..., *id*_{n} he has assigned to the bidders *B*_{1}, ..., *B*_{n} according to size. This induces a permutation on the indices {1, ..., *n*} so that

The EP opens in each of the rows *R*_{1}, ..., *R*_{k} the *n* commitments COM(ID). Thus the rearranged row *R*_{j} will look to the Verifiers as:

Recall that for every quadruple COM(*V B*), *id*, COM(*Y*), COM(*Z*), the bid value *b* of the bidder *B* to whom the EP secretly attached the identifier number *id* is *b* = val(*Y*) + val(*Z*).

Using the *k* rows (14) as inputs and noting that the pairwise value consistency for these rows has already been established for the Verifiers, the EP can interactively prove to the Verifiers that for identifier numbers *id*_{w} and *id*_{s} the bid value represented in the quadruple containing *id*_{w} is the highest and the bid value represented in the quadruple containing *id*_{s} is the second highest. The interactive proofs are as in Rabin et al.^{10,11} and as detailed in the section discussing previous results.

**Step 7.5** Informing the winner, the second highest bidder and the other bidders. The EP now privately proves to the winning bidder that his associated identifier number is the *id*_{w} of step 7.4, thereby proving to him that he is the Winner. The EP reveals to the winner in a deniable way that the bid value associated with the identifier number *id*_{s} is *b*_{s} and collects that payment from the Winner.

In preparation for the kick back promised by the EP/AU to the second highest bidder, the EP privately and deniably proves to the second highest bidder that his identifier number is *id*_{s}.

The EP also privately proves to every other bidder that his identifier number is neither *id*_{s} nor *id*_{w}. These interactive proofs are conducted without revealing to the bidder in question his identifier number.

In the interest of brevity, we omit the detailed constructions of the above proofs. They follow the patterns and employ the tools developed in Rabin et al.^{10,11} and in previous sections of this article.

The construction of a bidding process having Properties 18 is now complete.

**Formation of the cartel**. By way of example we assume that seven bidders, *B*_{1}, ..., *B*_{7}, out of the *n* bidders get together before the closing of the auction and, following a discussion, agree that:

- Bidder
*B*_{i}will bid according to strategy*s*_{i}, 1*i*7. - If a cartel bidder
*B*_{i}is the winner, he will make side payments to each player*B*_{j}*, j**i*, in the cartel.

REMARK. Clauses (a)(b) enable, for example, an agreement that *B*_{1} will be the highest bidder among *B*_{1}, ..., *B*_{7}, and that if he wins he will make promised side payments to *B*_{2}, ..., *B*_{7}. On the other hand, if one of *B*_{2}, ..., *B*_{7} wins by deviating from the agreement then he will make punitively high side payments to the other cartel members.

THEOREM 8. *If the auction mechanism satisfies conditions 19 then collusion is avoidable*.

PROOF. We assume that the bidders *B*_{1}, ..., *B*_{7} are independent self-interested entities and that the auction for the item IT with reserve price *r* is a one-time event.

When announcing the auction, the AU promises in a binding way that the second price bidder *B*_{j} among all bidders *B*_{1}, ..., *B*_{n}, whoever he will turn out to be, will get a kick back payment of (*b*_{j} *r*)/*k*, where *b*_{j} is his bid and *r* is the announced reserve price. Say *k* = 10.

Now, every cartel member *B*_{i} argues for himself as follows. In the proof of correctness of the auction result, all bid values will remain information-theoretically secret. Each of the cartel members can arrange it so that if he wins, the fact that he won will remain unknown to me (bidder *B*_{i}). Because that winner is self-interested, he will not make the side payment to me without any danger of reprisal. Also if I win, this fact will remain unknown to everyone except to me and to the AU, hence I shall not need to make any side payments. On the other hand, if I bid *b*_{i} = my true private value for IT, then if I win I shall get the IT at the second highest bid value. If I am the second highest bidder, then I shall get a kick back payment of (*b*_{i} *r*)*/k*, where *b*_{i} = my private true value for the IT. The fact that I got the kick back payment will remain secret and be deniable by me.

The above argument can be strengthened to cover certain instances where the identity of the winner does not remain secret. Namely, the winner *B*_{w} has to pay the AU the second highest bid value *b*_{s}. But the identity of the second highest bidder *B*_{s} is secret from everyone except for the AU and *B*_{s} himself. The bidder *B*_{s} is informed that he is the second highest in a deniable way. The winner *B*_{w} learns from the AU in a deniable way of the payment *b*_{s} he has to make. Thus he can claim to other cartel members anything about that payment and consequently cheat them about the level of side payments he has to make.

The only concern that a cartel member *B*_{i} planning to deviate from the cartel agreement may have is that if another cartel member was designated as winner and that if he (*B*_{i}) bids his true value, he may turn out to be the winner and be subject to a fine payment. If *B*_{i}, based on his estimate of bids by other bidders, concludes that this is a likely outcome, then he will deviate only if he knows that his becoming the winner can be concealed. Possible concealment strategies are described following this Theorem.

*Conclusion*. Cartels are useless and the best strategy for every bidder is to bid his private true value.

**Keeping the winner's identity secret**. The possibility of doing so depends on laws governing auctions and on special circumstances of a bidder, auctioneer, and the nature of the item IT up for auction.

For example: If the Auctioneer is a government agency, then there are often transparency requirements with respect to who gets the IT. Similarly, if a bidder is a government agency. The same restrictions may apply to publicly held corporations. In the latter case, the corporation may circumvent restrictions by use of an entity registered in another jurisdiction.

If the IT is a financial instrument, then transfer to the winner may be secretly done and subsequently known only to tax authorities.

Consider an auction of a large plot of land. If a bidder is a developer intending to build on it, then if he wins the fact is not concealable. If the bidder is an investor who intends to later on resell for a profit, then if he wins he can ask the AU to transfer right to sell to a confidentiality protecting trust. That trust will arrange the transfer of title to a subsequent buyer while keeping the winner's identity concealed.

All in all the possibility of keeping the winner's identity concealed depends on a myriad of legal and practical factors governing the auction in question. It gives rise to creative solutions. It is in the interest of the auctioneer and a winning bidder to cooperate in implementing a solution when legal and possible.

In 1962, Gale and Shapley^{2} formulated the stable matching problem and provided an efficient algorithm for its solution. A number of players *H*_{1}, ..., *H*_{m} are looking at a pool of candidates *G*_{1}, ..., *G*_{k}.

In one example, the players are women, the candidates are men, and *m* = *k*. Every woman has her ordering of preference of men as spouses, and similarly for every man. A matching is a permutation : [1, *n*] [1, *n*] assigning to *H*_{i} the spouse *G*_{}(*i*). The matching is *stable* if there is no pair of indexes *i, j* such that *H*_{i} prefers *G*_{}(*j*) to *G*_{}(*i*) and *G*_{}(*j*) prefers *H*_{i} to *H*_{j}. If the latter happens, then *H*_{i} can drop *G*_{}(*i*) and *G*_{}(*j*) will move to *H*_{i}.

In another important example, the players are hospital departments (say surgery departments) and the candidates are graduating medical interns looking to become residents. In this case, *k* > *m* and every department may induct several residents. Again every department has its ordering of preference of candidates and every candidate has his ordering of preference of departments. These orderings are submitted to an agency that computes a stable matching and announces the assignments while keeping the preferences secret.

Assume that a resident *G*_{i} assigned to hospital department *H*_{j} suspects that the agency could have assigned him to another department preferred by him because such a department got assigned a resident less desirable to it than *G*_{i}. Upon demand, *G*_{i} can get a proof that that is not the case. The proof of correctness does not reveal any preferences, only that *G*_{i} was not cheated. Similarly a department can obtain a secrecy preserving proof that no more desirable candidate is willing to move over to it.

Michael O. Rabin thanks Eric Maskin for very useful conversations and comments on the topic of Vickrey auctions, and Hal Varian for suggesting the application to matching problems.

1. Ben-David, A., Nisan, N., Pinkas, B. Fairplaymp a system for secure multi-party computations. In *CCS* (2008), ACM.

2. Gale, D., Shapley, L.S. College admissions and the stability of marriage. *Am. Math. Mon. 69* (1962), 914.

3. Goldreich, O., Micali, S., Wigderson, A. Proofs that yield nothing but their own validity, or all languages in np have zkp systems. *J. ACM 38* (1991), 692729.

4. Goldwasser, S., Micali, S., Racoff, C. The knowledge complexity of interactive proof systems. *SIAM J. Comput. 18* (1989), 186208.

5. Graham, D., Marshall, R. Collusive bidder behavior in single-object second-price and English auctions. *J. Polit. Econ. 95*, 6 (1987).

6. Marshall, R., Marx, L. Bidder collusion. *J. Econ. Theor. 133* (2007), 374402.

7. Paillier, P. Public-key encryptions based on composite residuosity classes. In *Proceedings of EUROCRYPT 99* (1999), 223239.

8. Parkes, D., Rabin, M.O., Shieber, S., Thorpe, C. Practical secrecy-preserving verifiably correct and trust worthy auctions. In *Proceedings of 8*^{th} *International Conference on Electronic Commerce* (*ICEC*) (2006), 7181.

9. Pedersen, T. Non-interactive and information-theoretic secure verifiable secret sharing. In *Proceedings of CRYPTO 91* (1991), Springer Verlag, 129140.

10. Rabin, M., Mansour, Y., Muthukrishnan, S., Yung, M. Strictly black-box zero-knowledge and efficient validation of financial transactions. In *Proceedings of ICALP* (2012), Springer Verlag, 738749.

11. Rabin, M., Servedio, R., Thorpe, C. Practical secrecy-preserving, verifiably correct and trustworthy auctions. In *Proceedings of IEEE Symposium on Logic in Computer Science* (Wroclaw, 2007).

12. Sandhholm, T. Limitations of the Vickrey auction in computational multi-agent systems. Research Paper. Department of Computer Science, Washington University, St. Louis, MO.

13. Ungern-Sternberg, T.V. Cartel stability in sealed bid second price auctions. *J. Ind. Econ. 36* (Mar. 1988), 351358.

14. Vickrey, W. Counterspeculation, auctions, and competitive sealed tenders. *J. Finance 16* (1961), 837.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.

No entries found