Scalable mechanisms for rational secret sharing

We consider the classical secret sharing problem in the case where all agents are rational. In recent work, Kol and Naor show that, when there are two players, in the non-simultaneous communication model, i.e., when rushing is possible, there is no Nash equilibrium that ensures both players learn the secret. However, they describe a mechanism for this problem, for any number of players, that is an \(\epsilon \) -Nash equilibrium, in 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. We address this issue by describing mechanisms for rational secret sharing that are designed for large \(n \ge 3\). Our first result is a non-cryptographic mechanism for \(n\)-out-of-\(n\) rational secret sharing that is Nash equilibrium, rather than just \(\epsilon \)-Nash equilibrium. Our second result is a cryptographic mechanism for rational \(t\)-out-of-\(n\) secret sharing that is everlasting \(\epsilon \)-Nash equilibrium. Both our mechanisms are scalable in the sense that they requires each player to send only an expected \(O(\log n)\) bits. Furthermore, the latency of these mechanisms is \(O(\log n)\) in expectation, compared to \(O(n)\) expected latency for the Kol and Naor result. Both of our mechanisms are not susceptible to backwards induction.