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)
- 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
-
CC BY