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

Abstract

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.

1 Introduction

Secret sharing schemes, which were introduced by Shamir [1] and Blakley [2] independently more than 30 years ago, have been widely used in many secure communications. In these schemes, there is a finite set of participants and a collection, $\Gamma$, of subsets of the participants (called the access structure). A secret sharing scheme for $\Gamma$ is a method in which a dealer distributes shares of a secret to the participants such that (1) any subset in $\Gamma$ can reconstruct the secret from its shares, and (2) any subset not in $\Gamma$ cannot reveal any partial information about the secret in the information theoretic sense.

A secret sharing scheme is called ideal if the shares of participants are taken from the same domain as the secret. As proved in [3], this is the minimal size of the shares. The access structures which can be realized by ideal secret-sharing schemes are called ideal access structures. This definition of ideal single-secret sharing can be extended to multi-secret sharing, that is, a secret sharing scheme with multiple secrets is said to be ideal if all secrets and the shares of participants have the same size. This is the optimal efficiency for multi-secret sharing schemes.

Many secret sharing applications, in particular those associated with the key management, require the protection of more than one secret. As an example, consider the following situation described by Simmons [4]. There is a missile battery in which each missile has a different launch enable code. The problem is to devise a scheme to protect these codes by using the same pieces of private information. This problem could be trivially solved by realizing different secret sharing schemes, one for each launch enable code; but in this case each participant should remember too much information. In order to reduce the amount of information given to participants, it is interesting to investigate the possibility of constructing multiple secret sharing schemes without necessarily using multiple single secret sharing schemes.

Specific models for the sharing of many secrets have already been considered in the literature. In [3], Karnin et al. considered the problem of sharing $m$ secrets $s_1,\ldots ,s_m$ among a set of $n$ participants. In particular, they considered the situation in which, for a fixed value $k\le n$, any set of $k$ participants can reconstruct the secret $s_j$, for $1\le j\le m$, whereas, any subset of $k-1$ participants has no information about the secret $s_j$. These schemes are called $(m,k,n)$ multi-secret sharing threshold schemes, which have been constructed by several papers (see [5–10]). Schemes of this kind have also been considered by Jackson et al. [11, 12]. In particular, they considered the situation in which, for a fixed value, $t\in \{1,2,\ldots ,n\}$, there is a secret associated with each subset ${\mathcal {P}}^{\prime }\subseteq {\mathcal {P}}$, such that $|{\mathcal {P}}^{\prime }|=t$. For a fixed parameter, $k\le t$, this secret can be reconstructed by any $k$ participants in ${\mathcal {P}}^{\prime }$. They proved bounds on the size of the information that participants must be held in order to ensure that up to $w$ participants $(0\le w\le n-t+k-1)$ cannot obtain any information about a secret which they have no access right. Such schemes are referred to a $w$-secure $(k,t,n)$ multi-threshold schemes.

In [13], the problem of sharing multiple secrets among a set of shareholders has been generalized to the case where all secrets are shared according to a general secret access structure. In the proposed model, any qualified set of participants can recover all the secrets, whereas, any unqualified set of participants has absolutely no information about each secret but, knowing some secrets, might have some information about the other secrets. Schemes of this kind have also been considered in [14], where some optimal constructions have been proposed. The problem of sharing many secrets according to different access structures has been considered in [15] and further investigated in [16], where a classification of ideal secret sharing schemes with multiple secrets has been proposed.

By using a multi-party computation protocol, [17] solved a secret-leaking problem in multi-secret sharing schemes. They also showed that the non-direct sum linear multi-secret sharing scheme was preferred in reducing share expansion after comparing it with the associated “direct sum” scheme. A corresponding relation between monotone span programs and linear multi-secret sharing schemes has been studied in [18], where the optimal linear multi-secret sharing schemes have also been discussed. These results are fairly interesting as to how to construct ideal multi-secret sharing schemes for general access structures.

So far, very little is known about how to devise ideal multi-secret sharing schemes for general access structures. Due to the difficulty of finding general results, the construction of ideal multi-secret sharing schemes for specific families of access structures may have interesting applications which is worth investigation (see [19, 20]). Today, secure communication has become more and more important for many communication applications. In this paper, we consider the following scenario in a group communication. We assume that there are $t$ users and every pair of users have a secure communication channel connecting them (each channel is controlled by a server). Because some communication channels may be shut down due to natural cause or by human interruption, the secure communication service between two users should be maintained properly as long as the remaining channels can establish an alternative connection between two users. To achieve this objective of secure services, we advise to use a secret key to encrypt message between every pair of users. There are all $t(t-1)/2$ secret keys, where $t$is the number of users in the communication. How to efficiently share these $t(t-1)/2$ secret keys among $t(t-1)/2$ servers such that for every pair of users, a set of servers who provide the alternative connection between users can recover the shared secret key of two users is the subject of our proposed scheme.

Using monotone span programs (MSP), we devise an ideal linear multi-secret sharing scheme (LMSS) based on connectivity of graphs. In our proposed scheme, the dealer is a trusted entity, the servers act the role of shareholders in a secret sharing scheme, the communication channels are denoted by edges and the users are denoted by vertices. We propose an efficient multi-secret sharing scheme. In addition, we prove that the proposed scheme satisfies the definition of a perfect multi-secret sharing scheme. Here, we list the contributions of our paper.

• A novel LMSS based on connectivity of graphs is proposed, which ensures secure and fault-tolerant communications.

• The efficiency of proposed scheme is optimal. Namely, it is an ideal LMSS and all secrets and the shares of participants are the same size.

• The proposed scheme is a perfect LMSS, that is, a set of servers who provide the alternative connection between two users can recover the shared secret key between two users.

The rest of the paper is organized as follows: In Sect. 2, some preliminaries are reviewed. The MSP to permit more than one target vector is introduced in Sect. 3. Then, in Sect. 4, we build an ideal LMSSS based on connectivity of graphs. Section 5 proves the correctness and security of the proposed scheme. Conclusions are given in Sect. 6.

2 Preliminaries

In this section, we review some basic definitions related to secret sharing schemes. For a unified description and detailed proof of results in the subject of secret sharing schemes, the reader can refer to the survey articles by Simmons [4] and Stinson [21].

2.1 Positive Access Structures and Negative Access Structures

Let ${\mathcal {P}}=\{1,\ldots ,n\}$ be the set of players. A positive access structure, denoted by $\Gamma$, is a collection of subsets of ${\mathcal {P}}$ satisfying the monotone ascending property: for any $A^{\prime }\in \Gamma$ and $A\in 2^{{\mathcal {P}}}, A^{\prime }\subseteq A$ implies $A\in \Gamma$. A negative structure, denoted by $\mathcal{A}$, is a collection of subsets of ${\mathcal {P}}$ satisfying the monotone descending property: for any $A^{\prime }\in \mathcal{A}$ and $A\in 2^{{\mathcal {P}}}, A\subseteq A^{\prime }$ implies $A\in \mathcal{A}$. Because of the monotone properties, for any positive access structure $\Gamma$ and any negative access structure $\mathcal{A}$, it is enough to consider the minimum positive access structure $\Gamma _{\min } =\{A\in \Gamma \,|\,\forall B\subset A\Rightarrow B\notin \Gamma \}$ and the maximum negative access structure $\mathcal{A}_{\max } =\{B\in \mathcal{A}\,|\, \forall A\supset B\Rightarrow A\notin \mathcal{A}\}$, respectively. In this paper, we consider the complete situation, i.e., $\mathcal{A}=2^{{\mathcal {P}}}-\Gamma$.

We use the following example to illustrate these two structures. We assume that there are 3 users, A, B and C. The positive access structure of a secret is $\Gamma =\{\{AB\}, \{BC\}, \{ABC\}\}$. By taking the logically complement of the access structure, we obtain the negative access structure as A={{A$^\prime$B$^\prime$},{A$^\prime$C$^\prime$},{A$^\prime$B$^\prime$C$^\prime$},{B$^\prime$C$^\prime$}}. We can obtain that the minimum positive access structure is $\Gamma _{\min } =\{\{AB\},\{BC\}\}$ and the maximum negative access structure is $\hbox {A}_\mathrm{max}$={{B$^\prime$}.{A$^\prime$B$^\prime$}}.

2.2 Linear Secret Sharing Schemes and Monotone Span Programs

Suppose that $S$ is the secret-domain and $P_i$ is the share-domain of player $i$, where $1\le i\le n$. When a dealer $D$ wants to share a secret $s\in S$ among a set of players ${\mathcal {P}}=\{1,\ldots ,n\}$, he will give each player a share $p_i \in P_i$. The shares should be distributed secretly, so no player knows the share given to another player. At a later time, a subset of players will attempt to reconstruct the secret $s$ from the shares they collectively hold. By using Shannon’s entropy function, a secret sharing scheme with respect to an access structure $\Gamma$ is defined such that the following requirements are satisfied.

• (i) Correctness requirement: any subset $A\subseteq {\mathcal {P}}$ of players enabled to recover $s$ can compute $s$. Formally, for all $A\in \Gamma$, it holds $H(S\,|\,A)=0$.

• (ii) Security requirement: any subset $A\subseteq {\mathcal {P}}$ of players not enabled to recover $s$, even pooling all of their shares together, can not reconstruct $s$. Formally, for all $A\notin \Gamma$, it holds $0<H(S\,|\,A)\le H(S)$.

In the security requirement, if for any $A\notin \Gamma$ it holds $H(S\,|\,A)=H(S)$ (that is, players in $A$ pool their shares together obtain no information on $s)$, we call it a perfect secret sharing scheme which we are interested in. If $|\,S\,|=|P_i |$ for $1\le i\le n$, then the secret sharing scheme is called ideal. Furthermore, a perfect secret sharing scheme is linear, if $S=\mathcal{K}$ is a finite field, $P_i$ are linear spaces over $\mathcal{K}$ and the reconstruction operations are linear [22].

Karchmer and Wigderson [23] introduced monotone span programs (MSP) as linear models computing monotone Boolean functions. Usually we denote an MSP by $\mathcal{M}(\mathcal{K},M,\psi )$, where $M$ is a $d\times l$ matrix over a finite field $\mathcal{K}$ and $\psi :\{1,\ldots ,d\}\rightarrow \{1,\ldots ,n\}$ is a surjective labeling map which actually distributes to each player some rows of $M$. We call $d$ the size of the MSP. For any subset $A\subseteq {\mathcal {P}}$, there is a corresponding characteristic vector $\vec {\delta }_A =(\delta _1,\ldots ,\delta _n )\in \{0,1\}^{n}$ where for $1\le i\le n, \delta _i =1$ if and only if $i\in A$. Consider a monotone Boolean function $f:\{0,1\}^{n}\rightarrow \{0,1\}$ which satisfies that for any $A\subseteq {\mathcal {P}}$ and $B\subseteq A, f(\vec {\delta }_B )=1$ implies $f(\vec {\delta }_A )=1$. We say that an MSP $\mathcal{M}(\mathcal{K},M,\psi )$ computes the monotone Boolean function $f$ with respect to a target vector $\vec {v}\in \mathcal{K}^{l}\backslash \{(0,\ldots 0)\}$, if it holds that $\vec {v}\in span\{M_A \}$ if and only if $f(\vec {\delta }_A )=1$, where $M_A$ consists of the rows $r$ of $M$ with $\psi (r)\in A$ and $\vec {v}\in span\{M_A \}$ means that there exists a vector $\vec {w}$ such that $\vec {v}=\vec {w}M_A$.

Beimel [22] proved that devising a linear secret sharing scheme (LSSS) for an access structure $\Gamma$ is equivalent to constructing an MSP computing the monotone Boolean function $f_\Gamma$ which satisfies $f_\Gamma (\vec {\delta }_A )=1$ if and only if $A\in \Gamma$. On the other hand, an MSP $\mathcal{M}(\mathcal{K},M,\psi )$ can compute $f_\Gamma$ if and only if there exists a vector $\vec {v}$ which lies in the space $\bigcap _{A\in \Gamma _{\min } } {\sum _{i\in A} {V_i } } -\bigcup _{B\in \mathcal{A}{ }_{\max }} {\sum _{i\in B} {V_i } }$, where $V_i$ is the space spanned by the row vectors of $M$ distributed to player $i$ according to $\psi$ and the vector $\vec {v}$ can be seemed as the target vector described above. Hence, finding the linear spaces $V_i$ with the condition $\bigcap _{A\in \Gamma _{\min } } {\sum _{i\in A} {V_i } } -\bigcup _{B\in \mathcal{A}{ }_{\max }} {\sum _{i\in B} {V_i } } \ne \varnothing$ is the key point of building an LSSS with respect to $\Gamma$.

2.3 Multi-secret Sharing Schemes

The problem of sharing many secrets simultaneously among the same set of players has been considered (with some differences in the definitions) by several researchers (see [3, 11, 13–16, 24]). The most straightforward definition of a multi-secret sharing scheme for $m$ secrets $s_1,\ldots ,s_m$ is a natural generalization of single secret sharing schemes, where for any $1\le j\le m$, each secret $s_j$ is associated with a (potentially different) access structure $\Gamma _j$ on ${\mathcal {P}}$. Let $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ be the $m$-tuple of access structures and let $S_1 \times \cdot \cdot \cdot \times S_m$ be the set from which the secrets are chosen (the $j$th secret to be shared is chosen in $S_j )$, according to some probability distribution on such a set. For any $i\in {\mathcal {P}}$, denote by $P_i$ the set of all possible shares given to player $i$.

In the definition of a perfect multi-secret sharing scheme, an $m$-tuple of secrets $(s_1,\ldots ,s_m )$ $\in S_1 \times \cdot \cdot \cdot \times S_m$ is shared in an $m$-tuple $\vec {\Gamma }=(\Gamma _1,\ldots ,\Gamma _m )$ of access structures on ${\mathcal {P}}$ in such a way that, for each $j=1,\ldots ,m$, the access structure $\Gamma _j$ is the set of all subsets of ${\mathcal {P}}$ that can recover secret $s_j \in S_j$. This means that only the sets in $\Gamma _j$ can recover the secret $s_j$, but any set $A\notin \Gamma _j$ has no more information on $s_j$ than that already conveyed by the known secrets. A perfect multi-secret sharing scheme is defined in [15] as follows.

Definition 1

Let $\vec {\Gamma }=(\Gamma _1,\ldots ,\Gamma _m )$ be an $m$-tuple of access structures on the set of players ${\mathcal {P}}$. A multi-secret sharing scheme for $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ is a sharing of the secrets $(s_1,\ldots ,s_m )\in S_1 \times \cdot \cdot \cdot \times S_m$ in such a way that, for $j=1,\ldots ,m$,

• (i) Any subset $A\subseteq {\mathcal {P}}$ of players enabled to recover $s_j$ can compute $s_j$. Formally, for all $A\in \Gamma _j$, it holds $H(S_j |\,A)=0$.

• (ii) Any subset $A\subseteq {\mathcal {P}}$ of players not enabled to recover $s_j$, even knowing some of the other secrets, has no more information on $s_j$ than that already conveyed by the known secrets. Formally, for all $A\notin \Gamma _j$ and $T\subseteq \{S_1,\ldots ,S_m \}\backslash \{S_j \}$, it holds $H(S_j |AT)=H(S_j |\,T)$.

2.4 Some Concepts About Graphs

Let $G(V,E)$ be a graph with the vertex set $V$ and the edge set $E$. Two vertices $u,v\in V$ are adjacent if they are, respectively the two endpoints of an edge in $G$, i.e., $uv\in E$. A path in $G$ is of the form $v_0 v_1 \ldots v_l$ such that $v_0,v_1 ,\ldots ,v_l$ are distinct vertices in $G$ and $v_j v_{j+1} \in E$ for $0\le j<l$. More precisely, we call it a path from $v_0$ to $v_l$. When $l\ge 2$ and $v_l$ is adjacent to $v_0$, we get a cycle. Two vertices $u,v\in V$ are connected, if there is a path from $u$ to $v$. The graph $G$ is called connected if each pair of vertices in $G$ are connected. A tree is a connected graph with no cycles.

A subgraph of a graph $G(V,E)$ is a graph $G^{\prime }(V^{\prime },E^{\prime })$ such that $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$. A spanning subgraph of $G(V,E)$ is a subgraph $G^{\prime }(V^{\prime },E^{\prime })$ with the vertex set $V^{\prime }=V$. A spanning tree is a spanning subgraph that is a tree. When a graph is not connected (i.e., disconnected), its maximal connected subgraphs are called components. An isolated vertex is a vertex that is not an endpoint of any edge.

3 MSP Computing ${\varvec{m}}$ Monotone Boolean Functions

In this section we introduce the MSP computing $m$ monotone Boolean functions.

Let $\mathcal{M}(\mathcal{K},M,\psi )$ be an MSP to permit $m$ target vectors $v_1 ,\ldots ,v_m$, where $M$ is a $d\times l$ matrix over a finite field $\mathcal{K}$ and $\psi :\{1,\ldots ,d\}\rightarrow \{1,\ldots ,n\}$ is a surjective labeling map which actually distributes to each player some rows of $M$. We call $d$ the size of the MSP. For any subset $A\subseteq {\mathcal {P}}$, there is a corresponding characteristic vector $\vec {\delta }_A =(\delta _1 ,\ldots ,\delta _n )\in \{0,1\}^{n}$ where for $1\le i\le n, \delta _i =1$ if and only if $i\in A$. Consider a monotone Boolean function $f:\{0,1\}^{n}\rightarrow \{0,1\}$ which satisfies that for any $A\subseteq {\mathcal {P}}$ and $B\subseteq A, f(\vec {\delta }_B )=1$ implies $f(\vec {\delta }_A )=1$. We say that an MSP $\mathcal{M}(\mathcal{K},M,\psi )$ computes $m$ monotone Boolean functions $f_1 ,\ldots ,f_m$ with respect to $m$ target vectors $\vec {v}_1 ,\ldots ,\vec {v}_m \in \mathcal{K}^{l}\backslash \{(0,\ldots 0)\}$, if it holds that for each $j=1,\ldots ,m, \vec {v}_j \in span\{M_A \}$ if and only if $f_j (\vec {\delta }_A )=1$, where $M_A$ consists of the rows $r$ of $M$ with $\psi (r)\in A$ and $\vec {v}_j \in span\{M_A \}$ means that there exists a vector $\vec {w}$ such that $\vec {v}_j =\vec {w}M_A$.

Likewise, by using the same method of proof in [22], it is easy to obtain that devising a linear multi-secret sharing scheme (LMSSS) for an $m$-tuple $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ of access structures is equivalent to constructing an MSP $\mathcal{M}(\mathcal{K},M,\psi )$ computing $m$ monotone Boolean functions $f_{\Gamma _1 } ,\ldots ,f_{\Gamma _m }$ which satisfies for each $j=1,\ldots ,m, f_{\Gamma _j } (\vec {\delta }_A )=1$ if and only if $A\in \Gamma _j$. On the other hand, an MSP $\mathcal{M}(\mathcal{K},M,\psi )$ can compute $f_{\Gamma _j }$ for each $j=1,\ldots ,m$ if and only if there exists a vector $\vec {v}_j$ which lies in the space $\bigcap _{A\in (\Gamma _j )_{\min } } {\sum _{i\in A} {V_i } } -\bigcup _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum _{i\in B} {V_i } }$, where $V_i$ is the space spanned by the row vectors of $M$ distributed to player $i$ according to $\psi$ and the vector $\vec {v}_j$ can be seemed as the target vector described above. Hence, finding the linear spaces $V_i$ with the condition $\bigcap _{A\in (\Gamma _j )_{\min } } {\sum _{i\in A} {V_i } } -\bigcup _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum _{i\in B} {V_i } } \ne \varnothing$ is the key point of building an LMSSS with respect to $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$.

4 An Ideal LMSSS Based on Connectivity of Graphs

In this section we firstly define an $m$-tuple $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ of access structures with respect to the problem described in the introduction, i.e., the access structures is defined based on connectivity of graphs. Afterwards, we devise an ideal LMSSS which realizes such an $m$-tuple $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ of access structures.

4.1 Definition of the Access Structures

Let $t$ be a positive integer, $n=\Big ({\begin{array}{l} t \\ 2 \\ \end{array} }\Big )=t(t-1)/2$, and ${\mathcal {P}}=\{1,\ldots ,n\}$ be the set of players. Let $G(V,E)$ be an undirected complete graph with the vertex set $V=\{v_0 ,v_1 ,\ldots ,v_{t-1} \}$ and edge set $E=\left\{ {v_p v_q \,|\,p\ne q,0\le p,q\le t-1} \right\}$. Suppose that $f:E\rightarrow P$ is a bijection which associates each player with an edge, in other words, associates every two vertices with a number. For any subset $A\subseteq P, G(V,E_A )$ is a spanning subgraph of $G(V,E)$ where $E_A =\left\{ {v_p v_q \in E\,|\,f(v_p v_q )\in A} \right\}$. Seeing that every two vertices $v_p$ and $v_q$ use the related secret $s_{f(v_p v_q )}$ to communicate with each other and a set of players can recover $s_{f(v_p v_q )}$ if the edges related to the players in this set can construct a path from $v_p$ to $v_q$, there are all $m=n=t(t-1)/2$ secrets such that for any $p\ne q\hbox { and }0\le p,q\le t-1$, each secret $s_{f(v_p v_q )}$ is associated with an access structure $\Gamma _{f(v_p v_q )}$ on ${\mathcal {P}}$ (naturally, $\mathcal{A}_{f(v_p v_q )} =2^{{\mathcal {P}}}-\Gamma _{f(v_p v_q )} )$. We define such an $m$-tuple $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ of access structures as follow:

$$\begin{aligned} \Gamma _{f(v_p v_q )} \!=\!\left\{ {A\!\subseteq \!P\,|\,v_p \hbox { }\hbox {and}\hbox { }v_q \hbox { }\hbox {are connected in}\hbox { }G(V,E_A )} \right\} , \quad p\ne q\hbox { and }0\le p,q\le t\!-\!1.\nonumber \\ \end{aligned}$$

(1)

Obviously, $\Gamma _{f(v_p v_q )}$ satisfies the monotone ascending property.

Example 1

Let $t=4,n=6$, and $V=\{v_0 ,v_1 ,v_2 ,v_3 \}$. Let ${\mathcal {P}}=\{1,\ldots ,6\}, f(v_0 v_1 )=1, \quad f(v_1 v_2 )=2,f(v_2 v_3 )=3,f(v_0 v_3 )=4,f(v_1 v_3 )=5,f(v_0 v_2 )=6$. See Fig. 1.

It is easy to see that $m=6$ and there are all six secrets, which are shared in such a 6-tuple $\vec {\Gamma }=(\Gamma _1 ,\Gamma _2 ,\Gamma _3 ,\Gamma _4 ,\Gamma _5 ,\Gamma _6 )$ of access structures on ${\mathcal {P}}$ as follows:

$$\begin{aligned} (\Gamma _1 )_{\min }&= \left\{ {\left\{ 1 \right\} ,\left\{ {2,3,4} \right\} ,\left\{ {2,6} \right\} ,\left\{ {4,5} \right\} ,\left\{ {3,5,6} \right\} } \right\} , \quad (\Gamma _2 )_{\min } =\left\{ {\left\{ 2 \right\} ,\left\{ {1,3,4} \right\} ,\left\{ {1,6} \right\} ,\left\{ {3,5} \right\} ,\left\{ {4,5,6} \right\} } \right\} ,\\ (\Gamma _3 )_{\min }&= \left\{ {\left\{ 3 \right\} ,\left\{ {1,2,4} \right\} ,\left\{ {4,6} \right\} ,\left\{ {2,5} \right\} ,\left\{ {1,5,6} \right\} } \right\} , \quad (\Gamma _4 )_{\min } =\left\{ {\left\{ 4 \right\} ,\left\{ {1,2,3} \right\} ,\left\{ {3,6} \right\} ,\left\{ {1,5} \right\} ,\left\{ {2,5,6} \right\} } \right\} ,\\ (\Gamma _5 )_{\min }&= \left\{ {\left\{ 5 \right\} ,\left\{ {1,6,3} \right\} ,\left\{ {1,4} \right\} ,\left\{ {2,3} \right\} ,\left\{ {2,6,4} \right\} } \right\} , \quad (\Gamma _6 )_{\min } =\left\{ {\left\{ 6 \right\} ,\left\{ {1,5,3} \right\} ,\left\{ {1,2} \right\} ,\left\{ {3,4} \right\} ,\left\{ {2,5,4} \right\} } \right\} . \end{aligned}$$

Fig. 1

The access structures for $t=4$

4.2 Construction of the LMSSS

As pointed out in Sect. 3, designing an LMSSS with respect to $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ is equivalent to building an MSP $\mathcal{M}(\mathcal{K},M,\psi )$ by finding linear spaces $V_i ,\,i\in {\mathcal {P}}$ such that for each $j=1,\ldots ,m, \bigcap _{A\in (\Gamma _j )_{\min } } {\sum _{i\in A} {V_i } } -\bigcup _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum _{i\in B} {V_i } } \ne \varnothing$ and letting any vector in this nonempty space be the target vector $\vec {v}_j$. Based on this fact, we build an LMSSS realizing $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ defined by (1) as follows. This scheme consists of three phases:

(1) The setup phase.

Let $S_1 \times \cdot \cdot \cdot \times S_m$ be the set from which the secrets are chosen (that is, $s_j$ to be shared is chosen in $S_j , 1\le j\le m)$. Let $S_1 =\cdots =S_m =\mathcal{K}$ be a finite field with the characteristic $char(\mathcal{K})=2$ (that is, $\mathcal{K}={\mathbb {F}}_2 )$, and $\bar{{V}}=\mathcal{K}^{t-1}$ be the $t-1$ dimensional linear space over $\mathcal{K}$. Here the condition “$char(\mathcal{K})=2$” is needed in the proof of the following Proposition 1. For the lager secret space (that is $char(\mathcal{K})>2)$, we can choose a appropriate positive integer $h$ such that ${\mathbb {F}}_{2^{h}} =\mathcal{K}$ is satisfied and then by using our scheme, per bit sharing the secrets can be realized. Obviously, it is still an ideal LMSSS and parallel processing will succeed.

Suppose that $\vec {e}_0 =(0,\ldots ,0)\in \mathcal{K}^{t-1}$ and $\vec {e}_j =(0,\ldots ,0,_1^j ,0,\ldots 0)\in \mathcal{K}^{t-1}$for $1\le j\le t-1$. We can associate each vertex $v_k$ with a $(t-1)$-dimensional vector $\vec {e}_k$, where $0\le k\le t-1$. For any $1\le i\le n$, suppose that $f^{-1}(i)=v_p v_q$, where $p\ne q\hbox { and }0\le p,q\le t-1$, and then let $\vec {u}_i =\vec {e}_p +\vec {e}_q$ be the $(t-1)$-dimensional vector associated with the player $i$ and $V_i =span\{\vec {u}_i \}$.

Let $\vec {v}_j =\vec {u}_j , 1\le j\le m$ be the $m$ target vectors and $\vec {u}_i$ be the row vector distributed to player $i$ for $1\le i\le n$, where $m=n=t(t-1)/2$. We can build an MSP $\mathcal{M}(\mathcal{K},M,\psi )$ computing $f_{\Gamma _1 } ,\ldots ,f_{\Gamma _m }$, where $M$ is a $n\times (t-1)$ matrix over ${\mathcal {K}}$ with the $i$th row vector $\vec {u}_i$, (that is, $\psi (i)=i$ for $1\le i\le n)$ and $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ is defined according to (1).

Example 2

(following Example 1) Let $\bar{{V}}=\mathcal{K}^{3}$. Select $\vec {e}_0 =(0,0,0),\vec {e}_1 =(1,0,0), \quad \vec {e}_2 =(0,1,0),\vec {e}_3 =(0,0,1)$. Associate vertex $v_0$ with $\vec {e}_0$, vertex $v_1$ with $\vec {e}_1$, vertex $v_2$ with $\vec {e}_2$, vertex $v_3$ with $\vec {e}_3$ (see Fig. 2). We obtain that

$$\begin{aligned} V_1 =span\{(1,0,0)\},V_2&= span\{(1,1,0)\},V_3 =span\{(0,1,1)\},\\ V_4 =span\{(0,0,1)\},V_5&= span\{(1,0,1)\},V_6 =span\{(0,1,0)\}. \end{aligned}$$

(2) The distribution phase.

Fig. 2

Associate each vertex with a vector

The dealer first randomly selects a vector $\vec {r}\in \mathcal{K}^{t-1}$ such that the inner product $(\vec {v}_j ,\vec {r})=s_j , 1\le j\le m$. Then he computes $M\vec {r}^{\tau }$ and transmits $M_i \vec {r}^{\tau }$ to player $i$ ($1\le i\le n)$, where “$\tau$” is the transpose and $M_i$ denotes the matrix $M$ restricted to the row $i$ with $\psi (i)=i$. Thus, each player $i$ ($1\le i\le n)$ gets the share $M_i \vec {r}^{\tau }$.

(3) The reconstruction phase.

For any $A\in \Gamma _j \, (1\le j\le m)$, since $\vec {v}_j \in \sum _{i\in A} {V_i }$, there exists a vector $\vec {w}$ such that $\vec {v}_j =\vec {w}M_A$. So $s_j =(\vec {v}_j ,\hbox { }\vec {r})=\vec {v}_j \cdot \vec {r}^{\tau }=(\vec {w}M_A )\vec {r}^{\tau }=\vec {w}(M_A \vec {r}^{\tau })$, that is, the players in $A$ can reconstruct the secret $s_j$ by computing a linear combination of their shares.

Obviously, the linear multi-secret sharing scheme that we build is ideal. Namely, the lengths of all secrets and shares are equal to one bit.

Example 3

(following Example 2) Suppose that $\mathcal{M}(\mathcal{K},M,\psi )$ is the monotone span program constructed as above and the six target vectors are

$$\begin{aligned} \vec {v}_1&= \vec {u}_1 =(1,0,0),\hbox { }\vec {v}_2 =\vec {u}_2 =(1,1,0),\hbox { }\vec {v}_3 =\vec {u}_3 =(0,1,1),\\ \vec {v}_4&= \vec {u}_4 =(0,0,1),\hbox { }\vec {v}_5 =\vec {u}_5 =(1,0,1),\hbox { }\vec {v}_6 =\vec {u}_6 =(0,1,0).\\ \end{aligned}$$

Note that

$$\begin{aligned} M=\left( {{\begin{array}{l} {\vec {u}_1 } \\ {\vec {u}_2 } \\ {\vec {u}_3 } \\ {\vec {u}_4 } \\ {\vec {u}_5 } \\ {\vec {u}_6 } \\ \end{array} }} \right) , \end{aligned}$$

and $\psi (i)=i$ for $1\le i\le 6$. Then the distribution of six shares and the reconstruction of six secrets are completed as above.

5 Correctness and Security Proof

We now prove that our scheme is a perfect multi-secret sharing scheme. Firstly, we prove the following Proposition.

Proposition 1

Suppose that $\vec {\Gamma }=(\Gamma _1 ,\ldots ,\Gamma _m )$ is defined by (1) and ${\mathcal {K}},\vec {u}_i ,V_i ,1\le i\le n$ are given as above. For any $1\le j\le m$, let $\vec {v}_j =\vec {u}_j$, then it holds that $\vec {v}_j \in \bigcap _{A\in (\Gamma _j )_{\min } } {\sum _{i\in A} {V_i } } -\bigcup _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum _{i\in B} {V_i } }$.

Proof

Firstly, we prove that $\vec {v}_j \in \bigcap _{A\in (\Gamma _j )_{\min } } {\sum _{i\in A} {V_i } }$ for any $1\le j\le m$. For any $A\in (\Gamma _j )_{\min }$, suppose that $f^{-1}(j)=v_p v_q$. According to (1), it implies that there must exist a path $v_{i_0 } v_{i_1 } \ldots v_{i_k }$ from $v_p$ to $v_q$ in $G(V,E_A )$, where $v_{i_0 } =v_p ,v_{i_k } =v_q (0\le i_0 ,\ldots ,i_k \le t-1)$. Namely, $\vec {u}_j =\vec {e}_p +\vec {e}_q =\vec {e}_{i_0 } +\vec {e}_{i_k }$. We assume that $f(v_{i_l } v_{i_{l+1} } )=h_l (0\le l\le k-1)$, where $h_l \in A$ and $\vec {u}_{h_l } =\vec {e}_{i_l } +\vec {e}_{i_{l+1} }$. We obtain that

$$\begin{aligned} \vec {u}_{h_0 } +\vec {u}_{h_1 } +\cdots +\vec {u}_{h_{k-1} } =(\vec {e}_{i_0 } +\vec {e}_{i_1 } )+(\vec {e}_{i_1 } +\vec {e}_{i_2 } )+\cdots +(\vec {e}_{i_{k-1} } +\vec {e}_{i_k } )=\vec {e}_{i_0 } +\vec {e}_{i_k } =\vec {u}_j. \end{aligned}$$

Since $V_i =span\{\vec {u}_i \}(i\in {\mathcal {P}})$, it implies that for any $A\in (\Gamma _j )_{\min }$, there exists a linear combination of the vectors in $\sum _{i\in A} {V_i }$ such that it equals to $\vec {v}_j =\vec {u}_j$, where $1\le j\le m$. Namely, $\vec {v}_j =\vec {u}_j \in \sum _{i\in A} {V_i }$ for every $A\in (\Gamma _j )_{\min }$. Hence, we obtain that $\vec {v}_j \in \bigcap _{A\in (\Gamma _j )_{\min } } {\sum _{i\in A} {V_i } }$ for any $1\le j\le m$.$\square$

Then we prove that $\vec {v}_j \notin \bigcup _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum _{i\in B} {V_i } }$ for any $1\le j\le m$. For every $B\in (\mathcal{A}_j )_{\max }$, suppose that $f^{-1}(j)=v_p v_q$. According to (1), it implies that there does not exist a path from $v_p$ to $v_q$ in $G(V,E_B )$. We assume that there exists a linear combination of the vectors in $\sum _{i\in B} {V_i }$ such that it equals to $\vec {v}_j =\vec {u}_j$. Namely, $\vec {u}_{h_0 } +\vec {u}_{h_1 } +\cdots +\vec {u}_{h_g } =\vec {u}_j =\vec {e}_p +\vec {e}_q$, where $h_l \in B(0\le l\le g)$. Suppose that $f(h_l )=v_{x_l } v_{y_l }$. We obtain that

$$\begin{aligned} \vec {e}_p +\vec {e}_q =(\vec {e}_{x_0 } +\vec {e}_{y_0 } )+\cdots +(\vec {e}_{x_g } +\vec {e}_{y_g } ), \end{aligned}$$

(2)

where $\vec {e}_{x_l } ,\vec {e}_{y_l } \in \left\{ {\vec {e}_0 ,\vec {e}_1 ,\ldots ,\vec {e}_{t-1} } \right\} (0\le l\le g)$. Due to the fact that $\vec {e}_0 ,\vec {e}_1 ,\ldots ,\vec {e}_{t-1}$ are linearly independent and $\mathcal{K}=\mathrm{F}_2$, we obtain that the number of times $\vec {e}_p$ and $\vec {e}_q$ appears on the right side of (2) must be an odd number, but the number of times $\vec {e}_r (1\le r\le t-1\hbox { and }r\ne p,q)$ appears on the right side of (2) must be an even number. Thus, the Eq. (2) actually determines a path from $v_p$ to $v_q$ in $G(V,E_B )$. This is a contradiction. We obtain that for every $B\in (\mathcal{A}_j )_{\max }$, there does not exist a linear combination of the vectors in $\sum _{i\in B} {V_i }$ such that it equals to $\vec {v}_j =\vec {u}_j$, where $1\le j\le m$. Namely, $\vec {v}_j =\vec {u}_j \notin \sum _{i\in B} {V_i }$ for every $B\in (\mathcal{A}_j )_{\max }$. Hence, $\vec {v}_j \notin \bigcup _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum _{i\in B} {V_i } }$ for any $1\le j\le m$.

As a consequence of the above, it holds that

$$\begin{aligned} \vec {v}_j \in \bigcap \nolimits _{A\in (\Gamma _j )_{\min } } {\sum \nolimits _{i\in A} {V_i } } -\bigcup \nolimits _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum \nolimits _{i\in B} {V_i } } \end{aligned}$$

for any $1\le j\le m$.

Theorem 1

The scheme presented in Sect. 4 is a perfect multi-secret sharing scheme.

Proof

From Proposition 1, for $1\le j\le m$, seeing that $\vec {v}_j \in \bigcap _{A\in (\Gamma _j )_{\min } } {\sum _{i\in A} {V_i } }$, it implies that any subset $A\in \Gamma _j$ of players can reconstruct the secret $s_j$ by computing a linear combination of their shares. Hence, it holds that $H(S_j |\,A)=0$. $\square$

At the same time, from Proposition 1, for any $1\le j\le m$, seeing that $\vec {v}_j =\vec {u}_j \notin \bigcup _{B\in (\mathcal{A}_j ){ }_{\max }} {\sum _{i\in B} {V_i } }$, we obtain that there does not exist a linear combination of their shares such that it equals to $s_j$. It implies that any subset $B\notin \Gamma _j$ (namely, $B\in \mathcal{A}_j )$ of players, even knowing some of other secrets (that is, they can obtain some of other secrets by computing a linear combination of their shares), has no more information on $s_j$ than that already conveyed by the known secrets. Hence, it holds that $H(S_j |\,BS_B )=H(S_j |\,S_B )$, where $S_B$ denotes the secrets that $B$ can compute.

Therefore, according to Definition 1, the scheme is a perfect multi-secret sharing scheme.

As a consequence, our scheme is an ideal and perfect linear multi-secret sharing scheme.

Remark 1

In a verifiable secret sharing scheme the validity of the shares can be verified, hence players are not able to cheat. Based on our scheme, we can further construct an ideal verifiable multi-secret sharing scheme by adding the existing verifiability methods where the intractability of discrete logarithm problem is frequently used (see [6, 7, 9, 10]).

6 Conclusions

In this paper we consider an ideal linear multi-secret sharing scheme based on connectivity of graphs. For a set of players ${\mathcal {P}}=\{1,\ldots ,n\}$, every pair of vertices, $p$ and $q$, use the related secret $s_{pq}$ to communicate with each other such that a set of servers (edges) can recover $s_{pq}$ if these edges can provide an alternative comnnection between $p$ and $q$. In particular, we put forward a general and simple method of construction such a scheme based on monotone span programs. The correctness and security of the proposed scheme are proved. This scheme is suitable for secure and efficient communications.