TY - JOUR
T1 - An efficient and information theoretically secure rational secret sharing scheme based on symmetric bivariate polynomials
AU - Tartary, Christophe
AU - Wang, Huaxiong
AU - Zhang, Yun
PY - 2011/9
Y1 - 2011/9
N2 - 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.
AB - 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.
KW - bivariate polynomial
KW - information theoretical security
KW - rational cryptography
KW - Secret sharing scheme
UR - http://www.scopus.com/inward/record.url?scp=80052692651&partnerID=8YFLogxK
U2 - 10.1142/S0129054111008775
DO - 10.1142/S0129054111008775
M3 - Article
AN - SCOPUS:80052692651
SN - 0129-0541
VL - 22
SP - 1395
EP - 1416
JO - International Journal of Foundations of Computer Science
JF - International Journal of Foundations of Computer Science
IS - 6
ER -