Multi-secret Sharing Schemes Based On Random Walks Of Graphs

In this article we introduce the monotone span programs and bull function firstly. Then we introduce access structures and secret sharing schemes. Our main position is to introduce multi-secret sharing schemes. multi-secret sharing schemes is that participants P share arbitrary m keys and only qualified subsets of P are able to reconstruct the secret value,while nonqualified subsets can not obtain any information about the value of the secret. Then we define two classes of access structures. One is that access structures based on connectivity of graphs. Other is that access structure based on random walks on graphs. We construct monotone span programs to realize preview access structure from the relation between monotone span programs and secret sharing schemes. But this paper analyzes access structure based on random walks on graphs mainly. And we know there exists multi-secret sharing schemes realizing these classes of access structure.