共查询到20条相似文献,搜索用时 875 毫秒
1.
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. 相似文献
2.
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.
相似文献
3.
A perfect threshold secret sharing scheme to identify cheaters 总被引:10,自引:0,他引:10
Marco Carpentieri 《Designs, Codes and Cryptography》1995,5(3):183-187
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. 相似文献
4.
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.
相似文献
5.
Cheating in Visual Cryptography 总被引:3,自引:0,他引:3
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. 相似文献
6.
Hypergraph decomposition and secret sharing 总被引:1,自引:0,他引:1
Giovanni Di Crescenzo 《Discrete Applied Mathematics》2009,157(5):928-946
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. 相似文献
7.
Tight Bounds on the Information Rate of Secret Sharing Schemes 总被引:4,自引:0,他引:4
Carlo Blundo Alfredo De Santis Roberto De Simone Ugo Vaccaro 《Designs, Codes and Cryptography》1997,11(2):107-110
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]. 相似文献
8.
Detection of Cheaters in Vector Space Secret Sharing Schemes 总被引:23,自引:0,他引:23
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. 相似文献
9.
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.) 相似文献
10.
TanXiaoqing WangZhiguo 《高校应用数学学报(英文版)》2004,19(2):160-166
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. 相似文献
11.
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. 相似文献
12.
Barbara Masucci 《Designs, Codes and Cryptography》2006,39(1):89-111
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. 相似文献
13.
Ying-pu Deng Li-feng Guo Mu-lan Liu 《应用数学学报(英文版)》2007,23(1):67-78
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. 相似文献
14.
Mahabir Prasad Jhanwar Ayineedi Venkateswarlu Reihaneh Safavi-Naini 《Designs, Codes and Cryptography》2014,73(2):529-546
A verifiable secret sharing is a secret sharing scheme with an untrusted dealer that allows participants to verify validity of their own shares. A publicly verifiable secret sharing (PVSS) scheme is a verifiable secret sharing scheme that allows a third party to verify correctness of the distributed shares. We propose an efficient non-interactive PVSS scheme using Paillier additively homomorphic encryption system, and analyze its security in a model that we define in line with the classic semantic-security definition and offering stronger security compared to the previous models. We reduce security of our PVSS scheme to the well studied decisional composite residuosity assumption in this model. 相似文献
15.
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. 相似文献
16.
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. 相似文献
17.
In this work, a renewable, multi-use, multi-secret sharing scheme for general access structure based on the one-way collision resistant hash function is presented in which each participant has to carry only one share. As it applies the collision resistant one-way hash function, the proposed scheme is secure against conspiracy attacks even if the pseudo-secret shares are compromised. Moreover, high complexity operations like modular multiplication, exponentiation and inversion are avoided to increase its efficiency. Finally, in the proposed scheme, both the combiner and the participants can verify the correctness of the information exchanged among themselves. 相似文献
18.
19.
Oriol Farràs Jessica Ruth Metcalf-Burton Carles Padró Leonor Vázquez 《Designs, Codes and Cryptography》2012,63(2):255-271
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. 相似文献
20.
Perfect Secret Sharing Schemes on Five Participants 总被引:1,自引:0,他引:1
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. 相似文献