Cryptography Reference
In-Depth Information
This simplifies (8.24) to
:
x k
n k q(i)
=
min
q2P k1
max
i=0;:::;n
(8.25)
Equation 8.25 is almost identical to the following classical problem in ap-
proximation theory:
jx k q(x)j
min
q2P k1
max
x2[1;1]
(8.26)
The only difference is that the approximation points in our problem are dis-
crete.
A well-known result from approximation theory states:
Result 15 (see for example Theorem 5.7 of [18]) Of all monic polyno-
mials of degree k the best approximation to 0 in [1; 1] with the k:k 1 -norm
is 2 1k T 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 1k T k (x) :
The minimum in (8.26) is 2 k1 . Transforming it back to (8.25) we get an
upper bound for (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 4 1k n k
n k
Asymptotically continuous evaluation points and discrete evaluation points
are the same, thus we have also
n!1 4 1k n k
n k = 4 1k :
n!1 n;k lim
lim
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 vi-
sual secret sharing scheme satisfies
4 k1 n;k 4 k1 n k
n k :
 
Search WWH ::




Custom Search