Multipartite Secret Sharing Based on CRT

Secure communication has become more and more important for system security. Since avoiding the use of encryption one by one can introduce less computation complexity, secret sharing scheme (SSS) has been used to design many security protocols. In SSSs, several authors have studied multipartite access structures, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Access structures realized by threshold secret sharing are the simplest multipartite access structures, i.e., unipartite access structures. Since Asmuth–Bloom scheme based on Chinese remainder theorem (CRT) was presented for threshold secret sharing, recently, threshold cryptography based on Asmuth–Bloom secret sharing were firstly proposed by Kaya et al. In this paper, we extend Asmuth–Bloom and Kaya schemes to bipartite access structures and further investigate how SSSs realizing multipartite access structures can be conducted with the CRT. Actually, every access structure is multipartite and, hence, the results in this paper can be seen as a new construction of general SSS based on the CRT. Asmuth–Bloom and Kaya schemes become the special cases of our scheme.     

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.     

Multipartite Secret Sharing by Bivariate Interpolation

Given a set of participants that is partitioned into distinct compartments, a multipartite access structure is an access structure that does not distinguish between participants belonging to the same compartment. We examine here three types of such access structures: two that were studied before, compartmented access structures and hierarchical threshold access structures, and a new type of compartmented access structures that we present herein. We design ideal perfect secret sharing schemes for these types of access structures that are based on bivariate interpolation. The secret sharing schemes for the two types of compartmented access structures are based on bivariate Lagrange interpolation with data on parallel lines. The secret sharing scheme for the hierarchical threshold access structures is based on bivariate Lagrange interpolation with data on lines in general position. The main novelty of this paper is the introduction of bivariate Lagrange interpolation and its potential power in designing schemes for multipartite settings, as different compartments may be associated with different lines or curves in the plane. In particular, we show that the introduction of a second dimension may create the same hierarchical effect as polynomial derivatives and Birkhoff interpolation were shown to do in Tassa (J. Cryptol. 20:237–264, 2007). A preliminary version of this paper appeared in The Proceedings of ICALP 2006.     

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.     

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 .     

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.     

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.     

The Size of a Share Must Be Large

A secret sharing scheme permits a secret to be shared among participants of an n-element group in such a way that only qualified subsets of participants can recover the secret. If any nonqualified subset has absolutely no information on the secret, then the scheme is called perfect. The share in a scheme is the information that a participant must remember. In [3] it was proved that for a certain access structure any perfect secret sharing scheme must give some participant a share which is at least 50\percent larger than the secret size. We prove that for each n there exists an access structure on n participants so that any perfect sharing scheme must give some participant a share which is at least about times the secret size.^1 We also show that the best possible result achievable by the information-theoretic method used here is n times the secret size. ^1 All logarithms in this paper are of base 2. Received 24 November 1993 and revised 15 September 1995     

向量空间接入结构上信息论安全的可验证秘密分享

可验证秘密分享在诸如对机密信息的安全保存与合法利用、密钥托管、面向群体的密码学、多 方安全计算、接入控制及电子商务等许多方面都有着广泛的应用。该文对向量空间接入结构上的可验证秘密分享进行了研究。提出了这类接入结构上的一个信息论安全的高效可验证秘密分享协议。新提出的协议不仅具有较高的信息速率,而且计算和通信代价都远远的低于已有的广义可验证秘密分享协议。     

完备秘密共享方案的信息率

讨论了一类以图为访问结构的秘密共享方案的最优信息率和最优平均信息率．     

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

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

Linear codes from perfect nonlinear mappings and their secret sharing schemes

In this paper, error-correcting codes from perfect nonlinear mappings are constructed, and then employed to construct secret sharing schemes. The error-correcting codes obtained in this paper are very good in general, and many of them are optimal or almost optimal. The secret sharing schemes obtained in this paper have two types of access structures. The first type is democratic in the sense that every participant is involved in the same number of minimal-access sets. In the second type of access structures, there are a few dictators who are in every minimal access set, while each of the remaining participants is in the same number of minimal-access sets.     

含至多四个参与者的量子秘密共享方案的最优信息率

信息率是衡量量子秘密共享方案性能的一个重要指标.在本文中,我们利用超图的相关理论刻画了量子存取结构.然后,利用超图和量子存取结构间的关系给出了参与者人数至多为4的所有13个量子存取结构,并基于量子信息论研究了其最优信息率及所对应的完善的量子秘密共享方案.对其中的5种存取结构的最优信息率的准确值进行了计算,并讨论了达到此信息率的方案的具体构造;对余下的8种存取结构的最优信息率的上界进行了计算.     

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

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

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

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

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

基于向量空间接入结构的分布式密钥生成

密钥生成是密码系统的一个重要组成部分,其安全性对整个密码系统的安全性起着至关重要的作用.在群体保密通信、电子商务和面向群体的密码学中,往往需要采用分布式的密钥生成方式.本文对基于向量空间接入结构的分布式密钥生成进行了研究.以向量空间接入结构上信息论安全的一个可验证秘密分享方案为基础,提出了适应于这类接入结构的一个安全高效的分布式密钥生成协议.该协议比常见的基于门限接入结构的分布式密钥生成协议具有更广泛的适用性.     

基于极小线性码上的秘密共享方案

从理论上说,每个线性码都可用于构造秘密共享方案,但是在一般情况下,所构造的秘密共享方案的存取结构是难以确定的.本文提出了极小线性码的概念,指出基于这种码的对偶码所构造的秘密共享方案的存取结构是容易确定的.本文首先证明了极小线性码的缩短码一定是极小线性码.然后对几类不可约循环码给出它们为极小线性码的判定条件,并在理论上研究了基于几类不可约循环码的对偶码上的秘密共享方案的存取结构.最后用编程具体求出了一些实例中方案的存取结构.     

两类极小二元线性码的构造

线性码在数据存储、信息安全以及秘密共享等领域具有重要的作用。而极小线性码是设计秘密共享方案的首选码,设计极小线性码是当前密码与编码研究的重要内容之一。该文首先选取恰当的布尔函数,研究了函数的Walsh谱值分布,并利用布尔函数的Walsh谱值分布构造了两类极小线性码,确定了码的参数及重量分布。结果表明,所构造的码是不满足Ashikhmin-Barg条件的极小线性码,可用作设计具有良好访问结构的秘密共享方案。