Cryptology ePrint Archive: Report 2010/635

An Efficient and Information Theoretically Secure Rational Secret Sharing Scheme based on Symmetric Bivariate Polynomials

Zhang Yun and Christophe Tartary

Abstract: 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 \geq 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.

Category / Keywords: cryptographic protocols / secret sharing scheme, rational cryptography, information theoretical security, bivariate polynomial.

Publication Info: Submitted to ICITS 2011.

Date: received 13 Dec 2010, withdrawn 13 Dec 2010

Contact author: ctartary at mail tsinghua edu cn

Available format(s): (-- withdrawn --)

Version: 20101214:055709 (All versions of this report)

Short URL: ia.cr/2010/635

Discussion forum: Show discussion | Start new discussion