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