We consider the rational secret sharing problem introduced by Halpern and Teague[3], where players prefer to get the secret than not to get the secret and with lower preference, prefer that as few of the other players get the secret. The impossibility of a deterministic protocol for rational secret sharing is proved by Halpern and Teague[3]. The impossibility result is based on the fact that a rational player always chooses a dominating strategy and so there is no incentive for a player to send his secret share. This rational behavior makes secret sharing impossible, but there is an interesting way by which we can force rational players to cooperate for achieving successful secret sharing. A rational player may be deterred from exploiting his short term advantage by the threat of punishment that reduces his long term payoff. This can be captured by the repeated interaction of players. Hence, we study rational secret sharing in a scenario, where players interact repeatedly in several rounds which enables the possibility of secret sharing among rational players. In our model, the dealer, instead of sending shares, forms polynomials of the secret shares and sends points on that polynomial (say subshares) to the players. The dealer constructs polynomials in a manner that the degrees of polynomials used differ by at most one and each player is not aware of the degree of polynomial employed for others. The players distribute shares in terms of subshares. We show a surprising result on the deterministic protocol for rational secret sharing problem in synchronous model. This is the first protocol that achieves rational secret sharing in a reasonable model to the best of our knowledge.
We consider the rational secret sharing problem introduced by Halpern and Teague[3], where players prefer to get the secret than not to get the secret and with lower preference, prefer that as few of the other players get the secret. The impossibility of a deterministic protocol for rational secret sharing is proved by Halpern and Teague[3]. The impossibility result is based on the fact that a rational player always chooses a dominating strategy and so there is no incentive for a player to send his secret share. This rational behavior makes secret sharing impossible, but there is an interesting way by which we can force rational players to cooperate for achieving successful secret sharing. A rational player may be deterred from exploiting his short term advantage by the threat of punishment that reduces his long term payoff. This can be captured by the repeated interaction of players. Hence, we study rational secret sharing in a scenario, where players interact repeatedly in several rounds which enables the possibility of secret sharing among rational players. In our model, the dealer, instead of sending shares, forms polynomials of the secret shares and sends points on that polynomial (say subshares) to the players. The dealer constructs polynomials in a manner that the degrees of polynomials used differ by at most one and each player is not aware of the degree of polynomial employed for others. The players distribute shares in terms of subshares. We show a surprising result on the deterministic protocol for rational secret sharing problem in synchronous model. This is the first protocol that achieves rational secret sharing in a reasonable model to the best of our knowledge.
We consider the problem of secret sharing among n rational players. This problem was introduced by Halpern and Teague (STOC 2004), who claim that a solution is impossible for n = 2 but show a solution for the case n >= 3. Contrary to their claim, we show a protocol for rational secret sharing among n = 2 players; our protocol extends to the case n 3, where it is simpler than the Halpern-Teague solution and also o#ers a number of other advantages. We also show how to avoid the continual involvement of the dealer, in either our own protocol or that of Halpern and Teague. Our
In the problem of rational secret sharing, each player, who prefers to be the only one to learn the secret, acts rationally rather than merely honestly or maliciously in the traditional cryptographic settings. The core issue of rational secret sharing is to construct a mechanism so that all rational participants have incentive to provide their shares in the reconstruction phase. However, lack of enough incentive and how to achieve fairness in asynchronous model are always the hot potatoes for obtaining a deterministic protocol in this field. In this paper, we devote our attention to solving the above two difficulties in asynchronous model and succeed in obtaining a satisfactory result, 1/p-rational secret sharing protocol, in 2-out-of-2 case. Firstly, we apply the repeated interaction method to provide motivation so as to attract the players to participant in the collaboration and make it possible for a deterministic protocol. Secondly, inspired by 1/p-security of partial fairness, we propose a new concept, 1/p-advantage, to reduce the unavoidable probability of unfairness in asynchronous model to a satisfactory level. Besides, in order to perfect our protocol, we bring in the augmented perfect coin-tossing to determine the sending-order at the start of every round. Compared with previous ones, our protocol is applicable to the asynchronous model as well as the traditional synchronous model, which makes our protocol more practical. Furthermore, the new concept, 1/p-advantage, gives us a new perspective on rational secret sharing and makes our solution fresh.
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].
Abstract. Rational secret sharing was proposed by Halpern and Teague in [12]. The authors show that, in a setting with rational players, secret sharing and multiparty computation are only possible if the actual secret reconstruction round remains unknown to the players. All the subsequent works use a similar approach with different assumptions. We change the direction by bridging cryptography, game theory, and reputation systems, and propose a “social model ” for repeated rational secret sharing. We provide a novel scheme, named socio-rational secret sharing, in which players are invited to each game based on their reputations in the community. The players run secret sharing protocols while founding and sustaining a public trust network. As a result, new concepts such as a rational foresighted player, social game, and social Nash equilibrium are introduced. To motivate our approach, consider a repeated secret sharing game such as “secure auctions”, where the auctioneers receive sealed-bids from the bidders to compute the auction outcome without revealing the losing bids. If we assume each party has a reputation value, we can then penalize (or reward) the players who are selfish (or unselfish) from game to game. We show that this social reinforcement rationally stimulates the players to be cooperative.
Rational secret sharing was first introduced by Halpern and Teague (STOC, 2004). Since then, a series of works have focused on designing rational secret sharing protocols. However, most existing solutions can share only one secret at one secret sharing process. To share multiple secrets such as m secrets, the dealer must redistribute shares for m times. In addition, previous works assume existence of broadcast channel which is not realistic. Motivated by those problems, this paper proposes a rational multi-secret sharing scheme, which combines the secret sharing scheme with game theory. In the protocol, the problem of sharing multiple secrets is addressed, and there are multiple secrets to be shared during one secret sharing process. Furthermore, this work starts off by constructing a protocol in simultaneous broadcast networks, and then we emulate the broadcast channel over point-to-point networks. Based on a computational assumption, we show that rational players have no incentive to deviate from the protocol and every player can obtain multi-secret fairly.
Abstract. The problem of carrying out cryptographic computations when the participating parties are rational in a game-theoretic sense has recently gained much attention. One problem that has been studied considerably is that of rational secret sharing. In this setting, the aim is to construct a mechanism (protocol) so that parties behaving rationally have incentive to cooperate and provide their shares in the reconstruction phase, even if each party prefers to be the only one to learn the secret. Although this question was only recently asked by Halpern and Teague (STOC 2004), a number of works with beautiful ideas have been presented to solve this problem. However, they all have the property that the protocols constructed need to know the actual utility values of the parties (or at least a bound on them). This assumption is very problematic because the utilities of parties are not public knowledge. We ask whether this dependence on the actual utility values is really necessary and prove that in the basic setting, rational secret sharing cannot be achieved without it. On the positive side, we show that by somewhat relaxing the standard assumptions on the utility functions, it is possible to achieve utility independence. In addition to the above, observe that the known protocols for rational secret sharing that do not assume simultaneous channels all suffer from the problem that one of the parties can cause the others to output an incorrect value. (This problem arises when a party gains higher utility by having another output an incorrect value than by learning the secret itself; we argue that such a scenario is not at all unlikely.) We show that this problem is inherent in the non-simultaneous channels model, unless the actual values of the parties ’ utilities from this attack is known, in which case it is possible to prevent this from happening. 1