An Ideal Multi-secret Sharing Scheme Based on Connectivity of Graphs

Secure communication has become more and more important for many modern communication applications. In a secure communication, every pair of users need to have a secure communication channel (each channel is controlled by a server) In this paper, using monotone span programs we devise an ideal linear multi-secret sharing scheme based on connectivity of graphs. In our proposed scheme, we assume that every pair of users, (p) and (q) , use the secret key (s_{pq} ) to communicate with each other and every server has a secret share such that a set of servers can recover (s_{pq} ) if the channels controlled by the servers in this set can connect users, (p) and (q) . The multi-secret sharing scheme can provide efficiency for key management. We also prove that the proposed scheme satisfies the definition of a perfect multi-secret sharing scheme. Our proposed scheme is desirable for secure and efficient secure communications.