Monotone Span Program With The Secret Sharing Scheme

Secret sharing is about how to share a secret among participants, in such a way that only qualified subsets of the participants can reconstruct it and unqualified subsets get no information about the secret. Since Shamir and Blakley have introduced the concept of the (t, n) threshold secret sharing respectively in 1979, the theory is researched deeply by many experts and researchers. So a great number of schemes have been put forward, included many schemes with special functions, such as cheat-proof secret sharing, verifiable secret sharing, dynamic secret sharing, multi-dealers secret sharing, linear secret sharing and so on. At the same time, secret sharing have been widely applied to digital signature, electronic commerce, multi-party computation and so on.Based on the analysis of several secret sharing schemes, some weaknesses for these schemes are as follows:(1) During the process of secret sharing, there is a dealer in many schemes. When the participants are changed, the dealer must redistribute the secret shares of the other members which increase the cost of the system.(2) When constructing the linear secret sharing scheme by the monotone span program, we discovered that most linear secret sharing schemes are constructed based on the target vector is v=(1,1,…,1). But in real life, the constructions under the target vector is e=(1,0,…,0) are more required.To solve these problems, the article mainly focuses on Multi-Secret sharing scheme based on multi-dealer and the constructions of linear secret sharing scheme by monotone span program when the target vector is e=(1,0,…,0). The research results of this paper are showed in the following:1. By means of Homogeneous linear recursion sequence and discrete logarithm, a novel secret sharing scheme is proposed based on the multi-dealer problem. In this scheme, the secret are maintained by several dealers and it can be dynamically renewed by any dealer. In the secret updated phase, the dealer just needs to publish a little public information instead of redistributing the new secret shadows. Its security is based on the security of RSA cryptosystem and the intractability of discrete logarithm problem.2. We study the constructions of linear secret sharing scheme by the monotone span program and give the corresponding matrix of a target vector e=(1,0,…,0) and the examples.3. We introduced that the monotone Boolean circuit can construct the secret sharing scheme, and it also can construct the linear secret sharing scheme. Further more, we illustrates the equivalence relation between the monotone span program and the monotone Boolean circuit, when they are used to construct the linear secret sharing scheme.