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.     

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.     

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 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.     

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.     

A perfect threshold secret sharing scheme to identify cheaters

In this paper we consider the problem of identifying cheaters in secret sharing schemes. Rabin and Ben-Or presented a perfect and unconditionally secure secret sharing scheme in which the honest participants are able to identify the cheaters. We present a similar scheme, but one in which the information distributed to each participant is smaller.     

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.     

On Some Methods for Unconditionally Secure Key Distribution and Broadcast Encryption

This paper provides an exposition of methods by which a trusted authority can distribute keys and/or broadcast a message over a network, so that each member of a privileged subset of users can compute a specified key or decrypt the broadcast message. Moreover, this is done in such a way that no coalition is able to recover any information on a key or broadcast message they are not supposed to know. The problems are studied using the tools of information theory, so the security provided is unconditional (i.e., not based on any computational assumption).We begin by surveying some useful schemes for key distribution that have been presented in the literature, giving background and examples (but not too many proofs). In particular, we look more closely at the attractive concept of key distribution patterns, and present a new method for making these schemes more efficient through the use of resilient functions. Then we present a general approach to the construction of broadcast schemes that combines key predistribution schemes with secret sharing schemes. We discuss the Fiat-Naor Broadcast Scheme, as well as other, new schemes that can be constructed using this approach.     

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.     

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.     

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.     

基于线性码的新的秘密分享方案

A secret sharing system can be damaged when the dealer cheating occurs. In this paper,two kinds of secret sharing schemes based on linear code are proposed. One is a verifiable scheme which each participant can verify his own share from dealer‘s distribution and ensure each participant to receive valid share. Another does not have a trusted center, here, each participant plays a dual-role as the dealer and shadow(or share) provider in the whole scheme.     

Detection and identification of cheaters in (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) secret sharing scheme

In a (t, n) secret sharing scheme, a secret s is divided into n shares and shared among a set of n shareholders by a mutually trusted dealer in such a way that any t or more than t shares will be able to reconstruct this secret; but fewer than t shares cannot know any information about the secret. When shareholders present their shares in the secret reconstruction phase, dishonest shareholder(s) (i.e. cheater(s)) can always exclusively derive the secret by presenting faked share(s) and thus the other honest shareholders get nothing but a faked secret. Cheater detection and identification are very important to achieve fair reconstruction of a secret. In this paper, we consider the situation that there are more than t shareholders participated in the secret reconstruction. Since there are more than t shares (i.e. it only requires t shares) for reconstructing the secret, the redundant shares can be used for cheater detection and identification. Our proposed scheme uses the shares generated by the dealer to reconstruct the secret and, at the same time, to detect and identify cheaters. We have included discussion on three attacks of cheaters and bounds of detectability and identifiability of our proposed scheme under these three attacks. Our proposed scheme is an extension of Shamir’s secret sharing scheme.      

Hypergraph decomposition and secret sharing

A secret sharing scheme is a protocol by which a dealer distributes a secret among a set of participants in such a way that only qualified sets of them can reconstruct the value of the secret whereas any non-qualified subset of participants obtain no information at all about the value of the secret. Secret sharing schemes have always played a very important role for cryptographic applications and in the construction of higher level cryptographic primitives and protocols.In this paper we investigate the construction of efficient secret sharing schemes by using a technique called hypergraph decomposition, extending in a non-trivial way the previously studied graph decomposition techniques. A major advantage of hypergraph decomposition is that it applies to any access structure, rather than only structures representable as graphs. As a consequence, the application of this technique allows us to obtain secret sharing schemes for several classes of access structures (such as hyperpaths, hypercycles, hyperstars and acyclic hypergraphs) with improved efficiency over previous results. Specifically, for these access structures, we present secret sharing schemes that achieve optimal information rate. Moreover, with respect to the average information rate, our schemes improve on previously known ones.In the course of the formulation of the hypergraph decomposition technique, we also obtain an elementary characterization of the ideal access structures among the hyperstars, which is of independent interest.     

对偶单调张成方案的有效构造

由线性码和线性秘密分享体制的对应关系,利用线性码的对偶码,分别从单秘密分享和多秘密分享两个方面给出对偶单调张成方案的有效构造.作为一个应用,可以得到线性多秘密分享的乘性构造.     

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.     

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 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.     

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.