One obstacle to this revolution is the lack of willingness of different entities to share their data, due to reasons such as possible loss of privacy or competitive edge. Whereas cryptographic works address the privacy aspects, they shed no light on individual parties' losses and gains when access to data carries tangible rewards. Even if it is clear that better overall conclusions can be drawn fom collaboration, are individual collaborators better off by collaborating? Addressing this question is the topic of this paper.
Our contributions are as follows.
* We formalize a model of $n$-party collaboration for computing functions over private inputs in which the participants receive their outputs in sequence, and the order depends on their private inputs. Each output ``improves'' on all previous outputs according to a score function.
* We say that a mechanism for collaboration achieves a \emph{collaborative equilibrium} if it guarantees a higher reward for all participants when joining a collaboration compared to not joining it. We show that while in general computing a collaborative equilibrium is NP-complete, we can design polynomial-time algorithms for computing it for a range of natural model settings. When possible, we design mechanisms to compute a distribution of outputs and an ordering of output delivery, based on the $n$ participants' private inputs, which achieves a collaborative equilibrium.
The collaboration mechanisms we develop are in the standard model, and thus require a central trusted party; however, we show that this assumption is not necessary under standard cryptographic assumptions. We show how the mechanisms can be implemented in a decentralized way by $n$ distrustful parties using new extensions of classical secure multiparty computation that impose order and timing constraints on the delivery of outputs to different players, in addition to guaranteeing privacy and correctness.
Category / Keywords: cryptographic protocols / MPC, fairness, timed-release crypto, data-sharing mechanisms Original Publication (with major differences): Innovations in Theoretical Computer Science (ITCS) 2016 Date: received 1 Mar 2015, last revised 10 Jan 2016 Contact author: sunoo at csail mit edu Available format(s): PDF | BibTeX Citation Version: 20160111:005953 (All versions of this report) Short URL: ia.cr/2015/178 Discussion forum: Show discussion | Start new discussion