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.     

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.     

Distance and routing labeling schemes for non-positively curved plane graphs

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this paper we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.     

Simplicial grid refinement: on Freudenthal's algorithm and the optimal number of congruence classes

Summary. In the present paper we investigate Freudenthal's simplex refinement algorithm which can be considered to be the canonical generalization of Bank's well known red refinement strategy for triangles. Freudenthal's algorithm subdivides any given (n)-simplex into subsimplices, in such a way that recursive application results in a stable hierarchy of consistent triangulations. Our investigations concentrate in particular on the number of congruence classes generated by recursive refinements. After presentation of the method and the basic ideas behind it, we will show that Freudenthal's algorithm produces at most n!/2 congruence classes for any initial (n)-simplex, no matter how many subsequent refinements are performed. Moreover, we will show that this number is optimal in the sense that recursive application of any affine invariant refinement strategy with sons per element results in at least n!/2 congruence classes for almost all (n)-simplices. Received February 23, 1998/ Revised version received December 9, 1998 / Published online January 27, 2000     

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.     

Existence of large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ (denoted by LS (2ⁿ4¹)) were first studied by Schellenberg and Stinson and motivated by their connection with perfect threshold schemes. It is known that such large sets can exist only for n ≡ 0 (mod 3) and do exist for any n ? {12, 36, 48, 144} ∪ {m > 6 : m ≡ 6,30 (mod 36)}. In this paper, we show that an LS (2^{12k + 6}4¹) exists for any k ≠ 2. So, the existence of LS (2ⁿ4¹) is almost solved with five possible exceptions n ∈ {12, 30, 36, 48, 144}. This solution is based on the known existence results of S (3, 4, v)s by Hanani and special S (3, {4, 6}, 6m)s by Mills. Partitionable H (q, 2, 3, 3) frames also play an important role together with a special known LS (2¹⁸4¹) with a subdesign LS (2⁶4¹). © 2004 Wiley Periodicals, Inc.     

Secret sharing schemes with partial broadcast channels

In a conventional secret sharing scheme a dealer uses secure point-to-point channels to distribute the shares of a secret to a number of participants. At a later stage an authorised group of participants send their shares through secure point-to-point channels to a combiner who will reconstruct the secret. In this paper, we assume no point-to-point channel exists and communication is only through partial broadcast channels. A partial broadcast channel is a point-to-multipoint channel that enables a sender to send the same message simultaneously and privately to a fixed subset of receivers. We study secret sharing schemes with partial broadcast channels, called partial broadcast secret sharing schemes. We show that a necessary and sufficient condition for the partial broadcast channel allocation of a (t, n)-threshold partial secret sharing scheme is equivalent to a combinatorial object called a cover-free family. We use this property to construct a (t, n)-threshold partial broadcast secret sharing scheme with O(log n) partial broadcast channels. This is a significant reduction compared to n point-to-point channels required in a conventional secret sharing scheme. Next, we consider communication rate of a partial broadcast secret sharing scheme defined as the ratio of the secret size to the total size of messages sent by the dealer. We show that the communication rate of a partial broadcast secret sharing scheme can approach 1/O(log n) which is a significant increase over the corresponding value, 1/n, in the conventional secret sharing schemes. We derive a lower bound on the communication rate and show that for a (t,n)-threshold partial broadcast secret sharing scheme the rate is at least 1/t and then we propose constructions with high communication rates. We also present the case of partial broadcast secret sharing schemes for general access structures, discuss possible extensions of this work and propose a number of open problems.      

XOR-based Visual Cryptography Schemes

A recent publication introduced a Visual Crypto (VC) system, based on the polarisation of light. This VC system has goodresolution, contrast and colour properties.Mathematically, the VC system is described by the XOR operation (modulo two addition). In this paper we investigate Threshold Visual Secret Sharing schemes associated to XOR-based VC systems. Firstly, we show that n out of n schemes with optimal resolution and contrast exist, and that (2,n) schemes are equivalent to binary codes. It turns out that these schemes have much better resolution than their OR-based counterparts. Secondly, we provide two explicit constructions for general k out of n schemes. Finally, we derive bounds on the contrast and resolution of XOR-based schemes. It follows from these bounds that for k<n, the contrast is strictly smaller than one. Moreover, the bounds imply that XOR-based k out of n schemes for even k are fundamentally different from those for odd k.AMS Classification: 94A60     

Another Set of Conditions for Strong n (n = −1, 0) Discount Optimality in Markov Decision Processes

Abstract

In this paper we study discrete-time Markov decision processes with average expected costs (AEC) and discount-sensitive criteria in Borel state and action spaces. The costs may have neither upper nor lower bounds. We propose another set of conditions on the system's primitive data, and under which we prove (1) AEC optimality and strong ? 1-discount optimality are equivalent; (2) a condition equivalent to strong 0-discount optimal stationary policies; and (3) the existence of strong n (n = ?1, 0)-discount optimal stationary policies. Our conditions are weaker than those in the previous literature. In particular, the “stochastic monotonicity condition” in this paper has been first used to study strong n (n = ?1, 0)-discount optimality. Moreover, we provide a new approach to prove the existence of strong 0-discount optimal stationary policies. It should be noted that our way is slightly different from those in the previous literature. Finally, we apply our results to an inventory system and a controlled queueing system.     

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.     

A general method for construction of (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-threshold visual secret sharing schemes for color images

This paper is concerned with the construction of basis matrices of visual secret sharing schemes for color images under the (t, n)-threshold access structure, where n ≥ t ≥ 2 are arbitrary integers. We treat colors as elements of a bounded semilattice and regard stacking two colors as the join of the two corresponding elements. We generate n shares from a secret image with K colors by using K matrices called basis matrices. The basis matrices considered in this paper belong to a class of matrices each element of which is represented by a homogeneous polynomial of degree n. We first clarify a condition such that the K matrices corresponding to K homogeneous polynomials become basis matrices. Next, we give an algebraic scheme for the construction of basis matrices. It is shown that under the (t, n)-threshold access structure we can obtain K basis matrices from appropriately chosen K − 1 homogeneous polynomials of degree n by using simple algebraic operations. In particular, we give basis matrices that are unknown so far for the cases of t = 2, 3 and n − 1.     

On Minimal Defining Sets of Full Designs and Self-Complementary Designs, and a New Algorithm for Finding Defining Sets of t-Designs

A defining set of a t-(v, k, λ) design is a partial design which is contained in a unique t-design with the given parameters. A minimal defining set is a defining set, none of whose proper partial designs is a defining set. This paper proposes a new and more efficient algorithm that finds all non-isomorphic minimal defining sets of a given t-design. The complete list of minimal defining sets of 2-(6, 3, 6) designs, 2-(7, 3, 4) designs, the full 2-(7, 3, 5) design, a 2-(10, 4, 4) design, 2-(10, 5, 4) designs, 2-(13, 3, 1) designs, 2-(15, 3, 1) designs, the 2-(25, 5, 1) design, 3-(8, 4, 2) designs, the 3-(12, 6, 2) design, and 3-(16, 8, 3) designs are given to illustrate the efficiency of the algorithm. Also, corrections to the literature are made for the minimal defining sets of four 2-(7, 3, 3) designs, two 2-(6, 3, 4) designs and the 2-(21, 5, 1) design. Moreover, an infinite class of minimal defining sets for 2-((v) || 3){v\choose3} designs, where v ≥ 5, has been constructed which helped to show that the difference between the sizes of the largest and the smallest minimal defining sets of 2-((v) || 3){v\choose3} designs gets arbitrarily large as v → ∞. Some results in the literature for the smallest defining sets of t-designs have been generalized to all minimal defining sets of these designs. We have also shown that all minimal defining sets of t-(2n, n, λ) designs can be constructed from the minimal defining sets of their restrictions when t is odd and all t-(2n, n, λ) designs are self-complementary. This theorem can be applied to 3-(8, 4, 3) designs, 3-(8, 4, 4) designs and the full 3-(8 || 4)3-{8 \choose 4} design using the previous results on minimal defining sets of their restrictions. Furthermore we proved that when n is even all (n − 1)-(2n, n, λ) designs are self-complementary.     

A Construction for Multisecret Threshold Schemes

A multisecret threshold scheme is a system that protects a number of secrets (or keys) among a group of participants, as follows. Given a set of n participants, there is a secret s _K associated with each k–subset K of these participants. The scheme ensures that s _K can be reconstructed by any group of t participants in K ( ). A lower bound has been established on the amount of information that participants must hold in order to ensure that any set of up to w participants cannot obtain any information about a secret with which they are not associated. In this paper, for parameters t=2 and w=n-k+t-1, we give a construction for multisecret threshold schemes that satisfy this bound.     

Class-uniformly resolvable designs with block sizes 2 and 3

In this article we consider restricted resolvable designs (RRP) with block sizes 2 and 3 that are class uniform. A characterization scheme is developed, based on the ratio a:b of pairs to triples, and necessary conditions are provided for the existence of these designs based on this characterization. We show asymptotic existence results when (a,b) = (1, 2n), n ≥ 1 and when (a,b) = (9, 2). We also study the specific cases when (a,b) = (1, 2n), 1 ≤ n ≤ 5, (a,b) = (3, 6u−2), u ≥ 1 and when (a,b) E {(1, 1), (3, 1), (7, 2), (3, 4), (9, 2)}. © 1996 John Wiley & Sons, Inc.     

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.     

Correction to: “Exponential bounds on the number of designs with affine parameters”

It is well known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n?3, grows exponentially. This result was extended recently [5] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2?d?n ? 1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n ? 1. Exponential bounds are also proved for the number of resolvable designs with these parameters. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:156‐166, 2011     

Exponential bounds on the number of designs with affine parameters

It is well‐known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n≥3, grows exponentially. This result was extended recently [D. Jungnickel, V. D. Tonchev, Des Codes Cryptogr, published online: 23 May, 2009] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2≤d≤n−1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n−1, as well as resolvable designs with these parameters. An exponential lower bound is also proved for the number of non‐isomorphic resolvable 3‐designs with the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, 2), for any 2≤d≤n−1. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 475–487, 2010     

Proximity‐preserving labeling schemes

This article considers informative labeling schemes for graphs. Specifically, the question introduced is whether it is possible to label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. A labeling scheme enjoying this property is termed a proximity‐preserving labeling scheme. It is shown that, for the class of n‐vertex weighted trees with M‐bit edge weights, there exists such a proximity‐preserving labeling scheme using O(M log n + log²n) bit labels. For the family of all n‐vertex unweighted graphs, a labeling scheme is proposed that using O(log² n · κ · n^1/κ) bit labels can provide approximate estimates to the distance, which are accurate up to a factor of In particular, using O(log³n) bit labels, the scheme can provide estimates accurate up to a factor of $\sqrt{2 \log n}$. (For weighted graphs, one of the log n factors in the label size is replaced by a factor logarithmic in the network's diameter.) © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 167–176, 2000     

Gauss periods as constructions of low complexity normal bases

Optimal normal bases are special cases of the so-called Gauss periods (Disquisitiones Arithmeticae, Articles 343–366); in particular, optimal normal bases are Gauss periods of type (n, 1) for any characteristic and of type (n, 2) for characteristic 2. We present the multiplication tables and complexities of Gauss periods of type (n, t) for all n and t = 3, 4, 5 over any finite field and give a slightly weaker result for Gauss periods of type (n, 6). In addition, we give some general results on the so-called cyclotomic numbers, which are intimately related to the structure of Gauss periods. We also present the general form of a normal basis obtained by the trace of any normal basis in a finite extension field. Then, as an application of the trace construction, we give upper bounds on the complexity of the trace of a Gauss period of type (n, 3).     

Some results on 4<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> designs with clear two-factor interaction components

Clear effects criterion is one of the important rules for selecting optimal fractional factorial designs, and it has become an active research issue in recent years. Tang et al. derived upper and lower bounds on the maximum number of clear two-factor interactions (2fi’s) in 2 ^n−(n−k) fractional factorial designs of resolutions III and IV by constructing a 2 ^n−(n−k) design for given k, which are only restricted for the symmetrical case. This paper proposes and studies the clear effects problem for the asymmetrical case. It improves the construction method of Tang et al. for 2 ^n−(n−k) designs with resolution III and derives the upper and lower bounds on the maximum number of clear two-factor interaction components (2fic’s) in 4 ^m 2 ⁿ designs with resolutions III and IV. The lower bounds are achieved by constructing specific designs. Comparisons show that the number of clear 2fic’s in the resulting design attains its maximum number in many cases, which reveals that the construction methods are satisfactory when they are used to construct 4 ^m 2 ⁿ designs under the clear effects criterion. This work was supported by the National Natural Science Foundation of China (Grant Nos. 10571093, 10671099 and 10771123), the Research Foundation for Doctor Programme (Grant No. 20050055038) and the Natural Science Foundation of Shandong Province of China (Grant No. Q2007A05). Zhang’s research was also supported by the Visiting Scholar Program at Chern Institute of Mathematics.