1 Introduction

A (k, n) visual cryptography scheme (VCS), where k ≤ n, for a set of n participants is a method to split a secret image into n shadow images called shares, where each participant receives one share. One can reconstruct the secret image with any k or more than k shares; but, one cannot obtain any information of the secret image from fewer than k shares. The attractiveness of VCS is the stacking-to-see property by which the reconstruction requires neither knowledge of cryptography nor a computer. Any k or more than k participants may photocopy their shares onto transparencies and stack them on an overhead projector to visually decode the secret image through the human visual system.

In some circumstances where the cost of computations may be not affordable, the decoding time should be instantly done in a constant time, or the recognition of the secret shape/pattern is sensitive or meaningful only to the human perception, VCS becomes very appropriate.

The first VCS was proposed by Naor and Shamir [14] and they gave a formal description to (k, n)-VCS. Specifically, each pixel of the secret image is encoded into m subpixels, referred to as pixel expansion, for each of the n shares by designing two collections C 0 and C 1 of n × m Boolean matrices. To share a white pixel, the dealer randomly chooses one of the matrices in C 0, and to share a black pixel, the dealer randomly chooses one of the matrices in C 1. The chosen matrix defines the color of the m subpixels in each of the shares. If any k or more shares are stacked together, our eyes can perceive the secret information due to the darkness difference, referred to as contrast, between black pixels and white pixels in the stacked result, while if fewer than k shares are superimposed it is impossible to perceive the secret information.

Following Naor and Shamir’s work, many related problems of VCS, such as reducing the pixel expansion [14, 16], improving the contrast [3, 4], sharing multiple secrets [15, 24], cheating prevention [10, 12], sharing color image [5, 19], keeping aspect ratio invariant [11, 22], meaningful shares [17, 20], progress recovery [9], region incrementing [23], special access structures [2, 8] and applications [21] were subsequently proposed. Also studies have tried to sacrifice contrast to obtain less pixel expansion [6, 18]. Though VCS has a very rich literature, a very few papers have been published for the construction of VCS for general access structures, which is a specification of all qualified and forbidden sets of participants.

In 1996, Ateniese et al. [2] extended (k, n) threshold access structures to general access structures. They also introduced basis matrices, which save memory requirements, to the model of VCS and presented two techniques to construct basis matrices of VCS for general access structures: cumulative arrays and smaller schemes.

Shyu and Chen [14] applied the skills of integer linear programming (ILP) into constructing basis matrices to acquire the optimal pixel expansion of VCS for threshold access structures. Then they [16] generalized and extended the formulation of ILP to general access structures, where the optimal pixel expansions are obtained. However, the proposed method resorts to an exhaustive search strategy and takes exponential time in the worst case. Therefore, whether there is an efficient construction of VCS with near optimal pixel expansions is still a challenging topic.

Recently, Adhikari [1] proposed a linear algebraic technique to construct VCS for general access structures. He first obtained the initial basis matrices, which are the basis matrices before removing the common columns, by solving some systems of two linear equations. Then he deleted the common columns from the initial basis matrices and obtained the reduced basis matrices with less pixel expansion. This technique is more efficient than ILP [14, 16] since it mainly requires solving some linear systems. Yet the question of finding exact number of common columns in the initial basis matrices was left open. Towards this end, Dutta et al. [7] found a closed form of the exact number of common columns in the initial basis matrices of (n − 1, n)-VCS. However, the above works focused on constructing basis matrices by taking two equations at a time. As they pointed out, constructing basis matrices by taking more equations simultaneously to obtain less pixel expansion is worthy of study. Moreover, it is also a challenging problem that finding the exact number of common columns in the initial basis matrices for other access structures.

In this paper, we deal with the above open issues. We first put forward an efficient construction of VCS for general access structures using linear algebra, where we can take more equations at a time. Then we find out the exact number of common columns in the initial basis matrices of (2, n) threshold access structures. Our main contribution is that the proposed construction, in an efficient way, gets the smallest initial pixel expansion compared to some well-known constructions and achieves the optimal pixel expansions in most cases after deleting the common columns from the initial basis matrices.

The rest of the paper is organized as follows. In Section 2 we give some preliminaries including the model of VCS for general access structures and some previous studies. In Section 3 we provide a characterization of the set of access structures on a set of participants where we can exploit the linear algebraic technique to take more equations simultaneously. In Section 4 we give an efficient construction of VCS for general access structures based on the characterization. What’s more, we find the exact number of common columns in the initial basis matrices to be n − 2 for (2, n) threshold access structures. In Section 5, we discuss some interesting examples, which will lead to future research directions. Lastly we conclude the paper in Section 6.

2 Preliminaries

2.1 The model

The model that we describe here is based on basis matrices and similar to the model as described in Ateniese et al. [2].

Let P = {1, 2, …, n} be a set of participants and 2P denote the set of all subsets of P. Let Γ Q u a l ⊆ 2P and Γ F o r b ⊆ 2P, where Γ Q u a l ∩Γ F o r b = ∅. Members of Γ Q u a l are referred to as qualified sets and members of Γ F o r b are referred to as forbidden sets. The pair (Γ Q u a l , Γ F o r b ) is called an access structure on P. A participant p ∈ P is an essential participant if there exists a set X ⊆ P such that X∪{p}∈Γ Q u a l but X∉Γ Q u a l . In fact, a non-essential participant does not need to participate “actively” in the reconstruction of the image, since the information he has is not needed during recovering the secret image.

In this paper, we mostly deal with strong access structures, which are defined as follows.

Definition 1

[2] The access structure (Γ Q u a l , Γ F o r b ) on P = {1,2,…, n} is said to be strong if the following conditions are satisfied:

  1. 1.

    Γ Q u a l is monotone increasing. Formally, for each Q ∈ Γ Q u a l and Q ⊆ Q ′⊆P, we have Q ′∈Γ Q u a l .

  2. 2.

    Γ F o r b is monotone decreasing. Formally, for each F ∈ Γ F o r b and F ′⊆F ⊆ P, we have F ′∈Γ F o r b .

  3. 3.

    Γ Q u a l ∪Γ F o r b =2P.

Let Γ0={Q ∈ Γ Q u a l :Q ′ ∉ Γ Q u a l f o r a l l Q ′ ⊂ Q} be the collection of all minimal qualified sets and Z M ={F ∈ Γ F o r b :F∪{i}∈Γ Q u a l f o r a l l i ∈ P∖F} be the collection of all maximal forbidden sets. Γ0 is termed a basis, which completely determines its corresponding strong access structure by Γ Q u a l ={Q ′⊆P:Q ⊆ Q ′ f o r s o m e Q ∈ Γ0}.

Let M be an n × m Boolean matrix and X ⊆ P. Then M[X] denotes the |X| × m submatrix obtained from M by considering its restriction to rows corresponding to the elements in X. M X denotes the Boolean “OR” operation to the rows of M[X]. ω(M X ) denotes the Hamming weight of the row vector M X , which is the number of 1’s in the vector M X . For a 1 × n Boolean row vector v = {v 1, v 2, …, v n }, let R v ={j|v j =1, j = 1,2,…, n}. Given two Boolean row vectors v 1 and v 2, define \(\Re _{\textbf {v}_{1}}\oplus \Re _{\textbf {v}_{2}}=\Re _{\textbf {v}_{1}\oplus \textbf {v}_{2}}\). Denote \({\Gamma }_{0}^{odd}\) as the “ ⊕”ed result of any odd number of elements of Γ0 and \({\Gamma }_{0}^{even}\) as the “ ⊕”ed result of any even number of elements of Γ0.

Definition 2

[2] Let (Γ Q u a l , Γ F o r b ) be an access structure on a set of n participants. Two n × m basis matrices S 0 and S 1, which generate the two collections of n × m Boolean matrices C 0 and C 1 by permuting the columns of the corresponding basis matrix (S 0 for C 0, and S 1 for C 1) in all possible ways, constitute a (Γ Q u a l , Γ F o r b , m)-VCS if the following conditions are satisfied:

  1. 1.

    (Contrast) If X = {i 1, i 2, …, i p }∈Γ Q u a l , \(\omega ({S^{0}_{X}})<\omega ({S^{1}_{X}})\).

  2. 2.

    (Security) If X = {i 1, i 2, …, i p }∈Γ F o r b , the p × m matrices obtained by restricting S 0 and S 1 to rows i 1, i 2, …, i p are identical up to a column permutation.

Then, for constructing VCS by cumulative arrays, the following lemma is presented by Ateniese et al. [2].

Lemma 1

[2] For a strong access structure (Γ Qual ,Γ Forb ) with Z M , there exists a VCS with \(m=2^{|Z_{M}|-1}\).

Before giving the construction of VCS from smaller schemes, the following lemma is described without a proof.

Lemma 2

[2] Let \(({\Gamma }^{\prime }_{Qual},{\Gamma }^{\prime }_{Forb})\) and \(({\Gamma }^{\prime \prime }_{Qual},{\Gamma }^{\prime \prime }_{Forb})\) be two access structures on a set P of n participants. If a participant i∈P is non-essential for \(({\Gamma }^{\prime }_{Qual},{\Gamma }^{\prime }_{Forb})\) , we assume that \(i\in {\Gamma }^{\prime }_{Forb}\) and that i receives a share completely “white”. Analogously for \(({\Gamma }^{\prime \prime }_{Qual},{\Gamma }^{\prime \prime }_{Forb})\) . Suppose there exist a \(({\Gamma }^{\prime }_{Qual},{\Gamma }^{\prime }_{Forb},m^{\prime })\) -VCS and a \(({\Gamma }^{\prime \prime }_{Qual},{\Gamma }^{\prime \prime }_{Forb},m^{\prime \prime })\) -VCS constructed using basis matrices. Then there exists a \(({\Gamma }^{\prime }_{Qual}\cup {\Gamma }^{\prime \prime }_{Qual},{\Gamma }^{\prime }_{Forb}\cap {\Gamma }^{\prime \prime }_{Forb},m^{\prime }+m^{\prime \prime })\) -VCS. If the original access structures are both strong, then so is the resulted access structure.

Based on Lemma 2, the following lemma is presented immediately.

Lemma 3

[2] For a strong access structur (Γ Qual ,Γ Forb ) with Γ 0 , there exists a VCS with \(m={\sum }_{X\in {\Gamma }_{0}}2^{|X|-1}\).

Furthermore, we present the following lemma, illustrating why we can delete the common columns in the initial basis matrices. In other words, if there exist two initial basis matrices having common columns, then we can delete the common columns and obtain two reduced basis matrices with less pixel expansion, where the conditions of Definition 2 are still hold.

Lemma 4

[2] Let (Γ Qual , Γ Forb ) be an access structure. Let S 0 and S 1 be the basis matrices in a (Γ Qual , Γ Forb , m)-VCS and let D be any n × p Boolean matrix. The two matrices S ′0 =S 0 ∘D and S ′1 =S 1 ∘D, where ∘ denotes the operator “concatenation” of two matrices, comprise a (Γ Qual ,Γ Forb ,m+p)-VCS.

2.2 VCS and linear equations

Adhikari [1] introduced a construction procedure for the two n × m basis matrices S 0 and S 1 of (Γ Q u a l , Γ F o r b , m)-VCS using linear algebraic technique. He started with the following two associated systems of linear equations over the binary field,

$$\begin{array}{@{}rcl@{}} A\textbf{x} &=& \textbf{0} \end{array} $$
(1)
$$\begin{array}{@{}rcl@{}} A\textbf{x} &=& \textbf{1} \end{array} $$
(2)

where, A is an r × n known Boolean matrix of rank r, 0 < r < n; x is an n × 1 vector of unknowns; 0 and 1 are r × 1 vectors of 0’s and 1’s respectively. Since A is full of row rank, both the systems (1) and (2) are consistent. Let S 0 (resp. S 1) be an n × 2n − r Boolean matrix whose columns are all possible solutions of the system (1) (resp. (2)). Then, to show S 0 and S 1 can form the basis matrices of a (Γ Q u a l , Γ F o r b , 2n − r)-VCS, he proved the following lemma which plays an important role in our new insight into the linear algebraic technique to construct visual cryptography schemes.

Lemma 5

[1] Let X = {i 1 , i 2 , …, i p } ⊆ P = {1, 2, …, n}. Then X ∈ Γ Qual (resp. X ∈ Γ Forb ) if and only if the system of equations

$$ \left( \begin{array}{l} A \\ B_{X} \end{array} \right)\textbf{x}=\left( \begin{array}{l} \textbf{1} \\ \textbf{0} \end{array} \right) $$
(3)

is inconsistent (resp. consistent), where B X is a column permutation of the p × n Boolean matrix (I p | 0 p × (n − p) ) with unit vectors of the identity matrix Ix p , which is of order p, occupying columns indexed by i 1 , i 2 , …, i p in B X .

Then based on the above knowledge, Adhikari [1] proposed a construction of VCS for any strong access structure by taking two equations simultaneously, where the pixel expansion is less than that of Lemma 3. The following lemma presents the result.

Lemma 6

[1] For any given strong access structure (Γ Qual , Γ Forb ) on a set P = {1, 2, …, n} of n participants with Γ 0 = {Q 1 , Q 2 , …, Q t } where Q i ⊆ P, ∀i = 1, 2, …, t and for any permutation σ ∈ SG t , the symmetric group of degree t, there exists a strong (Γ Qual , Γ Forb )-VCS with m σ , where m σ is given as follows:

$$m_{\sigma}=\left\{ \begin{array}{ll} {\sum}^{l}_{i=1}2^{|Q_{\sigma(2i-1)}\cup Q_{\sigma(2i)}|-2} & if t=2l,l\geq 1\\ {\sum}^{l}_{i=1}2^{|Q_{\sigma(2i-1)}\cup Q_{\sigma(2i)}|-2}+2^{|Q_{\sigma(2l+1)}|-1} & if t=2l+1,l\geq 0. \end{array} \right. $$

3 New insight into linear algebraic technique to construct VCS

In this section, we give some new insight into the linear algebraic technique to construct VCS, where we can take more equations simultaneously to reduce the pixel expansion. First, we also start with the following two systems of linear equations over the binary field,

$$\begin{array}{@{}rcl@{}} A\textbf{x} &=& \textbf{0} \end{array} $$
(4)
$$\begin{array}{@{}rcl@{}} A\textbf{x} &=& \textbf{1} \end{array} $$
(5)

where, A is a t × n known Boolean matrix of rank r, 0 < r ≤ t < n; x is an n × 1 vector of unknowns; 0 and 1 are t × 1 vectors of 0’s and 1’s respectively; both the systems (4) and (5) are consistent. The difference from Adhikari’s systems [1] is the coefficient matrix A, which does not have to be of full row rank.

Also, let S 0 (resp. S 1) be an n × 2n − r Boolean matrix whose columns are all possible solutions of the system (4) (resp. (5)). Then, to prove S 0 and S 1 can form the basis matrices of a (Γ Q u a l , Γ F o r b , 2n − r)-VCS, the following lemma is immediate since the proof of Lemma 5 also works for this lemma.

Lemma 7

Let X = {i 1 , i 2 , …, i p } ⊆ P = {1, 2, …, n}. Build a system of equations as follows:

$$ \left( \begin{array}{l} A \\ B^{X} \end{array} \right)\textit{\textbf{x}}=\left( \begin{array}{l} \textit{\textbf{1}} \\ \textit{\textbf{0}} \end{array} \right) $$
(6)

where B X is a column permutation of the p×n Boolean matrix (I p | 0 p × (n − p) ) with unit vectors of the identity matrix I p , which is of order p, occupying columns indexed by i 1 , i 2 , …, i p in B X . Then, for an access structure (Γ Qual ,Γ Forb ), S 0 and S 1 form the basis matrices of a (Γ Qual , Γ Forb , m = 2 n − r )-OVCS if the following conditions are satisfied:

  1. 1.

    For X ∈ Γ Qual , the system (6) is inconsistent;

  2. 2.

    For X ∈ Γ Forb , the system (6) is consistent.

Next we are going to explore the conditions for consistency or inconsistency of the system (6). Let rows of A 1 (resp. A 2) represent all possible sum of odd (resp. even) number of rows in A. Then we have the following lemma.

Lemma 8

For an access structure (Γ Qual , Γ Forb ), S 0 and S 1 form the basis matrices of a (Γ Qual , Γ Forb , m = 2 n − r )-OVCS if the following conditions are satisfied:

  1. 1.

    For X ∈ Γ Qual , any row vector of A 1 belongs to the row space of B X.

  2. 2.

    For X ∈ Γ Forb , A and B X are independent, or, any row vector of A 2 belongs to the row space of B X.

Proof

In light of the system (6), there are two possibilities: the coefficient matrix A and B X are either linearly independent or linearly dependent.

If they are independent, since the system (5) is consistent and B X x = 0 is consistent (B X is of full row rank), the system (6) is consistent.

If they are linearly dependent, then there exists a vector u = (u 1, u 2)≠0, where u 1 and u 2 are 1 × t and 1 × p vectors respectively, such that \(\textbf {u}\left (\begin {array}{l} A \\ B^{X} \end {array} \right )\) = 0 ⇔ u 1 A + u 2 B X = 0. Note that u 1 is nonzero, otherwise this will imply linear dependence of the rows of B X. Now u 1 A + u 2 B X = 0 ⇔ u 1 A ∈ the row space of B X. Also note that if u 1 has an odd (resp. even) number of 1’s then u 1 A will be a row of A 1 (resp. A 2). Then we have that any row of A 1 or A 2 belongs to the row space of B X. On the right of the system (6), \(\textbf {u}\left (\begin {array}{l} \textbf {1} \\ \textbf {0} \end {array} \right )=\textbf {u}_{1}\textbf {1}\). If u 1 has an odd (resp. even) number of 1’s then the system (6) is inconsistent (resp. consistent).

Based on the above discussions and Lemma 7, this lemma is proved. □

Until now, we have seen that given a suitable binary matrix A and a suitable access structure (Γ Q u a l , Γ F o r b ), which satisfy the conditions of Lemma 8, we can construct a VCS by solving the two systems (4) and (5). In other words, we have concluded the sufficient conditions for constructing VCS by using linear equations. Then, we are now in a position to give a concrete structure of the coefficient matrix A. Towards this end, we prove the following lemma.

Lemma 9

For an access structure (Γ Qual ,Γ Forb ) with Γ 0 = {Q 1 ,Q 2 ,…,Q t }, let A = (v 1, v 2 ,…, v t )T of rank r and \(\Re _{\textbf {v}_{i}}=Q_{i}\) , i = 1, 2, …, t. S 0 and S 1 form the basis matrices of a (Γ Qual , Γ Forb , m = 2 n − r )-OVCS if the following conditions are satisfied:

  1. 1.

    For any row v of A 1 , R v ∈ Γ Qual ;

  2. 2.

    For any row v of A 2 , R v =∅ or R v ⫅̸ Q ∈ Γ 0.

Proof

For X ∈ Γ Q u a l , because R v ∈Γ Q u a l for any row v of A 1, v obviously belongs to the row space of B X.

For X ∈ Γ F o r b , there are three cases to be considered:

Case 1

For any row v of A 1, R v ∈Γ Q u a l ; for any row v of A 2, R v = ∅.

In this case, any row vector of A 2 belongs to the row space of B X immediately.

Case 2

For any row v of A 1, R v ∈Γ Q u a l ; for any row v of A 2, R v ⊄Q ∈ Γ0 and R v ∈Γ F o r b .

In this case, any row vector of A 2 also belongs to the row space of B X immediately.

Case 3

For any row v of A 1, R v ∈Γ Q u a l ; for any row v of A 2, R v ∉Γ0 and R v ∈Γ Q u a l .

In this case, no row vector of A 1 and A 2 belongs to the row space of B X, namely, A and B X are independent. □

It should be noted that the sum operation “ + ” over the binary field is actually the Boolean XOR operation “ ⊕”. Therefore, the sum of a number of row vectors, say v 1, ⋯ , v i , of the coefficient matrix A equals to v 1⊕⋯⊕v i . Since \(Q_{i}=\Re _{\textbf {v}_{i}}\), we have \(\Re _{\textbf {v}_{1}\oplus \cdots \oplus \textbf {v}_{i}}=Q_{1}\oplus \cdots \oplus Q_{i}\). So, for clarity, we restate Lemma 9 as follows, and hence omit its proof.

Theorem 1

For an access structure (Γ Qual ,Γ Forb ) with Γ 0 ={Q 1 ,Q 2 ,…,Q t }, if Γ 0 satisfies the following two conditions:

  1. 1.

    The “ ⊕”ed result of any odd number of elements of Γ 0 is an element of Γ Qual . Formally, \({\Gamma }_{0}^{odd}\in {\Gamma }_{Qual}\).

  2. 2.

    The “ ⊕”ed result of any even number of elements of Γ 0 is an empty set, or not a subset of any element of Γ 0 . Formally, \({\Gamma }_{0}^{even}=\emptyset \) or \({\Gamma }_{0}^{even}\not \subseteq Q\in {\Gamma }_{0}\).

Then the basis matrices S 0 and S 1 of a (Γ Qual ,Γ Forb ,m=2 n−r)-OVCS are composed of all possible solutions of the systems (4) and (5) respectively, where A=(v 1, v 2,…, v t ) T of rank r and \(\Re _{\textbf {v}_{i}}=Q_{i}\) , i = 1, 2, …, t.

Remark 1

Theorem 1 helps us to prove Lemma 3 on the existence of a VCS for any given strong access structure with the basis Γ0, since we can construct a VCS by taking one equation at a time regarding each element, satisfying the conditions of Theorem 1 obviously, of Γ0. Analogously for Lemma 6 since we can construct a VCS by taking two equation at a time regarding any two elements, satisfying the conditions of Theorem 1 obviously, of Γ0. Therefore, our Theorem 1 is a generalization of Lemma 3 and Lemma 6.

Let us try to illustrate the above theory through the following example.

Example 1

Consider the following strong access structure (Γ Q u a l , Γ F o r b ) on a set of four participants having Γ0 = {{1, 2}, {1, 3}, {1, 4}}. Obviously, this access structure satisfies the conditions of Theorem 1. Then we can construct a (Γ Q u a l , Γ F o r b )-VCS with basis matrices S 0 and S 1, which are obtained by solving the following two systems of three linear equations over the binary field:

$$ \left\{ \begin{array}{l} x_{1}+x_{2}=0\\ x_{1}+x_{3}=0\\ x_{1}+x_{4}=0 \end{array} \right. $$
(7)

and

$$ \left\{ \begin{array}{l} x_{1}+x_{2}=1\\ x_{1}+x_{3}=1\\ x_{1}+x_{4}=1 \end{array} \right. $$
(8)

Let S 0 and S 1 be the Boolean matrices whose columns are just all possible solutions of (7) and (8), respectively. Thus, \(S^{0}=\left [ \begin {array}{ll} 0 & 1\\ 0 & 1\\ 0 & 1\\ 0 & 1 \end {array} \right ]\) and \(S^{1}=\left [ \begin {array}{ll} 0 & 1\\ 1 & 0\\ 1 & 0\\ 1 & 0 \end {array} \right ]\). Clearly, S 0 and S 1 satisfy the properties of basis matrices for the strong access structure (Γ Q u a l , Γ F o r b ) determined by Γ0. It gives pixel expansion 2, which is less than pixel expansion 4 obtained by taking two equations simultaneously as proposed by Theorem 4.2 of [1] (described in Appendix A).

4 On construction of VCS for general access structures

In this section, we give a construction of VCS for any strong access structure to obtain less pixel expansion. To begin with, the following definition is presented.

Definition 3

A strong access structure (Γ Q u a l , Γ F o r b ) is called feasible if it satisfies the conditions of Theorem 1. The Γ0 obtained from the feasible (Γ Q u a l , Γ F o r b ) is called a feasible basis.

Obviously, for any given strong access structure, the conditions of Theorem 1 are not always satisfied. A comprehensive idea to construct a VCS for any given strong access structure is to group the access structure into some feasible access structures, and then to realize a VCS by Lemma 2. We are now in a position to describe such a grouping algorithm.

Then, we need to give a sorting method for a basis Γ0. For a 1 × n Boolean row vector v i , define \(Dec_{\textbf {v}_{i}}\) as the decimal number corresponding to v i , then a sorting method for a basis Γ0 is defined as follows.

Definition 4

A basis Γ0 is sorted such that for any two different elements \(Q_{i},Q_{i^{\prime }}\in {\Gamma }_{0}\), if i < i ′, then \(Dec_{\textbf {v}_{i}}<Dec_{\textbf {v}_{i^{\prime }}}\), where \(\Re _{\textbf {v}_{i}}=Q_{i}\) and \(\Re _{\textbf {v}_{i^{\prime }}}=Q_{i^{\prime }}\).

Then, we describe a grouping algorithm for any strong access structure in Algorithm 1. Note that Steps 2–8 guarantee that each of \({{\Gamma }^{1}_{0}},{{\Gamma }^{2}_{0}},\ldots ,{{\Gamma }^{d}_{0}}\) is feasible since the conditions of Theorem 1 are satisfied.

figure e

For any given strong access structure, we can apply Algorithm 1 to group the access structure and construct a VCS for each feasible access structure based on Theorem 1, and then realize a final VCS by Lemma 2. Let us try to illustrate the proposed algorithm through the following example.

Example 2

Consider the following strong access structure (Γ Q u a l , Γ F o r b ) on a set of four participants having Γ0={{1,2},{1,3},{2,3},{1,4}}. Obviously, this access structure is not feasible. By Algorithm 1, we can obtain the following two feasible bases \({{\Gamma }^{1}_{0}}=\{\{1,2\},\{1,3\},\{1,4\}\}\) and \({{\Gamma }^{2}_{0}}=\{\{2,3\}\}\). For \({{\Gamma }^{1}_{0}}\), consider the following two systems of three linear equations over the binary field:

$$ \left\{ \begin{array}{l} x_{1}+x_{2}=0\\ x_{1}+x_{3}=0\\ x_{1}+x_{4}=0 \end{array} \right. $$
(9)

and

$$ \left\{ \begin{array}{l} x_{1}+x_{2}=1\\ x_{1}+x_{3}=1\\ x_{1}+x_{4}=1 \end{array} \right. $$
(10)

Let \({S^{0}_{1}}\) and \({S^{1}_{1}}\) be the Boolean matrices whose columns are just all possible solutions of the above two systems (9) and (10), respectively. Thus, \({S^{0}_{1}}=\left [ \begin {array}{ll} 0 & 1\\ 0 & 1\\ 0 & 1\\ 0 & 1 \end {array} \right ]\) and \({S^{1}_{1}}=\left [ \begin {array}{ll} 0 & 1\\ 1 & 0\\ 1 & 0\\ 1 & 0 \end {array} \right ]\).

For \({{\Gamma }^{2}_{0}}\), let us consider the two following systems of one linear equation over the binary field:

$$ \begin{array}{l} x_{2}+x_{3}=0 \end{array} $$
(11)

and

$$ \begin{array}{l} x_{2}+x_{3}=1 \end{array} $$
(12)

Let \({S^{0}_{2}}\) and \({S^{1}_{2}}\) be the Boolean matrices whose columns are just all possible solutions of the above two linear systems (11) and (12), respectively. Thus, \({S^{0}_{2}}=\left [ \begin {array}{ll} 0 & 0\\ 0 & 1\\ 0 & 1\\ 0 & 0 \end {array} \right ]\) and \({S^{1}_{2}}=\left [ \begin {array}{ll} 0 & 0\\ 0 & 1\\ 1 & 0\\ 0 & 0 \end {array} \right ]\). Note that the first and fourth participants are non-essential for the strong access structure determined by \({{\Gamma }^{2}_{0}}\), so we assign both of them the values (00) for the two Boolean matrices.

Finally, by Lemma 2 we construct a (Γ Q u a l , Γ F o r b )-VCS on a set of four participants having Γ0 = {{1, 2}, {1, 3}, {2, 3}, {1, 4}}, where the basis matrices \(S^{0}=\left [ \begin {array}{llll} 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 0 \end {array} \right ]\) and \(S^{1}=\left [ \begin {array}{llll} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 \end {array} \right ]\).

Remark 2

Based on Theorem 1, Algorithm 1 groups any given strong access structure so that we can take more than two equations simultaneously to obtain the basis matrices. In Example 2, we obtain the pixel expansion 4, which is less than the pixel expansion 5 obtained by taking \({{\Gamma }^{1}_{0}}=\{\{1,2\},\{1,3\}\}\) and \({{\Gamma }^{2}_{0}}=\{\{2,3\},\{1,4\}\}\) according to Lemma 6 (described in Appendix B). Moreover, in Lemma 6, the role of σ is very important for the reduction of pixel expansion. Different σ may give rise to different pixel expansion. For example, if we take \({{\Gamma }^{1}_{0}}=\{\{1,2\},\{2,3\}\}\) and \({{\Gamma }^{2}_{0}}=\{\{1,3\},\{1,4\}\}\) (described in Appendix C), then the pixel expansion will be 4, which is the same as ours. Therefore, our construction is more efficient than Lemma 6.

4.1 Finding common columns of (2, n)-VCS

Though there are many dedicated nice constructions available for the (2, n)-VCS which even achieve the optimal pixel expansion, in this subsection we are going to provide an efficient construction of (2, n)-VCS, which comes as a direct consequence of Algorithm 1, by finding the exact number of common columns in the initial basis matrices.

figure f

Let us apply Algorithm 1 to (2, n) threshold access structure, then Algorithm 1 is reduced to a simple grouping algorithm for (2, n) threshold access structure, which is illustrated in Algorithm 2. Note that, for any basis \({{\Gamma }^{l}_{0}}\) of Algorithm 2, l = 1,2,…, n − 1, there are a total of n − l elements and they have a common participant l. The “ ⊕”ed result of any odd number of elements of \({{\Gamma }^{l}_{0}}\) consists a common participant l and an odd number of participants of {l + 1, l + 2, …, n}, so the first condition of Theorem 1 is met. The “ ⊕”ed result of any even number of elements of \({{\Gamma }^{l}_{0}}\) is an even number of participants of {l + 1, l + 2,…, n}, so the second condition of Theorem 1 is met. Then, we have the following lemma.

Lemma 10

For (2, n)-VCS on a set P={1,2,…,n} of n participants with Γ 0 ={X⊆P:|X|=2}, there exists a strong (2, n)-VCS with m ini =2(n−1).

Proof

By Algorithm 2, we can group (2, n) threshold access structures into n − 1 feasible bases \({{\Gamma }^{1}_{0}},{{\Gamma }^{2}_{0}},\ldots ,{\Gamma }^{n-1}_{0}\). The number of elements of \({{\Gamma }^{l}_{0}}\) is n − l, l = 1,2,…, n − 1. For any \({{\Gamma }^{l}_{0}}\), its set of participants is {l, l + 1,…, n}, and then there exists a VCS on it with m = 2n − l + 1−(n − l)=2 by Theorem 1. Since there are n − 1 feasible bases, there exists a strong (2, n)-VCS with m i n i =2(n − 1) by Lemma 2. □

In Lemma 10, m i n i denotes the initial pixel expansion obtained without deleting the common columns in the initial basis matrices of (2, n)-VCS. Hence, we need to find the exact number of common columns and obtain the reduced basis matrices with less pixel expansion. We are now going to determine the exact number of common columns occurring in the initial basis matrices for different feasible bases and find the exact value of the reduced pixel expansion of the scheme. Towards finding the results, let us explore the structure of initial basis matrices of the (2, n)-VCS constructed by our linear algebraic method.

For any feasible basis \({{\Gamma }^{l}_{0}}\) output by Algorithm 2, l = 1, 2, …, n − 1, let us consider the following two systems of n − l linear equations over the binary field:

$$ \left\{ \begin{array}{l} x_{l}+x_{l+1}=0\\ x_{l}+x_{l+2}=0\\ {\vdots} \\ x_{l}+x_{n-1}=0\\ x_{l}+x_{n}=0\\ \end{array} \right. $$
(13)

and

$$ \left\{ \begin{array}{l} x_{l}+x_{l+1}=1\\ x_{l}+x_{l+2}=1\\ {\vdots} \\ x_{l}+x_{n-1}=1\\ x_{l}+x_{n}=1\\ \end{array} \right. $$
(14)

Let \({S^{0}_{l}}\) and \({S^{1}_{l}}\) be the Boolean matrices whose columns are just all possible solutions of the above two systems (13) and (14) respectively. Thus,

$${S^{0}_{l}}=\left[ \begin{array}{cc} 0 & 0\\ \vdots\\ 0 & 0\\ 0 & 1\\ 0 & 1\\ \vdots\\ 0 & 1\\ \end{array} \right] \begin{array}{c} x_{1} \\ \vdots\\ x_{l-1} \\ x_{l} \\ x_{l+1} \\ \vdots\\ x_{n} \\ \end{array} \text{ and } {S^{1}_{l}}=\left[ \begin{array}{cc} 0 & 0\\ \vdots\\ 0 & 0\\ 0 & 1\\ 1 & 0\\ \vdots\\ 1 & 0\\ \end{array} \right] \begin{array}{c} x_{1} \\ \vdots\\ x_{l-1} \\ x_{l} \\ x_{l+1} \\ \vdots\\ x_{n} \\ \end{array}. $$

Note that the participants {1, 2, …, l − 1} is non-essential for the strong access structure determined by \({{\Gamma }^{l}_{0}}\), so we assign all of them the values (00).

Finally, by Lemma 2 we construct (2, n)-VCS with the initial basis matrices \(S^{0}={S^{0}_{1}}\circ {S^{0}_{2}}\circ \cdots \circ S^{0}_{n-1}\) and \(S^{1}={S^{1}_{1}}\circ {S^{1}_{2}}\circ \cdots \circ S^{1}_{n-1}\). Obviously, there exists one common column \(\begin {array}{ccccccc} (0 & {\cdots } & 0 & 0 & 1 & {\cdots } & 1)^{T}\\ x_{1} & {\cdots } & x_{1-1} & x_{1} & x_{1+1} & {\cdots } & x_{n}\\ \end {array}\) in the two matrices \({S^{1}_{l}}\) and \(S^{0}_{l+1}\). As a result, there exist n − 2 common columns in the initial basis matrices S 0 and S 1.

So, based on the above discussions and Lemma 10, the following theorem is given immediately to obtain the reduced pixel expansion m r e d .

Theorem 2

For (2, n)-VCS on a set P = {1, 2, …, n} of n participants with Γ 0 = {X ⊆ P : |X| = 2}, there exists a strong (2, n)-VCS with m red =n.

4.2 Comparison of pixel expansion between our construction and some well-known constructions

We deal with any strong access structures by taking more equations at a time. In [1] the author pointed out [Remark 4, Sect. 3] that one may take more than two equations at a time to reduce pixel expansion. In this subsection we will show that our construction, where more equations are taken at a time, can get the smallest initial pixel expansion compared to some well-known constructions. At the same time, by using the technique of deleting the common columns from the initial basis matrices, it can also achieve the optimal pixel expansions in most cases according to our experimental results.

Tables 1 and 2 summarize the comparisons of pixel expansion, including initial pixel expansion and reduced pixel expansion, between our construction and some well-known constructions for different access structures with up to four participants. In Table 1, m i n i stands for the initial pixel expansion of our construction, \(m^{A}_{ini}\) denotes the initial pixel expansion obtained by taking two equations simultaneously of [1], \(m^{CA}_{ini}\) denotes the initial pixel expansion obtained by cumulative arrays of [2], \(m^{SS}_{ini}\) denotes the initial pixel expansion obtained by smaller schemes of [2]. In Table 2, m r e d stands for the reduced pixel expansion of our construction, \(m^{A}_{red}\) denotes the reduced pixel expansion obtained by taking two equations simultaneously of [1], \(m^{CA}_{red}\) denotes the reduced pixel expansion by cumulative arrays of [2], \(m^{SS}_{red}\) denotes the reduced pixel expansion by smaller schemes of [2], m ILP denotes the optimal pixel expansion by ILP of [14,16]. Table 3 lists the reduced pixel expansions of our (k, n)-VCS for 2 ≤ k ≤ n ≤ 8, where the optimal pixel expansions by ILP of [14,16] are given in parentheses.

Table 1 Comparison of initial pixel expansion between our construction and some well-known constructions for different access structures having four participants at most
Full size table
Table 2 Comparison of reduced pixel expansion between our construction and some well-known constructions for different access structures having four participants at most
Full size table
Table 3 Reduced pixel expansions of our (k, n)-VCS
Full size table

From Table 1, it is easy to see that our construction gets the smallest initial pixel expansion compared to some well-known constructions. From Tables 2 and 3, we conclude that the proposed construction achieves the optimal pixel expansions in most cases after deleting the common columns from the initial basis matrices.

5 Open problems

In Table 2, our proposed construction for four access structures (Γ0 = {{1, 2}, {1, 3}, {2, 3}, {1, 4}}, Γ0 = {{1, 2}, {1, 3}, {1, 4}, {2, 3, 4}}, Γ0 = {{1, 2}, {1, 3}, {2, 4}}, Γ0 = {{1, 2}, {1, 3, 4}, {2, 3, 4}}) does not achieve the optimal pixel expansion. In this section, based on Theorem 1 we are going to present constructions case by case and finally achieve the optimal pixel expansions for the above four access structures.

Example 3

Let us start with the strong access structure (Γ Q u a l , Γ F o r b ) with Γ0 = {{1, 2}, {1, 3}, {2, 3}, {1, 4}}. Apply Algorithm 1 to group the collection Γ0 into two collections, namely \({{\Gamma }^{1}_{0}}=\{\{1,2\},\{1,3\},\{1,4\}\}\) and \({{\Gamma }^{2}_{0}}=\{\{2,3\}\}\). After this grouping operation, we construct the initial basis matrices for \({{\Gamma }^{1}_{0}}\) just like Example 2, and hence \({S^{0}_{1}}=\left [ \begin {array}{ll} 0 & 1\\ 0 & 1\\ 0 & 1\\ 0 & 1 \end {array} \right ]\) and \({S^{1}_{1}}=\left [ \begin {array}{ll} 0 & 1\\ 1 & 0\\ 1 & 0\\ 1 & 0 \end {array} \right ]\). For \({{\Gamma }^{2}_{0}}\), the first and fourth participants are non-essential. Different from Example 2, we assign the first participant the values (11) and the fourth participant the values (00). Thus, \({S^{0}_{2}}=\left [ \begin {array}{ll} 1 & 1\\ 0 & 1\\ 0 & 1\\ 0 & 0 \end {array} \right ]\) and \({S^{1}_{2}}=\left [ \begin {array}{ll} 1 & 1\\ 0 & 1\\ 1 & 0\\ 0 & 0 \end {array} \right ]\). Finally, by concatenating the initial basis matrices respectively, we construct a (Γ Q u a l , Γ F o r b )-VCS with Γ0={{1,2},{1,3},{2,3},{1,4}}, where the basis matrices are \(S^{0}=\left [ \begin {array}{llll} 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 0 \end {array} \right ]\) and \(S^{1}=\left [ \begin {array}{llll} 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 \end {array} \right ]\). By deleting the common column (1000)T from the initial basis matrices S 0 and S 1, we obtain the optimal pixel expansion 3.

Example 4

For the strong access structure (Γ Q u a l , Γ F o r b ) with Γ0 = {{1, 2}, {1, 3}, {1, 4}, {2, 3, 4}}, apply Algorithm 1 to group the collection Γ0 into two collections, namely \({{\Gamma }^{1}_{0}}=\{\{1,2\},\{1,3\},\{1,4\}\}\) and \({{\Gamma }^{2}_{0}}=\{\{2,3,4\}\}\). We can construct the initial basis matrices for \({{\Gamma }^{1}_{0}}\) like Example 2, and hence \({S^{0}_{1}}=\left [ \begin {array}{cc} 0 & 1\\ 0 & 1\\ 0 & 1\\ 0 & 1 \end {array} \right ]\) and \({S^{1}_{1}}=\left [ \begin {array}{cc} 0 & 1\\ 1 & 0\\ 1 & 0\\ 1 & 0 \end {array} \right ]\). For \({{\Gamma }^{2}_{0}}\), the first participant is non-essential. We assign the first participant the values (11). Thus, \({S^{0}_{2}}=\left [ \begin {array}{cccc} 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 \end {array} \right ]\) and \({S^{1}_{2}}=\left [ \begin {array}{cccc} 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 \end {array} \right ]\). Finally, by concatenating the initial basis matrices respectively, we construct a (Γ Q u a l , Γ F o r b )-VCS with Γ0={{1,2},{1,3},{1,4},{2,3,4}}, where the basis matrices are \(S^{0}=\left [ \begin {array}{cccccc} 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1 & 0 \end {array} \right ]\) and \(S^{1}=\left [ \begin {array}{cccccc} 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 & 0 & 1 \end {array} \right ]\). By deleting the common columns (1111)T and (1000)T from the initial basis matrices S 0 and S 1, we obtain the optimal pixel expansion 4.

Example 5

For the strong access structure (Γ Q u a l , Γ F o r b ) with Γ0={{1,2},{1,3},{2,4}}, apply Algorithm 1 to group the collection Γ0 into two collections, namely \({{\Gamma }^{1}_{0}}=\{\{1,2\},\{1,3\}\}\) and \({{\Gamma }^{2}_{0}}=\{\{2,4\}\}\). For \({{\Gamma }^{1}_{0}}\), the fourth participant is non-essential. We assign the fourth participant the values (00). Thus, we have \({S^{0}_{1}}=\left [ \begin {array}{cc} 0 & 1\\ 0 & 1\\ 0 & 1\\ 0 & 0 \end {array} \right ]\) and \({S^{1}_{1}}=\left [ \begin {array}{cc} 0 & 1\\ 1 & 0\\ 1 & 0\\ 0 & 0 \end {array} \right ]\). For \({{\Gamma }^{2}_{0}}\), the first and third participants are non-essential. We assign the first participant the values (11) and the third participant the values (00). Thus, \({S^{0}_{2}}=\left [ \begin {array}{cc} 1 & 1\\ 0 & 1\\ 0 & 0\\ 0 & 1 \end {array} \right ]\) and \({S^{1}_{2}}=\left [ \begin {array}{cc} 1 & 1\\ 0 & 1\\ 0 & 0\\ 1 & 0 \end {array} \right ]\). Finally, by concatenating the initial basis matrices respectively, we construct a (Γ Q u a l , Γ F o r b )-VCS with Γ0={{1,2},{1,3},{2,4}}, where the basis matrices are \(S^{0}=\left [ \begin {array}{cccc} 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end {array} \right ]\) and \(S^{1}=\left [ \begin {array}{cccc} 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 \end {array} \right ]\). By deleting the common column (1000)T from the initial basis matrices S 0 and S 1, we obtain the optimal pixel expansion 4.

Example 6

For the strong access structure (Γ Q u a l , Γ F o r b ) with Γ0={{1,2},{1,3,4},{2,3,4}}, apply Algorithm 1 to group the collection Γ0 into two collections, namely \({{\Gamma }^{1}_{0}}=\{\{1,2\},\{1,3,4\}\}\) and \({{\Gamma }^{2}_{0}}=\{\{2,3,4\}\}\). For \({{\Gamma }^{1}_{0}}\), we construct the initial basis matrices by solving the corresponding linear equations, and we have \({S^{0}_{1}}=\left [ \begin {array}{cccc} 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 \end {array} \right ]\) and \({S^{1}_{1}}=\left [ \begin {array}{cccc} 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 \end {array} \right ]\). For \({{\Gamma }^{2}_{0}}\), the first participant is non-essential and we construct the initial basis matrices by assigning the first participant the values (0100) for \({S^{0}_{2}}\) and (0001) for \({S^{1}_{2}}\), thus \({S^{0}_{2}}=\left [ \begin {array}{cccc} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 \end {array} \right ]\) and \({S^{1}_{2}}=\left [ \begin {array}{cccc} 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 \end {array} \right ]\). Finally, by concatenating the initial basis matrices respectively, we construct a (Γ Q u a l , Γ F o r b )-VCS with Γ0={{1,2},{1,3,4},{2,3,4}}, where the basis matrices are \(S^{0}=\left [ \begin {array}{cccccccc} 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \end {array} \right ]\) and \(S^{1}=\left [ \begin {array}{cccccccc} 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end {array} \right ]\). By deleting the common column (1011)T, (0101)T and (0110)T from the initial basis matrices S 0 and S 1, we obtain the optimal pixel expansion 5.

Remark 3

In general, we construct a VCS based on Lemma 2, where the non-essential participants are assigned the value 0. However, the above examples do not follow Lemma 2 and achieve the optimal pixel expansions. A natural question for future studies may be asked. For the non-essential participants, how to assign them the values 0 or 1 to achieve the optimal pixel expansion, especially for (2, n) threshold access structure in Table 3. This question may lead to another problem that how to assign the non-essential participants the values 0 or 1 to guarantee that we can construct a VCS for the corresponding strong access structure by the concatenation of matrices.

6 Conclusion

In this paper we mainly deal with the following two issues: taking more equations simultaneously to construct the initial basis matrices and finding exact number of common columns in the initial basis matrices. For the first issue, we give a useful theory (Theorem 1), by which we could exploit the linear algebraic technique to construct efficient VCS for general access structures. For the second issue, we obtain the exact number of common columns in the initial basis matrices of (2, n)-VCS. Though our proposed construction based on Theorem 1 may not achieve the optimal pixel expansions for some cases, our theory lays a sound and constructive foundation for the minimization of pixel expansion for general access structures in the algebraic aspect of VCS.