Optimal Multiple Assignments Based on Integer Programming in Secret Sharing Schemes with General Access Structures
Optimal Multiple Assignments Based on Integer Programming in Secret Sharing Schemes with General Access Structures
复制标题
DOI：
10.1093/ietfec/e90-a.1.101
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
Mitsugu Iwamoto;Hirosuke Yamamoto;Hirohisa Ogawa
中科院分区：
文献类型：
--
作者：
Mitsugu Iwamoto;Hirosuke Yamamoto;Hirohisa Ogawa
众所周知，对于任何一般的访问结构，秘密共享方案（SSS）都可以通过使用所谓的累积映射从(m, m)-阈值方案构建，也可以通过修改的累积映射从(t, m)-阈值SSS构建。然而，这种构建的SSSs通常效率不高。针对任意给定的一般接入结构，提出了一种由(t, m)-阈值格式构造SSS的新方法。在该方法中，采用整数规划方法推导出最优（t, m）阈值方案和股票的最优分配，以最小化分配给参与者的股票的平均或最大规模。从最优性上看，由于累积映射在很多情况下无法达到最优分布，因此总能获得比累积映射更低的编码率。同样的方法也适用于为不完整的通道结构及/或匝道通道结构建造SSSs。
It is known that for any general access structure, a secret sharing scheme (SSS) can be constructed from an (m, m)-threshold scheme by using the so-called cumulative map or from a (t, m)-threshold SSS by a modified cumulative map. However, such constructed SSSs are not efficient generally. In this paper, a new method is proposed to construct a SSS from a (t, m)-threshold scheme for any given general access structure. In the proposed method, integer programming is used to derive the optimal (t, m)-threshold scheme and the optimal distribution of the shares to minimize the average or maximum size of the distributed shares to participants. From the optimality, it can always attain lower coding rate than the cumulative maps because the cumulative maps cannot attain the optimal distribution in many cases. The same method is also applied to construct SSSs for incomplete access structures and/or ramp access structures.