New results and applications for multi-secret sharing schemes
New results and applications for multi-secret sharing schemes
复制标题
DOI：
10.1007/s10623-013-9831-6
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
Javier Herranz;Alexandre Ruiz;Germán Sáez
中科院分区：
文献类型：
--
作者：
Javier Herranz;Alexandre Ruiz;Germán Sáez
在多秘密共享方案（MSSS）中，不同的秘密在某个集合中的参与者之间分配，每个参与者根据一个访问结构。这个问题的简单解决方案是运行标准秘密共享方案的独立实例，每个秘密一个。在该解决方案中，每个参与者存储的秘密份额的长度随着（当保持所有其他参数固定时）线性增长。密码学界主要从理论的角度研究多秘密共享方案：针对无条件（信息论）和计算安全性，提出了不同的模型和定义。在无条件安全的情况下，有两种不同的定义。它已被证明，对于某些特定的情况下，访问结构，包括阈值的情况下，一个MSSS具有最强的无条件安全性的水平必须有份额长度线性。因此，这种情况下的最优解等价于平凡解。在这项工作中，我们证明，即使是一个更宽松的概念，无条件的安全性，并为某些类型的访问结构（特别是，阈值的），我们有同样的效率问题：每个秘密份额的长度必须线性增长。由于我们想要更有效的解决方案，我们转向具有计算安全性的MSSS场景。我们提出了一个新的MSSS，其中每个秘密份额具有恒定的长度（只有一个元素），我们正式证明了它的计算安全性的随机预言模型。据我们所知，这是第一个正式的分析计算安全的MSSS。我们使用它作为两个新的功能：多策略签名和多策略解密的两个计划的设计中的关键成分，新的MSSS的效用。我们证明了这两个新的多策略密码系统的安全性在一个正式的安全模型。这两个新的原语提供了类似的功能，基于属性的密码系统，一些优点和一些缺点，我们讨论在这项工作的最后。
In a multi-secret sharing scheme (MSSS),different secrets are distributed among the players in some set, each one according to an access structure. The trivial solution to this problem is to runindependent instances of a standard secret sharing scheme, one for each secret. In this solution, the length of the secret share to be stored by each player grows linearly with(when keeping all other parameters fixed). Multi-secret sharing schemes have been studied by the cryptographic community mostly from a theoretical perspective: different models and definitions have been proposed, for both unconditional (information-theoretic) and computational security. In the case of unconditional security, there are two different definitions. It has been proved that, for some particular cases of access structures that include the threshold case, a MSSS with the strongest level of unconditional security must have shares with length linear in. Therefore, the optimal solution in this case is equivalent to the trivial one. In this work we prove that, even for a more relaxed notion of unconditional security, and for some kinds of access structures (in particular, threshold ones), we have the same efficiency problem: the length of each secret share must grow linearly with. Since we want more efficient solutions, we move to the scenario of MSSSs with computational security. We propose a new MSSS, where each secret share has constant length (just one element), and we formally prove its computational security in the random oracle model. To the best of our knowledge, this is the first formal analysis on the computational security of a MSSS. We show the utility of the new MSSS by using it as a key ingredient in the design of two schemes for two new functionalities: multi-policy signatures and multi-policy decryption. We prove the security of these two new multi-policy cryptosystems in a formal security model. The two new primitives provide similar functionalities as attribute-based cryptosystems, with some advantages and some drawbacks that we discuss at the end of this work.