We present a general construction of a rational secret-sharing protocol that converts any rational secret-sharing protocol to a protocol with an expected 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 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 construction can be extended to a construction that preserves the immunity to unexpectedly behaving players. Then, for any constantm ≥ 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 same protocol also achieves a strict Nash equilibrium with coalition resilience 1. We show that our protocol with immunity achieves the optimal coalition resilience among constant-round protocols with immunity with respect to both Nash and strict Nash equilibria.
We present a general construction of a rational secret-sharing protocol that converts any rational secret-sharing protocol to a protocol with an expected 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 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 construction can be extended to a construction that preserves the immunity to unexpectedly behaving players. Then, for any constantm ≥ 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 same protocol also achieves a strict Nash equilibrium with coalition resilience 1. We show that our protocol with immunity achieves the optimal coalition resilience among constant-round protocols with immunity with respect to both Nash and strict Nash equilibria.
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.
We propose cryptographic rational secret sharing protocols over general networks. In a general network, the dealer may not have direct connections to each player, and players may not have direct connections to each of the other players. We present conditions on the network topology for which our proposed protocols are computational strict Nash equilibria and (k−1)-resilient, along with analysis on their round and communication complexity. We also present new notions of equilibria such as Φ-resilient computational Nash equilibria, whereby a protocol is resilient to coalitions that satisfy conditions in Φ, regardless of the coalition’s size. We also propose (n−1)-key leakage-tolerant equilibria applicable to cryptographic protocols involving secret keys, whereby the equilibrium holds even if some players acquire (n−1) tuples of secret keys.
Most rational secret sharing protocols aim to achieve a more appealing equilibrium or resist adversaries. However, all previous protocols achieve resilience against irrational adversaries at the cost of inducing a weak guarantee of Nash equilibrium surviving iterated deletion, which has been proved weaker than strict Nash equilibrium. Moreover, they achieve equilibrium in a computational way based on the computational limitations of adversaries. In this paper, we design two unconditionally secure rational (t, n) secret sharing protocols. Contrary to prior works, our protocols induce an enhanced notion of strict equilibrium with respect to adversary structure A, and resist the computationally unbounded and adaptive adversary without using cryptographic primitives. Our protocols achieve stronger stability, since rational players have an incentive not to deviate no matter how the adversary behaves, and they are immune to the backward induction. Our protocols are secure against the adversary corrupting less than [n/3] players and the adversary corrupting less than [n/2]-1 players respectively. Both of them achieve utility independence.
Rational secret sharing, first introduced by Halpern and Teague, means that whether players send their shares relies on their utilities, whereas in traditional scheme, players are assumed to contribute their shares willingly. This paper puts forward a rational secret-sharing scheme where players run their reconstruction protocol in point-to-point communication networks other than broadcast channels which are often used in previous papers. Kol and Naor propose an efficient t -out-of- n protocol for rational secret sharing without using cryptographic primitives while it has weak robustness to coalition when short player colludes with any long players. The protocol proposed by Fuchsbauer and Katz runs efficiently in asynchronous or point-to-point networks. Although it achieves strict Nash equilibrium and is stable with respect to trembles, it is susceptible to realise fairness among the whole party. This paper proposes a rational secret-sharing scheme in point-to-point communication networks to achieve fairness and robustness to coalition.
We consider the problem of rational secret sharing introduced by Halpern and Teague [1], where the players involved in secret sharing play only if it is to their advantage.This can be characterized in the form of preferences.Players would prefer to get the secret than to not get it and secondly with lesser preference, they would like as few other players to get the secret as possible.Several positive results have already been published to efficiently solve the problem of rational secret sharing but only a handful of papers have touched upon the use of an asynchronous broadcast channel.[2] used cryptographic primitives, [3] used an interactive dealer, and [4] used an honest minority of players in order to handle an asynchronous broadcast channel.In our paper, we propose an m-out-of-n rational secret sharing scheme which can function over an asynchronous broadcast channel without the use of cryptographic primitives and with a non-interactive dealer.This is possible because our scheme uses a small number, k+1, of honest players.The protocol is resilient to coalitions of size up to k and furthermore it is ε-resilient to coalitions of size up to and including m-1.The protocol will have a strict Nash equilibrium with probability Pr ( ାଵ ) and an ε-Nash equilibrium with probability Pr ( ିିଵ ) .Furthermore, our protocol is immune to backward induction.Later on in the paper, we extend our results to include malicious players as well.We also show that our protocol handles the possibility of a player deviating in order to force another player to get a wrong value in what we believe to be a more time efficient manner than was done in Asharov and Lindell [5].
We propose a new methodology for rational secret sharing leading to various instantiations (in both the two-party and multi-party settings) that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks. We also propose new equilibrium notions (namely, computational versions of strict Nash equilibrium and stability with respect to trembles) and prove that our protocols satisfy them. These notions guarantee, roughly speaking, that at each point in the protocol there is a unique legal message a party can send. This, in turn, ensures that protocol messages cannot be used as subliminal channels, something achieved in prior work only by making strong assumptions on the communication network. 1