一类不可表示的多部秘密共享拟阵

 一直以来,理想的存取结构具有的特性是秘密共享领域中主要的开放性问题之一,并且该问题与拟阵论有着密切的联系.多部存取结构是指将参与者集合划分为多个部分,使得同一部分中的参与者在存取结构中扮演等价的角色,由于每个存取结构都可以看作是多部的,于是多部存取结构的特性被广泛地研究.在EUROCRYPT’07上,Farras等人研究了秘密共享方案中理想多部存取结构的特性.他们的工作具有令人振奋的结果：通过研究多部拟阵和离散多拟阵之间的关系,他们得到了多部存取结构为理想存取结构的一个必要条件和一个充分条件,并且证明了一个多部拟阵是可表示的当且仅当其对应的离散多拟阵是可表示的.在文中,他们给出了一个开放性问题：可表示的离散多拟阵具有的特性,即哪些离散多拟阵是可表示的,哪些是不可表示的.本文给出并证明了一类不可表示的离散多拟阵,即给出了一个离散多拟阵为不可表示的离散多拟阵的一个充分条件.我们将这一结论应用于Vamos拟阵,于是得到了一族不可表示的多部拟阵,同时我们利用向量的线性相关和线性无关性对Vamos拟阵的不可表示性给出了新的证明.     

Strongly ideal secret sharing schemes

We define strongly ideal secret sharing schemes to be ideal secret sharing schemes in which certain natural requirements are placed on the decoder. We prove an information-theoretic characterization of perfect schemes, and use it to determine which access structures can be encoded by strongly ideal schemes. We also discuss a hierarchy of secret sharing schemes that are more powerful than strongly ideal schemes.     

理想的多密门限体制的拟阵结构

门限体制是秘密共享体制中最基本的一类,其特点是简洁而实用．本文讨论了门限体制的拟阵结构,得到理想的多密门限体制存在的条件．     

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.     

Divergence From Factorizable Distributions and Matroid Representations by Partitions

Maximization of the information divergence from any hierarchical log-linear model is studied. A new upper bound on the maximum is presented and its tightness analyzed. For the models given by the bases of a matroid, the latter is related to matroid representations by partitions or, equivalently, to ideal secret-sharing schemes. A new link between the divergence maximization, the maximum-likelihood principle, and secret sharing is established.      

Ideal Multipartite Secret Sharing Schemes

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. In this work, the characterization of ideal multipartite access structures is studied with all generality. Our results are based on the well-known connections between ideal secret sharing schemes and matroids and on the introduction of a new combinatorial tool in secret sharing, integer polymatroids .     

On Codes, Matroids, and Secure Multiparty Computation From Linear Secret-Sharing Schemes

Error-correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, the connections between codes, matroids, and a special class of secret sharing schemes, namely, multiplicative linear secret sharing schemes (LSSSs), are studied. Such schemes are known to enable multiparty computation protocols secure against general (nonthreshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. A property of strongly multiplicative LSSSs that could be useful in solving this problem is proved. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, it is shown that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, the considered open problem is to determine whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be restated in terms of representability of identically self-dual matroids by self-dual codes. A new concept is introduced, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. It is proved that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.     

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.     

Universally ideal secret-sharing schemes

Given a set of parties {1, ···, n}, an access structure is a monotone collection of subsets of the parties. For a certain domain of secrets, a secret-sharing scheme for an access structure is a method for a dealer to distribute shares to the parties. These shares enable subsets in the access structure to reconstruct the secret, while subsets not in the access structure get no information about the secret. A secret-sharing scheme is ideal if the domains of the shares are the same as the domain of the secrets. An access structure is universally ideal if there exists an ideal secret-sharing scheme for it over every finite domain of secrets. An obvious necessary condition for an access structure to be universally ideal is to be ideal over the binary and ternary domains of secrets. The authors prove that this condition is also sufficient. They also show that being ideal over just one of the two domains does not suffice for universally ideal access structures. Finally, they give an exact characterization for each of these two conditions     

基于网络流上的秘密共享体制

给定一个通道结构,使它的极小通道结构对应于一个网络的极小割集族,那么存在一个实现它的理想秘密共享体制。而每一个密钥的子密钥正好构成该网络的一个流,反之亦然。给出的实现这些体制的方法极其有效。     

Hierarchical Threshold Secret Sharing

We consider the problem of threshold secret sharing in groups with hierarchical structure. In such settings, the secret is shared among a group of participants that is partitioned into levels. The access structure is then determined by a sequence of threshold requirements: a subset of participants is authorized if it has at least k₀ 0 members from the highest level, as well as at least k₁ > k₀ members from the two highest levels and so forth. Such problems may occur in settings where the participants differ in their authority or level of confidence and the presence of higher level participants is imperative to allow the recovery of the common secret. Even though secret sharing in hierarchical groups has been studied extensively in the past, none of the existing solutions addresses the simple setting where, say, a bank transfer should be signed by three employees, at least one of whom must be a department manager. We present a perfect secret sharing scheme for this problem that, unlike most secret sharing schemes that are suitable for hierarchical structures, is ideal. As in Shamir's scheme, the secret is represented as the free coefficient of some polynomial. The novelty of our scheme is the usage of polynomial derivatives in order to generate lesser shares for participants of lower levels. Consequently, our scheme uses Birkhoff interpolation, i.e., the construction of a polynomial according to an unstructured set of point and derivative values. A substantial part of our discussion is dedicated to the question of how to assign identities to the participants from the underlying finite field so that the resulting Birkhoff interpolation problem will be well posed. In addition, we devise an ideal and efficient secret sharing scheme for the closely related hierarchical threshold access structures that were studied by Simmons and Brickell.     

Secret sharing schemes from three classes of linear codes

Secret sharing has been a subject of study for over 20 years, and has had a number of real-world applications. There are several approaches to the construction of secret sharing schemes. One of them is based on coding theory. In principle, every linear code can be used to construct secret sharing schemes. But determining the access structure is very hard as this requires the complete characterization of the minimal codewords of the underlying linear code, which is a difficult problem in general. In this paper, a sufficient condition for all nonzero codewords of a linear code to be minimal is derived from exponential sums. Some linear codes whose covering structure can be determined are constructed, and then used to construct secret sharing schemes with nice access structures.     

On the classification of ideal secret sharing schemes

In a secret sharing scheme a dealer has a secret key. There is a finite set P of participants and a set of subsets of P. A secret sharing scheme with as the access structure is a method which the dealer can use to distribute shares to each participant so that a subset of participants can determine the key if and only if that subset is in . The share of a participant is the information sent by the dealer in private to the participant. A secret sharing scheme is ideal if any subset of participants who can use their shares to determine any information about the key can in fact actually determine the key, and if the set of possible shares is the same as the set of possible keys. In this paper we show a relationship between ideal secret sharing schemes and matroids.This work was performed at the Sandia National Laboratories and was supported by the U.S. Department of Energy under Contract No. DE-AC04-76DP00789.     

具有传递性质的接入结构上的秘密分享方案的构造

引入了具有传递性质的接入结构的概念,并给出一种构造具有这类接入结构的秘密分享方案的通用方法,该方法简捷易行.对要分享的一个秘密,不管一个参与者属于多少个最小合格子集,他只需保存一个秘密份额.而且用于分享多个秘密时,不需要增加分享者额外的信息保存量.因而优于已有的其他许多方法.文中还给出了实例以说明如何具体地构造具有这类接入结构的秘密分享方案.     

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     

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     

Generalized Access Structure Congestion System

The k-out-of-n secret sharing schemes are effective, reliable, and secure methods to prevent a secret or secrets from being lost, stolen, or corrupted. The circular sequential k-out-of-n congestion (CSknC) system , based upon this type of secret sharing scheme, is presented for reconstructing secret(s) from any k servers among n servers in circular, sequential order. When a server is connected successfully, it will not be reconnected in later rounds until the CSknC system has k distinct, successfully connected servers. An optimal server arrangement in a CSknC system is determined in where n servers have known network connection probabilities for two states, i.e., congested, and successful. In this paper, we present: i) a generalized access structure congestion (GGammaC) system that is based upon the generalized secret sharing scheme, and ii) an efficient connection procedure for the GGammaC system in terms of the minimal number of server connection attempts. The k-out-of-n secret sharing schemes are considered as simple cases of the generalized secret sharing schemes. It implies that the GGammaC system is a more general system than the CSknC system. We established an iterative connection procedure for the new system. Simulation results are used to demonstrate that the iterative connection procedure is more efficient in terms of minimizing the number of connection attempts     

异或视觉密码的理想存取结构研究

该文给出异或视觉密码的理想存取结构的定义,分析了其特征,研究了理想存取结构的共享份构造方法。在此基础上,提出将通用存取结构划分为若干个理想存取结构的算法,设计了通用存取结构的秘密分享与恢复流程。与现有的方案相比,该方案实现了秘密图像的完全恢复,且明显地减小了共享份的规模。     

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.