Collusion-preserving computation

Joël Alwen*, Jonathan Katz, Ueli Maurer, Vassilis Zikas

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 when parties are connected 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 (including 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 when parties can communicate via other means. (This property is not implied by collusion-freeness.) - To support composition, so 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. We formalize a model for concurrently playing multiple extensive-form, mediated games while preserving many important equilibrium notions.

Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2012
Subtitle of host publication32nd Annual Cryptology Conference, Proceedings
EditorsReihaneh Safavi-Naini, Ran Canetti
Place of PublicationBerlin, Heidelberg
Number of pages20
ISBN (Electronic)978-3-642-32009-5
ISBN (Print)978-3-642-32008-8
Publication statusPublished - 3 Sept 2012
Event32nd Annual International Cryptology Conference - Santa Barbara, CA, United States
Duration: 19 Aug 201223 Aug 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer, Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference32nd Annual International Cryptology Conference
Abbreviated titleCRYPTO 2012
Country/TerritoryUnited States
CitySanta Barbara, CA


Dive into the research topics of 'Collusion-preserving computation'. Together they form a unique fingerprint.

Cite this