Collusion-Free Protocols in the Mediated Model

Joël Alwen, Jonathan I. Katz, Yehuda Lindell +3 more

Jonathan I. Katz, Yehuda Lindell

Amjed Shareef, Akshay Agrawal, Chandrasekharan Pandu Rangan

Abstract. A common problem in many markets is that competing firms cannot plan joint business strategies which are socially beneficial, as each firm has its own preferable business strategy which would yield higher profits for it and lower profits for the others. The solution to this problem becomes complex because each firm need not stick to its commitment to follow the pre-designated strategy. Game theory suggests to us a way to enforce this commitment, as when every player chooses his actions according to his observation of the value of a common public signal and, assuming that the others do not deviate, no player is willing to deviate from his recommended strategy. The players do not deviate from their recommended strategy as playing them would yield them a much higher expected pay-off than playing individually. The common public channel can be a trusted external mediator which may send each player his recommended strategy. This mediator can be simulated by a cryptographic protocol, which all the players agree to implement. This problem of suggesting the protocol is known as the Correlated Element Selection Problem. The first two-player protocol was proposed by Dodis et. al[1] in Crypto 2000. The extension of the two-player protocol to an n-player protocol is highly prone to collusions, as two firms can collude and cheat the rest of the firms. The main contribution of the paper is the first n-player collusion free protocol for the correlated element selection problem that does not use hardware primitives. We assume that players are honest but curious. 1

Joël Alwen, Jonathan I. Katz, Ueli M. Maurer +1 more

Andrew William Roscoe, Lei Wang

Silvio M. Micali, Matthew Lepinski

Steganography, the hiding of covert messages inside innocuous communication, is an active area of cryptographic research. Recent research has shown that provably undetectable steganography is possible in a wide variety of settings. We believe that the existence of such undetectable steganography will have far reaching implications. In this thesis, we investigate the impact of steganography on the design of cryptographic protocols. In particular, we show that all existing cryptographic protocols allow malicious players to collude and coordinate their actions by steganographicly hiding covert messages inside legitimate protocol traffic. Such collusion is devastating in many settings, and thus we argue that its elimination is an important direction for cryptographic research. Defeating such steganographic collusion requires not only new cryptographic protocols, but also a new notion of protocol security. Traditional notions of protocol security attempt to minimize the injuries to privacy and correctness inflicted by malicious participants who collude during run-tune. They do not, however, prevent malicious parties from colluding and coordinating their actions in the first place! We therefore put forward the notion of a collusion-free protocol which guarantees that no set of players can use the protocol to maliciously coordinate their actions. As should be expected, such a strong notion of security is very difficult to achieve. We show that achieving collusion-free security is impossible in a model with only broadcast communication and that even with physically private communication (e.g. physical envelopes) there are still many ideal functionalities that have no collusion-free protocols. Fortunately, under natural assumptions collusion-free protocols exist for an interesting class of ideal functionalities. Assuming the existence of trapdoor permutations, we construct collusion-free protocols, in a model with both broadcast messages and physical envelopes, for every finite ideal functionality in which all actions are public.