Collusion-Preserving
Computation
Joel
Alwen (ETH
Jonathan
Katz (
Ueli Maurer (ETH
Vassilis Zikas (
Abstract:
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 in the case when parties can
communicate (a bounded amount of information) 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 and show how to reduce the trust in
mechanisms of such games while preserving many important equilibrium notions.