Perfect Secret Sharing Schemes on Five Participants

A perfect secret sharing scheme is a system for the protection of a secret among a number of participants in such a way that only certain subsets of these participants can reconstruct the secret, and the remaining subsets can obtain no additional information about the secret. The efficiency of a perfect secret sharing scheme can be assessed in terms of its information rates. In this paper we discuss techniques for obtaining bounds on the information rates of perfect secret sharing schemes and illustrate these techniques using the set of monotone access structures on five participants. We give a full listing of the known information rate bounds for all the monotone access structures on five participants.     

Properties and constraints of cheating-immune secret sharing schemes

A secret sharing scheme is a cryptographic protocol by means of which a dealer shares a secret among a set of participants in such a way that it can be subsequently reconstructed by certain qualified subsets. The setting we consider is the following: in a first phase, the dealer gives in a secure way a piece of information, called a share, to each participant. Then, participants belonging to a qualified subset send in a secure way their shares to a trusted party, referred to as a combiner, who computes the secret and sends it back to the participants.Cheating-immune secret sharing schemes are secret sharing schemes in the above setting where dishonest participants, during the reconstruction phase, have no advantage in sending incorrect shares to the combiner (i.e., cheating) as compared to honest participants. More precisely, a coalition of dishonest participants, by using their correct shares and the incorrect secret supplied by the combiner, have no better chance in determining the true secret (that would have been reconstructed if they submitted correct shares) than an honest participant.In this paper we study properties and constraints of cheating-immune secret sharing schemes. We show that a perfect secret sharing scheme cannot be cheating-immune. Then, we prove an upper bound on the number of cheaters tolerated in such schemes. We also repair a previously proposed construction to realize cheating-immune secret sharing schemes. Finally, we discuss some open problems.     

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.     

An explication of secret sharing schemes

This paper is an explication of secret sharing schemes, emphasizing combinatorial construction methods. The main problem we consider is the construction of perfect secret sharing schemes, for specified access structures, with the maximum possible information rate.In this paper, we present numerous direct constructions for secret sharing schemes, such as the Shamir threshold scheme, the Boolean circuit construction of Benaloh and Leichter (for general access structures), the vector space construction of Brickell, and the Simmons geometric construction. We discuss the connections between ideal schemes (i.e., those with information rate equal to one) and matroids. We also mention the entropy bounds of Capocelli et al. Then we give a very general construciton, called the decomposition construction, and numerous applications of it. In particular, we study schemes for access structures based on graphs and the many interesting bounds that can be proved; and we determine the exact value of the optimal information rate for all access structures on at most four participants.Research supported by NSERC (Canada) grant A9287.     

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.     

On the optimization of bipartite secret sharing schemes

Optimizing the ratio between the maximum length of the shares and the length of the secret value in secret sharing schemes for general access structures is an extremely difficult and long-standing open problem. In this paper, we study it for bipartite access structures, in which the set of participants is divided in two parts, and all participants in each part play an equivalent role. We focus on the search of lower bounds by using a special class of polymatroids that is introduced here, the tripartite ones. We present a method based on linear programming to compute, for every given bipartite access structure, the best lower bound that can be obtained by this combinatorial method. In addition, we obtain some general lower bounds that improve the previously known ones, and we construct optimal secret sharing schemes for a family of bipartite access structures.     

Optimal complexity of secret sharing schemes with four minimal qualified subsets

The complexity of a secret sharing scheme is defined as the ratio between the maximum length of the shares and the length of the secret. This paper deals with the open problem of optimizing this parameter for secret sharing schemes with general access structures. Specifically, our objective is to determine the optimal complexity of the access structures with exactly four minimal qualified subsets. Lower bounds on the optimal complexity are obtained by using the known polymatroid technique in combination with linear programming. Upper bounds are derived from decomposition constructions of linear secret sharing schemes. In this way, the exact value of the optimal complexity is determined for several access structures in that family. For the other ones, we present the best known lower and upper bounds.     

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.     

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.     

Geometrical contributions to secret sharing theory

Finite geometry has found applications in many different fields and practical environments. We consider one such application, to the theory of secret sharing, where finite projective geometry has proved to be very useful, both as a modelling tool and as a means to establish interesting results. A secret sharing scheme is a means by which some secret data can be shared among a group of entities in such a way that only certain subsets of the entities can jointly compute the secret. Secret sharing schemes are useful for information security protocols, where they can be used to jointly protect cryptographic keys or provide a means of access control. We review the contribution of finite projective geometry to secret sharing theory, highlighting results and techniques where its use has been of particular significance.     

Tight Bounds on the Information Rate of Secret Sharing Schemes

A secret sharing scheme is a protocol by means of which a dealer distributes a secret s among a set of participants P in such a way that only qualified subsets of P can reconstruct the value of s whereas any other subset of P, non-qualified to know s, cannot determine anything about the value of the secret.In this paper we provide a general technique to prove upper bounds on the information rate of secret sharing schemes. The information rate is the ratio between the size of the secret and the size of the largest share given to any participant. Most of the recent upper bounds on the information rate obtained in the literature can be seen as corollaries of our result. Moreover, we prove that for any integer d there exists a d-regular graph for which any secret sharing scheme has information rate upper bounded by 2/(d+1). This improves on van Dijk's result dik and matches the corresponding lower bound proved by Stinson in [22].     

On the Dealer's Randomness Required in Secret Sharing Schemes

In this paper we provide upper and lower bounds on the randomness required by the dealer to set up a secret sharing scheme for infinite classes of access structures. Lower bounds are obtained using entropy arguments. Upper bounds derive from a decomposition construction based on combinatorial designs (in particular, t-(v,k,) designs). We prove a general result on the randomness needed to construct a scheme for the cycle Cn; when n is odd our bound is tight. We study the access structures on at most four participants and the connected graphs on five vertices, obtaining exact values for the randomness for all them. Also, we analyze the number of random bits required to construct anonymous threshold schemes, giving upper bounds. (Informally, anonymous threshold schemes are schemes in which the secret can be reconstructed without knowledge of which participants hold which shares.)     

Finding lower bounds on the complexity of secret sharing schemes by linear programming

Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants.By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.     

Ideal secret sharing schemes whose minimal qualified subsets have at most three participants

One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. Brickell and Davenport proved that every one of these ideal access structures is related in a certain way to a unique matroid. Specifically, they are matroid ports. In addition to the search of general results, this difficult open problem has been studied in previous works for several families of access structures. In this paper we do the same for access structures with rank 3, that is, structures whose minimal qualified subsets have at most three participants. We completely characterize and classify the rank-3 access structures that are matroid ports. We prove that all access structures with rank three that are ports of matroids greater than 3 are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the rank-3 matroids that can be represented by an ideal secret sharing scheme. A previous version of this paper appeared in Fifth Conference on Security and Cryptography for Networks, SCN 2006, Lecture Notes in Computer Science 4116 (2006) 201–215.     

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.     

Linear Secret Sharing Schemes and Rearrangements of Access Structures

In this paper we study linear secret sharing schemes by monotone span programs, according to the relation between realizing access structures by linear secret sharing schemes and computing monotone Boolean functions by monotone span programs. We construct some linear secret sharing schemes. Furthermore, we study the rearrangements of access structures that is very important in practice.     

On-line secret sharing

In a perfect secret sharing scheme the dealer distributes shares to participants so that qualified subsets can recover the secret, while unqualified subsets have no information on the secret. In an on-line secret sharing scheme the dealer assigns shares in the order the participants show up, knowing only those qualified subsets whose all members she has seen. We often assume that the overall access structure (the set of minimal qualified subsets) is known and only the order of the participants is unknown. On-line secret sharing is a useful primitive when the set of participants grows in time, and redistributing the secret when a new participant shows up is too expensive. In this paper we start the investigation of unconditionally secure on-line secret sharing schemes. The complexity of a secret sharing scheme is the size of the largest share a single participant can receive over the size of the secret. The infimum of this amount in the on-line or off-line setting is the on-line or off-line complexity of the access structure, respectively. For paths on at most five vertices and cycles on at most six vertices the on-line and offline complexities are equal, while for other paths and cycles these values differ. We show that the gap between these values can be arbitrarily large even for graph based access structures. We present a general on-line secret sharing scheme that we call first-fit. Its complexity is the maximal degree of the access structure. We show, however, that this on-line scheme is never optimal: the on-line complexity is always strictly less than the maximal degree. On the other hand, we give examples where the first-fit scheme is almost optimal, namely, the on-line complexity can be arbitrarily close to the maximal degree. The performance ratio is the ratio of the on-line and off-line complexities of the same access structure. We show that for graphs the performance ratio is smaller than the number of vertices, and for an infinite family of graphs the performance ratio is at least constant times the square root of the number of vertices.     

The exact values of the optimal average information ratio of perfect secret-sharing schemes for tree-based access structures

A perfect secret-sharing scheme is a method of distributing a secret among a set of participants such that only qualified subsets of participants can recover the secret and the joint shares of the participants in any unqualified subset is statistically independent of the secret. The set of all qualified subsets is called the access structure of the scheme. In a graph-based access structure, each vertex of a graph \(G\) represents a participant and each edge of \(G\) represents a minimal qualified subset. The information ratio of a perfect secret-sharing scheme is defined as the ratio between the maximum length of the share given to a participant and the length of the secret. The average information ratio is the ratio between the average length of the shares given to the participants and the length of the secret. The infimum of the (average) information ratios of all possible perfect secret-sharing schemes realizing a given access structure is called the (average) information ratio of the access structure. Very few exact values of the (average) information ratio of infinite families of access structures are known. Csirmaz and Tardos have found the information ratio of all trees. Based on their method, we develop our approach to determining the exact values of the average information ratio of access structures based on trees.     

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.      

Unconditionally Secure Group Authentication

Group authentication schemes as introduced by Boyd and by Desmedt and Frankel are cryptographic schemes in which only certain designated groups can provide messages with authentication information. In this paper we study unconditionally secure group authentication schemes based on linear perfect secret sharing and authentication schemes, for which we give expressions for the probabilities of successful attacks. Furthermore, we give a construction that uses maximum rank distance codes.