Sign In

Communications of the ACM

Contributed articles

Cryptography Miracles, Secure Auctions, Matching Problem Verification


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
auction mallet

Credit: iStockPhoto.com

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.

Back to Top

Key Insights

ins01.gif

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 B1, ..., Bn submit sealed bids b1, ..., bn for a single item IT to a seller/auctioneer AU. At an announced end of bidding time T1, the AU opens the bids and determines that, say, bw was the highest bid value and bs was the second highest bid. Bidder Bw will get the item IT and pay to AU the second-highest bid value bs.

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 B1's true value b1 (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, B1 will bid b1 and each of the other bidders B2, ..., Bn will bid r. They also agree that if B1 gets the IT, then he will make certain side payments to Cartel members B2, ..., Bn. 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 B1 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.

  1. Bidders submit sealed bids b1, ..., bn 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.
  2. The AU assigns to every bidder Bi a secret identifier idi. Identifiers are known to AU but NOT known to bidders.
  3. After the closing time of the auction, the AU determines that bidder Bw is the highest/winning bidder and that Bs is the second highest bidder with bid value bs.
  4. AU proves to the bidders, referring only to identifiers, that the bid by the bidder with identifier value idw (say identifier value 10325) is the highest bid. Also that the bid by the bidder with identifier value ids (say identifier value 21131) is the second highest bid.
  5. 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.
  6. The AU proves to Bw that his identifier is the above-mentioned idw, that is, that he is the winner of the IT. AU proves to Bw that the bid value associated with the above-mentioned identifier ids is bs. AU collects from the winner Bw the price bs. That is, the winner gets IT and pays to the AU the second highest bid value bs (Vickrey). These proofs to Bw are again secrecy preserving with respect to the actual identity of Bs and any other bid value except bs.
  7. The AU proves to Bs that his identifier is ids. The AU proves to every bidder Bj, j s, that his identifier is different from ids.
  8. The proofs of 67 are again secrecy preserving and deniable by the bidders involved.
  9. Every bidder Bi, 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.

Back to Top

Sealed Bid Auctions Implementation by Encryption and Secure Bulletin Board

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.

Back to Top

Previous Results and Background

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 encryption7 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 Fp. 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 P1, ..., Pn secretly submit to an Evaluator Prover EP input values x1, ..., xn taken from Fp (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 x1, ..., xn Fp with K outputs xL+1, ..., xL+K is a sequence

eq01.gif

where for all m > n there exist i, j < m, L, such that xm = (xi + xj) mod p, or xm = (xi × xj) mod p, or xm = xi, or xm = TruthValue (xi xj).

An example of a GSLC for the output x(2n 1) = x1 + ··· + Xn is

eq02.gif

Random vector representations of values x Fp. We now come to the main construct for enabling Secrecy Preserving Proofs for the correctness of the results xL+1, ..., xL+K of the GSLC(1).

DEFINITION 2. Let x Fp be a value. A random vector representation RR(x) of x is a vector X = (u, v) where u, v Fp; u was chosen randomly (notation u Fp) 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 Fp 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 function9 for values u Fp. 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 logg(h) = e (i.e., ge = h) is not known and by the intractability assumption not computable in, say, a thousand years.

DEFINITION 3. Let u Fp, the commitment COM(u, r) to u, using the help value r [0, q 1], is COM(u, r) = gu × hr.

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 logg (h) = e is efficiently computable from the equation gu × hr = gv × hs. 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) = gu × hr. Another bidder who sees the posted C will post D = C × g × hs. 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 (gi, hi), 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 x + y = z. The EP prepares random representations X = (u1, v1), Y = (u2, v2), and Z = (u3, v3), of the values x, y, and z. Note that

eq03.gif

if and only if there exists a w Fp such that X + Y = Z + (w, w).

The EP prepares commitments

eq04.gif

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 uj, rj, j = 1, 2, 3. The Verifier checks the commitments, that is, computes COM(uj, rj), j = 1, 2, 3, and compares to the posted first coordinates of COM(X), COM(Y), COM(Z).

The Verifier next checks that u1 + u2 = u3 + w. If c = 2 was chosen, then the Verifier asks for the second coordinates of X, Y, Z, and checks that u1 + u2 = u3 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 uj, vj, j = 1, 2, 3, in only one way. Now, if (3) does not hold, then at least one of the equations u1 + u2 = u3 + w, or v1 + v2 = v3 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 u1, u2, u3, w which satisfy u1 + u2 = u3 + 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 v1,1, v2,2, v3,3, satisfying v1,1 + v2,2 = v3,3 w. Thus, the interactive proof is consistent with any three vectors X1, Y1, Z1 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 x1, ..., xn, and has as output their sum x1 + ··· + xn. The EP will present to Verifier 2n 1 commitments COM(Xj), 1 j 2n 1, for random representation for the values xj, 1 j 2n 1. The interactive proofs for correctness of all n 1 claimed equalities val(Xn+1) = val(X1) + val(X2), val(Xn+2) = val(Xn+1) + val(X3), etc., will be done simultaneously for all equations. The EP will present to Verifier n 1 values w1, ..., wn1. 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 xm = xi × xj in the SLC (1), the EP will have posted on the SBB for the Verifier commitments COM(Xm), COM(Xi), COM(Xj) for random representations of the values xm, xi, xj. The EP has to prove to Verifier that

eq05.gif

Let Xi = (u1, v1), Xj = (u2, v2), and Xm = (u3, v3). The EP prepares auxiliary vectors Z0 = (u1u2, v1v2), Z1 = (u1v2 + w1, p w1), Z2 = (u2v1 + w2, p w2), where w1, w2 are randomly chosen values. The EP augments the commitments presented to Verifier into:

eq06.gif

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

ueq01.gif

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 Xm, Xi, Xj and Z0. 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 u1 of Xi and the second coordinate v2 of Xj and both coordinates of Z1 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 xi can appear in the GSLC (1) as left factor and as right factor. One example arises if the GSLC has an operation xm = xi × xi. In this case, verifying Aspect 1 will reveal both coordinates of Xi and hence reveal the value xi = val(Xi). When preparing a proof of correctness of the GSLC (1), the EP creates for every xi involved in multiplications two random vector representations cacm5702_a.gif and cacm5702_b.gif.

The proof of correctness of the multiplication xm = xi × xj will be:

ueq02.gif

where now cacm5702_a.gif= (u1, v1), cacm5702_b.gif= (u2, v2). It is clear that even if i = j, and Aspect 1 is checked, u1 and v2 are independent random values from Fp. Similarly if SLC contains another multiplication xk = xs × xi, it, as well as xm = xi × xj, is verified with respect to Aspect 1. For the first multiplication, cacm5702_b.gif will be employed, and for the second multiplication, cacm5702_a.gif will be used. Thus again independent random first coordinate of cacm5702_b.gif and second coordinate of cacm5702_a.gif are revealed.

Proving claimed inequalities xm = TruthValue(xi xj). Such inequalities x y are proved for cases x, y < p/2. It is clear that for such x, y, we have x y iff y x < p/2. Example: Let p = 17, x = 7, y = 5. Then x y is false and y x = 15 > 17/2.

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: cacm5702_c.gif 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(X1), ..., COM(Xn) to input values x1, ..., xn 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.

Back to Top

Amplification of Verifier's Confidence

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 y1, ..., ym. Some of these inputs were supplied by players P1, ..., Pn (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 3k rows:

eq07.gif

Each of these 3k rows consists of m commitments to vector representations of the m values val(cacm5702_d.gif) = yi, 1 i m. For some column indices i, the 3k commitments COM(cacm5702_d.gif), 1 j 3k, to vector representations of the value yi were provided by one of the players P1, ..., Pn. For the other column indices i, the 3k 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(cacm5702_d.gif), 1 j 3k, 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

eq08.gif

are called value consistent if val(Xi) = val(Yi), 1 i m.

Assume that the EP wants to prove for two posted commitments COM(X) and COM(Y), where X = (u1, v1) and Y = (u2, v2), 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 u1 and u2. The VER checks that u1 = u2 + 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 (wi, wi), 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 3k 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):

eq09.gif

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

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

  1. Among the initially posted 3k rows (7) at least a majority of 2k rows are pairwise value consistent. By definition, the m values y1, ..., ym of the vectors committed to in that 2k majority are the input values to the process.
  2. In the additional M rows (9) posted by EP, at least (1 1/L)M rows are pairwise value consistent with at least 2k pairwise value consistent rows of (7).
  3. The probability that the Verifier will accept claims 12 when not both are true is at most (1/2 + 1/e2)k + (1/2 + 1/e2)3k < 2(1/2 + 1/e2)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 = 4L = 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.

Back to Top

Deniable Revelation of a Value

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:

eq10.gif

where P is a name of a player, to random representations of a value x, that is, val(X(j)) = x, 1 j 20k. 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 2k of the above 20k commitments are not to vector representations of x, then the probability that P will accept the false claim is at most dk; (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 10k commitments out of the 20k commitments (P, COM(X (i))).

For each of the 10k 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 10k selected COM(X(i)), independently a random challenge ci {1, 2} and presents ci to EP. If ci = 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 ci = 2. Player P accepts that (10) are 20k commitments to representations of the value x only if all the above 10k checks are true.

The opening of the commitment to the coordinate ci 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 10k 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 dk on the probability of P being cheated is close to cacm5702_f.gif, e being the natural log base 2.71. ... Namely, if more than 2k of the 20k 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 10k choices, the probability of accepting is smaller than (11/20)10k. But (11/20)10 approximates cacm5702_f.gif.

Back to Top

Uncontrollable, Deniable Bidding

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 T1 > T for completion of submission of bids.

Step 6.2 Assume that bidders B1, ..., Bn have decided to participate in the auction. As each bidder Bi declares to AU prior to time T his intention to participate in the auction, the AU assigns to Bi a randomly chosen identification number idi Fp and a randomly chosen value xi Fp. The value xi will be subsequently used to enable Bi to submit his bid in an uncontrollable, deniable way.

The EP posts for every Bi 20k pairs (Bi, COM(Xi(j))), 1 j 20k, to random vector representations of the value xi, that is, val(Xi(j)) = xi, 1 j 20k.

In a private meeting, EP reveals to Bi the value xi in a deniable way as discussed earlier.

Step 6.3 To bid the value bi, bidder Bi computes, while still privately meeting with EP, the zi Fp such that xi + zi = bi mod p.

Bidder Bi prepares 3k commitments COM(cacm5702_g.gif), 1 j 3k, to random vector representations of the value zi, that is, val(cacm5702_g.gif) = zi, 1 j 3k. He digitally signs these commitments and hands them over to EP who posts them on the SBB.

Now Bi erases from his device the values xi and bi but retains the value zi and the data required for opening/decommitting COM(cacm5702_g.gif), 1 j 3k.

Note that at this point in time, before the closing of the auction, Bi has made his chosen bid bi, but the EP does not know what that bid value is because he does not know the value zi.

THEOREM 7. The above process implements a sealed-bid uncontrollable and deniable submission of a bid by bidder Bi.

PROOF. The bid value bi equals the sum xi + zi. While EP knows the value xi, he will know the value zi only after bidder Bi will reveal it to the EP at the closing of the auction at time T1. Thus we have a sealed-bid auction.

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

Back to Top

Conducting the Second Price Auction

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 Bi a random identifier idi. 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:

eq11.gif

where ID1(j) is the jth random vector representation of the identifier id1; COM(Y1(j)) is the jth random vector representation of the value x1 chosen as explained at the end of of the section "Deniable Revelation of a Value"; and cacm5702_g.gif is the jth random vector representation of the value z1. 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 3k rows (11), every bidder Bi opens his 3k commitments COM(cacm5702_g.gif), 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 Bi M commitments COM(VBi) to random vector representations VBi of the value Bi (the names of the bidders are ASCII code words reduced to numbers).

The EP now creates and posts M new rows R3k+h, 1 h M each row R3k+h, a random permutation h of the n quadruples:

eq12.gif

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

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

The only new point in this interactive proof is that whenever a row R3k+h is chosen by the Verifier, the EP/Prover opens all the n commitments COM(VBi(3k+h)) revealing the names B1, ..., Bn and ordering the quadruples according to the names.

As mentioned, 4 kL of the rows R3k+h remain untouched at the end of this Step 7.3.

Step 7.4 Now the EP proves which identifier number idw had highest bid and which identifier number ids 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 B1, ..., Bn randomly choose k rows R3k+h out of the 4 kL remaining untouched rows in Step 7.3. Slightly abusing notations, call these rows R1, ..., Rk.

The EP orders the identifier numbers id1, ..., idn he has assigned to the bidders B1, ..., Bn according to size. This induces a permutation on the indices {1, ..., n} so that

eq13.gif

The EP opens in each of the rows R1, ..., Rk the n commitments COM(ID). Thus the rearranged row Rj will look to the Verifiers as:

eq14.gif

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 idw and ids the bid value represented in the quadruple containing idw is the highest and the bid value represented in the quadruple containing ids 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 idw 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 ids is bs 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 ids.

The EP also privately proves to every other bidder that his identifier number is neither ids nor idw. 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.

Back to Top

Countering Collusion

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, B1, ..., B7, out of the n bidders get together before the closing of the auction and, following a discussion, agree that:

  1. Bidder Bi will bid according to strategy si, 1 i 7.
  2. If a cartel bidder Bi is the winner, he will make side payments cacm5702_h.gif to each player Bj, j i, in the cartel.

REMARK. Clauses (a)(b) enable, for example, an agreement that B1 will be the highest bidder among B1, ..., B7, and that if he wins he will make promised side payments to B2, ..., B7. On the other hand, if one of B2, ..., B7 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 B1, ..., B7 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 Bj among all bidders B1, ..., Bn, whoever he will turn out to be, will get a kick back payment of (bj r)/k, where bj is his bid and r is the announced reserve price. Say k = 10.

Now, every cartel member Bi 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 Bi). 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 bi = 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 (bi r)/k, where bi = 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 Bw has to pay the AU the second highest bid value bs. But the identity of the second highest bidder Bs is secret from everyone except for the AU and Bs himself. The bidder Bs is informed that he is the second highest in a deniable way. The winner Bw learns from the AU in a deniable way of the payment bs 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 Bi planning to deviate from the cartel agreement may have is that if another cartel member was designated as winner and that if he (Bi) bids his true value, he may turn out to be the winner and be subject to a fine payment. If Bi, 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.

Back to Top

Verification of Stable Matching Solutions

In 1962, Gale and Shapley2 formulated the stable matching problem and provided an efficient algorithm for its solution. A number of players H1, ..., Hm are looking at a pool of candidates G1, ..., Gk.

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 Hi the spouse G(i). The matching is stable if there is no pair of indexes i, j such that Hi prefers G(j) to G(i) and G(j) prefers Hi to Hj. If the latter happens, then Hi can drop G(i) and G(j) will move to Hi.

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 Gi assigned to hospital department Hj 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 Gi. Upon demand, Gi can get a proof that that is not the case. The proof of correctness does not reveal any preferences, only that Gi was not cheated. Similarly a department can obtain a secrecy preserving proof that no more desirable candidate is willing to move over to it.

Back to Top

Acknowledgments

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.

Back to Top

References

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 8th 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.

Back to Top

Authors

Silvio Micali (silvio@csail.mit.edu) is the Ford Professor of Engineering in the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, Cambridge, MA. He is co-recipient of the 2012 ACM A.M. Turing Award.

Michael O. Rabin (morabin@gmail.com) is The Thomas J. Watson Professor of Computer Science at Harvard University, Cambridge, MA, and professor of computer science at Columbia University, New York, NY. He is co-recipient of the 1976 ACM A.M. Turing Award.


Copyright held by Owner(s)/Author(s). Publication rights licensed to ACM.

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


 

No entries found