Ideal secret sharing schemes with multiple secrets

We consider secret sharing schemes which, through an initial issuing of shares to a group of participants, permit a number of different secrets to be protected. Each secret is associated with a (potentially different) access structure and a particular secret can be reconstructed by any group of participants from its associated access structure without the need for further broadcast information. We consider ideal secret sharing schemes in this more general environment. In particular, we classify the collections of access structures that can be combined in such an ideal secret sharing scheme and we provide a general method of construction for such schemes. We also explore the extent to which the results that connect ideal secret sharing schemes to matroids can be appropriately generalized.The work of the second and third authors was supported by the Australian Research Council.     

On Matroids and Nonideal Secret Sharing

Secret-sharing schemes are a tool used in many cryptographic protocols. In these schemes, a dealer holding a secret string distributes shares to the parties such that only authorized subsets of participants can reconstruct the secret from their shares. The collection of authorized sets is called an access structure. An access structure is ideal if there is a secret-sharing scheme realizing it such that the shares are taken from the same domain as the secrets. Brickell and Davenport (Journal of Cryptology, 1991) have shown that ideal access structures are closely related to matroids. They give a necessary condition for an access structure to be ideal-the access structure must be induced by a matroid. Seymour (Journal of Combinatorial Theory B, 1992) has proved that the necessary condition is not sufficient: There exists an access structure induced by a matroid that does not have an ideal scheme. The research on access structures induced by matroids is continued in this work. The main result in this paper is strengthening the result of Seymour. It is shown that in any secret-sharing scheme realizing the access structure induced by the Vamos matroid with domain of the secrets of size k, the size of the domain of the shares is at least k + Omega(radic(k)). The second result considers nonideal secret-sharing schemes realizing access structures induced by matroids. It is proved that the fact that an access structure is induced by a matroid implies lower and upper bounds on the size of the domain of shares of subsets of participants even in nonideal schemes (as long as the shares are still relatively short). This generalized results of Brickell and Davenport for ideal schemes. Finally, an example of a nonideal access structure that is nearly ideal is presented.     

On Self-Healing Key Distribution Schemes

Self-healing key distribution schemes allow group managers to broadcast session keys to large and dynamic groups of users over unreliable channels. Roughly speaking, even if during a certain session some broadcast messages are lost due to network faults, the self-healing property of the scheme enables each group member to recover the key from the broadcast messages he has received before and after that session. Such schemes are quite suitable in supporting secure communication in wireless networks and mobile wireless ad-hoc networks. Recent papers have focused on self-healing key distribution, and have provided definitions, stated in terms of the entropy function, and some constructions. The contribution of this paper is the following: We analyze current definitions of self-healing key distribution and, for two of them, we show that no protocol can achieve the definition. We show that a lower bound on the size of the broadcast message, previously derived, does not hold. We propose a new definition of self-healing key distribution, and we show that it can be achieved by concrete schemes. We give some lower bounds on the resources required for implementing such schemes, i.e., user memory storage and communication complexity. We prove that the bounds are tight     

Capacity Bounds for Broadcast Channels With Confidential Messages

This paper studies capacity bounds for discrete memoryless broadcast channels with confidential messages. Two private messages as well as a common message are transmitted; the common message is to be decoded by both receivers, while each private message is only for its intended receiver. In addition, each private message is to be kept secret from the unintended receiver where secrecy is measured by equivocation. Both inner and outer bounds are proposed to the rate equivocation region for broadcast channels with confidential messages. The proposed inner bound generalizes Csiszar and Korner's rate equivocation region for broadcast channels with a single confidential message, Liu 's achievable rate region for broadcast channels with perfect secrecy, Marton's and Gel'fand-Pinsker's achievable rate region for general broadcast channels. The proposed outer bounds, together with the inner bound, help establish the rate equivocation region of several classes of discrete memoryless broadcast channels with confidential messages, including the less noisy, deterministic, and semideterministic broadcast channels. Furthermore, specializing to the general broadcast channel by removing the confidentiality constraint, the proposed outer bounds reduce to new capacity outer bounds for the discrete memory broadcast channel.     

Graph decompositions and secret sharing schemes

In this paper we continue a study of secret sharing schemes for-access structures based on graphs. Given a graph G, we require that a subset of participants can compute a secret key if they contain an edge of G; otherwise, they can obtain no information regarding the key. We study the information rate of such schemes, which measures how much information in being distributed as shares compared with the size of the secret key, and the average information rate, which is the ratio between the secret size and the arithmetic mean of the size of the shares. We give both upper and lower bounds on the optimal information rate and average information rate that can be obtained. Upper bounds arise by applying entropy arguments due to Capocelli et al. [15]. Lower bounds come from constructions that are based on graph decompositions. Application of these constructions requires solving a particular linear programming problem. We prove some general results concerning the information rate and average information rate for paths, cycles, and trees. Also, we study the 30 (connected) graphs on at most five vertices, obtaining exact values for the optimal information rate in 26 of the 30 cases, and for the optimal average information rate in 28 of the 30 cases.The research of C. Blundo, A. De Santis, and U. Vaccaro was partially supported by the Italian Ministry of University and Research (M.U.R.S.T.) and by the National Council for Research (C.N.R.) under Grant 91.02326.CT12. The research of D. R. Stinson was supported by NSF Grant CCR-9121051.     

Mutually Trusted Authority-Free Secret Sharing Schemes

Traditional secret sharing schemes involve the use of a mutually trusted authority to assist in the generation and distribution of shares that will allow a secret to be protected among a set of participants. In contrast, this paper addresses the problem of establishing secret sharing schemes for a given access structure without the use of a mutually trusted authority. A general protocol is discussed and several implementations of this protocol are presented. Several efficiency measures are proposed and we consider how to refine the general protocol in order to improve the efficiency with respect to each of the proposed measures. Special attention is given to mutually trusted authority-free threshold schemes. Constructions are presented for such threshold schemes that are shown to be optimal with respect to each of the proposed efficiency measures. Received 13 September 1995 and revised 10 April 1996     

Optimal Communication Complexity of Generic Multicast Key Distribution

We prove a tight lower bound on the communication complexity of secure multicast key distribution protocols in which rekey messages are built using symmetric-key encryption, pseudorandom generators, and secret sharing schemes. Our lower bound shows that the amortized cost of updating the group key for each group membership change (as a function of the current group size) is at least $log_2(n) - o(1)$ basic rekey messages. This lower bound matches, up to a subconstant additive term, the upper bound due to Canetti [Proc. INFOCOM 1999], who showed that $log_2(n)$ basic rekey messages (each time a user joins and/or leaves the group) are sufficient. Our lower bound is, thus, optimal up to a small subconstant additive term. The result of this paper considerably strengthens previous lower bounds by Canetti [Proc. Eurocrypt 1999] and Snoeyink [Computer Networks, 47(3):2005] , which allowed for neither the use of pseudorandom generators and secret sharing schemes nor the iterated (nested) application of the encryption function. Our model (which allows for arbitrarily nested combinations of encryption, pseudorandom generators and secret sharing schemes) is much more general and, in particular, encompasses essentially all known multicast key distribution protocols of practical interest.      

适用于任意接入结构的可验证多秘密分享方案

对一般接入结构上的可验证多秘密分享进行了研究，给出了可适用于任意接入结构的一类可验证多秘密分享方案的构造方法。用这种方法构造的可验证多秘密分享方案具有以下性质：可在一组分享者中同时分享多个秘密；分发者发送给每一分享者的秘密份额都是可公开验证的；关于每一秘密的公开信息也是可公开验证的；恢复秘密时可防止分享者提供假的份额。分析表明，用此方法构造的可验证多秘密分享方案不仅是安全的，而且是高效的。     

Communication in key distribution schemes

A (g, b) key distribution scheme allows conferences of g users to generate secret keys, such that disjoint coalitions of b users cannot gain any information on the generated key (in the information-theoretic sense). We study the relationships between communication and space efficiency of key distribution schemes. We prove that communication does not help in the context of unrestricted schemes. On the other hand, we show that for restricted schemes, which are secure only when used by a limited number of conferences, communication can substantially improve the space efficiency. We also present lower bounds on the space efficiency of restricted schemes     

On the Contrast in Visual Cryptography Schemes

A visual cryptography scheme is a method to encode a secret image SI into shadow images called shares such that certain qualified subsets of shares enable the ``visual' recovery of the secret image. The ``visual' recovery consists of xeroxing the shares onto transparencies, and then stacking them. The shares of a qualified set will reveal the secret image without any cryptographic computation. In this paper we analyze the contrast of the reconstructed image in k out of n visual cryptography schemes. (In such a scheme any k shares will reveal the image, but no set of k-1 shares gives any information about the image.) In the case of 2 out of n threshold schemes we give a complete characterization of schemes having optimal contrast and minimum pixel expansion in terms of certain balanced incomplete block designs. In the case of k out of n threshold schemes with we obtain upper and lower bounds on the optimal contrast. Received 27 September 1996 and revised 13 February 1998     

Secret sharing with public reconstruction

All known constructions of information theoretic t-out-of-n secret-sharing schemes require secure, private communication channels among the parties for the reconstruction of the secret. We investigate the cost of performing the reconstruction over public communication channels. A naive implementation of this task distributes 2n-2 one times pads to each party. This results in shares whose size is 2n-1 times the secret size. We present three implementations of such schemes that are substantially more efficient. A scheme enabling multiple reconstructions of the secret by different subsets of parties, with factor O(n/t) increase in the shares' size. A one-time scheme, enabling a single reconstruction of the secret, with O(log(n/t)) increase in the shares' size. A one-time scheme, enabling a single reconstruction by a set of size exactly t, with factor O(1) increase in the shares' size. We prove that the first implementation is optimal (up to constant factors) by showing a tight Ω(n/t) lower bound for the increase in the shares' size     

基于多项式秘密共享的前摄性门限RSA签名方案

现有可证明安全的前摄性门限RSA签名方案均依赖加性秘密共享方法,存在每次签名均需所有成员参与,易暴露合法成员的秘密份额,签名效率低下等问题。该文以Shoup门限签名为基础,提出一种基于多项式秘密共享的前摄性门限RSA签名方案,并对其进行了详细的安全性及实用性分析。结果表明,在静态移动攻击者模型中,该方案是不可伪造的和稳健的,与现有同类方案相比,其通信开销更低,运算效率更高。     

Some improved bounds on the information rate of perfect secret sharing schemes

In this paper we study secret sharing schemes for access structures based on graphs. A secret sharing scheme enables a secret key to be shared among a set of participants by distributing partial information called shares. Suppose we desire that some specified pairs of participants be able to compute the key. This gives rise in a natural way to a graphG which contains these specified pairs as its edges. The secret sharing scheme is calledperfect if a pair of participants corresponding to a nonedge ofG can obtain no information regarding the key. Such a perfect secret sharing scheme can be constructed for any graph. In this paper we study the information rate of these schemes, which measures how much information is being distributed as shares compared with the size of the secret key. We give several constructions for secret sharing schemes that have a higher information rate than previously known schemes. We prove the general result that, for any graphG having maximum degreed, there is a perfect secret sharing scheme realizingG in which the information rate is at least 2/(d+3). This improves the best previous general bound by a factor of almost two. The work of E. F. Brickell was performed at the Sandia National Laboratories and was supported by the U.S. Department of Energy under Contract Number DE-AC04-76DP00789. The research of D. R. Stinson was supported by NSERC Operating Grant A9287 and by the Center for Communication and Information Science, University of Nebraska.     

AN EFFICIENT AND SECURE （t, n） THRESHOLD SECRET SHARING SCHEME

Based on Shamir＇s threshold secret sharing scheme and the discrete logarithm problem, a new （t, n） threshold secret sharing scheme is proposed in this paper. In this scheme, each participant＇s secret shadow is selected by the participant himself, and even the secret dealer cannot gain anything about his secret shadow. All the shadows are as short as the shared secret. Each participant can share many secrets with other participants by holding only one shadow. Without extra equations and information designed for verification, each participant is able to check whether another participant provides the true information or not in the recovery phase. Unlike most of the existing schemes, it is unnecessary to maintain a secure channel between each participant and the dealer. Therefore, this scheme is very attractive, especially under the circumstances that there is no secure channel between the dealer and each participant at all. The security of this scheme is based on that of Shamir＇s threshold scheme and the difficulty in solving the discrete logarithm problem. Analyses show that this scheme is a computationally secure and efficient scheme.     

新型有效的秘密共享方案

提出了一种新的秘密共享方案。该方案分两层实现:上层,基于Stern-Brocot树把一个大的秘密拆分为t个小整数(子秘密);底层,借鉴一维元胞自动机模型中的进化方法,把上层的t个子秘密作为初始状态,动态生成各参与者的共享。特别地,该方案能够动态扩展参与者,动态调整门限值,动态更新秘密和共享。另外,还具有计算简单,各参与者共享份额短的优点。分析结果表明,该方案安全、有效。     

Wireless broadcast encryption based on smart cards

Wireless broadcasting is an efficient way to broadcast data to a large number of users. Some commercial applications of wireless broadcasting, such as satellite pay-TV, desire that only those users who have paid for the service can retrieve broadcast data. This is often achieved by broadcast encryption, which allows a station securely to broadcast data to a dynamically changing set of privileged users through open air. Most existing broadcast encryption schemes can only revoke a pre-specified number of users before system re-setup or require high computation, communication and storage overheads in receivers. In this paper, we propose a new broadcast encryption scheme based on smart cards. In our scheme, smart cards are used to prevent users from leaking secret keys. Additionally, once an illegally cloned smart card is captured, our scheme also allows tracing of the compromised smart card by which illegal smart cards are cloned, and can then revoke all cloned smart cards. The new features of our scheme include minimal computation needs of only a few modular multiplications in the smart card, and the capability to revoke up to any number of users in one revocation. Furthermore, our scheme is secure against both passive and active attacks and has better performance than other schemes.     

具有前向安全性质的秘密共享方案

由于已有的秘密共享方案都不具有前向安全的性质,该文基于有限域上离散对数难解问题和强RSA 假设,应用前向安全理论和已有的秘密共享方案特别是Boyd提出的乘法门限方案的思想,提出了一种具有前向安全特性的秘密共享方案。该方案具有子密的可验证性,能够检测伪子密,防止欺诈者;具有子密更新简便及更新后的子密的可验证性;具有秘密恢复快捷且能直接恢复时间周期j 的秘密信息及检测恢复得到的秘密信息是否正确等功效。该文同时还对方案的安全性进行了分析。     

Secret sharing schemes with bipartite access structure

We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights     

On the size of shares for secret sharing schemes

A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. The set of all qualified subsets defines the access structure to the secret. Sharing schemes are useful in the management of cryptographic keys and in multiparty secure protocols.We analyze the relationships among the entropies of the sample spaces from which the shares and the secret are chosen. We show that there are access structures with four participants for which any secret sharing scheme must give to a participant a share at least 50% greater than the secret size. This is the first proof that there exist access structures for which the best achievable information rate (i.e., the ratio between the size of the secret and that of the largest share) is bounded away from 1. The bound is the best possible, as we construct a secret sharing scheme for the above access structures that meets the bound with equality.This work was partially supported by Algoritmi, Modelli di Calcolo e Sistemi Informativi of M.U.R.S.T. and by Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of C.N.R. under Grant Number 91.00939.PF69.     

基于身份的泛在通信隐私保护方案

针对泛在通信应用场景中数据传输的私密性要求,基于IBE公钥加密算法和Shamir门限秘密共享,提出了一种泛在通信隐私保护方案。方案以不同信任域身份标识为公钥,加密后的影子密钥可通过广播信道分发,满足门限条件的节点可以重构隐私会话密钥。方案具有随机预言模型下可证明的IND-sID-CPA安全性,支持安全的新成员加入策略,具有较小的计算复杂度和存储、通信开销。