Paper 2010/238

Collusion Free Protocol for Correlated Element Selection Problem

Amjed Shareef, Akshay Agrawal, and C. Pandu Rangan


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 \textit{Correlated Element Selection Problem}. The first two-player protocol was proposed by Dodis et. al\cite{dhr00} 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 \textit{correlated element selection problem} that does not use hardware primitives. We assume that players are honest but curious.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Rational cryptography
Contact author(s)
amjedshareef @ gmail com
2010-04-28: last of 2 revisions
2010-04-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Amjed Shareef and Akshay Agrawal and C.  Pandu Rangan},
      title = {Collusion Free Protocol for Correlated Element Selection Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2010/238},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.