You are looking at a specific version 20140210:055056 of this paper. See the latest version.

Paper 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$.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
rational secret sharinggame theory
Contact author(s)
yasunaga @ se kanazawa-u ac jp
History
2015-04-27: last of 2 revisions
2013-12-29: received
See all versions
Short URL
https://ia.cr/2013/874
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.