8 Visual Cryptography and Contrast Bounds

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Andreas Klein

Ghent University, Belgium

8.1 Introduction

8.2 Preliminaries

8.3 Approximate Inclusion Exclusion

8.4 Designs and Codes

8.5 Optimal 3-out-of-n Schemes

8.6 Asymptotic Optimal k-out-of-n Schemes

8.7 Contrast Trade-Offs for Extended Visual Cryptography Schemes

8.8 Enhancing the Contrast by Nonstandard Models

8.9 Conclusion

Bibliography

8.1 Introduction

To describe a visual cryptography scheme we encode the encryption of a pixel by Boolean matrices. The rows represent the slides and the columns represent the different subpixels.

For example, the encoding illustrated in Figure 8.1 is described by

M = ⎛ ⎝ ⎜ 000101011110 ⎞ ⎠ ⎟ .

$M = (\begin{array}{l} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{array}) .$

To describe the random decision, which must be made when encoding a pixel, we use multisets that contain all possible choices with the right frequency.

This leads to the formal definition of a visual cryptography scheme.

Definition 1 Let Γ be any access structure for n persons. A visual cryptography scheme is a pair of multisets M_b and M_w of Boolean n × m matrices. Which satisfy:

Images

FIGURE 224.8
Example of encoding a visual cryptography scheme.

|M_b| = |M_w| = r
For each ∈ ∉ Γ the restriction of all matrices in M_b to the rows indexed by i ∈ ∈ gives the same multiset of |G| × n matrices as the restriction of all matrices in M_w to the rows indexed by i ∈ G. (This formalizes the requirement that an unqualified set of persons gain no information about the secret.)
G ∈ Γ is a minimal qualified set if every proper subset G′ ⊂ G is not an element of Γ.

For each minimal qualified set of persons G the restriction of a matrix in M_b to the rows indexed by i ∈ G give a |G| × m matrix with at least h(G) nonzero columns and the restriction of a matrix in M_w to the rows indexed by i ∈ G give a |G| × m matrix with at least l(G) nonzero columns. The inequality h(G) > l(G) must be satisfied. (This formalizes the idea that we see a black pixel as a darker gray than a white pixel.)

Note: The condition (a) can be relaxed a bit, we choose |M_b| = |M_w| for simplicity. Some authors require that condition (c) holds for all qualified sets G ∈ Γ not only for the minimal qualified sets.

The performance of visual cryptography scheme is described by 3 parameters.

The randomness r, that measures the amount of entropy needed to encode an image.
The number of subpixels m need to encode an pixel (pixel expansion).
The contrast α = min{(h(G) − l(G))/m|G ∈ Γ} that measures the quality of the reconstructed image.

In applications the contrast is the most important factor. (Anything below 1/10 can be hardly used if you really stack transparencies.) Thus, finding contrast optimal schemes is an important task.

The goal of this chapter is to prove upper bounds on the possible contrast and to construct schemes near that bounds.

8.2 Preliminaries

For the moment we will ignore the pixel expansion and the randomness. Then contrast optimal visual cryptography schemes can be simplified.

Lemma 1 Let Γ be any access structure then there exists a contrast optimal visual cryptography scheme (M_W, M_b) for Γ with the property that M_W is the multiset of all column permutations of a matrix M_w and M_b is the multiset of all column permutations of a matrix M_B.

Proof

Let (M′_W, M′_B) be a contrast optimal visual cryptography scheme for Γ with pixel expansion m and randomness r.

Let M_W = (M′_W⁽¹⁾, …, M′_W⁽^r⁾) be the n × (mr) matrix which consist of all matrices M′_W⁽ⁱ⁾ ∈ M′_W(i = 1, …,r) written in sequence, one after the other. Similarly let M_B be the n × (mr) matrix that consists of the matrices in M′_B written after each other.

Let G ∉ Γ, by Definition 1 (b) the restriction of M_W and M_B to the rows i ∈ Γ must give return two matrices that different only for a permutation of their columns, i.e., the scheme (M_W, M_B) satisfies the security requirement (Definition 1 (b)).

Now let G ∈ Γ by Definition 1 (c) the restriction of every matrix in M_B to the rows i ∈ Γ contains at least am more nonzero columns than the restriction of a matrix in M_W to the same rows. Thus, the restriction of M_B to the rows i ∈ Γ contains at least amr more nonzero columns than the restriction of M_W to the rows i ∈ Γ. That proves that the scheme (M_W, M_B) reconstructs the secret image.□

The advantage of the scheme constructed by Lemma 1 is that the visual cryptography scheme is now described by just two Boolean matrices M′_W and M′_B instead of two multisets of Boolean matrices. Moreover the order of the columns in M′_W and M′_B does not matter. For each S ⊆ {1, … ,n} let x(W)S $x_{S}^{(W)}$ denote the number of columns in M′_W with 1 in the rows corresponding to S and 0 in the other rows. Similarly define the variables x(B)S $x_{S}^{(B)}$ . The scheme is described completely by the values x(B)S,x(W)S $x_{S}^{(B)}, x_{S}^{(W)}$ .

The security requirements of the visual cryptography scheme translates to the linear equations

\sum S \subseteq {1, \dots n} S \cap G \neq 0 x (W) s = \sum S \subseteq {1, \dots n} S \cap G \neq 0 x (B) s (8.1)

$\sum_{\begin{matrix} S \subseteq {1, \dots n} \\ S \cap G \neq 0 \end{matrix}} x_{s}^{(W)} = \sum_{\begin{matrix} S \subseteq {1, \dots n} \\ S \cap G \neq 0 \end{matrix}} x_{s}^{(B)} (8.1)$

for all G ∉ Γ and the requirement that a qualified subset can see the image translates to

\sum S \subseteq {1, \dots n} S \cap G \neq 0 x (W) s = \sum S \subseteq {1, \dots n} S \cap G \neq 0 x (B) s (8.2)

$\sum_{\begin{matrix} S \subseteq {1, \dots n} \\ S \cap G \neq 0 \end{matrix}} x_{s}^{(W)} = \sum_{\begin{matrix} S \subseteq {1, \dots n} \\ S \cap G \neq 0 \end{matrix}} x_{s}^{(B)} (8.2)$

for all minimal qualified subsets G.

The equations (8.1) and (8.2) lead to the linear program. Replace (8.1) by

\sum S \subseteq {1, \dots n} S \cap T \neq 0 x (W) s + α \leq \sum S \subseteq {1, \dots n} S \cap T \neq 0 x (B) s

$\sum_{\begin{matrix} S \subseteq {1, \dots n} \\ S \cap T \neq 0 \end{matrix}} x_{s}^{(W)} + α \leq \sum_{\begin{matrix} S \subseteq {1, \dots n} \\ S \cap T \neq 0 \end{matrix}} x_{s}^{(B)}$

and require

\sum S \subseteq {1, \dots n} x (B) s = \sum S \subseteq {1, \dots n} x (W) s = 1

$\sum_{\begin{matrix} S \subseteq {1, \dots n} \end{matrix}} x_{s}^{(B)} = \sum_{\begin{matrix} S \subseteq {1, \dots n} \end{matrix}} x_{s}^{(W)} = 1$

and maximize α. For small values of n it is no problem to feed that program into a computer and get the optimal visual cryptography scheme. (I prepared such a program for my book [11]. You can download it from my homepage http://cage.ugent.be/~klein/vis-crypt/buch/).

For the k-out-of-n access structure it is possible to simplify the linear program and solve it directly.

Lemma 2 Let Γ be the k-out-of-n access structure. Then in addition to Lemma 1 we can require that any row permutation of M_w is also a column permutation of M_W and, similarly, every row permutation of M_B is also a column permutation of M_B.

Proof

Let M_W and M_B be the two Boolean matrices that describe the visual cryptography scheme constructed in Lemma 1.

For every row permutation a the matrices MσW $M_{W}^{σ}$ and MσB $M_{B}^{σ}$ also describe a k-out-of-n visual cryptography scheme.

Let MσW $M_{W}^{σ}$ be the n × (mn!) matrix that consists of all row permutations MˆB ${\hat{M}}_{B}$ of M_W written after each other. Similarly define MˆW ${\hat{M}}_{W}$ . As we have seen already in the proof of Lemma 1 this also gives a solution of the k-out-of-n visual cryptography scheme. In addition MˆB ${\hat{M}}_{B}$ and x(B)S=x(B)S′ $x_{S}^{(B)} = x_{S^{'}}^{(B)}$ satisfy the permutation invariance stated in the Lemma. ☐

Lemma 2 allows us to simplify the linear program for a contrast optimal k-out-of-n visual cryptography scheme. With the notations from above we get x(B)S=x(B)S′ $x_{S}^{(B)} = x_{S^{'}}^{(B)}$ and x(W)S=x(W)S′ $x_{S}^{(W)} = x_{S^{'}}^{(W)}$ for |S| = |S′|. Let for i ∈ {0, …, n} be x(B)i=x(B){1,…,i} $x_{i}^{(B)} = x_{{1, \dots, i}}^{(B)}$ and x(B)i=x(B){1,…,i}. $x_{i}^{(B)} = x_{{1, \dots, i}}^{(B)} .$

The linear program simplifies to:

\sum i = 0 n (n i) x (W) i = \sum i = 0 n (n i) x (B) i = 1 (8.3)

$\sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(W)} = \sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(B)} = 1 (8.3)$

This equation express that the variables denotes the fractions of black subpixels and that all fractions add up to 1.

\sum i = 0 n - j (n - j i) x (W) i = \sum i = 0 n - j (n - j i) x (B) i (8.4)

$\sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(W)} = \sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(B)} (8.4)$

for j = 0, …, k − 1. This equation expresses that the stack of j transparencies always has the same number of white subpixels and replaces (8.1).

Maximize

α = \sum i = 0 n - k (n - k i) x (W) i - \sum i = 0 n - k (n - k i) x (B) i (8.5)

$α = \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(W)} - \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(B)} (8.5)$

In this form the linear program is simple enough to solve it directly. We will track this problem in Sections 8.5 and 8.6.

The linear program has been independently deduced by several researchers. (Variable transformations like xˆ(W)i=x(W)n−i or xˆ(W)i=(ni)x(W)i ${\hat{x}}_{i}^{(W)} = x_{n - i}^{(W)} or {\hat{x}}_{i}^{(W)} = (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(W)}$ are common. This makes the results look quite different in various articles. Always check the meaning of the variables.)

8.3 Approximate Inclusion Exclusion

The well-known inclusion-exclusion-formula states.

| A 1 \cup A 2 \cup \dots \cup A n | = \sum i | A i | - \sum | A i \cap A j | + \sum i < j < k | A i \cap A j \cap A k | - \dots - (- 1) n | A 1 \cap \dots \cap A n | .

$\begin{array}{l} | A_{1} \cup A_{2} \cup \dots \cup A_{n} | = \sum_{i} | A_{i} | - \sum_{} | A_{i} \cap A_{j} | + \\ \sum_{i < j < k} | A_{i} \cap A_{j} \cap A_{k} | - \dots - {(- 1)}^{n} | A_{1} \cap \dots \cap A_{n} | . \end{array}$

Obviously, every term on the right-hand side is needed to determine the size of the union. At this point we can ask whether it is possible to give an approximate inclusion-exclusion formula. More formally we ask:

Given integers m, n with m ≤ n and sets A₁, …, A_n and B₁, …, B_n where not all B_i are empty and where

∣ ∣ ∣ \cap i \in S A i ∣ ∣ ∣ = ∣ ∣ ∣ \cap i \in S B i ∣ ∣ ∣

$| \underset{i \in S}{\cap} A_{i} | = | \underset{i \in S}{\cap} B_{i} |$

for every subset S ⊆ {1, …,n} such that |S| < m, what is the smallest (or largest) possible value for the fraction

| A 1 \cup \dots \cup A n | | B 1 \cup \dots \cup B n | ?

$\frac{| A_{1} \cup \dots \cup A_{n} |}{| B_{1} \cup \dots \cup B_{n} |} ?$

The problem of approximate inclusion-exclusion is closely related to contrast bounds in visual cryptography schemes. For n-out-of-n and (n−1)-out-of-n scheme the solution of the approximate inclusion-exclusion problem translates directly to a contrast optimal visual cryptography scheme (see Theorem 4 for the details of the translation). Other applications of the approximate inclusion-exclusion are constant depth circuits and Boolean functions [15].

It is convenient to replace the size of the sets in the approximated inclusion exclusion problem by arbitrary measures to get a continuous problem. This leads to the following problem. Let (Ω, A, μ) be a measurable space and let A₁, …, A_n and B₁, …, B_n be measurable sets with

μ (\cap i \in S A i) = μ (\cap i \in S B i)

$μ (\underset{i \in S}{\cap} A_{i}) = μ (\underset{i \in S}{\cap} B_{i})$

for every subset S ⊆ {1, …, n} such that |S| < m, what is the smallest (or largest) possible value for the fraction

μ ( A 1 \cup \dots \cup A n ) μ ( B 1 \cup \dots \cup B n ) ?

$\frac{μ (A_{1} \cup \dots \cup A_{n})}{μ (B_{1} \cup \dots \cup B_{n})} ?$

Similarly to Lemma 1 we can restrict the approximate inclusion-exclusion problem to symmetric collections. With

x i = (n j) [μ (\cap j \in S A j \cap \cap j \notin S A j ¯ ¯ ¯ ¯) - μ (\cap j \in S B j \cap \cap j \notin S B j ¯ ¯ ¯ ¯)]

$x_{i} = (\begin{array}{l} n \\ j \end{array}) [μ (\underset{j \in S}{\cap} A_{j} \cap \underset{j \notin S}{\cap} \bar{A_{j}}) - μ (\underset{j \in S}{\cap} B_{j} \cap \underset{j \notin S}{\cap} \bar{B_{j}})]$

for |S| = i the approximate inclusion-exclusion problem leads to the linear program

Maximize: \sum i = 1 n x i (8.6)

$\begin{matrix} Maximize: & \sum_{i = 1}^{n} x_{i} \end{matrix} (8.6)$

subject to:

\sum i = j n (i j) x i = 0 for1 \leq j < m (8.7)

$\begin{matrix} \sum_{i = j}^{n} (\begin{matrix} i \\ j \end{matrix}) x_{i} = 0 & for1 \leq j < m \end{matrix} (8.7)$

- 1 \leq \sum i \in S x i \leq 1 for all S \subseteq {1, \dots, n} . (8.8)

$\begin{matrix} - 1 \leq \sum_{i \in S} x_{i} \leq 1 & for all S \subseteq {1, \dots, n} . \end{matrix} (8.8)$

(See [15] Lemma 3 for a proof).

Dualizing the linear program leads to the following problem of approximation theory (see [15] Lemma 5 and Section 8.6 where we use that technique to determine the asymptotic behavior of k-out-of-n schemes).

Determine

inf q max x = 1, \dots, n 1 - q (x) (8.9)

$inf_{q} max_{x = 1, \dots, n} 1 - q (x) (8.9)$

where the infimum ranges over all polynomials q of less than m that have zero constant terms and satisfies q(x) ≤ 1 for all x ∈ {1, …, n}.

The special case m = n leads to Krawtchuck polynomials (see [15] Theorem 3). But for this special case a elementary combinatorial proof exists (see [12]).

Theorem 3 Let A₁, …, A_n and B₁, …, B_n be two collections of sets satisfying

∣ ∣ ∣ \cap i \in S A i ∣ ∣ ∣ = ∣ ∣ ∣ \cap i \in S B i ∣ ∣ ∣

$| \underset{i \in S}{\cap} A_{i} | = | \underset{i \in S}{\cap} B_{i} |$

for all proper subsets S of {1, …, n}. Then

∣ ∣ \cup n i = 1 B i ∣ ∣ - ∣ ∣ \cup n i = 1 A i ∣ ∣ ∣ ∣ \cup n i = 1 B i ∣ ∣ \leq 1 2 n - 1 .

$\frac{| \cup_{i = 1}^{n} B_{i} | - | \cup_{i = 1}^{n} A_{i} |}{| \cup_{i = 1}^{n} B_{i} |} \leq \frac{1}{2^{n - 1}} .$

The bound is sharp.

Proof

We prove by induction on n that the conditions

∣ ∣ ∣ \cap i \in S A i ∣ ∣ ∣ = ∣ ∣ ∣ \cap i \in S B i ∣ ∣ ∣

$| \underset{i \in S}{\cap} A_{i} | = | \underset{i \in S}{\cap} B_{i} |$

for all S ⊊ {1, …, n} and the condition

∣ ∣ ∣ \cup i = 1 n A i ∣ ∣ ∣ + k = ∣ ∣ ∣ \cup i = 1 n B i ∣ ∣ ∣

$| \cup_{i = 1}^{n} A_{i} | + k = | \cup_{i = 1}^{n} B_{i} |$

with k > 0 imply that

∣ ∣ ∣ \cup i = 1 n B i ∣ ∣ ∣ \geq k 2 n - 1 .

$| \cup_{i = 1}^{n} B_{i} | \geq k 2^{n - 1} .$

For n = 1 this is trivial. Now suppose that the theorem holds for n and let the sets A₁, …, A_n₊₁ and B₁, …, B_n₊₁ satisfy

$| \underset{i \in S}{\cap} A_{i} | = | \underset{i \in S}{\cap} B_{i} |$

for all S ⊊ {1, …, n +1} and

$| \cup_{i = 1}^{n + 1} A_{i} | + k = | \cup_{i = 1}^{n + 1} B_{i} | .$

The collections A′_i = A_iA_n₊₁ and B′_i = B_iB_n₊₁ satisfy $| \cup_{i = 1}^{n} {A^{'}}_{i} | + k = | \cup_{i = 1}^{n} {B^{'}}_{i} |$ and for every proper subset S ⊊ {1, …, n} we have

$\begin{array}{l} | \underset{i \in S}{\cap} {A^{'}}_{i} | = | \underset{i \in S}{\cap} A_{i} | - | \underset{i \in S}{\cap} A_{i} \cap A_{n + 1} | \\ = | \underset{i \in S}{\cap} B_{i} | - | \underset{i \in S}{\cap} B_{i} \cap B_{n + 1} | = | \underset{i \in S}{\cap} {B^{'}}_{i} | . \end{array}$

Thus the collections A′_i, B′_i satisfy the induction hypothesis, i.e., we have $| \cup_{i = 1}^{n} {B^{'}}_{i} | \geq k 2^{n - 1}$ .

On the other hand, we have the collections A″_i = A_i ∩ A_n+1 and A″_i = B_i ∩ B_n₊₁. Since

$\begin{matrix} | \cup_{i = 1}^{n} A_{i} | = | \cup_{i = 1}^{n} B_{i} | \\ \Leftrightarrow | \cup_{i = 1}^{n} {A^{'}}_{i} | + | \cup_{i = 1}^{n} {A^{'}}^{'}_{i} | = t | \cup_{i = 1}^{n} {B^{'}}_{i} | + | \cup_{i = 1}^{n} {B^{'}}^{'}_{i} | \end{matrix}$

and $| \cup_{i = 1}^{n} {A^{'}}_{i} | + k = | \cup_{i = 1}^{n} {B^{'}}_{i} |$ we find that the collections A″_i and B″_i satisfy the induction hypothesis with $| \cup_{i = 1}^{n} {B^{″}}_{i} | + k = | \cup_{i = 1}^{n} {A^{″}}_{i} |$ . Thus, $| B_{n + 1} | = | A_{n + 1} | \geq | \cup_{i = 1}^{n} {A^{″}}_{i} | \geq k 2^{n - 1}$ . This proves

$| \cup_{i = 1}^{n + 1} B_{i} | = | \cup_{i = 1}^{n} {B^{'}}_{i} | + | B_{n + 1} | \geq k 2^{n - 1} + k 2^{n - 1} = k 2^{n}$

as desired.

To see that the bound is sharp consider the sets

$A_{i} = {S \subset {1, \dots, n} | | S | even, i \in S}$

and

$A_{i} = {S \subset {1, \dots, n} | | S | odd, i \in S} .$

Since for each nonempty set the number of subsets of even cardinality is trie same as the number subsets of odd cardinality $(0 = {(1 - 1)}^{n} = \sum_{j = 0}^{n} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}))$ we get

$| \underset{i \in S}{\cap} A_{i} | = | \underset{i \in S}{\cap} B_{i} | = 2^{n - | S | - 1}$

for each proper subset S of {1, …, n}. Hence, the sets A_i and B_i satisfies the requirement conditions of the approximate inclusion-exclusion problem and

$\frac{| \cup_{i = 1}^{n} B_{i} | - | \cup_{i = 1}^{n} A_{i} |}{| \cup_{i = 1}^{n} B_{i} |} = \frac{2^{n - 1} - (2^{n - 1} - 1)}{2^{n - 1}} = \frac{1}{2^{n - 1}},$

i.e., the bound given by the Theorem is sharp.□

Theorem 3 translates directly to an contrast optimal n-out-of-n visual cryptography scheme.

Theorem 4 (see [16]) The optimal contrast of a n-out-of-n visual cryptography scheme is α = 2¹⁻ⁿ and the minimal pixel-expansion is m = 2ⁿ⁻¹.

Proof

By Lemma 1 a n-out-of-n visual cryptography scheme can be described by two Boolean matrices M_W and M_B.

Interpret the row vectors of M_W and M_B as incidence vectors of the sets A_i and B_i.

The security requirement ((b) in Definition 1) says |∪_i_∈_S A_i| = |∪_i_∈_S B_i| for all proper subsets S of {1, …, n}. By the inclusion-exclusion formula this is equivalent to |∪_i_⊂_S A_i| = |∪_i_⊂_S B_i| for all proper subsets S of {1, …, n}. By Theorem 3 we have

$α = \frac{| \cup_{i = 1}^{n} B_{i} | - | \cup_{i = 1}^{n} A_{i} |}{| \cup_{i = 1}^{n} B_{i} |} \leq 2^{1 - n} .$

Vice versa the incidence vectors of sets solving the approximated inclusion-exclusion problem define a contrast optimal n-out-of-n visual cryptography scheme. Note that 1/α is also a lower bound for the pixel expansion m and the example shows that this bound is sharp. ☐

Using the proof technique of Theorem 3 one could also solve the approximate inclusion-exclusion problem for the case that only the size intersections of up to n − 2 sets are known.

Result 5 (see [12] Theorem 3.6) Let A₁, …, A_n and B₁, …, B_n be two collections of sets satisfying

$| \underset{i \in S}{\cap} A_{i} | = | \underset{i \in S}{\cap} B_{i} |$

for all proper subsets S of {1, …, n} with |S| ≤ n − 2. Then

$\frac{| \cup_{i = 1}^{n} A_{i} |}{| \cup_{i = 1}^{n} B_{i} |} \geq 1 - {(\begin{matrix} n - 1 \\ ⌊ \frac{n - 1}{2} ⌋ \end{matrix})}^{- 1} .$

The bound is sharp.

For the proof see [12]. At this point we show only the construction that proves the sharpness.

We give for every subset S ⊆ {1, …, n} the size

$\begin{matrix} | \underset{i \in S}{\cap} A_{i} \underset{i \notin S}{\cup} A_{i} | & and & | \underset{i \in S}{\cap} B_{i} \underset{i \notin S}{\cup} B_{i} | \end{matrix} .$

The construction is best understood if we look at the example n = 9 first.

In general we will have a zigzag line of numbers starting on the left side in the B-row with the value $⌊ \frac{n - 1}{2} ⌋$ , going down to 1, then has one gap and restart with 1. The general rule is as follows:

$| \underset{i \in S}{\cap} A_{i} \underset{i \notin S}{\cup} A_{i} | = {\begin{array}{l} | S | - ⌈ \frac{n}{2} ⌉ & if | S | > n / 2, and | S | is odd \\ ⌈ \frac{n}{2} ⌉ - | S | & if | S | < n / 2, and | S | is even \\ 0 & in all other cases \end{array} (8.10)$

$| \underset{i \in S}{\cap} B_{i} \underset{i \notin S}{\cup} B_{i} | = {\begin{array}{l} | S | - ⌈ \frac{n}{2} ⌉ & if | S | > n / 2, and | S | is even \\ ⌈ \frac{n}{2} ⌉ - | S | & if | S | < n / 2, and | S | is odd \\ 0 & in all other cases \end{array} (8.11)$

Some elementary combinatorial calculations ([12] Theorem 3.8) show that this example satisfies Result 5 with equality.

Similar to Theorem 4 we can use Result 5 to prove that the contrast α of the optimal (n−1)-out-of-n visual cryptography scheme satisfies $α \leq \frac{2}{n (\begin{matrix} n - 1 \\ ⌊ \frac{n - 1}{2} ⌋ \end{matrix})}$ . The example given above can be used to construct a scheme that satisfies the bound with equality (see [12] Theorem 3.10).

8.4 Designs and Codes

2-out-of-n visual cryptography schemes are a very special case. In a symmetric, contrast optimal scheme we encode a white pixel by giving all participants the same share. For a black pixel we want to minimize the overlap of black subpixels on the transparencies. This is a typical coding theory problem.

The link to coding theory becomes clear by comparing the following two theorems and their proofs.

Theorem 6 (Plotkin bound) A binary code of length n with minimal distance $d > \frac{1}{2} n$ has at most $2 ⌊ \frac{d}{2 d - n} ⌋$ codewords.

Proof

Let m be the number of codewords. Let A = ∑_c_≠_c_′ d(c, c′) where the sum ranges over all pairs of codewords. Since the code has minimal distance d the sum is bounded below by $(\begin{matrix} m \\ 2 \end{matrix})$ d.

Let m_i be the number of codewords that have 1 in the ith column. The contribution of those columns to the total distance A is m_i(m − m_i) ≤ ⌊m/2⌋ ⌈m/2⌉.

Hence, $⌊ m / 2 ⌋ ⌈ m / 2 ⌉ \geq A \geq \frac{1}{2} m (m - 1) d$ . For $d > \frac{1}{2} n$ this gives the bound stated by the Theorem. □

Theorem 7 ([3] Theorem 4.2) The contrast a of an 2-out-of-n visual cryptography scheme is bounded by

$α \leq \frac{⌈ n / 2 ⌉ ⌊ n / 2 ⌋}{n (n - 1)} = {\begin{array}{l} \frac{n}{4 n - 4} & f o r n e v e n \\ \frac{n + 1}{4 n} & f o r n o d d \end{array}$

Proof

Let m be the number of subpixels and α be the contrast. When stacking transparencies the fraction of black subpixels cannot become smaller. Thus, the number of black subpixels on each transparencies must be increased at least by am, i.e. for every transparency t₁ and every transparency t₂ there must be at least am subpixels that are write on t₁ and black on t₂. All pairs of transparencies give, therefore, at least n( n − 1) αm black-white subpixel combinations.

Now look at the number of black-white combinations that come from a single subpixel. If the subpixel is white on i transparencies and black on n − i transparencies it contributes i(n − i) black-white combinations. The term i(n − 1) is bounded by ⌊n/2⌋ ⌈n/2⌉.

This lead to the inequality

$n (n - 1) α m \leq ⌊ n / 2 ⌋ ⌈ n / 2 ⌉ m .$

Solving the inequality gives the theorem.

The bound of Theorem 7 is sharp and the contrast optimal 2-out-of-n schemes are related to designs. Let’s recall the definition of a 2 — (v, k, λ) design. (I recommend [1] as a reference for design theory.)

Definition 2 A 2 − (v,k, λ) design is a an incidence structure (V, B, I) with

|V| = v points
Every block B ∈ B is incident with k points.
Every pair of points p, q ∈ V is joined by exactly λ blocks.

Theorem 8 (see [3] Theorem 4.4) Let n be even. A 2-out-of-n visual cryptography scheme with optimal contrast $α = \frac{n + 1}{4 n}$ and pixel expansion m exists if and only if there exists a $2 - (n, \frac{n}{2}, \frac{m (n - 2)}{4 n - 4})$ design.

Proof

If we have equality in Theorem 7 we must have equality in every step.

Thus, for each two transparencies there are exactly am subpixels that are white on the first and black on the second transparency. Furthermore, each subpixel is black on exactly n/2 transparencies.

Let M_B be the Boolean matrix that describes the encoding of a black pixel. Interpret M_B as an incidence matrix of incidence structure (V, B, I) (Columns of M_B corresponds to block and rows of M_B to points.)

As we have seen above every block consists of $\frac{n}{2}$ points.

Since for every two transparencies the number of subpixels that is white on the first and black on the second is constant. Each transparency must have the same number of black subpixels. Since each subpixel is black on exactly half of the transparencies the number of black subpixels per transparency must be $\frac{m}{2}$ .

Thus, two transparencies have exactly $\frac{m}{2} = α m = \frac{m (n - 1)}{4 n - 4}$ common black subpixels In the interpretation as incidence structure: Each two points are joined by $\frac{m (n - 1)}{4 n - 4}$ blocks.

In other words M_B is the incidence matrix of a $2 - (n, \frac{n}{2}, \frac{m (n - 2)}{4 n - 4})$ design. Conversely the incidence matrix of a $2 - (n, \frac{n}{2}, \frac{m (n - 2)}{4 n - 4})$ design satisfies all requirements of a 2-out-of-n visual cryptography scheme. □

Similarly, we can deal with the case of n odd. The Proof of Theorem 7 shows that every column in M_B must contain either ⌊n/2⌋ or ⌈n/2⌉ zero entries. So we do not get a design (every block is of the same size), but a structure called pairwise balanced design (PDB) where the size of block may vary between some values. We skip the details and just state the final result.

Result 9 (see [3] Theorem 4.5) Let n he odd. A 2-out-of-n visual cryptography scheme with optimal contrast $α = \frac{n}{4 n - 4}$ and pixel expansion m exists if and only if there exists a $2 - (n, {\frac{n - 1}{2}, \frac{n + 1}{2}}, w - \frac{m (n + 1)}{4 n})$ PBD such that every point lies in exactly w blocks, where w is an integer in the range

$\frac{(n - 1) m}{2 n} \leq w \leq \frac{(n + 1) m}{2 n} .$

A well-known result from coding theory states that Hadamard codes archive equality in the Plotkin bound. So we are not surprised that Hadamard matrices can also be used to construct optimal 2-out-of-n visual cryptography schemes.

Recall the Definition of Hadamard matrices.

Definition 3 A Hadamard matrix is a n × n matrix H with entries ±1 and HH^t = nI.

It is well known that except for n = 1, 2 the order of a Hadamard matrix must be divisible by 4. The famous Hadamard conjecture states that for every n a (4n) × (4n) Hadamard matrix exists. See [8] for an overview of constructions of Hadamard matrices.

The connection to visual cryptography is established by the next theorem.

Theorem 10 (see [3] Theorem 4.7) The pixel expansion of a contrast optimal 2-out-of-(4n − 1) visual cryptography scheme is at least m ≥ 4n − 1. A scheme with m = 4n − 1 is equivalent to the existence of a 2 − (4n − 1, 2n − 1, n − 1) design (called a Hadamard design). This is equivalent to the existence of a Hadamard matrix of order 4n.

Proof

Let M_b be the matrix describing the encoding of a black pixel. As in the proof of Theorem 8 we find that each transparency must have the same number w of black subpixels and each two transparencies must share the same number λ < w of black subpixels. Interpret M_B as an integer matrix, then

$M_{B} M_{B}^{t} = (w - λ) I + λ J .$

This matrix has a full rank (det(w − λ)I + λJ = (w − λ)ⁿ⁻¹ (nλ − λ + w)) and hence,

$4 n - 1 = rank M_{B} M_{B}^{t} \leq {rankM}_{B} \leq m .$

(This is the Fisher’s inequality.)

Now assume m = 4n − 3 then w must be either 2n − 1 or 2n. In the first case every column of M_W must contain 2n − 1 entries 1 and M_W is the incidence matrix of a 2 − (4n − 1, 2n − 1, n − 1) design. In the second case every column of M_W must contain 2n entries 1 and M_W is the incidence matrix of a 2 − (4n − 1, 2n, n) design. But then the complement of M_W is the incidence matrix of a 2 − (4n − 1, 2n − 1, n − 1) design. This shows that a contrast optimal 2-out-of-(4n − 1) visual cryptography scheme with pixel expansion m = 4n − 3 implies the existence of a 2 − (4n − 1, 2n − 1, n − 1) design. But conversely you get a 2-out-of-(4n − 1) visual cryptography scheme from a 2 − (4n − 1, 2n − 1, n − 1) design by defining M_b to be the incidence matrix of the design and encode it with a pixel by choosing on all transparencies the same subpixels.

Now we prove that the existence of 2 − (4n − 1, 2n − 1, n − 1) design is equivalent to the existence of a Hadamard matrix of order 4n.

Multiplying a row or a column of a Hadamard matrix with −1 again gives a Hadamard matrix. So without loss of generality we may assume that the first row and the first column of a Hadamard matrix has only 1 as entries. Let H be a Hadamard matrix of order 4n in that normal from. All rows except the first row of H must contain 2n entries −1 and for two rows different rows must differ in exactly 2n columns. Hence, after deleting the first row and first column H forms the incidence matrix of a 2 − (4n − 1, 2n − 1, n − 1) design (with −1 instead of 0 to mark that a point is not incident with a block). Conversely the incidence matrix of a 2 − (4n − 1, 2n − 1, n − 1) becomes a Hadamard matrix, if one replaces all 0 by −1 and adds an extra column and an extra row that contains only 1.

Other 2-out-of-n visual cryptography schemes are also connected to Hadamard matrices.

Result 11 (see [3] Theorem 4.9) The minimal pixel expansion m of contrast optimal 2-out-of-n visual cryptography schemes satisfies:

$m \geq {\begin{array}{l} 2 n - n & i f n e v e n \\ n & i f n \equiv 3 & \mod 4 \\ 2 n & i f n \equiv 1 & \mod 4 \end{array}$

If the Hadamard conjecture is true the bounds are sharp.

We remark that there are 2-out-of-n visual cryptography schemes with smaller pixel-expansion that are not contrast optimal. In [3] (Theorem 4.12) 2-out-of-n visual cryptography schemes with pixel expansion $m \approx \sqrt{n}$ and contrast $α \approx \frac{1}{4}$ are constructed. For $n = (\begin{matrix} m \\ ⌊ m / 2 ⌋ \end{matrix})$ there exists a 2-out-of-n visual cryptography scheme with pixel expansion m and contrast 1/m (just color on each transparency is a different set of ⌊m/2⌋ subpixels). This is the minimal possible pixel expansion.

8.5 Optimal 3-out-of-n Schemes

We construct a scheme that has the normal form of Lemma 2. Remember that we denoted by $x_{i}^{(W)}$ the number of subpixels when encoding a white pixel that are black of the slides 1, …, i and white on the other slides. Similarly $x_{i}^{(B)}$ describes the encoding rule for a black pixel. As we have seen in the introduction, a k-out-of-n scheme must satisfy

$α m = \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(W)} - \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(B)} (8.12)$

and

$\sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(W)} - \sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(B)} (8.13)$

for j = 0, …, k − 1.

Let S(3, g, n) be the visual cryptography scheme that is described by the values $x_{0}^{(W)} = x_{n}^{(B)} = (\begin{matrix} n - 1 \\ g \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix}), x_{n - g}^{(W)} = x_{g}^{(B)} = 1$ and all other variables are 0.

Theorem 12 ([2] Theorem 4.6) S(3, g, n) is a 3-out-of-n visual cryptography scheme with pixel expansion m $= 2 (\begin{matrix} n - 1 \\ g \end{matrix})$ and contrast

$α = \frac{g (n - 2 g)}{2 (n - 1) (n - 2)} .$

Proof

For j = 0 we have in (8.13):

$(\begin{array}{l} n \\ 0 \end{array}) [(\begin{matrix} n - 1 \\ g \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix})] + (\begin{matrix} n \\ n - g \end{matrix}) \cdot 1 = (\begin{matrix} n \\ g \end{matrix}) \cdot 1 + (\begin{matrix} n \\ n \end{matrix}) [(\begin{matrix} n - 1 \\ g \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix})] = m$

For j = 1 we get

$(\begin{matrix} n - 1 \\ 0 \end{matrix}) [(\begin{matrix} n - 1 \\ g \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix})] + (\begin{matrix} n - 1 \\ n - g \end{matrix}) \cdot 1 = (\begin{matrix} n - 1 \\ g \end{matrix}) \cdot 1$

which is also true, since $(\begin{matrix} n - 1 \\ n - g \end{matrix}) = (\begin{matrix} n - 1 \\ g - 1 \end{matrix})$ . For j = 2 we get

$(\begin{matrix} n - 2 \\ 0 \end{matrix}) [(\begin{matrix} n - 1 \\ g \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix})] + (\begin{matrix} n - 2 \\ n - g \end{matrix}) \cdot 1 = (\begin{matrix} n - 2 \\ g \end{matrix}) \cdot 1$

which is true since $(\begin{matrix} n - 1 \\ g \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix}) = (\begin{matrix} n - 2 \\ g \end{matrix})$ and $(\begin{matrix} n - 2 \\ g \end{matrix}) + (\begin{matrix} n - 2 \\ n - g \end{matrix}) = (\begin{matrix} n - 2 \\ g \end{matrix}) + (\begin{matrix} n - 2 \\ q - 1 \end{matrix}) = (\begin{matrix} n - 2 \\ g \end{matrix})$ .

Thus, S(3, g, n) satisfies the security requirements of an 3-out-of-n visual cryptography scheme.

The contrast of S(3, g, n) is

$\begin{array}{l} α m & = (\begin{matrix} n - 3 \\ 0 \end{matrix}) [(\begin{matrix} n - 1 \\ g \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix})] + (\begin{matrix} n - 3 \\ n - g \end{matrix}) \cdot 1 - (\begin{matrix} n - 3 \\ g \end{matrix}) \cdot 1 \\ = (\begin{matrix} n - 2 \\ g \end{matrix}) + (\begin{matrix} n - 2 \\ g - 1 \end{matrix}) - (\begin{matrix} n - 1 \\ g - 1 \end{matrix}) + (\begin{matrix} n - 3 \\ g - 3 \end{matrix}) - (\begin{matrix} n - 3 \\ 3 \end{matrix}) \\ = (\begin{matrix} n - 3 \\ g - 1 \end{matrix}) - (\begin{matrix} n - 2 \\ g - 3 \end{matrix}) + (\begin{matrix} n - 3 \\ g - 3 \end{matrix}) \\ = (\begin{matrix} n - 3 \\ g - 1 \end{matrix}) - (\begin{matrix} n - 3 \\ g - 2 \end{matrix}) \end{array}$

So the image is indeed recovered.

The scheme S(3, g, n) archives optimal contrast if we choose $g = ⌊ \frac{n + 1}{4} ⌋$ . This is the best possible contrast for a 3-out-of-n scheme. To prove this result we introduce the canonical form of a k-out-of-n scheme.

Remember that a k-out-of-n scheme is described by the following linear program.

Maximize:

$α = \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(W)} - \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(B)} (8.14)$

Subject to

$\sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(W)} - \sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(B)} = 1 (8.15)$

and

$\sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(W)} = \sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(B)} (8.16)$

for j = 0, …, k − 1.

Lemma 13 There is an optimal solution of the linear program defined by (8.14), (8.15), and (8.16) that satisfies:

If k is even, then $x_{i}^{(W)} = x_{n - i}^{(W)}$ and $x_{i}^{(B)} = x_{n - i}^{(B)}$ for i = 0, …, n.
If k is odd, then $x_{i}^{(W)} = x_{n - i}^{(B)}$ for i = 0, …, n.
$x_{i}^{(W)} x_{i}^{(B)} = 0$ for all i ∈ {0, …, n}.

We will say the solution of the linear program is in a canonical form.

Proof

We first show that replacing each transparency of a k-out-of-n visual cryptography scheme by its complement again gives a solution of a k-out-of-n visual cryptography scheme. In the language of linear programming:

Let $x_{i}^{(W)}, x_{i}^{(B)}$ be a solution of the linear program (8.14)–(8.16). We claim that

${\hat{x}}_{i}^{(W)} = {\begin{array}{l} x_{n - i}^{(W)} & if k is even \\ x_{n - i}^{(B)} & if k is odd \end{array}$

and

${\hat{x}}_{i}^{(B)} = {\begin{array}{l} x_{n - i}^{(B)} & if k is even \\ x_{n - i}^{(W)} & if k is odd \end{array}$

is also a solution of the linear program.

Since $(\begin{matrix} n \\ i \end{matrix}) = (\begin{matrix} n \\ n - i \end{matrix})$ the variables ${\hat{x}}_{i}^{(W)} m {\hat{x}}_{i}^{(B)}$ satisfy (8.16).

We claim that equation 8.16 implies

$\sum_{i = 0}^{n - j} (\begin{array}{l} n - j \\ i - h \end{array}) x_{i}^{(W)} = \sum_{i = 0}^{n - j} (\begin{array}{l} n - j \\ i - h \end{array}) x_{i}^{(B)}$

for all h ≤ j. For j = 0 this is trivial and for j ≥ 1, h ≥ 1 it follows from $(\begin{matrix} n - j \\ i - h \end{matrix}) = (\begin{matrix} n - j + 1 \\ i - h + 1 \end{matrix}) - (\begin{matrix} n - j \\ i - h + 1 \end{matrix})$ by induction

$\sum_{i = 0}^{n - j} (\begin{array}{l} n - j + 1 \\ i - h + 1 \end{array}) x_{i}^{(W)} = \sum_{i = 0}^{n - j} (\begin{array}{l} n - j + 1 \\ i - h + 1 \end{array}) x_{i}^{(B)}$

and

$\sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i - h + 1 \end{matrix}) x_{i}^{(W)} = \sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i - h + 1 \end{matrix}) x_{i}^{(B)}$

To simplify the notation let us assume in the following that k is even.

When k is odd, it is necessary to exchange $x_{i}^{(W)}$ by $x_{i}^{(B)}$ and vice versa.

$\begin{array}{r} \sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) {\hat{x}}_{i}^{(W)} = \sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{n - i}^{(W)} \\ = \sum_{i = j}^{n} (\begin{matrix} n - j \\ n - i \end{matrix}) x_{i}^{(W)} \\ = \sum_{i = j}^{n} (\begin{matrix} n - j \\ n - i \end{matrix}) x_{i}^{(W)} \\ = \sum_{i = j}^{n} (\begin{matrix} n - j \\ n - i \end{matrix}) x_{i}^{(B)} \\ = \sum_{i = j}^{n - j} (\begin{matrix} n - j \\ n - i \end{matrix}) x_{i}^{(B)} \end{array}$

i.e., the variables ${\hat{x}}_{i}^{(W)} m {\hat{x}}_{i}^{(B)}$ satisfy (8.16).

By the same argument we get

$\sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i - h \end{matrix}) x_{i}^{(B)} + {(- 1)}^{h} α = \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i - h \end{matrix}) x_{i}^{(W)} (8.17)$

for h ≤ k.

For h = k this shows that ${\hat{x}}_{i}^{(W)} m {\hat{x}}_{i}^{(B)}$ is an optimal solution of the linear program.

Let $x_{i}^{(W)}, x_{i}^{(B)}, x_{i}^{(W)}$ and ${\hat{x}}_{i}^{(B)}$ be two solutions of the linear program, then ${\tilde{x}}_{i}^{(W)} = \frac{1}{2} (x_{i}^{(W)} + x_{i}^{(W)}), {\tilde{x}}_{i}^{(B)} = \frac{1}{2} (x_{i}^{(B)} + {\hat{x}}_{i}^{(B)})$ is also a solution of the linear program.

After this transformations we have a solution that satisfies (a) and (b).

Assume that we have a scheme that does not satisfy (c), i.e., the matrices M_W and M_B have columns in common. Since the corresponding subpixels occur independent of the encoded color they can be omitted. Deleting all columns that occur in M_W and M_B we get a scheme with smaller pixel expansion and higher contrast. That proves that every optimal k-out-of-n scheme must satisfy (c). □

Now we are ready to determine the optimal contrast of a 3-out-of-n visual cryptography scheme.

Theorem 14 ([2] Theorem 4.7) The contrast a of a 3-out-of-n visual cryptography scheme satisfies

$α \leq \frac{(n - 2 ⌊ \frac{n + 1}{4} ⌋) ⌊ \frac{n + 1}{4} ⌋}{2 (n - 1) (n - 2)}$

Proof

Assume that the scheme is in canonical form (see Lemma 13) and let M_W and M_B be the n × m Boolean matrices that describe the encoding.

Since the scheme is in canonical form, m is even and exactly $m^{'} = \frac{m}{2}$ subpixels on each slide are black. In terms of the linear program this means

$\sum_{j = 0}^{n - 1} x_{j}^{(W)} (\begin{matrix} n - 1 \\ j \end{matrix}) = \sum_{j = 0}^{n - 1} x_{j}^{(B)} (\begin{matrix} n - 1 \\ j \end{matrix}) = \frac{1}{2} . (8.18)$

By equation 8.17 (with h =1) the contrast α is

$α = \sum_{i = 0}^{n - k} (\begin{matrix} n - 3 \\ i - 1 \end{matrix}) x_{i}^{(B)} - \sum_{i = 0}^{n - k} (\begin{matrix} n - 3 \\ i - 1 \end{matrix}) x_{i}^{(W)}$

Since the scheme is in canonical form we have $x_{i}^{(W)} = x_{n - i}^{(B)}$ and hence,

$\begin{matrix} α = \sum_{i = 0}^{n - k} ((\begin{matrix} n - 3 \\ i - 1 \end{matrix}) x_{i}^{(B)} - (\begin{matrix} n - 3 \\ i - 1 \end{matrix}) x_{n - i}^{(B)}) \\ = \sum_{i = 0}^{n} x_{i}^{(B)} ((\begin{matrix} n - 3 \\ i - 1 \end{matrix}) - (\begin{matrix} n - 3 \\ n - i - 1 \end{matrix})) \\ = \sum_{i = 0}^{n} x_{i}^{(B)} ((\begin{matrix} n - 3 \\ i - 1 \end{matrix}) - (\begin{matrix} n - 3 \\ i - 2 \end{matrix})) \end{matrix}$

Now use equation (8.18) to multiply with 1 and we get

$α = \frac{\sum_{i = 0}^{n} x_{i}^{(B)} ((\begin{matrix} n - 3 \\ i - 1 \end{matrix}) - (\begin{matrix} n - 3 \\ i - 2 \end{matrix}))}{2 \sum_{i = 0}^{n} x_{i}^{(B)} (\begin{matrix} n - 1 \\ j \end{matrix})}$

The inequality $\frac{\sum_{x} f (x)}{\sum_{x} g (x)} \leq \max_{x} \frac{f (x)}{g (x)}$ holds for any functions f and g. Hence,

$α \leq \max_{0 \leq i \leq n} \frac{(\begin{matrix} n - 3 \\ i - 1 \end{matrix}) - (\begin{matrix} n - 3 \\ i - 2 \end{matrix})}{2 (\begin{matrix} n - 1 \\ j \end{matrix})}$

The maximum is reached for $i = ⌊ \frac{n + 1}{4} ⌋$ , which proves the theorem. □

In a recent article M. Bose and R. Mukerjee [5] show how to use group divisible designs and balanced incomplete block designs to construct 3-out-of-n visual cryptography schemes with optimal contrast and small pixel expansion.

8.6 Asymptotic Optimal k-out-of-n Schemes

In the previous sections we solved the problem of contrast optimal visual cryptography schemes exactly. The result for general k-out-of-n is a little bit weaker; we have only a tight bound for the optimal contrast.

We start with the linear program

Maximize:

$α = \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(W)} - \sum_{i = 0}^{n - k} (\begin{matrix} n - k \\ i \end{matrix}) x_{i}^{(B)}$

Subject to:

$\sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(W)} - \sum_{i = 0}^{n} (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(B)}$

and

$\sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(W)} = \sum_{i = 0}^{n - j} (\begin{matrix} n - j \\ i \end{matrix}) x_{i}^{(B)}$

for j = 0, …, k − 1. The sign conditions are $x_{i}^{(W)} \geq 0, x_{i}^{(B)} \geq 0$ .

For the following it is convenient to use the variable transform ${\hat{x}}_{i}^{(W)} = (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(W)}$ and ${\hat{x}}_{i}^{(B)} = (\begin{matrix} n \\ i \end{matrix}) x_{i}^{(B)}$ . The linear program takes the form

Maximize $α = c^{'} ({\hat{x}}^{(W)} - {\hat{x}}^{(B)})$ subject to

$\sum_{i = 0}^{n} {\hat{x}}_{i}^{(W)} = \sum_{i = 0}^{n} {\hat{x}}_{i}^{(B)} = 1$

and

$A ({\hat{x}}^{(W)} - {\hat{x}}^{(B)}) = 0$

where A is the k × (n +1) matrix with entries A = (a_j,i)

$a_{j, i} = (\begin{matrix} n - j \\ i \end{matrix}) {(\begin{matrix} n \\ i \end{matrix})}^{- 1} = q j (i)$

Note that the j-th row of A is the evaluation of a polynomial q_j of degree j at the positions i = 0, …, n. Similarly the vector c is the evaluation of k-th degree polynomial $p (i) = (\begin{matrix} n - k \\ i \end{matrix}) {(\begin{matrix} n \\ i \end{matrix})}^{- 1}$ at the places i = 0, …, n.

Now dualize the linear program. For each constraint we get a variable in the dual program and since all constraints of the primal program are equalities the variables in the dual program have no sign restriction. Each variable of the primal program gives a constraint in the dual program and since all variables have a sign condition we get inequalities as constraints in the dual program. The dual program is

Minimize s +t subject to

$A^{'} u + (s, \dots, s) \geq c (8.19)$

$\begin{matrix} A^{'} u + (t, \dots, t) \geq c & \Leftrightarrow & A^{'} - (t, \dots, t) \leq c \end{matrix} (8.20)$

Equations (8.19) and (8.20) just state that

$\begin{array}{l} s \geq \max_{i = 0, \dots, n} (c_{i} - {A^{'}}_{i} u) \\ t \geq \max_{i = 0, \dots, n} ({A^{'}}_{i} u - c_{i}) . \end{array}$

In the optimal solution these inequalities must be equalities, i.e.,

$s = \max_{i = 0, \dots, n} (c_{i} - {A^{'}}_{i} u) (8.21)$

$t = \max_{i = 0, \dots, n} ({A^{'}}_{i} u - c_{i}) . (8.22)$

Now we translate these equations into the language of polynomials. Remember that c_j = p(i) for a k-th degree polynomial and that the j-th row of A is the evaluation of a j-th degree polynomial q_j. The polynomials q_j (j = 0,…, k − 1) form a basis of the vector space P_k₋₁ of all polynomials of a degree up to k − 1.

So we may write the dual problem as:

Determine

$α = \min_{q \in P_{k - 1}} (\min_{i = 0, \dots, n} (p (i) - q (i)) + \max_{i = 0, \dots, n} (q (i) - p (i))) . (8.23)$

By adding the right constant to q, we can choose max_i=_0,…,_n(p(i) − q(i)) = max_i=_0,…,_n(q(i) − p(i)), which simplifies (8.23) to

$α = \min_{q \in P_{k - 1}} \max_{i = 0, \dots, n} | p (i) - q (i) | . (8.24)$

The low terms of p lie in P_k₋₁, so the problem is just to approximate the term of degree k. Since

$\begin{array}{l} p (i) = (\begin{matrix} n - k \\ i \end{matrix}) {(\begin{matrix} n \\ i \end{matrix})}^{- 1} \\ = \frac{(n - i)!}{(n - i - k)!} \frac{(n - k)}{n!} \\ = \frac{(n - i) (n - 1 - i) \dots (n - (k - 1) - i)}{n (n - 1) \dots (n - (k - 1))} \\ = (1 - \frac{i}{n}) (1 - \frac{i}{n - 1}) \dots (1 - \frac{i}{n - (k - 1)}) \end{array}$

the highest degree term of p(i) is ( − 1)^k/n^ki^k where n^k = n(n−1) ⋯ (n−k+1).

This simplifies (8.24) to

$α = \min_{q \in P_{k - 1}} \max_{i = 0, \dots, n} | \frac{x^{k}}{n^{\underline{k}}} - q (i) | . (8.25)$

Equation 8.25 is almost identical to the following classical problem in approximation theory:

$\min_{q \in P_{k - 1}} \max_{x \in [- 1, 1]} | x^{k} - q (x) | (8.26)$

The only difference is that the approximation points in our problem are discrete.

A well-known result from approximation theory states:

Result 15 (see for example Theorem 5.7 of [18]) Of all monic polynomials of degree k the best approximation to 0 in [−1, 1] with the ‖ ‖_∞-norm is 2¹−^kT_k, where T_k(x) = cos(k arccos x) denotes the Chebychev polynomial of the first kind.

Hence, the solution of (8.26) is

$q (x) = x^{k} - 2^{1 - k} T_{k} (x) .$

The minimum in (8.26) is 2^k⁻¹. Transforming it back to (8.25) we get an upper bound for a (only an upper bound since we switch from continuous evaluation points to discrete points.)

Thus, we have the contrast α_n,_k of a k-out-of-n visual cryptography scheme is bounded by:

$α_{n, k} \leq 4^{1 - k} \frac{n^{k}}{n^{\underline{k}}}$

Asymptotically continuous evaluation points and discrete evaluation points are the same, thus we have also

$\lim_{n \to \infty} α_{n, k} \leq \lim_{n \to \infty} 4^{1 - k} \frac{n^{k}}{n^{\underline{k}}} = 4^{1 - k} .$

Obtaining a lower bound for α_n,_k need a bit extra work. We just cite without proof.

Result 16 (see [14]) The contrast α_n,_k of a contrast optimal k-out-of-n visual secret sharing scheme satisfies

$4^{k - 1} \leq α_{n, k} \leq 4^{k - 1} \frac{n^{k}}{n^{\underline{k}}} .$

8.7 Contrast Trade-Offs for Extended Visual Cryptography Schemes

In this section we look at a visual cryptography scheme with extended capacity. In [16] Naor and Shamir show that it is possible to create two transparencies such that each transparency shows an image and the stack of the two transparencies reveals another image. The three images must not satisfy any relation.

In general, we have n slides and a subset $S$ of P({1,…,n}){∅}. For an $S$ -extended visual cryptography scheme we require that for every $S \in S$ the stack of the transparencies i ∈ S reveals an image I_S. Furthermore, we require that there is no other way to get information about the image I_S.

As in the case of the simple visual cryptography schemes we formalize these ideas by describing the encoding algorithm by a multiset of Boolean matrices. This leads to Definition 4.

Definition 4 Let $S \subseteq P ({1, \dots, n}) {\emptyset}$ .

An $S$ -extended visual cryptography scheme is described by multisets $M^{T}$ of n × m Boolean matrices for $T \subseteq S$ . (For given $T$ each Boolean matrix in $M^{T}$ describes the colors of the subpixels on each transparency, where the corresponding pixel in image I_t is black if and only if $T \in T$ . For encoding, each matrix in $M^{T}$ is chosen with the same probability.)

The multisets $M^{T}$ must satisfy the following conditions:

1. Let $B \in M^{T}$ . For ${i_{1}, \dots, i_{q}} \in S$ the Hamming weight of the OR of the rows i₁,…, i_q of B is $h_{{i_{1}, \dots, i_{q}}}$ if ${i_{1}, \dots, i_{q}} \in T$ and $l_{{i_{1}, \dots, i_{q}}}$ otherwise, i.e.,

$\begin{matrix} w_{H a m} ((b_{i 1,} 1, \dots, b_{i_{1}, m}) O R \dots O R (b_{i_{q}, 1 \dots,} b_{i_{q,} m})) \\ = {\begin{matrix} h_{{i_{1}, \dots, i_{q}}} & i f {i_{1}, \dots, i_{q}} \in ℐ \\ l_{{i_{1}, \dots, i_{q}}} & i f {i_{1}, \dots, i_{q}} \notin ℐ \end{matrix} \end{matrix}$

(This means stacking the transparencies i₁,…,i_q together we recover the image $I_{{i_{1}, \dots, i_{q}}}$ .)

2. For {i₁,…,i_q} ⊆ {1,…,n} and $T, T^{'} \subseteq S$ with $T \cap P ({i_{1}, \dots, i_{q}}) = T^{'} \cap P ({i_{1}, \dots, i_{q}})$ we obtain the same multisets if we restrict the matrices in $M^{T}$ and $M T^{'}$ , respectively, to the rowsi₁,…,i_q.

(This condition guarantees the security of the different images.)

If $S = P ({1, \dots, n}) {\emptyset}$ we simply call this an extended visual cryptography scheme.

$S$ -extended schemes exists as the following theorem shows.

Theorem 17 (see [9]) An $S$ -extended schemes with pixel expansion

$m = \sum_{S \in G} 2^{| S | - 1}$

and contrast α = 1/m exists

Proof

The $S$ -extended scheme is built from several k-out-of-k schemes. For each $S \in S$ we reserve 2^|^s^{| −1} subpixels. On slides with number i ∉ S these subpixels are colored black. For the slides i ∈ S these 2^|^S^{| −1} subpixels are used to construct an |S|-out-of-|S| visual cryptography scheme to encode the image I_S (see Theorem 4 for the construction).

To illustrate the construction let $S = {{1, 2}, {1, 3}}$ then m = 4. The first two pixels are used to encode the image I_{1,2} and the next two subpixels are for the image I_{1,2}.

A typical matrix of M^ø is

$M^{\emptyset} = (\begin{array}{l} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 \end{array})$

and a typical matrix of M^{{1,2}} is

$M^{\emptyset} = (\begin{array}{l} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \end{array}) .$

In the upper right corner you see the 2-out-of-2 scheme for the image I_{1,2}.

We claim that this construction yields an $S$ -extended scheme.

Let T ⊆ {1,…, n}, what happens if we stack the transparencies i ∈ T?

In the 2^|^T^|−1 subpixels associated with the image I_T we have |T|-out-of-|T| scheme and hence either all 2^|^T^|−1 subpixels in the stack are black or only 2^|^T^{| −1} −1 subpixels are black depending on the color in the image I_T.

For S ≠ T and T ⊈ S we find an i ∈ T with i ∉ S. On transparency i all 2^|^S^{| −1} subpixels associated with I_S are black. Hence, in the stack of the transparencies i ∈ T these 2 ^|^S^{| −1} subpixels are always black and do not contribute to the encoded color.

For S ≠ T and T ⊆ S we have a |S|-out-of-|S| scheme for the image I_S. By the security requirement stacking only the transparencies i ∈ T the number of black subpixels must be independent of the color of image I_S. (There will be exactly 2^|^S^{| −1} − 2^|^S^{| −|}^T^{| −1} black subpixels associated with the image I_S.)

As we can see, only the 2^|^T^{| −1} subpixels associated with the image I_T contribute to the image that we see when stacking the transparencies i ∈ T. Hence, the stack of the transparencies i ∈ T reveals image I_T.

Since the scheme is built from several standard k-out-of-k schemes, it inherits the security from the standard visual cryptography scheme. □

Similar to Lemma 1 we can restrict ourselves to the case that $M^{T}$ is the multiset that consists of all column permutations of a matrix $M^{T}$ .

For S ⊆ {1,…, n} we denote by $x_{s}^{T}$ the number of columns of $M^{T}$ that have a 1 in the rows i ∈ S and a zero in the rows i ∉ S. The number of black subpixels in the image I_S is either h_S (when a black pixel is encoded) or l_S when a white pixel is encoded. Analog to the linear program for ordinary visual cryptography we get

$M x^{ℐ} = r^{ℐ} (8.27)$

where $r^{T} = (r_{S}^{T}) \emptyset \neq S \subseteq {1, \dots, n}$ with $x_{S}^{T} = h_{S}$ if $S \in T$ and $r_{S}^{T} = l_{S}$ if $S \notin T$ .

The (2ⁿ − 1) × (2ⁿ − 1) matrix M = (m_S,T)_ø≠_S,T _⊆{1,…,_n_} is defined by m_S,T= 1 if S ∩ T ≠ ø and m_S,T= 1 otherwise.

It possible to solve the program explicitly and the starting point is the observation that M has an simple inverse.

Lemma 18 The matrix M = (m_S,T)_ø≠_S,T _⊆{1,…,_n_} with m_S,T = 1 if S ∩ T ≠ ø and m_S,T = 0 otherwise is invertible and M⁻¹ has only the entries ±1 and 0 .

Proof

We prove this by induction on the number n of transparencies.

Sort the variables x_T by the following order: First, we enumerate all subsets that do not contain n. The next subset is the set {n}. Then, the other subsets containing n follow.

Writing M₁ = (1), we obtain the following recursion formula that follows directly from the definition:

$M_{n + 1} = (\begin{matrix} M_{n} & 0_{n, 1} & M_{n} \\ 0_{1, n} & 1 & 1_{1, n} \\ M_{n} & 1_{n, 1} & 1_{n, n} \end{matrix}) .$

Here the index denotes the number of transparencies. 0_i,j or 1_i,j, respectively, denoting a (2ⁱ − 1) × (2^j − 1) matrix with all entries 0 or 1, respectively.

With $M_{1}^{- 1} = (1)$ we obtain the following recursion formula for $M_{n}^{- 1}$ :

$M_{n + 1}^{- 1} = (\begin{matrix} 0_{n, n} & - M_{n}^{- 1} 1_{n, 1} & M_{n}^{- 1} \\ - 1_{1, n} M_{n}^{- 1} & 0 & 1_{1, n} M_{n}^{- 1} \\ M_{n}^{- 1} & M_{n}^{- 1} 1_{n, 1} & - M_{n}^{- 1} \end{matrix}) .$

Thus, M is invertible, i.e., Equation (8.27) has a unique solution.

We notice that the components of $M_{n}^{- 1} 1_{n, 1}$ are only −1, 0, and 1 and that $1_{1, n} M_{n}^{- 1} 1_{n, 1} = 1$ . Then the formula can be proved by induction.

Thus, $M_{n}^{- 1}$ contains only the entries −1, 0, and 1 and therefore the solution of equation (8.27) is integral. □

By Lemma 18 the solution $x^{T}$ of equation (8.27) is an integer vector if the right-hand side $r^{T}$ is an integer vector.

We can explicitly solve equation (8.27) by multiplying with M⁻¹ and get:

$x_{S}^{ℐ} = \sum_{{1, \dots n} S \subseteq T \subseteq {1, \dots n}} {(- 1)}^{| T | + | S | + n + 1} r_{T}^{ℐ} (8.28)$

To verify equation (8.28) we can plug in the values of $x_{S}^{T}$ in equation (8.27). The calculation is elementary and uses only the identity

$\sum_{i = 0}^{n} {(- 1)}^{i} (\begin{matrix} n \\ i \end{matrix}) = {\begin{matrix} 1 & for n = 0 \\ 0 & for n > 0 \end{matrix} .$

In a solution of an extended visual cryptography scheme every $x_{S}^{T}$ must be nonnegative. This leads to

$\sum_{S \subseteq T \subseteq {1, \dots n}} {(- 1)}^{| S | + | T |} r_{T}^{ℐ} \leq 0 (8.29)$

for all possible subsets $T of P ({1, \dots, n}) {\emptyset}$ .

In left-hand side of inequality (8.29) we have the sum over r_T for |S| + |T| even and over −r_T for |S| + |T| odd. This becomes maximal if all r_T with |S| + |T| even are as large as possible (i.e., equal h_T) and all r_t with |S| + |T| odd are as small as possible (i.e., equal l_T).

Thus, an extended visual cryptography scheme exists if and only if

$\sum_{\begin{array}{l} S \subseteq T \subseteq {1, \dots n} \\ | S | \equiv | T | \mod 2 \end{array}} h_{T} \leq \sum_{\begin{array}{l} S \subseteq T \subseteq {1, \dots, n} \\ | S | \neq | T | \mod 2 \end{array}} l_{T} (8.30)$

holds for each S ⊊ {1,…, n}.

The linear program given by equation (8.30) is very simple and can be solved directly.

Theorem 19 ([13] Theorem 3.4) An extended visual cryptography scheme with n transparencies needs at least $\frac{1}{2} (3^{n} - 1)$ subpixels. Hence, the construction of Theorem 17 is optimal with respect to the pixel expansion, i.e.,

$M (p ({1, \dots, n}) {\emptyset}) = \frac{1}{2} (3^{n} - 1) .$

Proof

For each ø ≠ T ⊆ {1,…, n}, let δ_T = h_T − l_T. Our goal is to prove that equation (8.30) implies

$m \geq h_{{1, \dots n}} \geq \sum_{\emptyset \neq T \subseteq {1, \dots, n}} δ_{T} 2^{| T | - 1} . (8.31)$

As the first step in this proof we show that, for given values δ_T (for ø ≠ T ⊆ {1,…,n}), the number h{1,…,n} is minimal if for all S ⊊ {1,…,n} inequality (8.30) is satisfied with equality.

To this end, suppose

$\begin{matrix} \sum h_{T} < & \sum l_{T} \\ S \subseteq T \subseteq {1, \dots, n} & S \subseteq T \subseteq {1, \dots, n} \\ | S | \equiv | T | mod 2 & | S | \equiv | T | mod 2 \end{matrix}$

for some S ⊊ {1,…,n}. But the contrast levels

${\bar{h}}_{T} = {\begin{matrix} h_{T} & for T \subseteq S \\ h_{T} - 1 & othrrwise \end{matrix}$

and

${\bar{l}}_{T} = {\begin{matrix} l_{T} & for T \subseteq S \\ l_{T} - 1 & othrrwise \end{matrix}$

satisfy (8.30), since

$\begin{array}{l} | {T | S \subseteq T \subseteq {1, \dots, n}; | T | \equiv | S | mod 2} | \\ | {T | S \subseteq T \subseteq {1, \dots, n}; | T | \equiv | S | mod 2} | . \end{array}$

This proves that if inequality (8.30) is not satisfied with equality we can find smaller values for the parameters l_T and h_T, which also satisfy (8.30). Thus, in an optimal scheme (i.e., a scheme with the smallest possible values for l_T and h_T) inequality (8.30) is satisfied with equality for each T ⊊ {1,…, n}.

Next we claim that

$h t = \sum_{\emptyset \neq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} 2^{| T^{'} | - 1} - \sum_{T \subseteq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} 2^{| T^{'} | - 1 - | T |} (8.32)$

for ø ≠ S ⊆ {1,…, n} satisfy (8.30) with equality.

To prove this we have to show that

$\begin{array}{l} \begin{array}{l} \sum_{\begin{matrix} S \subseteq T \subseteq {1, \dots, n} \\ | S | \equiv | T | mod 2 \end{matrix}} [\sum_{\emptyset \neq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} 2^{| T^{'} | - 1_} \sum_{T \subseteq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} 2^{| T^{'} | - 1 - 1 | T |}] = \\ \sum_{\begin{matrix} S \subseteq T \subseteq {1, \dots, n} \\ | S | \equiv | T | mod 2 \end{matrix}} ([\sum_{\emptyset \neq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} 2^{| T^{'} | - 1_} \sum_{T \subseteq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} 2^{| T^{'} | - 1 - 1 | T |}] - δ_{T}) \end{array} \end{array}$

or equivalently

$\begin{matrix} \sum_{\emptyset \neq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} [\sum_{\begin{matrix} S \subseteq T \subseteq {1, \dots, n} \\ | S | \equiv | T | mod 2 \end{matrix}} 2^{| T^{'} | - 1_} \sum_{\begin{matrix} S \subseteq T \subseteq T' \\ | S | \equiv | T | mod 2 \end{matrix}} 2^{| T^{'} | - 1 - | T |}] = \\ \sum_{\emptyset \neq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} [\sum_{\begin{matrix} S \subseteq T \subseteq {1, \dots, n} \\ | S | \equiv | T | mod 2 \end{matrix}} 2^{| T^{'} | - 1_} \sum_{\begin{matrix} S \subseteq T \subseteq T' \\ | S | \equiv | T | mod 2 \end{matrix}} 2^{| T^{'} | - 1 - | T |}] + δ_{T^{'}} \frac{{(- 1)}^{| T' | + | S |_1}}{2} . \end{matrix}$

(Note that the last summand is equal to −δ_T, for |T’| ≢ |S| mod 2 and equal to 0 otherwise.)

Comparing coefficients for each (δ_T, we obtain

$\begin{array}{l} 2^{n - | S | - 1} \cdot 2^{| T^{'} | - 1} - \sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | S | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - 1 - | T |} = \\ 2^{n - | S | - 1} \cdot 2^{| T^{'} | - 1} (\sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | S | \neq | T | \mod 2 \end{matrix}} 2^{| T^{'} | - 1 - | T |}) + \frac{{(- 1)}^{| T^{'} | + | S |} - 1}{2}, \end{array} (8.33)$

but this is true since

$\begin{array}{l} {(- 1)}^{| T^{'} | - | S |} = {(1 - 2)}^{| T^{'} | - | S |} \\ = \sum_{i = 0}^{| T^{'} | - | S |} (\begin{matrix} | T^{'} | - | S | \\ i \end{matrix}) {(- 2)}^{i} \\ = \sum_{\begin{matrix} i = 0 \\ i even \end{matrix}}^{| T^{'} | - | S |} (\begin{matrix} | T^{'} | - | S | \\ i \end{matrix}) 2^{i} - \sum_{\begin{matrix} i = 0 \\ i odd \end{matrix}}^{| T^{'} | - | S |} (\begin{matrix} | T^{'} | - | S | \\ i \end{matrix}) 2^{i} \\ = \sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - | S |_} \sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - | S |} \\ , since (\begin{matrix} | T^{'} | - | S | \\ i \end{matrix}) = \sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | - | S | = i \end{matrix}} 1. \end{array}$

Thus,

$\sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - | T |} = (\sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - | T |}) + {(- 1)}^{| T^{'} | - | S |}$

and therefore,

$(\sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - | T |}) + 1 = (\sum_{\begin{matrix} S \subseteq t 3 T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - | T |}) + {(- 1)}^{| T^{'} | + | S |} .$

(Note that (−1)^|^T′^| − ^|^S^| = (−1)^|^T′^|+|^S^|.) Division by 2 gives

$(\sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - 1 - | T |}) = (\sum_{\begin{matrix} S \subseteq T \subseteq T^{'} \\ | T^{'} | \equiv | T | \mod 2 \end{matrix}} 2^{| T^{'} | - 1 - | T |}) + \frac{{(- 1)}^{| T^{'} | + | S |} - 1}{2}$

as required for equation (8.33).

Suppose that ${\bar{h}}_{T} (for \emptyset \neq T \subseteq {1, \dots, n})$ satisfy (8.30) with equality, too.

If inequality (8.30) is satisfied with equality for all subsets S, we can solve these equations recursively and get

$h_{S} = h_{{1, \dots, n}} + F_{S} (δ_{T} | T \subseteq {1, \dots, n}),$

for some function F_S Since inequality (8.30) is satisfied with equality for the contrast values h_T and h′_T this yields

${\bar{h}}_{S} = h_{S} + {\bar{h}}_{{1, \dots, n}} - h_{{1, \dots, n}} .$

But for S = ø inequality (8.30) yields $\begin{matrix} \bar{h} {1, \dots, n} & = & h {1, \dots, n} \end{matrix}$ and therefore $\begin{matrix} {\bar{h}}_{T} & = & h_{T} \end{matrix}$ for all $\emptyset \neq T \subseteq {1, \dots, n}$ .

This proves that (8.32) is the only solution of (8.30) that satisfies all inequalities with equality.

Thus, we find

$m \geq h_{{1, \dots, n}} \geq \sum_{\emptyset \neq T^{'} \subseteq {1, \dots, n}} δ_{T^{'}} 2^{| T^{'} | - 1} \geq \sum_{\emptyset \neq T^{'} \subseteq {1, \dots, n}} 2^{| T^{'} | - 1} = \frac{1}{2} (3^{n} - 1)$

what proves the theorem. □

Without proof we mention the following result about the contrast of the different images.

Result 20 ([13] Theorem 3.6) For ø ≠ T ⊆ {1,…,n} let $α_{T} = \frac{h_{T} - l_{T}}{m}$ be the contrast of the image I_t. The contrast levels of the images satisfy

$\sum_{\emptyset \neq T \subseteq {1, \dots, n}} 2^{| T | - 1} α T \leq 1. (8.34)$

Further, let α′_T ≥ 0 (for ø ≠ T ⊆ {1,…,n}) satisfy (8.34). Then for every ɛ > 0 there exists a generalized visual cryptography scheme with contrast levels α_T (for ø ≠ T ⊆ {1,…,n}) where |α_T − α′_T| < ɛ for all nonempty subsets T of {1,…,n}.

The situation becomes more complicated if we no longer require that all combinations of transparencies reveal an image. The only case that is completely solved is Result 21.

Result 21 ([13] Theorem 4.4) Let $S = O ({1, \dots, n}) {\emptyset, {1, \dots, n}}$ then the minimal pixel expansion m is given by

$m = {\begin{array}{l} \frac{1}{2} (3^{n} - 1) - 2^{n - 1} - 1 f o r n e u e n \\ \frac{1}{2} (3^{n} - 1) - 2^{n - 1} f o r n o d d \end{array} .$

8.8 Enhancing the Contrast by Nonstandard Models

All results in this chapter worked with the original model of visual cryptography as defined in [16]. In several papers extended models were discussed. Without going into details we mention:

In [19] the authors run an edge-detecting algorithm on the original image and use a higher number of subpixels on the edges for improved contrast.
Several authors studied colored visual cryptography (see [6, 17, 20, 7] and Chapter 7 of [11]). One can use additive and subtractive color mixing in combination to obtain good results. A possible variation of the classical 2-out-of-2 scheme replace the white and black subpixels by any two opposing colors.
It was also suggested to use polarization filters of different orientations to encrypt an image.
A interesting variation is the segment based visual cryptography [4]. For a 7-segment display an image may be encoded as:
In [10] the authors note that the contrast definition $α = \frac{h - l}{m}$ of Naor and Shamir do not always fit the human intuition. They suggest variations like $\frac{h - l}{h + l}$ and show how to optimize visual cryptography schemes with respect to the new goal.

8.9 Conclusion

We constructed contrast optimal visual cryptography schemes for various access structures. The constructions exhibit links to different fields like linear programming, approximation theory, the theory of error correcting codes, design theory, and elementary combinatorics.

Bibliography

[1] T. Beth, D. Jungnickel, and H. Lenz. Design Theory. Cambridge University Press, 1985.

[2] C. Blundo, P. D’Arco, A. De Santis, and D. R. Stinson. Contrast optimal threshold visual cryptography schemes. SIAM J. Discrete Math., 16(2):224–261 (electronic), 2003.

[3] C. Blundo, A. De Santis, and D. R. Stinson. On the contrast in visual cryptography schemes. J. Cryptology, 12((4):261–289, 1999.

[4] B. Borchert. Segment-based visual cryptography. Technical report, 17 Wilhelm-Schickard-Institut für Informatik, Univeristät Tübingen, 2007. http://w210.ub.uni-tuebingen.de/volltexte/2007/3048/.

[5] M. Bose and R. Mukerjee. Optimal (n, k) visual cryptography schemes for general k. Des. Codes Cryptogr., 55:19–35, 2010.

[6] S. Cimato, R. De Prisco, and A. De Santis. Optimal colored threshold visual cryptography schemes. Des. Codes Cryptogr., 35((3):311–335, 2005.

[7] S. Cimato, R. De Prisco, and A. De Santis. Colored visual cryptography without color darkening. Theoret. Comput. Sci., 374(1-3):261–276, 2007.

[8] R. Craigen. Hadamard matrices and designs. In C. J. Colbourn and J. H. Dinitz, editors, The CRC Handbook of Combinatorial Designs, pages 370–380. CRC Press, Boco Raton, New York, London, Tokyo, 1996.

[9] S. Droste. New results in visual cryptography. In Advances in cryptology – CRYPTO ’96, volume 1109 of Lect. Notes Comput. Sci., pages 401–415. Springer, Berlin, 1996.

[10] P. A. Eisen and D. R. Stinson. Threshold visual cryptography schemes with specified whiteness levels of reconstructed pixels. Des. Codes Cryptogr., 25((1):15–61, 2002.

[11] A. Klein. Visuelle Kryptographie. Springer-Verlag, Berlin, 2007.

[12] A. Klein and K. Metsch. On approximate inclusion-exclusion. Innov. Incidence Geom., 67:249–270, 2007/2008.

[13] A. Klein and M. Wessler. Extended visual cryptography schemes. Information and Computation, 205((5):716–732, 2007.

[14] M. Krause and H. U. Simon. Determining the optimal contrast for secret sharing schemes in visual cryptography. Combin. Probab. Comput., 12((3):285–299, 2003. Combinatorics, probability and computing (Oberwolfach, 2001).

[15] N. Linial and N. Nisan. Approximate inclusion-exclusion. Combinatorica, 10((4):349–365, 1990.

[16] M. Naor and A. Shamir. Visual cryptography. In Alfredo De Santis, editor, Advances in cryptology - EUROCRYPT '’94, volume 950 of Lect. Notes Comput. Sci., pages 1–12. Springer-Verlag, 1995.

[17] E. R. Verheul and H. C. A. van Tilborg. Constructions and properties of k out of n visual secret sharing schemes. Des. Codes Cryptogr., 11((2):179–196, 1997.

[18] G. A. Watson. Approximation Theory and Numerical Methods. John Wiley & Sons, 1980.

[19] C.N. Yang and T.S. Chen. Visual secret sharing scheme: Improving the contrast of a recovered image via different pixel expansions. In A. Campilho and M. Kamel, editors, ICIAR 2006, volume 4141 of LNCS, pages 468–479, Berlin Heidelberg, 2006. Springer-Verlag.

[20] C.N. Yang and C.S. Laih. New colored visual secret sharing schemes. Des. Codes Cryptogr., 20((3):325–336, 2000.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 8 Visual Cryptography and Contrast Bounds

Create new playlist

Sign In

Sign Up

Table of Contents for
8 Visual Cryptography and Contrast Bounds