MPC Galore: A Large List of MPC Applications

Secure and private auctions is a great example of where MPC shines: It has many participants that have an interest in keeping their personal bids private and the function to compute is fairly simple.

While there are many different types of auctions they all (I guess, I'm not an auction expert) the same basic principles:

1. A set of \(n\) parties who cannot all agree on a trusted third party. (Otherwise we'd just use that to conduct the auction).
2. Each party has a bid \(v_i\).
3. Whoever has the highest bid \(v=\max_i{v_i}\), wins (or more generally, there is some function that takes all bids as input, and outputs the id of the winner, and the price that the winner has to pay).

Secure and private auctions was the first application of MPC to be realized in a practical setting. This of course is the "famous" Danish sugar beet auction (Bogetoft et al. 2009).

Running an auction in MPC works particularly well using a binary protocol, since the bulk of the work involes non-linear computations, typically comparisons. In fact, fairly optimized protocols exist (Kurosawa & Ogata. 2002). Auctions are also one of those applications that make a lot of sense in the "outsourced MPC" setting. If there are 100s of bidders, then a protocol using involving all parties is likely gonna be too slow (not to mention that it would require all bidders to be online at the same time).

Lastly, a secure auction should probably be run with a protocol that guarantees output. At least if an abort would require bidders to re-submit their bid.

Voting is (in most scenarios) a private affair. Indeed, in many countries, privacy of a vote is something guaranteed by law.

A poll, or survey, can in principle be viewed as a type of vote.

• Linear regression