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

8.6 Asymptotic Optimalk-out-of-nSchemes
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:

nk
i

nk
i

n X n X

x (W)
i

x (B)
i

=

i=0 i=0

Subject to:

n
i

n
i

X X

x (W)
i

x (B)
i

= = 1

i=0 i=0

and

nj
i

nj
i

n X n X

x (W)
i

x (B)
i

=

i=0 i=0

for j = 0;:::;k 1. The sign conditions are x (W)

i 0, x (B i 0.
For the following it is convenient to use the variable transform x (W)
i

=

i x (W)

i

x (B i . The linear program takes the form
Maximize = c 0 (x (W) x (B) ) subject to

= i

and x (B)
i

X X

x (W)
i

x (B)
i

= = 1

i=0 i=0

and

A(x (W) x (B) ) = 0

where A is the k (n + 1) matrix with entries A = (a j;i )

nj
i

n
i

1

a j;i = = 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) = nk
i

i 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