Collusion-free protocols

Consider the clever cheating that occurred during an FCC spectrum auction in 1995 (see Cramton and J. Schwartz '02 for a history). Auction rules forbade companies from openly colluding to divide the spectrum cheaply; nonetheless, the major players circumvented the rules by using the least significant digits of their public messages to coordinate their overall bidding strategies. In other words, these parties used the auction protocol itself to cheat.

Standard notions of security for cryptographic protocols do not prevent this type of cheating. In this talk, we propose the idea of collusion-free protocols. Such protocols do not create any new opportunities---such as using the protocol messages and headers themselves---for malicious participants to coordinate their cheating during the execution of the protocol. We discuss both positive and negative results regarding this notion by showing that it is possible to construct such protocols but special communication assumptions are provably necessary. The conceptual barrier to achieving this novel security property is captured in the following paradox: it is widely acknowledged that players must use randomness to pick their messages in any secure protocol, but the presence of randomized messages also enables perfect steganography and thus perfect collusion.

We give an overview of two conceptually different approaches to overcome this paradox. The first method is based on the concept of verifiable determinism. This is a way to organize communication so that a player's next message is unpredictable, but once the message has been sent, everyone can verify that it was the one-and-only such message that an honest player could have sent. As a result, steganography becomes impossible. The second method takes an opposite approach: players generate arbitrary messages but send them to each other via a mediator who "re-randomizes"' the messages to eliminate steganographic channels. The goal is to design protocols where collusion-freeness is guaranteed as long as the mediator is honest, while standard security guarantees hold if the mediator is dishonest. This new approach enables us to use a less exotic communication channel to construct protocols that achieve a strong collusion-free property.

This talk is based on 4 papers with the following set of coauthors: Matt Lepinski and Silvio Micali, Joel Alwen and Ivan Visconti, and Alwen, Jonathan Katz, Yehuda Lindell, Giuseppe Persiano, and Visconti.