Visual Cryptography and Contrast Bounds - Visual Cryptography and Secret Image Sharing - page 242

We can explicitly solve equation (8.27) by multiplying with M 1

and get:

X

x T S = (1) jTj+jSj+n+1 r T T

(8.28)

f1;:::;ngnSTf1;:::;ng

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

( 1

(1) i n
i

X

for n = 0

=

for n > 0 :

0

i=0

In a solution of an extended visual cryptography scheme every x T S must be
nonnegative. This leads to

X

(1) jSj+jTj r T T 0

(8.29)

STf1;:::;ng

for all possible subsetsTof P(f1;:::;ng)nf;g.
In left-hand side of inequality (8.29) we have the sum over rT T for jSj+jTj
even and over r T for jSj + jTj odd. This becomes maximal if all r T with
jSj+jTj even are as large as possible (i.e., equal h T ) and all r t with jSj+jTj
odd are as small as possible (i.e., equal lT T ).
Thus, an extended visual cryptography scheme exists if and only if
X X

h T l T (8.30)

STf1;:::;ng
jSjjTj mod 2

STf1;:::;ng
jSj6jTj mod 2

holds for each S(f1;:::;ng.
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

2 (3 n 1) subpixels. Hence, the construc-
tion of Theorem 17 is optimal with respect to the pixel expansion, i.e.,

1

1
2 (3 n 1) :

M(P(f1;:::;ng)nf;g) =

Proof
For each ; 6= T f1;:::;ng, let T = h T l T . Our goal is to prove that
equation (8.30) implies

X

T 2 jTj1 m h f1;:::;ng : (8.31)

;6=Tf1;:::;ng

As the first step in this proof we show that, for given values T (for ; 6=