The Existence of Multi-secret Sharing Schemes Based on Random Walks on Graphs

A multi-secret sharing scheme is the extension of a secret sharing scheme to the case in which there are many secrets need to be shared, and each secret may with different qualified subsets of participants. We study multi-secret sharing schemes based on random walks on graphs. Since many problems of secret sharing can be seen as having structure of the graphs. Different access structures corresponding to different walks for a graph with n vertices can be defined. So considering multi-secret sharing scheme based on random walks on graphs is meaningful. We prove that there exists multi-secret sharing schemes based on random walks on graphs by studying monotone span programs computing monotone Boolean function and secret sharing schemes realizing these classes of access structure.