General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction: Table 1.
Akinori Kawachi, Yoshio Okamoto, Keisuke Tanaka, Kenji Yasunaga · The Computer Journal · 2016
We present a protocol compiler of rational secret-sharing that converts any rational secret-sharing protocol to a protocol with an expected constant-round reconstruction. Our compiler can be applied to protocols for synchronous channels, and preserves a strict Nash equilibrium of the original protocol. Combining with an existing protocol, we obtain the first expected constant-round protocol that achieves a strict Nash equilibrium with the optimal coalition resilience ⌈n2⌉−1, where n is the number of players. Our compiler can be extended to one that preserves the immunity to unexpectedly behaving players. For any constant m≥1, we obtain an expected constant-round protocol that achieves a Nash equilibrium with the optimal coalition resilience ⌈n2⌉−m−1 in the presence of m unexpectedly behaving players. The protocol also achieves a strict Nash equilibrium. As a negative result, we show that if an expected constant-round protocol has immunity m>0, then it cannot achieve a strict Nash equilibrium with the coalition resilience 2. Thus, our protocol with immunity achieves the optimal coalition resilience with respect to both Nash and strict Nash equilibrium.