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