<<

. 3
( 3 .)



egories: static and dynamic. Static heuristics go
through a ¬le, analyzing its structure and looking Pavan Verma
652 Visual secret sharing schemes


References recovers the secret by stacking their transparen-
cies (called shares) and setting s = 1 if the stack
is “suf¬ciently” black. The latter means calculat-
[1] Adleman, L. (1988). “An abstract theory of
ing the number c of black subpixels in the stack,
computer viruses.” Advances in Cryptology”
CRYPTO™88, Lecture Notes in Computer Science, i.e., the Hamming weight (see cyclic codes) of the
vol. 403, ed. S. Goldwasser. New York, NY, 354“ stack, and comparing it with some threshold.
374. Note that stacking transparencies is equivalent
[2] The CERT Coordination Center. http://www.cert to evaluating the OR of the corresponding Boolean
.org
vectors bi = (bi,1 , . . . , bi,m ) or wi = (wi,1 , . . . , wi,m ).
[3] Cohen, F. (1986). “Computer Viruses.” PhD Thesis,
For the most interesting case of a visual (n, k)
University of Southern California.
threshold scheme where any set of k or more par-
[4] Cohen, F. (1989). “Practical defenses against com-
ticipants can recover the secret “visually” (see
puter viruses.” Computers and Security, 8 (2), 149“
Conditions 1 and 2 below), while any set of less
160.
than k participants gains no additional, i.e., a pos-
[5] Denning, P. (1990). Computers Under Attack:
teriori, information about the secret (see Condi-
Intruders, Worms and Viruses. Addison-Wesley,
Reading, MA. tion 3 below) the formal de¬nition is the follow-
[6] Duff, T. (1989). “Experience with viruses on UNIX ing [1].
systems.” Computing Systems, 2 (2). Two collections B and W of n — m binary ma-
[7] Israel, H. (1987). “Computer viruses: Myth or real- trices are called (n, k) VSSS if the following three
ity?” Tenth National Computer Security Conference
conditions are met:
Proceedings, 238“244.
1. For any B ∈ B, the OR of any k of the n rows of
[8] McAfee Security. http://www.mcafee.com
B has Hamming weight of at least d1 .
[9] Network Associates Technology, Inc. http://www
2. For any W ∈ W, the OR of any k of the n rows
.nai.com
of W has Hamming weight of at most d0 .
[10] Staniford, Stuart, Vern Paxson, and Nicholas
3. For any subset {i1 , . . . , il } ‚ {1, . . . , n} with l <
Weaver (2002). “How to own the Internet in your
k, the two collections obtained by restricting
spare time.” Proceedings of the 11th USENIX Se-
each matrix in B and W to the rows i1 , . . . , il are
curity Symposium.
[11] Symantec Corporation. http://www.symantec.com indistinguishable in the sense that they contain
[12] Viruslist.com. http://www.viruslist.com/eng/ the same matrices with the same frequencies.
[13] VX Havens. http://vx.netlux.org/index.shtml The value ± = (d1 ’ d0 )/m is called the contrast
of the VSSS. Two other important parameters of
VSSS are:
r m, the number of subpixels in a share, or length
VISUAL SECRET SHARING of VSSS;
r
SCHEMES r, the number of matrices in collections B and W.
Obviously the contrast should be suf¬ciently
large while keeping m and r as small as it pos-
Visual secret sharing schemes (VSSS, for short-
sible. Construction of a VSSS turned out to be a
ness) were introduced in 1995 [1]. They form a
much more complicated problem than that of an
particular case of secret sharing schemes with the
ordinary SSS, even for the case of threshold (n, k)-
additional restriction that allowed (also called
schemes.
privileged or trusted in access structure) coalitions
For the simplest case of an (n, n) threshold
can recover the secret by visual means.
scheme, the optimal visual version consists of all
More precisely, consider the case when just one
2n’1 ! permutations of the columns of the n — 2n’1
bit of visual information, i.e., a black or white
matrix W, which columns of W are all binary vec-
pixel, has to be distributed as a secret s among
n
tors x = (x1 , . . . , xn ) with i=1 xi = 0 (mod 2) (in
n participants of VSSS. To realize this, the dealer
words, W is the code book of the (n, n ’ 1) even-
uses two sets B and W of binary (Boolean) n — m
weight code de¬ned by a single overall parity-
matrices in the following way. To distribute a
“black” secret (s = 1), he randomly chooses a ma- check symbol), and also of all 2n’1 ! permutations of
trix B = (bi, j) ∈ B and sends to the ith participant columns of the matrix B, where, analogously, the
columns of B are all binary vectors y = (y1 , . . . , yn )
a transparency consisting of m subpixels, where
n
such that i=1 yi = 1 (mod 2). This scheme has pa-
the j th subpixel is black if bi, j = 1 and the jth sub-
rameters m = d1 = 2n’1 and ± = 1/m, and is opti-
pixel is white if bi, j = 0. For distributing s = 0, the
mal since in any visual (n, n)-scheme ± ¤ 1/2n’1
dealer does the same but with a randomly cho-
and m ≥ 2n’1 [1].
sen matrix W = (wi, j) ∈ W. An allowed coalition
Visual secret sharing schemes 653


For general visual threshold (n, k)-schemes, [2] Droste, S. (1996). “New results on visual cryptog-
raphy.” Advances in Cryptology”CRYPTO™96, Lec-
various constructions were given in [1] yielding
± = 2’ (k) , which were further improved in [2, 3]. ture Notes in Computer Science, vol. 1109, ed. N.
Koblitz. Springer-Verlag, Berlin, 401“415.
Starting with [2, 4] the technique of linear pro-
[3] Verheul, E.R. H.C.A. van Tilborg (1997). “Construc-
gramming was applied to evaluate the maxi-
tions and properties of k out of n visual secret shar-
mal possible contrast of (n, k) visual threshold
ing schemes.” Designs, Codes and Cryptography, 11
schemes. This led [5] to the asymptotically an- (2), 179“196.
swer lim 4n ± = 4 for ¬xed k and growing n (see [6] [4] Hofmeister, T.M. Krause and H.U. Simon (2000).
for small values of k = 3, 4, 5). Generalizations of “Optimal k out of n secret sharing schemes in vi-
VSSS to the colored case have been also consid- sual cryptography.” Theoretical Computer Science,
ered, see [3]. vol. 240, 471“485.
[5] Krause, M. and H.U. Simon (2000). “On contrast
Robert Blakley optimal secret sharing schemes in visual cryptog-
Gregory Kabatiansky raphy: determining the optimal contrast exactly.”
Lecture Notes in Computer Science, vol. 1776, eds.
References G. H. Gonnet, D. Panario, and A. Viola. Springer,
Berlin, 280“291.
[1] Naor, M. and A. Shamir (1995). “Visual cryptog- [6] Blundo, C.P. D™Arco, A. De Santis, and D.R. Stinson
raphy.” Advances in Cryptology”EUROCRYPT™94, (2003). “Contrast optimal threshold visual cryptog-
Lecture Notes in Computer Science, vol. 950, ed. A. raphy schemes.” SIAM Journal on Discrete Mathe-
De Santis. Springer-Verlag, Berlin, 1“12. matics, vol. 16, 224“261.
654

<<

. 3
( 3 .)