visual cryptography

Visual Cryptography Schemes proposed by Naor and Shamir.
that the underlying algebraic structure is a semi-group rat her than a group. In particular, the visual effect of a black subpixel in one of the transparencies cannot be undone by the colour of that subpixel in other transparencies which are laid over it. This monot onicity rules out common encryption techniques which add random noise to the cleartext during the encryption process, and subtracts the same noise from the ciphertext during the decryption process. It also rules out the more natural model in which a white pixel is represented by a completely white collection of subpixels and a black pixel is represented by a com pletely black collection of subpixels, and thus we have to use a threshold d and relative difference 0 to distinguish bet ween the e colours Definition 2.1 A solution to the k: olt of n 17i. a! secret sharing scheme con si st s of t/0 collection s of n xm Boolean matrices co and cl. To share a white pi.el, the dealer randoml chooses one of the matrices in Co, and to share a black pirel, the dealer randomly chooses one of the matrices in Cl. The chosen matri defines the colour of the n subpiels in each one of the n transparencies. The solution is considered valid if the following three conditions are met 1. For any s in co,the“or” v of any k of the n rows satisfies h(V)≤d-a:m For any S in Cl, the "or"Vof any k of the n rows satisfies H(v) 3. For any subset i, i2,.ig of(1, 2, ..n with q <k, the two collections of q x m ices D for t E0,1 obtained by iz in Cl whe chat the e ame matrices with the same frequencics C,. Condition 3 implies that by inspecting fewer than k shares, even an infinitely powerfu cryptanalyst cannot gain any advantage in deciding whether the shared pixel was white or black. In most of our constructions there is a function f such that the combined shares from q<k transparencies consist of all the V's with H(V=f(q) with uniform probability distribution, regardless of whether the matrices were taken from Cn or Cl. Such a scheme is called un iform. The first two conditions are called contrast and the third condition is called ecurity The important parameters of a scheme are m, the number of pixels in a share. This represents the loss in resolution from the original picture to the shared one. We would like m to be as small as possible e o. the relative difference in weight bet ween combined shares that come from a white pixel and a black pixel in the original picture. This represents the loss in contrast We would like a to be as large as possible m, the size of the collect ions Co and C1(they need not be the same size, but in all of our constructions they are log r represents the number of random bits needed to generate the shares and does not effect the quality of the picture Results: We have a number of constructions for s pecific values of k and 7. For general k we have a construction for the k out k problem with m= 2k-1 and a and we have a proof of optimality of this scheme. For general k and n we have a construction wit h (k log k) and o 口日口 Figure 1 3 Eficient solutions for small k and n The 2 out. of n visula.I secret sharing problem can be solved hy t he following collect ions of ×? matrices: 100.0 fall the matrices obtained by permuting the columns of [all the matrices obtained by permuting the columns of 010...0 Any single share in eit her Co or Cl is a random choice of one black and m2-1 white subpix els. Any two shares of a white pixel have a combined hamming weight of 1, whereas any two shares of a l pixel have a combined Hamming weight of 2, which looks darker. The visual diference bet ween the t wo cases becomes clearer as we stack additional trallsparenlcies The original problem of visual cryptography is the special case of a 2 out of 2 visual secret. sharing problem. It can he solved wit h t wo subpixels per pixel, but in pra.ct.ice t his can distort the aspect ratio of the original image. It is thus recommended to use 4 subpixels arranged in a 2 x2 array where each share has one of the visual forms in Figure l. a white pixel is shared into two identical arrays froin this list, and a black pixel is shared into two omplementary arrays from this list. Any single share is a random choice of two black and two white subpixel, which looks medium grey. When two shares are stacked toget her, t he result is either medium grey(which represents white) or completely black(which represents black) The next case is the 3 out of 3 vis ual secret sharing problem, w hich is solved by the following scheme 0011 Co=all the matrices obtained by permuting the columns of0101 3 0110 1100 fall the matrices obtained by permuting the columns of 1010] □■■ figure 2 Note that the six shares described by the rows of ci and ci are exactly the six 2 2 arrays of subpixels from Fig. I. Each matrix in either Co or Ci contains one horizontal share one vertical share and one diagonal share. each share contains a randon selection of two black su b pixels, and any pair of shares from onc of the matrices contains a random selection of one common black su pixel and two individual black sul pixels. Consequent ly the analysis of one or two shares makes it impossible to distinguish between Co and cl However, a stack of three transparencies from Co is only 3 /4 black, whereas a stack of three transparencies froIn Cl is completely black The following scheme gcncralizcs this 3 out of 3 scheme into a 3 out of n schcme for an arbitrary n>3. Let b be the black nx(n-2) matrix which contains only 1s, and let I be the identity n x n matrix which contains 1s on the diagonal and o' s elsewhere. Let Bl denote the n(2n-2) matrix obtained by concatenating B and I, and let e(bn be the Boolean complement of the matrix Bl. Then Co=fall th ob permuting umns o C(BDY ll the matrices obtained by permuting the columns of BI1 has the following properties: Any single share contains an arbitrary collection of n-1 black and n-l white su pixels; any pair of shares have n-2 common black and two individual black sub pixels; any stacked triplet of shares from Co has n black subpixels whereas any stacked triplet of shares from Ci has n+l black subpixel The 4 out of 4 visua. I secret sharing problem can he solved by the shares described in Figure 2(along with all their permutations) Any single share contains 5 black subpixels, any stacked pair of shares contains 7 black u b pixels, any stacked triplet of shares contains 8 black subpixels, and any stacked q uadruple of shares contains cither & or g black subpixcls, depending on whether the shares were taken from Co or Cl. It is possible to reduce the number of su bpixels from 9 t o8. b 11t t hen t hev cannot be packed into a square array without distorting their aspect ratio Finally, we describe an efficient 2 out of 6 scheme. The scheme is defined by 1100 1100 Co=i all the matrices obtained by permuting the columns of 1100 1100 1100 1010 1100 Ci= tall the matrices obtained by permuting the columns o 007 1001 The scheme has cont rast J: any two shares of Co cover 2 out of 4 of the pixels, while any pair of shares from Ci covers at least 3 out of 4 pixels(some cover all four The security of the scheme follows from the fact that in both Co and ci each share is random subset of 2 black pixels out of 4 One possible generalization of this scheme to a 2 out of n scheme is to fix m so that (m?)>n and consider all subsets of size m/2 of some ground set of size m. The ith row is s corresponds to the it h subset, i. e. S i,j= 1 iff the jt h element is in the it h su hset. S is the n x m matrix where each row is 1m/0m/]. Co and CI are obtained from all column permutations of so and S. the contrast achieved this way is 1/m. As we shall see in Section 5. we call do better than that 4 A general k out of k scheme We now describe two general constructions which can solve any k out of k visual secret sharing problem by using 2 and 2k-1 subpixels respectively. We then prove that the second construction is optimal in that any k out k scheme must use at least 2 pixels 4.1 Construction 1 To define the two collections of matrices we make use of two lists of vectors. 1.7 o and Ji k a.. . g be vectors of length k over GF2] with the property that every 1 of them are linearly independent over GF2, but the set of all k vectors is not independent. Such a collection can be easily constructed, e.g. let g=0-l10k: for an nd Jie-1-0. Let J1, J 2,. J be vectors of length k over GF[2]with the property that they are linearly independent over GF2. (This call be thought of as a first order reed-Muller code 7) Fach list defines a k: 2 matrix st for t E10, 1 and the collections Co and Cl are o btained by permuting the columns of the corresponding matrix in all possible ways. We index the columns of st by vectors of length k over GF2 For t E 0, 1 let St be defined as follows: S[i, ]=<J, >for any 1 <is k and any vector a of length k over GF21 where <a, y> denotes the inner product over GF2 Lemma 4.1 The above schene is a k out of k scheme with parameters m=2, a=1/2k and r=2k Proof: In order to show contrast. note that in matrix so there are two columns that are all zero; in t he example given these are the column indexed by=0" and the column indexed by=0k-11.On the other hand, in Si there is only one column that is all 0. the one corresponding to=0. Therefore in any permutation of s°the“or” of the k o R-2 ones, whereas in any permutation of s the "or"of the ki rows yields 2s rows yields ones In order to show security, note that the vectors corresponding to any k-l rows in both so and s are linearly independent over GF2. Therefore if one considers the rows as subsets of a ground set of size 2, then every intersection of k 1 rows or their complement has the same size, twa.(Note that we include complemented sets, and thus if all possible intersections of k-1 are the same, then all smaller intersections are the same as well. )L other words. consider the columns in s and s obtained by rest ricting to the k-1 chosen rows. Then every possible assignment to the k-1 entries appears exactly twice. Hence, a random permutation of the columns, as is used to generate Co and ci, yields the same distribution regardless of which k-1 rows were chosen c 4.2 Construction 2 We now show a slightly better scheme with parameters m=2-1, a=1/ 2k-I and T=2k-1 Consider a ground set 4={e1,∈2,,ek} of k elements and let丌1,丌2, all the subsets of even cardinality and let 01, 02,... 0,k-1 be a list of all the subsets of w of odd cardinality (the order is not important Each list defines the following kx 24-1 matrices So and S For 1<i< k and 1<j< letS[,j=1ife;∈r; and s i,=1e;∈ As in the construction above, the collections Co and Cl are obtained by permuting all the columns of the corres ponding matrix Lemma 4.2 The above scheme is a k out of k scheme with parameters n= 2 -,C 1/2-1andr=2k-1! Proof: In order to show contrast. note the in matrix so there is one column that is all zero, the one indexed by the empty set. On the other hand, inl S there is n0 colunn that is all 0. Therefore in any permutation of So the"orof the k rows yields only 2-1 1 ones whereas in any permutation of SI the "or of the k rows vields 2k I ones In order to show security. note that if one examines any k-l rows in either So and s then the structure discovered is similar: consider the rows as su bsets of a ground set of size 2k; every intersection of k-1 rows or their complement has the sainle size, two Hence, as in the proof of lemma 4.1, a random permutation of the columns yields the same dist ribution rega.rdless of which A-1 rows were chosen. D 4.3 Upper bound on a We show that a must be exponentially small as a function of k and, in fact, get a tight bound that a> 2k-. The key combinatorial fact used is the following(see [5, 6]: given two sequences of sets A1, A2.. Ak and B1, B2,... B of some ground set G such that for every subset U Cf1,h) of size at most k-1 we have Nieu a: l=Nieu b:l, then JUL1 I< 5kr IG+Ui_1 Bil. In other words, if the intersections of the Ai's and B;'s agree in size for all subsets smaller than k elements, then the difference in the union cannot be too large Consider now a k out k scheme C with parameters m, a and r. Let the two collections be Co and cl. We construct from the collections two sequences of sets Al, A2,... A and B31,B Br. The ground set is of size m r and its elements are indexed by (., y) where 1<x≤rand1≤y≤m. Element(x,y) is in A; iff Soli?小=1 and element(x,y) is in B We claim that for any U c{1.….k} of size q< k the equality|∩ lieu a=|∩eUB2 holds: the security condition of C implies that we can construct a 1-1 mapping between all the q x m matrices obtained from considering only rows corresponding to l in Co and the q x m matrices of Ci such that any two matched matrices are identical. (Strictly speaking, the security condition is not strong enough to imply it, but given any scheme we can convert it into one that has this property wit hout changing a and m. Therefore when considering lieu a:l and i niel bil the contribution of each member of a pair of matched matrices is identical and hence∩:ErA=|∩∈B A pplying now the combinatorial fact mentioned above yields that 1 k-1 +|U=1A This ineans that for at least onle Natrix in Cl and one matrix in Co the dierence betweell the hamming weight of the"or"of their rows is at most k-I. m. Hence we have Theorem 4.3 In any k out k scheme a< o and m>24 1 5 A general k out of n scheme In this section we construct a k out of n scheme. What we show is how to go from a kout of k scheme to a k out of n scheme Let c be an k out of h visual secrct sharing scheme with paramcters m, a. Tho scheme c consists of two collections of k X m Boolean matrices Co =TU, T2 r and C1=T1, T2..T. Furthermore, assume the scheme is uniform, i. e. there is a function f(q) such that for any matrix T; where t∈{0,1}and1≤i≤ r and for every1 rows of T the hamming weight of the "or"of the q rows is f(q). Note that all our previous constructions have this property. Let i he a collection of e functions such that 1. he H we have h: 1mb>1.ki or all subsets b c1.n of sizc k and for all 1<9< h the probabilit randomly chosen h E h yields g different values on b is the same. Denote this probability by Ba We construct from C and h a k out of n scheme c as follows The ground set is V=UX H(i.e. it is of size m.e and we consider its elements as indexed by a member of U and a member of H) exed by a vector (11, t 2, .. t e) where each 1<t i< The matrix St for t=(t1, t2.. te)) where b(0, 1 is defined as {,(,b)]=T[b(i), Note that in the above expression th means the hth entry in t, where h is simply interpreted as a number between 1 and e Lemma 5.1 lfc is a scheme with parameters m, a, r, then ci is a scheme with parameters Proof: In order to show contrast, note that for any k rows in a matrix st and any h Eh if the subset corresponding to the k rows is mapped to g k different values by h, then we know by the assumption of uniformity that the weight of the or"of the g rows in C is f(q. The difference between white pixels and black pixels occurs only when h is 1-1 which happens at 3 of the h e h and it is a. m in this case. Therefore the hanmin weight of an"or"of rows of a white pixel is at most B(d-am)+∑2·f(q) and the weight of a black pixel is (Ad+∑·f(q which means that the relative difference between them is at least 3k.c In order to see the security of the scheme, note that we are essentially repeating e times the scheme c where each instance is independent of all other instances. Therefore from the security of c we get the security of s.D 5.1 Construction of h Onc can construct H from a collection of h wisc independent hash functions(scc c.g. 3 4,9). Suppose that H is such that for any k values 1, 2, ..kE 1,n the k random variables defined by X1=h(1), x2=h(2),.. k h( k) for a randomly chosen hE h are completely independent. Since they are independent the probability that they vield g dillerent values is the saime, 110 Inatter what 1, 2, .. k are. For a concrete example assume that k is a prime(otherwise we have to deal with its factors ), and let I be such that k >n2. The family h is based on the set of poly nomials of degree k-1 over gFk:l, where for ever hE h there is a corresponding polynomial q(x), and h(.)=q(a)mod k e size of H is about n". The probability B that a random h is 1-1 on a set of k elements is (k/e) kk kky2πk√2丌k We can therefore conclude by applying lenina 5.1 Theorem 5.2 For any n and k there eists a visual secret sharing scheme with parameters m=k.2-1 (2e) k 2Tk and r (2-11 5.2 Relaxing the conditions on H Suppose now that we relax Condition 2 in the definition of h to the following: there exists an E such that for all subsets b cf1.n of size k and for all 1<q<k the probability that a randomly chosen h e li yields g different values on B is the same to within E. As we shall see. this leeway allows for much smaller Hs Taking e to be small, say smaller than a Bk /4, cannot make a big difference in the quality of our construction: The Hamming weight of an"or"of k rows of a white pixel is at most (+6)·(d-am)+∑(3,+e)·f(q) and the weight of a black pixel is at least (1-6)·d+∑(1-6)·房·fq) ?=1 The relative difference bet ween black and white is therefore at least k a-26 Note that the security of the scheme is not effected at all. since fewer than k shares never map to k different values Construction of relaxed h We use small-bias probability spaces to construct such a relaxed family(see 82,3 for definitions and constructions). A probability space with random variables that are e-bias is an approximation to a probability s pace with com pletely independent random variables in that the bias (i.e. the difference between the pro bability that there parity is 0 and 1 is bounded by e(as opposed to 0 in the complete independence Similarly, a probability space which is k-wise e-bias is an approximation to k-wise independent probability spaces Assume that k is a power of 2. let r be a k log k-wise 8-bias probability space on n log k random variables which takes values in 0, 1. They are indexed as Yi; for 1<ix n and 1 <i< log k. There are explicit constructions of such probability spaces of size 20(klog)log n(see[8[1]) Each function h corresponds to a point in the probability space. h( )is the value of Y-1,1-2,., Yrlog k treated as a number bet ween 0 and 2-1. It can be shown that for all ∈{1,m} and for all y,v,vk∈{0,2k-1} we have 6·ks< Prob[h( h( 2)=32,.h (:k

...展开详情

sophia7718