Paper 2011/433

Collusion-Preserving Computation

Joel Alwen, Jonathan Katz, Ueli Maurer, and Vassilis Zikas


In collusion-free protocols, subliminal communication is impossible and parties are thus unable to communicate ``any information beyond what the protocol allows''. Collusion-free protocols are interesting for several reasons, but have specifically attracted attention because they can be used to reduce trust in game-theoretic mechanisms. Collusion-free protocols are impossible to achieve (in general) when all parties are connected by point-to-point channels, but exist under certain physical assumptions (Lepinksi et al., STOC~2005) or in specific network topologies (Alwen et al., Crypto~2008). We provide a ``clean-slate'' definition of the stronger notion of collusion preservation. Our goals in revisiting the definition are: -- To give a definition with respect to arbitrary communication resources (that includes as special cases the communication models from prior work). We can then, in particular, better understand what types of resources enable collusion-preserving protocols. -- To construct protocols that allow no additional subliminal communication in the case when parties can communicate (a bounded amount of information) via other means. (This property is not implied by collusion-freeness.) -- To provide a definition supporting \emph{composition}, so that protocols can be designed in a modular fashion using sub-protocols run among subsets of the parties. In addition to proposing the definition, we explore implications of our model and show a general feasibility result for collusion-preserving computation of arbitrary functionalities.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
vzikas @ cs umd edu
2011-08-13: last of 3 revisions
2011-08-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joel Alwen and Jonathan Katz and Ueli Maurer and Vassilis Zikas},
      title = {Collusion-Preserving Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2011/433},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.