Paper 2020/497

Collusion-Preserving Computation without a Mediator

Michele Ciampi and Yun Lu and Vassilis Zikas

Abstract

Collusion-free (CF) and collusion-preserving (CP) protocols offer alternatives to standard multi-party computation (MPC) in settings where subliminal communication is undesirable, e.g., in decentralizing mediators in mediated games. However, all existing solutions make too strong and uninstantiable assumptions on the setups, such as physical presence of the parties, access to physical envelopes and opaque ballot boxes, or extreme isolation, where the only means of communication is a star-topology network among the parties with a special resource, the mediator, at its center---and the mediator needs to be aware of the function to be computed. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic application scenarios. In this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the above, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving secure (in short, CP secure) as long as no parties abort. In the case of an aborting adversary our protocol loses CP security, but still achieves standard security---against monolithic adversaries---and additionally identifies a corrupted party. Leveraging the above identifiability property, we augment our protocol with a collateral and compensation mechanism which ensures that it is not profitable to abort, thereby obtaining CP security against incentive driven adversaries. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen et al. [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest. Similar to existing protocols in the CP/CF literature, our protocols preserve, as a fallback, the traditional security properties---i.e., security against monolithic adversaries---even when the setup (i.e., the hardware tokens) is compromised or corrupted.