This paper introduces the Repeated Rational Secret Sharing problem. We borrow the notion of rational secret sharing from Halpern and Teague[1], 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. We introduce the concept of repeated games in the rational secret sharing problem for the first time, which enables the possibility of a deterministic protocol for solving this problem. This is the first approach in this direction to the best of our knowledge. We extend the results for the mixed model (synchronous) where at most t players can be malicious. We also propose the first asynchronous protocol for rational secret sharing. © 2008 Springer-Verlag Berlin Heidelberg.

C Pandu Rangan

Department of Computer Science and Engineering

Shaik Maleka

Amjed Shareef

Distributed computer systems

Game theory

Network protocols

Problem solving

DETERMINISTIC PROTOCOLS

REPEATED GAMES

Secret sharing

Information dissemination

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Rational secret sharing with repeated games

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

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. ©2008 IEEE.

IPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM

The deterministic protocol for rational secret sharing

Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing - PODC '06

Distributed computing meets game theory

Lecture Notes in Computer Science Security and Cryptography for Networks

Rational Secret Sharing, Revisited

Lecture Notes in Computer Science Advances in Cryptology - CRYPTO 2006

Rationality and Adversarial Behavior in Multi-party Computation

Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04

Rational secret sharing and multiparty computation

Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN	03029743
Open Access	No