Improved Schemes for Visual Cryptography

A (k,n)-threshold visual cryptography scheme ((k,n)-threshold VCS, for short) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the visual recovery of the secret image, but by inspecting less than k shares one cannot gain any information on the secret image. The visual recovery consists of xeroxing the shares onto transparencies, and then stacking them. Any k shares will reveal the secret image without any cryptographic computation.In this paper we analyze visual cryptography schemes in which the reconstruction of black pixels is perfect, that is, all the subpixels associated to a black pixel are black. For any value of k and n, where 2 k n, we give a construction for (k,n)-threshold VCS which improves on the best previously known constructions with respect to the pixel expansion (i.e., the number of subpixels each pixel of the original image is encoded into). We also provide a construction for coloured (2,n)-threshold VCS and for coloured (n,n)-threshold VCS. Both constructions improve on the best previously known constructions with respect to the pixel expansion.     

Threshold Visual Cryptography Schemes with Specified Whiteness Levels of Reconstructed Pixels

In 1994, Naor and Shamir introduced an unconditionally secure method for encoding black and white images. This method, known as a threshold visual cryptography scheme (VCS), has the benefit of requiring no cryptographic computation on the part of the decoders. In a -VCS, a share, in the form of a transparency, is given to ">n users. Any ">k users can recover the secret simply by stacking transparencies, but ">k-1 users can gain no information about the secret whatsoever.In this paper, we first explore the issue of contrast, by demonstrating that the current definitions are inadequate, and by providing an alternative definition. This new definition motivates an examination of minimizing pixel expansion subject to fixing the VCS parameters ">h and ">l. New bounds on pixel expansion are introduced, and connections between these bounds are examined. The best bound presented is tighter than any previous bound. An analysis of connections between (2, ">n) schemes and designs such as BIBD's, PBD's, and (">r, )-designs is performed. Also, an integer linear program is provided whose solution exactly determines the minimum pixel expansion of a (2, ">n)-VCS with specified ">h and >l.     

Optimal Colored Threshold Visual Cryptography Schemes

Visual cryptography schemes allow the encoding of a secret image into n shares which are distributed to the participants. The shares are such that only qualified subsets of participants can visually recover the secret image. Usually the secret image consist of black and white pixels. In colored threshold visual cryptography schemes the secret image is composed of pixels taken from a given set of c colors. The pixels expansion and the contrast of a scheme are two measures of the goodness of the scheme.In this paper, we study c-color (k,n)-threshold visual cryptography schemes and provide a characterization of contrast-optimal schemes. More specifically we prove that there exists a contrast-optimal scheme that is a member of a special set of schemes, which we call canonical schemes, and that satisfy strong symmetry properties.Then we use canonical schemes to provide a constructive proof of optimality, with respect to the pixel expansion, of c-color (n,n)-threshold visual cryptography schemes.Finally, we provide constructions of c-color (2,n)-threshold schemes whose pixels expansion improves on previously proposed schemes.*This author is also a member of the Akamai Faculty Group, Akamai Technologies, 8 Cambridge center, Cambridge, MA 02142, USA.     

Periods in missing lengths of rainbow cycles

A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph G, define Then ??(G) is a monoid with respect to the operation n°m=n+ m?2, and thus there is a least positive integer π(G), the period of ??(G), such that ??(G) contains the arithmetic progression {N+ kπ(G)|k?0} for some sufficiently large N. Given that n∈??(G), what can be said about π(G)? Alexeev showed that π(G)=1 when n?3 is odd, and conjectured that π(G) always divides 4. We prove Alexeev's conjecture: Let p(n)=1 when n is odd, p(n)=2 when n is divisible by four, and p(n)=4 otherwise. If 2<n∈??(G) then π(G) is a divisor of p(n). Moreover, ??(G) contains the arithmetic progression {N+ kp(n)|k?0} for some N=O(n²). The key observations are: If 2<n=2k∈??(G) then 3n?8∈??(G). If 16≠n=4k∈??(G) then 3n?10∈??(G). The main result cannot be improved since for every k>0 there are G, H such that 4k∈??(G), π(G)=2, and 4k+ 2∈??(H), π(H)=4. © 2009 Wiley Periodicals, Inc. J Graph Theory     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

Optimal (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) visual cryptographic schemes for general <Emphasis Type="Italic">k</Emphasis>

In (k, n) visual cryptographic schemes (VCS), a secret image is encrypted into n pages of cipher text, each printed on a transparency sheet, which are distributed among n participants. The image can be visually decoded if any k(≥2) of these sheets are stacked on top of one another, while this is not possible by stacking any k − 1 or fewer sheets. We employ a Kronecker algebra to obtain necessary and sufficient conditions for the existence of a (k, n) VCS with a prior specification of relative contrasts that quantify the clarity of the recovered image. The connection of these conditions with an L ₁-norm formulation as well as a convenient linear programming formulation is explored. These are employed to settle certain conjectures on contrast optimal VCS for the cases k = 4 and 5. Furthermore, for k = 3, we show how block designs can be used to construct VCS which achieve optimality with respect to the average and minimum relative contrasts but require much smaller pixel expansions than the existing ones.     

Avoiding multiple entry arrays

In this paper we consider the problem of avoiding arrays with more than one entry per cell. An n × n array on n symbols is said to be if an n × n latin square, on the same symbols, can be found which differs from the array in every cell. Our first result is for chessboard squares with at most two entries per black cell. We show that if k ≥ 1 and C is a 4k × 4k chessboard square on symbols 1, 2, …, 4k in which every black cell contains at most two symbols and every symbol appears at most once in every row and column, then C is avoidable. Our main result is for squares with at most two entries in any cell and answers a question of Hilton. If k 3240 and F is a 4k × 4k array on 1, 2,…, 4k in which every cell contains at most two symbols and every symbol appears at most twice in every row and column, then F is avoidable. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 257–266, 1997     

Optimal (2, n) visual cryptographic schemes

In (2,n) visual cryptographic schemes, a secret image(text or picture) is encrypted into n shares, which are distributed among n participants. The image cannot be decoded from any single share but any two participants can together decode it visually, without using any complex decoding mechanism. In this paper, we introduce three meaningful optimality criteria for evaluating different schemes and show that some classes of combinatorial designs, such as BIB designs, PBIB designs and regular graph designs, can yield a large number of black and white (2,n) schemes that are optimal with respect to all these criteria. For a practically useful range of n, we also obtain optimal schemes with the smallest possible pixel expansion.     

On the Number of Balanced Lines

Given a set of n black and n white points in general position in the plane, a line l determined by them is said to be balanced if each open half-plane bounded by l contains precisely the same number of black points as white points. It is proved that the number of balanced lines is at least n . This settles a conjecture of George Baloglou. Received August 1, 2000, and in revised form October 23, 2000. Online publication April 6, 2001.     

On an online random k‐SAT model

Given n Boolean variables x₁,…,x_n, a k‐clause is a disjunction of k literals, where a literal is a variable or its negation. Suppose random k‐clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated k‐clauses as possible with the condition that it must be possible to satisfy every clause that is accepted. When cn random k‐clauses on n variables are given, a natural online algorithm known as Online‐Lazy accepts an expected (1 ? )cn + a_kn clauses for some constant a_k. If these clauses are given offline, it is possible to do much better, (1 ? )cn + Ω( )n can be accepted whp . The question of closing the gap between a_k and Ω( ) for the online version remained open. This article shows that for any k ≥ 1, any online algorithm will accept less than (1 ? )cn + (ln 2)n k‐clauses whp , closing the gap between the constant and Ω( ). Furthermore we show that this bound is asymptotically tight as k → ∞. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Local edge colorings that are global

A local (H, k)-coloring of K_n is a coloring of its edges in which each of its subgraphs isomorphic to H is colored by at most k colors. A necessary condition on H (conjectured to be sufficient) is found such that each local (H, k)-coloring is a k-coloring. Furthermore, necessary and sufficient conditions are given for each local (H, k)-coloring to be a coloring by a bounded number of colors.     

Cheating in Visual Cryptography

A secret sharing scheme allows a secret to be shared among a set of participants, P, such that only authorized subsets of P can recover the secret, but any unauthorized subset cannot recover the secret. In 1995, Naor and Shamir proposed a variant of secret sharing, called visual cryptography, where the shares given to participants are xeroxed onto transparencies. If X is an authorized subset of P, then the participants in X can visually recover the secret image by stacking their transparencies together without performing any computation. In this paper, we address the issue of cheating by dishonest participants, called cheaters, in visual cryptography. The experimental results demonstrate that cheating is possible when the cheaters form a coalition in order to deceive honest participants. We also propose two simple cheating prevention visual cryptographic schemes.     

Homological connectivity of random k‐dimensional complexes

Let Δ_n?1 denote the (n ? 1)‐dimensional simplex. Let Y be a random k‐dimensional subcomplex of Δ_n?1 obtained by starting with the full (k ? 1)‐dimensional skeleton of Δ_n?1 and then adding each k‐simplex independently with probability p. Let H_k?1(Y; R) denote the (k ? 1)‐dimensional reduced homology group of Y with coefficients in a finite abelian group R. It is shown that for any fixed R and k ≥ 1 and for any function ω(n) that tends to infinity © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Surface embeddings of Steiner triple systems

A Steiner triple system of order n (STS(n)) is said to be embeddable in an orientable surface if there is an orientable embedding of the complete graph K_n whose faces can be properly 2-colored (say, black and white) in such a way that all black faces are triangles and these are precisely the blocks of the STS(n). If, in addition, all white faces are triangular, then the collection of all white triangles forms another STS(n); the pair of such STS(n)s is then said to have an (orientable) bi-embedding. We study several questions related to embeddings and bi-embeddings of STSs. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 325–336, 1998     

Coloring graphs from lists with bounded size of their union

A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 2^4k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory     

2-noncrossing trees and 5-ary trees

Recently, Gu et al. [N.S.S. Gu, N.Y. Li, T. Mansour, 2-Binary trees: Bijections and related issues, Discrete Math. 308 (2008) 1209-1221] introduced 2-binary trees and 2-plane trees which are closely related to ternary trees. In this note, we study the 2-noncrossing tree, a noncrossing tree in which each vertex is colored black or white and there is no ascent (u,v) such that both the vertices u and v are colored black. By using the representation of Panholzer and Prodinger for noncrossing trees, we find a correspondence between the set of 2-noncrossing trees of n edges with a black root and the set of 5-ary trees with n internal vertices.     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

Hamiltonian graphs involving neighborhood unions

Dirac proved that a graph G is hamiltonian if the minimum degree , where n is the order of G. Let G be a graph and . The neighborhood of A is for some . For any positive integer k, we show that every (2k ? 1)‐connected graph of order n ≥ 16k³ is hamiltonian if |N(A)| ≥ n/2 for every independent vertex set A of k vertices. The result contains a few known results as special cases. The case of k = 1 is the classic result of Dirac when n is large and the case of k = 2 is a result of Broersma, Van den Heuvel, and Veldman when n is large. For general k, this result improves a result of Chen and Liu. The lower bound 2k ? 1 on connectivity is best possible in general while the lower bound 16k³ for n is conjectured to be unnecessary. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 83–100, 2006     

Properly colored hamilton cycles in edge-colored complete graphs

It is shown that, for ϵ>0 and n>n₀(ϵ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1-1/\sqrt2-\epsilon)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 179–186 (1997)     

Gray code enumeration of families of integer partitions

In this paper we show that the elements of certain families of integer partitions can be listed in a minimal change, or Gray code, order. In particular, we construct Gray code listings for the classes P_δ(n, k) and D(n, k) of partitions of n into parts of size at most k in which, for P_δ(n, k), the parts are congruent to one modulo δ and, for D(n, k), the parts are distinct. It is shown that the elements of these classes can be listed so that the only change between successive partitions is the increase of one part by δ (or the addition of δ ones) and the decrease of one part by δ (or the removal of δ ones), where, in the case of D(n, k), δ = 1.