Cryptography Reference
In-Depth Information
for all minimal qualified subsets G.
The equations (8.1) and (8.2) lead to the linear program. Replace (8.1) by
X
+
X
Sf1;:::ng
S\T6=0
x
(W)
s
x
(B)
s
Sf1;:::ng
S\T6=0
and require
X
x
(B
s
=
X
Sf1;:::ng
x
(W)
s
= 1
Sf1;:::ng
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 pre-
pared such a program for my book [11]. You can download it from my home-
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 cryp-
tography scheme constructed in Lemma 1.
For every row permutation the matrices M
W
and M
B
also describe a
k-out-of-n visual cryptography scheme.
Let M
W
be the n (mn!) matrix that consists of all row permutations
M
W
of M
W
written after each other. Similarly define M
B
. 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
W
and M
B
satisfy the permutation
invariance stated in the Lemma.
2
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
0
and x
(W)
= x
(W)
S
0
for jSj = jS
0
j. Let for i 2 f0;:::;ng be
S
x
(B)
i
= x
(B)
f1;:::;ig
and x
(W)
= x
(W)
f1;:::;ig
.
The linear program simplifies to:
i
n
i
n
i
X
X
x
(W)
i
x
(B)
i
=
= 1
(8.3)
i=0
i=0
This equation express that the variables denotes the fractions of black sub-
pixels and that all fractions add up to 1.
nj
i
nj
i
n
X
n
X
x
(W)
i
x
(B)
i
=
(8.4)
i=0
i=0
Search WWH ::
Custom Search