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     

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.     

New Colored Visual Secret Sharing Schemes

Visual secretsharing (VSS) schemes are used to protect the visual secret bysending n transparencies to different participantsso that k-1 or fewer of them have no informationabout the original image, but the image can be seen by stackingk or more transparencies. However, the revealedsecret image of a conventional VSS scheme is just black and white.The colored k out of n VSS scheme sharinga colored image is first introduced by Verheul and Van Tilborg[1]. In this paper, a new construction for the colored VSS schemeis proposed. This scheme can be easily implemented on basis ofa black & white VSS scheme and get much better block lengththan the Verheul-Van Tilborg scheme.     

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.     

Constructions and Properties of k out of n Visual Secret Sharing Schemes

The idea of visual k out of n secret sharing schemes was introduced in Naor. Explicit constructions for k = 2 and k = n can be found there. For general k out of n schemes bounds have been described.Here, two general k out of n constructions are presented. Their parameters are related to those of maximum size arcs or MDS codes. Further, results on the structure of k out of n schemes, such as bounds on their parameters, are obtained. Finally, the notion of coloured visual secret sharing schemes is introduced and a general construction is given.     

A New Approach for Visual Cryptography

Visual cryptography is to encrypt a secret image into some shares (transparencies) such that any qualified subset of the shares can recover the secret visually. The conventional definition requires that the revealed secret images are always darker than the backgrounds. We observed that this is not necessary, in particular, for the textual images.In this paper, we proposed an improved definition for visual cryptography based on our observation, in which the revealed images may be darker or lighter than the backgrounds. We studied properties and obtained bounds for visual cryptography schemes based on the new definition. We proposed methods to construct visual cryptography schemes based on the new definition. The experiments showed that visual cryptography schemes based on our definition indeed have better pixel expansion in average.     

Secret Sharing Schemes with Detection of Cheaters for a General Access Structure

In a secret sharing scheme, some participants can lie about the value of their shares when reconstructing the secret in order to obtain some illicit benefit. We present in this paper two methods to modify any linear secret sharing scheme in order to obtain schemes that are unconditionally secure against that kind of attack. The schemes obtained by the first method are robust, that is, cheaters are detected with high probability even if they know the value of the secret. The second method provides secure schemes, in which cheaters that do not know the secret are detected with high probability. When applied to ideal linear secret sharing schemes, our methods provide robust and secure schemes whose relation between the probability of cheating and the information rate is almost optimal. Besides, those methods make it possible to construct robust and secure schemes for any access structure.     

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.     

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.     

An Optimal Multisecret Threshold Scheme Construction

A multisecret threshold scheme is a system which protects a number of secret keys among a group of n participants. There is a secret s_K associated with every subset K of k participants such that any t participants in K can reconstruct the secret s_K, but a subset of w participants cannot get any information about a secret they are not associated with. This paper gives a construction for the parameters t = 2, k = 3 and for any n and w that is optimal in the sense that participants hold the minimal amount of information. Communicated by: P. Wild     

Secret Sharing Schemes with Three or Four Minimal Qualified Subsets

In this paper we study secret sharing schemes whose access structure has three or four minimal qualified subsets. The ideal case is completely characterized and for the non-ideal case we provide bounds on the optimal information rate.AMS Classification 94A62     

Detection of Cheaters in Vector Space Secret Sharing Schemes

A perfect secret sharing scheme is a method of distributing shares of a secret among a set P of participants in such a way that only qualified subsets of P can reconstruct the secret from their shares and non-qualified subsets have absolutely no information on the value of the secret. In a secret sharing scheme, some participants could lie about the value of their shares in order to obtain some illicit benefit. Therefore, the security against cheating is an important issue in the implementation of secret sharing schemes. Two new secret sharing schemes in which cheaters are detected with high probability are presented in this paper. The first one has information rate equal to 1/2 and can be implemented not only in threshold structures, but in a more general family of access structures. We prove that the information rate of this scheme is almost optimal among all schemes with the same security requirements. The second scheme we propose is a threshold scheme in which cheaters are detected with high probability even if they know the secret. The information rate is in this case 1/3 In both schemes, the probability of cheating successfully is a fixed value that is determined by the size of the secret.     

Sharing Multiple Secrets: Models, Schemes and Analysis

A multi-secret sharing scheme is a protocol to share more than one secret among a set of participants, where each secret may have a distinct family of subsets of participants (also called ‘access structure’) that are qualified to recover it. In this paper we use an information-theoretic approach to analyze two different models for multi-secret sharing schemes. The proposed models generalize specific models which have already been considered in the literature. We first analyze the relationships between the security properties of the two models. Afterwards, we show that the security property of a multi-secret sharing scheme does not depend on the particular probability distribution on the sets of secrets. This extends the analogous result for the case of single-secret sharing schemes and implies that the bounds on the size of the information distributed to participants in multi-secret sharing schemes can all be strengthened. For each of the two models considered in this paper, we show lower bounds on the size of the shares distributed to participants. Specifically, for the general case in which the secrets are shared according to a tuple of arbitrary (and possibly different) access structures, we show a combinatorial condition on these structures that is sufficient to require a participant to hold information of size larger than a certain subset of secrets. For specific access structures of particular interest, namely, when all access structures are threshold structures, we show tight bounds on the size of the information distributed to participants.     

Constructions for Anonymous Secret Sharing Schemes Using Combinatorial Designs

In an anonymous secret sharing scheme the secret can be reconstructed without knowledge ofwhich participants hold which shares.In this paper some constructions of anonymous secret sharing schemeswith 2 thresholds by using combinatorial designs are given.Let v(t,w,q)denote the minimum size of the setof shares of a perfect anonymous(t,w)threshold secret sharing scheme with q secrets.In this paper we provethat v(t,w,q)=(q)if t and w are fixed and that the lower bound of the size of the set of shares in[4]is notoptimal under certain condition.     

Providing Anonymity in Unconditionally Secure Secret Sharing Schemes

We discuss the concept of anonymity in an unconditionally secure secret sharing scheme, proposing several types of anonymity and situations in which they might arise. We present a foundational framework and provide a range of general constructions of unconditionally secure secret sharing schemes offering various degrees of anonymity.     

A General Decomposition Construction for Incomplete Secret Sharing Schemes

A secret sharing scheme for an incomplete access structure (,) is a method of distributing information about a secret among a group of participants in such a way that sets of participants in can reconstruct the secret and sets of participants in can not obtain any new information about the secret. In this paper we present a more precise definition of secret sharing schemes in terms of information theory, and a new decomposition theorem. This theorem generalizes previous decomposition theorems and also works for a more general class of access structures. We demonstrate some applications of the theorem.     

A Representation of a Family of Secret Sharing Matroids

Deciding whether a matroid is secret sharing or not is a well-known open problem. In Ng and Walker [6] it was shown that a matroid decomposes into uniform matroids under strong connectivity. The question then becomes as follows: when is a matroid m with N uniform components secret sharing? When N = 1, m corresponds to a uniform matroid and hence is secret sharing. In this paper we show, by constructing a representation using projective geometry, that all connected matroids with two uniform components are secret sharing     

A Linear Algebraic Approach to Metering Schemes

A metering scheme is a method by which an audit agency is able to measure the interaction between servers and clients during a certain number of time frames. Naor and Pinkas (Vol. 1403 of LNCS, pp. 576–590) proposed metering schemes where any server is able to compute a proof (i.e., a value to be shown to the audit agency at the end of each time frame), if and only if it has been visited by a number of clients larger than or equal to some threshold h during the time frame. Masucci and Stinson (Vol. 1895 of LNCS, pp. 72–87) showed how to construct a metering scheme realizing any access structure, where the access structure is the family of all subsets of clients which enable a server to compute its proof. They also provided lower bounds on the communication complexity of metering schemes. In this paper we describe a linear algebraic approach to design metering schemes realizing any access structure. Namely, given any access structure, we present a method to construct a metering scheme realizing it from any linear secret sharing scheme with the same access structure. Besides, we prove some properties about the relationship between metering schemes and secret sharing schemes. These properties provide some new bounds on the information distributed to clients and servers in a metering scheme. According to these bounds, the optimality of the metering schemes obtained by our method relies upon the optimality of the linear secret sharing schemes for the given access structure.     

Basic Properties of the (t, n)-Threshold Visual Secret Sharing Scheme with Perfect Reconstruction of Black Pixels

In this paper we consider the (t, n)-threshold visual secret sharing scheme (VSSS) in which black pixels in a secret black-white images is reproduced perfectly as black pixels when we stack arbitrary t shares. This paper provides a new characterization of the (t, n)-threshold visual secret sharing scheme with such a property (hereafter, we call such a VSSS the (t, n)-PBVSSS for short). We use an algebraic method to characterize basis matrices of the (t, n)-PBVSSS in a certain class of matrices. We show that the set of all homogeneous polynomials each element of which yields basis matrices of the (t, n)-PBVSSS becomes a set of lattice points in an (n−t+1)-dimensional linear space. In addition, we prove that the optimal basis matrices in the sense of maximizing the relative difference among all the basis matrices in the class coincides with the basis matrices given by Blundo, Bonis and De Santis [3] for all n≥ t ≥ 2.