
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Optimal Multiple Assignments Based on Integer Programming in Secret Sharing Schemes with General Access Structures
Mitsugu IWAMOTO Hirosuke YAMAMOTO Hirohisa OGAWA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E90A
No.1
pp.101112 Publication Date: 2007/01/01 Online ISSN: 17451337
DOI: 10.1093/ietfec/e90a.1.101 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Protocols Keyword: secret sharing schemes, general access structures, multiple assignment map, integer programming, ramp schemes,
Full Text: PDF(274.9KB)>>
Summary:
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 socalled 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.

