6.3.1 (2, n) Scheme

In this section, we show how to construct a (2, n) XOR-based visual cryptography scheme. The (2, n) scheme is equivalent to binary error-correcting codes. By a (m, n, d) code, that is, a binary code of length m consists of n words and a minimum Hamming distance of at least d.

Theorem 1 [17] Let m, l and h be positive integers such that l < h ≤ m. The three following statements are equivalent.

1. A [(2, n); m, m, l] VC scheme exists.

2. A [(2, n); m, h, l] VC scheme exists.

3. A binary (m, n, m − l) code exists.

Proof: It is clear that (i) implies (ii).

In order to show that (ii) implies (iii), let S = (C₀, C₁) be a [(2, n); m, h, l] VC scheme. Take a matrix A₁ ∈ C₁ and let C consist of the rows from A₁. As S is a [(2, n); m, h, l] VC scheme, the Hamming distance between two words from C is at least m − l. Consequently, C is a (m, n, m − l) code. Finally, to show (iii) implies (i), let C be a binary (m, n, m − l) code. For c ∈ C, let A(c) denote the n × m matrix for which each row equals c. Moreover, let B be an n × m matrix containing each word from C as a row, and for 0 ≤ i ≤ n − 1, let B(i) be the matrix obtained by a cyclic shift of the rows of B over i positions. We claim that (C₀, C₁) = ({A(c)|c ∈ C}, {B(0), B(1), ⋯, B(n − 1)}) is a [(2, n); m, m, l] scheme. It is clear that both collections contain n matrices, and that in each row, each word from C occurs in one matrix from C₀ and in one matrix from C₁, showing the indistinguishability. The sum of any two rows from a matrix in C₀ equals 0. Finally, the Hamming distance between any two rows of a matrix from C₁ is at least m − l, showing that the XOR of these two rows contains at most m − (m − l) = l zeros.

An example is given as follows.

Example 1 Let C be a binary (3, 3, 2) code containing words 100, 010 and 001 . Construct C₀ and C₁ as follows:

(C₀, C₁) is a [(2, 3); 3, 3,1] scheme. The contrast α=(h−l)h+l=24=12.

6.3.2 (n, n) Scheme

In this section, we show how to construct a (n, n) XOR-based visual cryptography scheme.

Proposition 2 [17] Let C₀ and C₁ be the set of all binary vectors of length n with even, odd number of ones, respectively. Then (C₀, C₁) is an [(n, n); 1, 1, 0] scheme.

An example is given as follows.

Example 2 Let C₀ and C₁ be

(C₀, C₁) is a [(3, 3); 1,1, 0] scheme with contrast α=(h−l)h+l=1.

6.3.3 (k, n) Scheme

In this section we will introduce three (k, n) XOR-based visual cryptography schemes. Construction 1 and Construction 2 are given by Tuyls (see more detail in Reference [17]). Construction 3 comes from Droste’s OR-based visual cryptography [9] and Liu et al. [13] shows that it is also a (k, n) XOR-based visual cryptography scheme.

Before introducing Construction 1 and Construction 2, some definitions and theorems will be given, which are used in both constructions.

For describing the constructions, we use the following notation. If A is a binary matrix, then P(A) is the multi set of matrices obtained by permuting the columns of A. Moreover, we use the concept of (k, n) pairs, defined as follows.

Definition 2 [17]A pair (A, B) of binary n × m matrices is called a (k, n) pair if there exist numbers a₁, ⋯, a_k and b₁, ⋯, b_k such that

1. For each i with 1 ≤ i ≤ k, the weight of the sum of any i rows from A equals a_i and the weight of the sum of any i rows from B equals b_i, and

2. a_i = b_i for 1 ≤ i < k, and a_k ≠ b_k.

The importance of this definition stems from the following theorem.

Theorem 2 [17] If (A, B) is a (k, n)-pair of n × m matrices, then (P(A), P(B)) is a [(k, n); m, h, l] VC scheme with h = max(m − a_k, m − b_k) and l = min(m − a_k, m − b_k). Here, a_k and b_k denote the weight of the sum of any k rows from A and B, respectively.

Some notations are given here for later use. For a binary vector v of length m, we define Z(v) as the number of zeros in v, and H(v) as its number of ones. Moreover, we define the unbalance δ(v) of v by δ(v) = Z(v) − H(v). Note that δ(v) = m − 2H(v). For later use, we also observe that δ(v)=∑j=1m(−1)vj. With each binary n × m matrices A we associate two vectors δ(A) and N(A) of length 2ⁿ, with the components indexed by binary vectors of length n. For each binary vector x of length n, the x-th component δ_x(A) of δ(A) is defined as δ_x(A) = δ(x^TA), the unbalance of the sum of the rows in A whose index i satisfies x_i = 1; also, the x-th component N_x(A) of N(A) is defined as the number of columns of A that are equal to x. Lemma 1 will show that the vectors δ(A) and N(A) can be computed from each other. To make this precise, define the 2ⁿ × 2ⁿ matrix H by H(x, y) = (−1)^(x,^y), where x, y are binary vectors of length n and (x,y)=∑i=1nxiyi denotes the inner product of x and y. Then we have the following lemma:

Lemma 1 [17]

1. The matrix H is a Hadamard matrix, that is, HH^T = 2ⁿI.

2. The vectors δ(A) and N(A) are related by δ(A) = HN(A).

We are now in the position to prove a generalization of Theorem 2. Before stating it, we need one more notation: if A is a n × m matrix, then w(A_I) denotes the weight of the sum of the rows of A indexed by I. Note that w(AI)=12(m−δχ(I)(A)), where χ(I) is the characteristic vector of the set I.

Theorem 3 [17] Let A and B be n × m matrices such that for each I ⊂ {1, 2, ⋯, n} of size at most k − 1, w(A_I) = w(B_I). Assume moreover that there exist integers h and I such that h > I and that for each I ⊂ {1, 2, ⋯, n} of size k, m − w(A_I) ≥ h and m − w(B_I) ≤ l. Then (P(A), P(B)) is a [(k, n); m, h, l] VC scheme.

Proof The only nontrivial thing we have to prove is the indistinguishability. Let I ={i₁,·⋯, i_t} be a subset of {1, 2, ⋯, n} of size t < k. Let Ā and B¯ denote the restrictions of A and B to the t rows indexed by I. Let x = {x₁, ⋯, x_t} be a binary vector of length t, and let X˜ be the binary vector of length n for which entry i_j is equal to x_j for j = 1, 2, ⋯, t, and whose other entries equal zero. It is clear that δ_x(Ā) = δ_x(Ā). As X˜ has weight at most t, we find, using properties of A and B, that δx(A¯)=δx(B¯).

Hence, by Lemma 1, the number of columns N_y(Ā) in Ā and the number of columns Ny(B¯) in B¯ of type y = {y₀, ⋯, y_t−1} are equal for all binary vectors y of length t. As a consequence, the matrices A and B are equal up to a column permutation, which readily implies indistinguishability in the rows under consideration in the multisets P(A) and P(B). ■

Construction 1

Now an explicit construction of (k, n) VC schemes for all n and all k with 1 ≤ k ≤ n will be given below. According to Theorem 3, it is sufficient to construct (k, n)-pairs for all such n and k. We will obtain such pairs by concatenation of matrices from a fixed collection of building blocks.

For each n and w with 0 ⩽ w ⩽ n, we let the n×(nw)-matrix C_w consist of all the (nw) different 0 − 1 column vectors of weight w, in any order.

In the sequel, we will need an explicit expression for the weight of the sum of any j rows from C_w. In Lemma 2, we state the result. Here and in what follows, we will use the standard convention that (nk)=0 whenever k < 0 or k > n.

Lemma 2 [17] The weight of the sum of any j rows, 1 ≤ j ≤ n, from C_w does not depend on the choice of the rows and is equal to M_j,_W, where

Let λ = (λ₀, ⋯, λ_n)^T be a vector of length n +1 with nonnegative integer entries. We define the matrix C(λ) to be the matrix consisting of the concatenation of λ₀ copies of C₀, λ₁ copies of C₁, ⋯, λ_n copies of the matrix C_n. It is clear that c₀(λ), the number of columns of C(λ), satisfies C0(λ)=∑wλw(nw).

According to Lemma 2, the weight of the sum of any j rows of C(λ) equals c_j(λ), where

Hence, if we define c(λ) = (c₀(λ), ⋯,c_n(λ))^T, then the above can also be written as c(λ) = Mλ, where M is the (n +1) × (n +1) matrix with entries the M_j,W as defined in Lemma 2 for j ≥ 1 and with M0,w=(nw). Now suppose that λ and µ are nonnegative integer vectors such that Mλ and Mµ agree in position 0, 1, ⋯, k − 1, but differ in position k. Then (C(λ), C(µ)) is a (k, n) pair of matrices to which we can apply Theorem 2. The way to find such vectors λ and µ is described in Theorem 5, which uses Lemma 3, Corollary 4, and Lemma 4 below.

Lemma 3 [17] For 1 ≤ j ≤ n, 1 ≤ w ≤ n, we have that Mj,w=∑k≥1(−2)k−1(jk)(n−kw−k)

The following corollary is a direct consequence of Lemma 3.

Corollary 4 Let R and L be the matrices defined as Rk,w=(n−kw−k) for 0 ≤ k, w ≤ n and L_0,0 = 1, L_i,0 = L_0,i =0 if i > 0, and Lj,k=(−2)k−1(jk) if 1 ≤ j, k ≤ n. Then M = LR.

We define the (n +1) × (n + 1) matrix S by Si,j=(−1)i+j(n−ij−i).

Lemma 4 [17]The matrices R and S are inverses of each other.

Theorem 5 [17] Let 1 ≤ k ≤ n − 1. Let θ = (θ₀, θ₁, ⋯, θ_n) be an integer-valued vector such that θ_j =0 if 0 ≤ j ≤ k − 1, and θ_k ≠ 0, and let ϕ := Sθ. For 0 ≤ j ≤ n, we define

Then λ and µ are vectors with nonnegative integer entries, and (C(λ), C(µ)) is a (k, n) pair. The parameters of the corresponding [(k, n); m, h, l] VC scheme satisfy the following equations:

Proof As S has integer entries, ϕ has integer entries, hence λ and µ have nonnegative integer entries. Using Corollary 4, Lemma 4, and the fact that ϕ = λ − µ, we find that

As L is a lower triangular matrix, and θ_j = 0 if j < k, it follows that c_j(λ) − c_j(µ) if 0 ≤ j ≤ k − 1, and that

Moreover, 2m = c₀(λ) + c₀(µ) = c₀(λ + µ) = c₀(|ϕ|), and similarly (m − h) + (m − l) = c_k (λ + µ) = c_k (|ϕ|). ■

We will give an example to illustrate the construction.

Example 3 Take θ = (0, ⋯, 0, 1, 2, ⋯, n − k, n − k + l)^T. As ϕ = Sθ, we have by definition

If k = 3, then ϕ = (2 − n, 1, 0, 0, ⋯, 1, n − 2). Consequently, λ = (0, 1, 0, ⋯, 0, n − 2) and µ = (n − 2, 0, ⋯, 0, 1, 0). That is to say, A = C(λ) consists of the n × n identity matrix and n − 2 columns of weight n, while B = C(µ) consists of n − 2 all-zero columns and furthermore contains each column of weight n − 1 once. It is clear that A and B both contain 2n − 2 columns. Straightforward computations show that a₁ = b₁ = n − 1, a₂ = b₂ = 2, a₃ = n + 1, b₃ = n − 3. As a consequence, we obtain a [(3, n); 2n − 2, n + 1, n − 3] VC scheme with α = 2/(n − 1).

Construction 2

In general, it seems hard to give manageable expression for the physical parameters of the schemes obtained with Construction 1. Tuyls [17] gave another explicit construction of a (k, n) VC scheme that has the virtue that the physical parameters of these schemes can readily be computed in Reference [17]. For constructing these matrices, they used maximum distance separable (MDS) codes over GF(q), the finite field with q elements. An [n, k] MDS code over GF(q) consists of q^k vectors of length n with entries from GF(q) such that any two codewords have a Hamming distance of at least n − k + 1. It is known that such a code exists whenever q + 1 ≥ n. Therefore, we choose q ≥ n − 1.

Lemma 5 [17] Let C be an [n, k] MDS code over GF(q). In any set of k positions, each of the q^k possible patterns occurs in exactly one of the words of C.

Proof Fix k positions, two codewords that agree in these positions, differ in at most n k positions. We conclude that each of the q^k patterns agrees with at most one codeword. As the number of patterns equals the number of codewords, each pattern agrees with exactly one codeword in the given positions. ■

Let C be an [n, k] MDS code over GF(q). Let U(C) be an n × q^k matrix over GF(q) in which each word from C occurs as a column once, and let A(C) be the binary n × q^k matrix obtained from U(C) by replacing each nonzero symbol in GF(q) by a ‘1,’ and the zero symbol in GF(q) by a ‘0.’

Proposition 3 [17] Let 1 ≤ j ≤ k, the sum of any j rows of A(C) has weight 12qk−j[qj−(2−q)j].

Proof Consider j rows from U(C). Lemma 5 implies that each of the q^j possible patterns occurs in these j positions in q^k−j words from C. The number of patterns with w nonzero elements equals (jw)(q−1)w. Each such pattern yields a column in A(C) with exactly w ones in the j prescribed rows. Consequently, the number of ones in the sum of the j rows from A(C) under consideration equals

Proposition 4 [17] The sum of any k + 1 rows of A(C) has a weight 12q(qk+1−(2−q)k+1)−q−1q2k.

Proof Consider k + 1 positions in C. Any two distinct words from C differ in at least two of these positions. That is, restricted to these k + 1 positions, C is a [k + 1, k, 2] code over GF(q). The number of words of weight w in such a code equals

The weight of the sum of the rows of A(C) corresponding to the k + 1 chosen positions is obtained by summing the above expressions of b_w over all odd w.

■

Theorem 6 [17] Let 2 ≤ k ≤ n − 1, and let q be a prime power not smaller than n − 1. There exists a[(k,n);qk,12(qk+(−1)k(q−2)k+(q−1)2k),12(qk+(−1)k(q−2)k)] VC scheme with contrast (q − 1)2^k−1/[q^k + (−1)^k(q − 2)^k + (q − 1)2^k−1].

Proof Let C be an [n, k] MDS code over GF(q), and let D be an [n, k − 1] MDS code over the same field. In the notation of this section, let A equal A(C), and let B equal the concatenation of q copies of A(D). By combining the above results, (A, B) is a (k, n) pair, and (P(A), P(B)) is a VC scheme with parameters as claimed in the theorem. ■

Bounds on the parameters m, h and l

Tuyls provided bounds on the parameters of a (k, n)-VC scheme. We start by proving that maximal contrast schemes (l = 0) do not exist. We note that for OR-based schemes maximal contrast schemes can always be constructed.

Proposition 5 [17] Let 3 ≤ k < n. There exists neither a [(k, n); m, h, 0] VC scheme, nor a [(k, n); m, m, l] VC scheme.

Proof Let S = (C₀, C₁) be a [(k, n); m, h, 0] VC scheme and let B ∈ C₁.. Denote by σ¹, σ² two arbitrary rows in B. Since n − 2 ≥ k − 1, B contains (at least) k − 1 more rows. We denote these rows by σ³, ⋯, σ^k+1. Since S is a scheme with l = 0, the XOR of σ¹, σ³, ⋯, σ^k+1 is the all-one vector, as is the XOR of σ², σ³, ⋯, σ^k+1. If follows that σ¹ = σ², so all rows of B are equal.

Next, let A ∈ C₀ and consider row i and j of A. As k ≥ 3, the indistinguishability property of Definition 1 implies that there is a B ∈ C₁ that agrees with A in these rows. As all rows of B are equal, the i-th and j-th row of A are equal. Since i and j are arbitrary, all rows of A are equal, so A = B, a contradiction.

The second statement follows from an analogous reasoning. ■

The next two propositions show that XOR-based VC schemes with odd and even k fundamentally differ.

Proposition 6 [17] Let k be odd, and let k < n. For each ϵ > 0, there are integers m, h, and l such that l/m < ϵ and a [(k, n); m, h, l] VC scheme exists.

Proposition 7 [17] Let k be even, and let k < n. If a [(k, n); m, h, l] VC scheme exists, then l/m ≥ 1/(k + 1).

Corollary 7 [17] For even k < n, the contrast of a k out of n VC scheme is at most k/(k + 2).

Proof Let S be a [(k, n); m, h, l] scheme. By definition, the contrast α is equal to (h − l)/(h + l). It is clear that α is increasing in h, and so α ≤ (m − l)/(m + l). As (m − l)/(m + l) is decreasing in l, we obtain an upper bound on α by plugging in the upper bound for l from Proposition 7. ■

Lemma 6 [17] Let k be an even integer. Let B be a binary matrix with n rows such that the sum of any k rows from B differs from 0. Then B has at least n − k + 2 distinct rows.

Lemma 7 [17] Let (C₀, C₁) be a [(k, n); m, h, l] VC scheme with k ≥ 3, and let c₁ and c₂ be two rows of a matrix in C₀ and hence also two rows of some matrix in C₁. Then, the Hamming distance between c₁ and c₂ satisfies

Proposition 8 [17] Let k be even, k ≥ 4. If a [(k, n); m, h, l] VC scheme exists, then n−k+1≤∑i=0min(l,2(m−h))(mi)

Proof Let k be even, k ≥ 4, and let S = (C₀, C₁) be a [(k, n); m, h, l] scheme. Let B be a matrix in C₁ . As l ≠ m, no k rows of B add to the all-zero word. Lemma 6 implies that B has at least n − k + 2 distinct rows. Since according to Lemma 7, all rows from B have a Hamming distance at most 2(m − h) to its top row, we obtain n−k+2≤∑i=02(m−h)(mi)

Now we assume without loss of generality that the top n — k + 1 rows of B are distinct. Let c be the sum of the k − 1 bottom rows of B. For 1 ≤ i ≤ n − k + 1, the sum of c and the i-th row of B contains at most l ones; that is to say, the i-th row of B has a Hamming distance at most l to the complement of c. As the n − k + 1 top rows of B are distinct, n − k + 1 is at most the number of vectors at distance at most l from the complement of c, so n−k+1≤∑i=0l(mi). ■

Construction 3

Droste [9] proposed an algorithm to construct a (k, n)-VC scheme under the OR operation. Liu et al. [13] proved that the basis matrices constructed by that algorithm are also the basis matrices of a (k, n)-VC scheme under the XOR operation. Droste’s algorithm can be described as follows.

For easy specification, we call a column of a Boolean matrix with an even number of 1’s even and otherwise odd. If B is a Boolean matrix, we define P(B) as the multiset of matrices obtained by permuting the columns of B, i.e., each permutation corresponds exactly to one element of P(B).

The following lemma will be needed later.

Lemma 8 [9] Let B₀ and B₁ be two n × m Boolean matrices so that there exist m − 2^k−1 column vectors v1,⋯,vm−2k−1∈{0,1}k with the following property: for every {i₁, ⋯, i_k} ⊆ {1, ⋯, n} the restriction of B₀ (resp. B₁) to the rows i₁, ⋯, i_k contains every even (resp. odd) column of length k exactly once and all columns v1,⋯,vm−2k−1. Then P(B₀) and P(B₁) are a k out of n secret sharing scheme with relative contrast 1/m; here the contrast is defined as α=h−lm.

The main idea for construction is to start with an empty matrix (which has no columns) and, for various q ∈ {0, ⋯, n} and all (nq) columns, which have exactly q 1’s. Because of the symmetry of this construction with respect to rows, all restrictions of such a matrix of k rows contain the same columns. And one can exactly determine which columns they contain.

Lemma 9 [9] For q ∈ {0, ⋯, n} let B be an n×(nq) Boolean matrix that contains every column with q 1’s exactly once. Then every restriction of B to k rows (with k ≤ n) contains every column with p 1’s exactly (n−kq−p)-times (where p ∈ max{0, q − (n − k), ⋯, min(q, k)}).

Lemma 9 shows a possibility to expand a matrix, if we add to all its restrictions every column with p 1’s exactly once: just add all columns with q = p or q = p + n − k 1’s to the entire matrix. So a subroutine ADD(p, B) adds to each restriction of k rows of a matrix B every column with p 1’s by adding columns to the entire matrix.

ADD(p, B)

Step 1: If p ≤ k − p, add all the columns with q = p 1’s to B.

Step 2: If p ≥ k − p, add all the columns with q = p + n − k 1’s to B.

The subroutine makes it easy to construct basis matrices B₀ (resp. B₁) whose restrictions always contain every even (resp. odd) column. But besides these columns, every restriction of B₀ and B₁ can contain remaining columns (which are the same for all restrictions of one matrix because of the construction principle). To be appropriate for a k out of n scheme these remaining columns have to be the same for B₀ and B₁ (see Lemma 8). So the remaining columns of every restriction of B₀, which are not remaining columns of every restriction of B₁, called the rest of B₀, have to be added to every restriction of B₁ and vice versa. In most cases, these added columns will create new rests that cause new columns to be added.

Droste’s algorithm

Step 1: For all even p ∈ {0, ⋯, k}, call ADD(p, B_o).

Step 2: For all odd p ∈ {0, ⋯, k}, call ADD(p, B₁).

Step 3: While the rests of B₀ and B₁ are not empty:

1. Add to B₀ all columns adjusting the rest of B₁ by calling ADD.

2. Add to B₁ all columns adjusting the rest of B₀ by calling ADD.

Theorem 8 shows that Droste’s algorithm also generates a (k, n)-VC scheme under the XOR operation, by Liu et al. [13].

Theorem 8 [13] Droste’s algorithm generates the basis matrices of a (k, n)-VCS, B₀ and B₁, under the XOR operation.

Proof We need to prove that the basis matrices B₀ and B₁ satisfy the contrast and security conditions of Definition 1.

First, for the contrast condition, we need to prove that the Hamming weight of the stacking (XOR operation) of any k out of n rows of B₀ is less than that of B₁. Denote B0k (resp. B1k) as the submatrix generated by restricting to arbitrary k rows of B₀ (resp. B₁). According to the Steps 1 and 2 in Droste’s algorithm, it is clear that all the even (resp. odd) columns appear in B0k (resp. odd). Denote I0k (resp.I1k) as the matrix whose columns are all the even (resp. odd) columns of length k. Because Droste’s algorithm terminates when the rests of B₀ and B₁ are empty, it implies that the remaining columns of B₀ and B₁ are the same, that is, B0kI0k=B1kI1k. Denote R as the remaining columns of B₀ and B₁, we have B0k=I0k∪R,B1k=I1k∪R. Because the XOR (operation) of the entries of an even (resp. odd) column is 0 (resp. 1), we have the result that the Hamming weight of the stacking (XOR operation) of the rows of B0k is less than that of B1k. Hence, the contrast condition is satisfied.

Second, for the security condition, we need to prove that the submatrices of any less than k rows of B₀ and B₁ have the same columns, and only in such a case, all the column permutations of the two submatrices will generate the same collection, that is, the security condition is satisfied. Denote B0t (resp. B1t) as the submatrix generated by restricting to arbitrary t rows of B₀ (resp. B₁), where t < k. Denote B0k (resp. B1k) as the submatrix generated by concatenating B0t (resp. B1t) and arbitrary k − t rows chosen from the remaining rows of B₀ (resp. B₁) (other than the rows in B0t and B1t). As discussed above, we have B0k=I0k∪R,B1k=I1k∪R, where I0k (resp. I1k) is the matrix that contains all the even (resp. odd) columns of length k. Note that I0k and I1k are the basis matrices of a (k, k)-VC scheme proposed in References [16, 3]. We have the result that the submatrices generated by restricting to any t rows of B₀ and B₁ have the same columns. Hence, the submatrices generated by restricting to any t rows of B₀ and B₁ have the same columns, that is, the security condition is satisfied. ■

Besides the above schemes, Liu et al. [15] proposed a step construction to construct XOR-based visual cryptography for general access structure by applying (2, 2)-VCS recursively, where a participant may receive multiple share images. Readers can refer to [15] for more detail. An approach to construct extended XOR-based visual cryptography was proposed in Reference [14].

6.4.1 (k, n) VC Scheme Using Cyclic-Shift Operation

Let the shadow image s = [s_ijk], and the element s_ijk is the secret pixel s_ij in a (W × H)-pixel secret image replaced by m subpixels (s_ij1, s_ij2, ⋯, s_ijm), where i ∈ [1, W], j ∈ [1, H], and k ∈ [1, m]. The cyclic-shift operation is Γ([s_ijk]) = [γ(s_ijk)], where γ(•) is a 1-bit cyclical right shift function, i.e.,

A matrix operation Γ(•) cyclically shifts right one subpixel in every m subpixels (for a secret pixel) in the shadow image.

When the difference of whiteness ”h − l” is odd, we can design an ideal contrast VC scheme even when the underlying VC scheme with reversing is nonperfect black. At this time the decoding needs an XOR operation.

Yang et al.’s scheme [25] is described in a pseudo-code style below in terms of its construction procedure and the revealing procedure.

Theorem 9 [25] The whiteness percentages of the white and black secret pixels for Yang et al.’s algorithm are P_W = 100% and P_W = 0%, respectively, after finishing m runs.

Proof There are ”m − h” B ”h” W (respectively ”m − l” B ”l” W) subpixels for the white (respectively black) secret pixel. When shifting right one bit m times, there are m h (respectively m − l) black subpixels for the white (respectively black) secret pixels in U′. Suppose ”m − h” is even (respectively odd); an XOR operation will result in all white subpixels for the white pixels in U′ (respectively U′). Thus, the P_W of the white secret pixel is 100%. On the other hand, even (respectively odd) ”m − h” means odd (respectively even) ”m − l” since ’h − l’ is odd. It is evident that an XOR operation will result in all black subpixels for the black pixels in U′ (respectively U′), i.e., the P_W of the black secret pixel is 0%. ■

An example (2,4) – NPBVCS is given below as a demonstration for Yang et al.’s algorithm.

Example 4 Suppose in (2, 4)-VCS with basis matrices B₀ and B₁.

The distribution phase is shown in Table 6.1 and the reconstruction phase is shown in Table 6.2 and Table 6.3.

Distribution phase:

Table 6.1 Distribution phase of (2, 4)-VCS using Yang et al.’s [25] algorithm.

Reconstruction phase

We can see that the white pixel is reconstructed as four white subpixels and the black pixel is reconstructed as four black subpixels.

6.4.2 A Scheme for General Access Structure

Let P = {1, 2, ⋯, n} be a set of participants, 2^P represents the set of all subsets of P. Let Γ_qual ⊆ 2^P and Γ_forb ⊆ 2^P, where Γ_qual; ∩ Γ_forb = ϕ. The members of Γ_qual;(resp. Γ_forb) is called qualified sets (resp. forbidden sets). The Γ = (Γ_qual, Γ_forb) is called the access structure. Define Γ₀ = {A ∈ Γ_qual: A′ ∉ Γ_qual for all A′ ⊂ A} be all the minimal qualified sets [1].

Suppose Γ0={ΓQ1,⋯,ΓQt}, by employing the optimal (k, k)-scheme [16], the basis matrices L₀ and L₁ are constructed as follows:

Let kp=|ΓQp|, and ΓQp={p1,⋯,pkp}, for 1 ≤ p ≤ t. We will construct a n×2kp−1 matrix Epi,i∈{0,1}, i ∈ {0, 1} according to the following steps: the p_i row of Ep0 is the i-th row of the basis matrix B₀ of the (k_p, k_p)-scheme. The elements of other rows of Ep0 are all 1’s.

Then L0=E10. The construction Ep1 of is similar to Ep0 except we replace the p_i row of from the basis matrix B₁ of the (k_p, k_p)-scheme instead of B₀. Then L1=E11‖⋯‖Et1.

Lemma 10 [10] The L₀ and L₁ are a pair of basis matrices of a perfect black VC scheme for Γ₀ such that the expansion rate is m=2|Q1−1|+⋯+2|Qt−1| and GRAY(white) = 1 − 1/m.

We now construct an n×2kp−1 matrix F_p, which has the property that the elements in p_i row of F_p are all 0’s and the other rows of F are all 1’s, here 1 ≤ p ≤ t. Then an auxiliary basis matrix A₀ = F₁|⋯|F_i.

Hu and Tzeng [10] algorithm for minimal access structure

Lemma 11 [10] The (k, k)-VC scheme [16] is an ideal contrast (k, k)-VC scheme with reversing.

Proof k participants perform XOR operations on the k transparencies by computing t₁ ⊕ t₂ ⊕ ⋯·⊕ t_k. It is easy to see that the white pixels are all white since S₀ has an even number of 1’s; whereas the black pixels are all black since S₁ has an odd number of 1’s. ■

Theorem 10 [10] Let Γ = (P, Q, F) be an access structure on a set ρ of n participants. Then the basis matrices B₀, B₁, and A₀ constitute a compatible ideal contrast VC scheme with reversing in two runs.

Proof It is obvious that the VC scheme is security. The basis matrix Ao also reveals absolutely no information about the secret image since no secret is encoded into the shares A_j for j = 1, ⋯, k_p.

Let L0=E10‖⋯‖Et0,L1=E11‖⋯‖Et1 and A₀ = F₁‖ ⋯ ‖F_t be the basis matrices for a VC scheme with reversing, constructed using the previously described technique. Without loss of generality, let Γ₀ = {Q₀, ·⋯, Q_t} and X = Q₁, X be a subset of qualified participants. Since the secret image is reconstructed by computing (T + A) ⊕ A, we will prove that the general access structure has an ideal contrast, i.e., H((E10+F1)⊕F1)=0,H((E11+F1)⊕F1)=2|Q1|−1 and H((Eib+Fi)⊕Fi) for i = 2, ⋯, |Γ| and b = 0, 1. It results that H((E10+F1)⊕F1)=H((E10+0)⊕0)=H(E10⊕0)=H(E10)=0 by Lemma 11, and H((E11+F1)⊕F1)=H((E11+0)⊕0)=H(E11⊕0)=H(E11)=2|Q1|−1 by Lemma 11, whereas, H((Eib+Fi)⊕Fi)=H((Eib+1)⊕1)=w(1⊕1)=0 for i = 2, ⋯, |Γ₀| and b = 0, 1. ■

We give the following example to illustrate the construction method above.

Example 5 Let p = {1, 2, 3, 4} and Γ₀ = {{1, 2}, {1, 3}, {2, 3}}. Then the basis matrices L₀, L₁, and A are constructed as follows according to the method above. B₀ and B₁ are basis matrices of a (2, 2) – VC scheme.

The distribution phase is shown in Table 6.4 and the reconstruction phase is shown in Tables 6.5, 6.6, and 6.7.

Distribution phase

Table 6.4 Distribution phase of the visual cryptography with minimal access structure Γ₀ = 1, 2, 1, 3, 2, 3 using Hu and Tzeng [10] algorithm.

Reconstruction phase

6.5.1 (2, n) Scheme

To solve the pixel expansion problem with VSS schemes, Ito et al. [11], Yang [24] and Cimato et al. [6] proposed probabilistic VSS models. The frequency of white pixels in a white (or black) area is used to display the contrast of the recovered image. In reconstructing the secret image, the ”OR”-ed operation of pixels of the shadows is the same as the stacking operation of subpixels in the nonprobabilistic VSS schemes. They defined p₀ (resp. p₁) as the appearance probability of a white pixel in a white (resp. black) area of the recovered image. For a fixed threshold probability 0 ≤ p_TH ≤ 1 and relative contrast α ≥ 0, if p₀ ≥ p_TH and p₁ ≤ p_TH − α, the frequency of white pixels in a white area of the recovered image should be higher than that in a black area.

Wang et al. [23] proposed a probabilistic (2, n) secret sharing scheme for binary images. Boolean XOR and AND operations are employed, and n + 1 distinct random matrices are generated as intermediate results. The scheme is described in a pseudo-code style below in terms of its input, output, the construction procedure, and the revealing procedure.

Wang et al.’s [23] algorithm for (2,n) scheme

For integer scalar inputs between 0 and c−1, each operand is represented in binary and the operation is carried out bit-by-bit. For example, when a = 125 and b = 18, the XOR between these two integers is

For matrix inputs, the XOR operation of two N_R × N_C matrices is defined pixel-wise. That is,

The AND operation for integer scalar operands and matrix operands can be defined similarly.

In all computations, every pixel is handled individually, separated from other pixels. Therefore, to make the context clear, we denote pixel A_i(s,t) simply as A_i. With the above construction procedure, for a ”0” pixel in A and any i, we have C_i = B_i&0 = 0 and A_i = B_n+1 ⊕ C_i = B_n+1, thus

For a ”1” pixel in A, C_i = B_i&1 = B_i and A_i = B_n+1 ⊕ B_i, thus

which could be 0 or 1. In other words, between the original image A and a reconstructed image A′, the ”0” bits are kept the same and the ”1” bits may or may not changed. With any single shadow image, no information of A is revealed because of the random nature of the matrices B′s. It is easy to verify that the n matrices A₁, A₂, ⋯ , A_n are n distinct random matrices from construction method above, each A_i (i = 1, ⋯ , n) does not contain any information of the original matrix A.

Associated Shamir’s secret sharing scheme and a gradual search algorithm for a single bitmap block truncation coding with the above (2, n) scheme, the secret sharing scheme for color images was proposed in Reference [3]. Combined the above (2, n) scheme with voting strategy, the probabilistic visual secret sharing scheme for grayscale images was provided in Reference [4]. Based on the above proposed (2, n) scheme, the matrices B₁, B₂, ⋯ , B_n are chosen according to Yang’s into ”probabilistic VC scheme and the (2, n) probabilistic scheme with improved contrast was given in Reference [19].

6.5.2 (n, n) Scheme

The construction steps are given in the context of grayscale images. It is trivially applicable to binary images and can be easily extended to color images.

Wang et al.’s [23] algorithm for (n,n) scheme

Theorem 11 [23] A₁ ⊕ A₂ ⊕⋯⊕ A_n = A.

Proof Because the ”⊕” operation is associative and B_i ⊕ B_i is a zero matrix for any i, we have

Theorem 12 [23] A_i1 ⊕A_i2 ⊕⋯⊕A_ik ≠ A for any set of integers {i₁,⋯,i_k} when k < n.

Proof We consider two cases. Case 1 is for n ∈ {i₁,⋯ i_k} and Case 2 is for n ∉ {i_ı,⋯, i_k}.

Case 1: n ∈ {i₁,⋯,i_k}. In this case, An⊕(⊕j=stAj)=A⊕Bn−1⊕(⊕j=stAj) where ⊕j=st means A_s ⊕ ⋯⊕ A_t with s,⋯,t being the indices in 1,⋯, i_k} besides n. Since there are an odd number of n − 2 term random matrices involved, at least one of them cannot be absorbed into a zero matrix, thus Ai1⊕Ai2⊕⋯⊕Aik must be random, thus not equal to A.

Case 2: n ∉ {i₁,⋯, i_k}. Since no matrix A involved in Ai1⊕Ai2⊕⋯⊕Aik to begin with, Ai1⊕Ai2⊕⋯⊕Aik is constructed from the n − 1 term random matrices only and it must be random.

Next, we analyze the steps of Wang et al.’s [23] (n,n) algorithm in the context of the grayscale image below. It is trivially applicable to a binary image and can be easily extended to a color image. Now we give an example to demonstrate the computation steps in the construction/revealing process using the above algorithm.

Example 6 Let n = 3 and the secret image A be a single pixel.

From the above algorithm, it is known that the proposed (n, n) scheme reconstructs the secret image exactly and when fewer than n shadows are used, the original secret image A will not be revealed. Moreover, only simple Boolean XOR operations are used and the size of each shadow image is the same as the original image, thus no pixel expansion. The above (n, n) secret sharing scheme was applied to deal with gray scale and color secret images respectively in Reference [22].

6.5.3 (k, n) Scheme

Based on above Wang et al.’s [23] (n, n) secret sharing scheme [23], Chao and Lin [5] have attempted to construct a (k, n) secret sharing scheme. To design a threshold (k, n) scheme, one may first directly utilize Wang et al.’s [23] (m, m) scheme for some carefully chosen parameter m=(nk−1). The (k, n, m) shadows-assignment matrix has n rows and m columns. Its n rows represent n persons; and its m columns represent the m (distinct) temporary shadows produced by the above (m, m) scheme. The element of H is either 0 or 1. The i-th person (row) has a copy of the j-th shadow image (column) if and only if H_ij. Each column of H have exactly k − 1 zeros and n − k + 1 ones.

Now we will introduce Chao et al.’s (k, n)-VC scheme based on the (k, n, m) shadows assignment matrix H.

Chao and Lin [5] algorithm for (k,n) scheme

Let the size of secret image A be N_R × N_C. Since the size of every temporary shadow C_i(1 ≤ i ≤ m) is 2 × (N_R × N_C)/m, the size of every final shadow Si(1≤i≤n)is[2×(NR×NC)m]×(n−1k−1)=2(NR×NC)(n−k+1)n. Notice that each final shadow S_i(1 ≤ i ≤ n) contains (n−1k−1) temporary shadows. After we divide by the size of secret image A, we obtain the pixel expansion rate per=2×n−k+1n<2. Each shadow will be at most two times larger than secret image A.