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.     

Secret image sharing scheme with hierarchical threshold access structure

A hierarchical threshold secret image sharing (HTSIS) scheme is a method to share a secret image among a set of participants with different levels of authority. Recently, Guo et al. (2012) [22] proposed a HTSIS scheme based on steganography and Birkhoff interpolation. However, their scheme does not provide the required secrecy needed for HTSIS schemes so that some non-authorized subsets of participants are able to recover parts of the secret image. In this paper, we employ cellular automata and Birkhoff interpolation to propose a secure HTSIS scheme. In the new scheme, each authorized subset of participants is able to recover both the secret and cover images losslessly whereas non-authorized subsets obtain no information about the secret image. Moreover, participants are able to detect tampering of the recovered secret image. Experimental results show that the proposed scheme outperforms Guo et al.’s approach in terms of visual quality as well.     

等级系统中的访问控制方案研究

本文基于Lagrange插值多项式,提出了等级系统中的一个访问控制方案,并从空间复杂度和时间复杂度角度分析了其性能.该方案具有很强的安全性,并且允许所有用户自主选择秘密密钥.提出了基于门限秘密共享体制的一般性访问控制方案,阐述了一般性的访问控制方案的基本思想、方案的构造算法及安全性.     

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.     

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

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

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

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.     

基于理想格的鲁棒门限代理重加密方案

代理重加密能够实现解密权限的转换,而鲁棒门限代理重加密（Threshold Proxy Re-Encryption,TPRE）不仅支持安全灵活的转化控制,而且支持转化密文的合法性验证.本文利用理想格上工具构造了一种TPRE方案,采用Shamir秘密共享实现门限控制,采用格上同态签名技术实现鲁棒性,可完全抗量子攻击.新方案与标准格上方案相比,密文尺寸小、密钥份额短、计算速度快;基于PRE和TPRE安全模型的差异,证明对TPRE的攻击多项式时间内可转化为对基础PRE方案的攻击,安全性可规约为R-LWE（Learning With Errors over Ring）困难假设;新方案适用于在去中心化环境中实现密文访问控制,可用于基于区块链网络的文件共享和多域网络快速互联等场景.     

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

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

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 secret sharing systems

A "secret sharing system" permits a secret to be shared amongntrustees in such a way that anykof them can recover the secret, but anyk-1have complete uncertainty about it. A linear coding scheme for secret sharing is exhibited which subsumes the polynomial interpolation method proposed by Shamir and can also be viewed as a deterministic version of Blakley's probabilistic method. Bounds on the maximum value ofnfor a givenkand secret size are derived for any system, linear or nonlinear. The proposed scheme achieves the lower bound which, for practical purposes, differs insignificantly from the upper bound. The scheme may be extended to protect several secrets. Methods to protect against deliberate tampering by any of the trustees are also presented.     

双重门限秘密共享方案

基于RSA密码体制、Shamir门限方案和哈希函数的安全性,设计了一种双重门限秘密共享方案。方案中,参与者只需维护一个秘密份额,可实现对多个秘密的共享。秘密份额由参与者确定和保管,秘密分发者也不知晓,秘密共享过程中,只需出示伪秘密份额。方案不需要维护安全信道,算法能够保证信息安全传送,以及验证参与者是否进行了欺骗。     

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     

一种门限代理签名方案的分析与改进

通过对Qian-cao-xue的基于双线性映射的的门限代理签名方案分析,发现该方案并不满足强不可伪造性,任何人包括原始签名人可以伪造一个有效的代理签名,同时该方案也不能抵抗原始签名人改变攻击.在此基础上提出了改进的门限代理签名方案(方案1),改进的方案克服了原方案的安全缺陷.并把矢量空间秘密共享和多重代理签名结合起来,构建了一种更为广泛的基于访问结构的多重代理签名(方案2).门限代理签名方案(方案1)成为方案2的特殊情形.方案2中任何参与者的授权子集能产生多重代理签名,而非参与者不可能产生有效的多重代理签名,接收者可以通过验证方法验证个体代理签名和多重代理签名的合法性,而且能保证任何参与者都能检测出错误的子秘密.能抵御各种可能的攻击.     

基于多项式秘密共享的图像密文域可逆信息隐藏

针对密文域可逆信息隐藏在多用户场景下算法嵌入率低、载体图像容灾性能较弱等问题，该文提出一种基于多项式秘密共享的图像密文域可逆信息隐藏方案。通过将图像分割成多幅影子图像并存储在不同的用户端，可以增强图像的容灾性，为了实现额外信息在图像重构前后提取的可分离性，该方案包括两种嵌入算法:算法1在图像分割的过程中，将额外信息嵌入多项式的冗余系数中得到含有额外信息的影子图像，该算法支持在图像重构之后提取额外信息；算法2针对图像分割后的任一影子图像，利用秘密共享的加法同态特性实施嵌入，该算法支持直接从影子图像中提取额外信息。实验在不同门限方案和影子图像压缩率的条件下进行测试，当压缩率为50%时，(3, 4)门限方案的嵌入率达4.18 bpp(bit per pixel)，(3, 5)门限方案的嵌入率达3.78 bpp。结果表明，两种嵌入算法分别支持从影子图像与重构图像中提取额外信息，实现了方案的可分离性；与现有方案相比，所提算法嵌入率较高、计算复杂度较低，具有较强的实用性。     

新的安全分布式n个秘密乘积共享方案

由于Shamir的秘密共享方案并不具有乘法的同态性质, 因此针对安全分布式乘法计算中利用传统的Shamir线性多项式进行n个秘密乘积共享时需要不断调用两方秘密乘积子协议的缺点,首先用哥德尔数对保密数据进行编码,接着利用这种具有乘法同态的编码方法和一种加法同态承诺方案,实现了一种新的安全分布式一次性共享n个秘密乘积的方案,并证明了即使有恶意的参与者存在时,此方案仍为安全的。分析表明,本方案不但简单可行,而且相比传统方案效率明显提高。     

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.     

Essential secret image sharing scheme with different importance of shadows

In (k, n) secret image sharing (SIS), a scheme encrypts a secret image into n shadow images. Any k or more shadow images can be collaborated together to reveal the secret image. Most of the previous SIS schemes don’t distinguish the importance of shadows. However, in some application environments, some participants are accorded special privileges due to their status or importance. Thus, some shadows may be more important than others. In this paper, we consider the (t, s, k, n) essential SIS (ESIS) scheme. All n shadows are classified into s essential shadows and (n–s) non-essential shadows. When reconstructing the secret image, the (t, s, k, n)-ESIS scheme needs k shadows, which should include at least t essential shadows.     

Scalable secret image sharing

In this paper, we propose an innovative scheme, namely the scalable secret image sharing scheme, for sharing an image O among n participants such that the clarity of the reconstructed image (i.e., the amount of information therein) scales with proportion with the number of the participants. The proposed scheme encodes O into n shadow images that exhibit the following features: (a) each shadow image reveals no information about O, (b) each shadow image is only half the size of O, (c) any k (2⩽k⩽n) shadow images can be used to reconstruct O in a scalable manner such that the amount of information about O is proportional to k, and (d) O can be reconstructed perfectly when all of the n shadow images are available. The clarity of O can be measured in terms of several metrics. We define three modes, namely the multisecret, priority, and progressive modes, for sharing O in our scheme. The scalability and flexibility of the proposed schemes indicate the wide range of potential applications for secret image sharing.