Secret sharing refers to a scheme whereby each member group of agents has a share of a secret, which can be reconstructed if and only if a sufficient number of the shares are pooled together. We study a version of the secret sharing problem in which all the agents are selfish but rational. In recent work, Kol and Naor show that in the non-simultaneous communication model (i.e. when rushing is possible), there is no Nash equilibrium that ensures all agents learn the secret. However, they describe a mechanism for this problem that is an epsilon-Nash equilibrium, i.e. it is close to an equilibrium in the sense that no player can gain more than epsilon utility by deviating from it.

Unfortunately, the Kol and Naor mechanism, and, to the best of our knowledge, all previous mechanisms for this problem require each agent to send O(n) messages in expectation, where n is the number of agents. This may be problematic for some applications of rational secret sharing such as secure multiparty computation and simulation of a mediator. We address this issue by describing a mechanism for rational n-out-of-n secret sharing that is an epsilon-Nash equilibrium, and is scalable in the sense that it requires each agent to send only an expected O(1) messages and polylogarithmic number of bits. Moreover, the latency of our mechanism is O(log n) in expectation, compared to O(n) expected latency for the Kol and Naor result. We also design scalable mechanisms for a relaxed variant of rational m-out-of-n secret sharing where m =3D =E8(n). Our mechanisms are non-cryptographic, and are not susceptible to backwards induction.

This is joint work with Jared Saia, Yamel Torres and Mahnush Movahedi.