Rational Secret Sharing AS Extensive Games
Some punishments in rational secret sharing schemes turn out to be empty threats. In this paper, we first model 2-out-of-2 rational secret sharing in an extensive game with imperfect information, and then provide a strategy for achieving secret recovery in this game. Moreover, we prove that the strategy is a sequential equilibrium which means after any history of the game no player can benefit from deviations so long as the other players stick to the strategy. Therefor, by considering rational secret sharing as an extensive game, we design a scheme which eliminates empty threats. Except assuming the existence of a simultaneous broadcast channel, our scheme can have dealer off-line and extend to the t-out-of-n rational secret sharing, and also satisfies computational equilibria in some sense.
Unconditionally Secure Rational Secret Sharing in Standard Communication Networks
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 $\epsilon$ by deviating from the protocol. More precisely, for the $2$-out-of-$2$ protocol the $\epsilon$ is a negligible function in the size of the secret, which is caused by the information-theoretic MACs used for authentication. The $t$-out-of-$n$ protocol is $(t-1)$-resilient and the $\epsilon$ 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.
Multiparty Computation Based on Connectivity of Graphs
In this paper, we contribute the construction of practical perfect multiparty computation protocols based on the connectivity of graphs.
Statistical Multiparty Computation Based on Random Walks on Graphs
With respect to a special class of access structures based on connectivity of graphs, we start from a linear secret sharing scheme and turn it into a secret sharing scheme with perfect security and exponentially small error probability by randomizing the reconstruction algorithm through random walks on graphs. It reduces the polynomial work space to logarithmic. Then we build the corresponding statistical multiparty computation protocol by using the secret sharing scheme. The results of this paper also imply the inherent connections and influences among secret sharing, randomized algorithms, and secure multi-party computation.