Cryptology ePrint Archive: Report 2013/874

Constant-Round Rational Secret Sharing with Optimal Coalition Resilience

Akinori Kawachi and Yoshio Okamoto and Keisuke Tanaka and Kenji Yasunaga

Abstract: We provide a general construction that converts any rational secret-sharing protocol to a protocol with a constant-round reconstruction. Our construction 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 rational secret-sharing protocol that achieves a strict Nash equilibrium with the optimal coalition resilience of $\ceil{\frac{n}{2}}-1$, where $n$ is the number of players.

Although the coalition resilience of $\ceil{\frac{n}{2}}-1$ is known to be optimal for constant-round protocols, we show that the limitation can be circumvented by considering a natural assumption that players avoid reconstructing \emph{fake} secrets. Under this assumption, we give a constant-round protocol that achieves a strict Nash equilibrium with the maximal coalition resilience of $n-1$.

Our construction can be extended to a construction that preserves the \emph{immunity} to unexpectedly behaving players. Then, we obtain a protocol that achieves a Nash equilibrium with the optimal coalition resilience of $\ceil{\frac{n}{2}}-t-1$ in the presence of $t$ unexpectedly behaving players for any constant $t \geq 1$.

Category / Keywords: rational secret sharing, game theory

Date: received 28 Dec 2013, last revised 9 Feb 2014

Contact author: yasunaga at se kanazawa-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20140210:055056 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]