Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)

Rational Secret Sharing Information -- Theoretically Secure against Adaptive Adversaries

Yang Yu, Zhanfei Zhou

Published Jul 1, 2013• 0 citations
Publisher

Abstract

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.

DOI
10.1109/trustcom.2013.34

Related papers

AN EFFICIENT AND INFORMATION THEORETICALLY SECURE RATIONAL SECRET SHARING SCHEME BASED ON SYMMETRIC BIVARIATE POLYNOMIALS

Christophe Tartary, Huaxiong Wang, Yun Zhang

The design of rational cryptographic protocols is a recently created research area at the intersection of cryptography and game theory. In this paper, we propose a new m-out-of-n rational secret sharing scheme requiring neither the involvement of the dealer (except during the initial share distribution) nor a trusted mediator. Our protocol leads to a Nash equilibrium surviving the iterated deletion of weakly dominated strategies for m ≥ 4. Our construction is information theoretically secure and it is immune against backward induction attacks. Contrary to Kol and Naor who used a specific cryptographic primitive in their TCC'08 paper (namely, meaningful/meaningless encryption), the immunity of our scheme is based on the use of bivariate polynomials and one-time pads. To the best of our knowledge, it is the first time that such polynomials have been used for rational secret sharing. Our scheme is efficient and does not require any physical assumptions such as envelopes or ballot boxes. As most of existing rational protocols, our construction requires simultaneous broadcast channels. However, our proposed scheme does not require any computational assumption and it provides information theoretical security.

International Journal of Foundations of Computer Science•Sep 1, 2011•6 citations

General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction.

Akinori Kawachi, Yoshio Okamoto, Keisuke Tanaka +1 more

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.

•Jan 1, 2013•2 citations

Cryptographic Rational Secret Sharing Schemes over General Networks

Alfonso B. Labao, Henry N. Adorna

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.

Cryptography•Oct 1, 2022•1 citation

Unconditionally Secure Rational Secret Sharing in Standard Communication Networks.

Zhifang Zhang

Abstract. Rational secret sharing protocols in both the two-party and multi-party settings are proposed. These protocols are built in standard communication networks and with unconditional security. Namely, the protocols run over standard point-to-point networks without requiring physical assumptions or simultaneous channels, and even a computationally unbounded player cannot gain more than ɛ by deviating from the protocol. More precisely, for the 2-out-of-2 protocol the ɛ is a negligible function in the size of the secret, which is caused by the informationtheoretic MACs used for authentication. The t-out-of-n protocol is (t−1)resilient and the ɛ is exponentially small in the number of participants. Although secret recovery cannot be guaranteed in this setting, a participant can at least reduce the Shannon entropy of the secret to less than 1 after the protocol. When the secret-domain is large, every rational player has great incentive to participate in the protocol.

•Jan 1, 2010•0 citations

General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction: Table 1.

Akinori Kawachi, Yoshio Okamoto, Keisuke Tanaka +1 more

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.

The Computer Journal•Nov 9, 2016•9 citations

Rational Secret Sharing Over an Asynchronous Broadcast Channel With Information Theoretic Security

William K. Moses, Chandrasekharan Pandu Rangan

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].

arXiv:1112.4033•International Journal of Network Security & Its Applications•Nov 30, 2011•6 citations
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.
The design of rational cryptographic protocols is a recently created research area at the intersection of cryptography and game theory. In this paper, we propose a new m-out-of-n rational secret sharing scheme requiring neither the involvement of the dealer (except during the initial share distribution) nor a trusted mediator. Our protocol leads to a Nash equilibrium surviving the iterated deletion of weakly dominated strategies for m ≥ 4. Our construction is information theoretically secure and it is immune against backward induction attacks. Contrary to Kol and Naor who used a specific cryptographic primitive in their TCC'08 paper (namely, meaningful/meaningless encryption), the immunity of our scheme is based on the use of bivariate polynomials and one-time pads. To the best of our knowledge, it is the first time that such polynomials have been used for rational secret sharing. Our scheme is efficient and does not require any physical assumptions such as envelopes or ballot boxes. As most of existing rational protocols, our construction requires simultaneous broadcast channels. However, our proposed scheme does not require any computational assumption and it provides information theoretical security.
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 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.
Abstract. Rational secret sharing protocols in both the two-party and multi-party settings are proposed. These protocols are built in standard communication networks and with unconditional security. Namely, the protocols run over standard point-to-point networks without requiring physical assumptions or simultaneous channels, and even a computationally unbounded player cannot gain more than ɛ by deviating from the protocol. More precisely, for the 2-out-of-2 protocol the ɛ is a negligible function in the size of the secret, which is caused by the informationtheoretic MACs used for authentication. The t-out-of-n protocol is (t−1)resilient and the ɛ is exponentially small in the number of participants. Although secret recovery cannot be guaranteed in this setting, a participant can at least reduce the Shannon entropy of the secret to less than 1 after the protocol. When the secret-domain is large, every rational player has great incentive to participate in the protocol.
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 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].