The Study Of The Secret Sharing Based On The Graph Structure

Secret sharing is widely application in information safety, digital signature, electronic auction, electronic voting, multi-party computation. A secret sharing scheme implies that all participants share a secret, and everyone of them saves a part of the secret. Meanwhile, the participants authorized can use sharing to obtain the secret, and any one who isn't authorized cannot get any information of the secret.Based on the features of the secret sharing, the thesis proposes four new secret sharing schemes in three, aspects of finite field Fq elements, the finite field Fq of n-dimension vector space Fqn vector and graph which the participant save. First, we resume that the vertex set of the graph is the set of the participants. We define the access structure use graph structure to make the number of the participants authorized more generalized. In this way, the scheme can stop dishonest participants cheating by nonlinear permutation. Secondly, we take the edge set of the graph as the set of participants. Based on the properties of complete graph, we finish distributing and retrieving of the secret, and then to a certain extent, the error-correcting algorithm of linear code is used to stop some cheating. Again, we propose a new secret sharing scheme to improve information rate utilizing the properties of cycles, meanwhile use independent set and vertex-covering research authorized subset. Finally, we research that how to share a graphics, using the new method of increasing vertex and edge share distribution, and the method of intersection set is used to retrieving the secret.According the optimization problem in graph theory to this thesis define mini-mal authorized subset, therefore the problem of defining minimal authorized subset, is equivalent to the problem of finding out the smallest, tree. According to the cal-culating formula of spanning-tree in the complete graph, the number of minimal authorized subset is fixed. In this paper, some methods of graph theory are used to make the secret sharing scheme easier and more applicable.