Optimal multiple assignment based on integer programming in secret sharing with general access structures
Mitsugu Iwamoto, Hirosuke Yamamoto and Hirohisa Ogawa
- 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 comulative map or from a $(t,m)$-theshold 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 map cannot attain the optimal distribution in many cases. The same method is also applied to construct SSSs fro incomplete access structures and/or ramp access structures.
- Keywords: Secret sharing schemes; Generla access strucrures; Multiple assignment map; Integer programming; Ramp schemes
- PDF (280Kbytes) Copyright(c)2007 IEICE
DOI: 10.1093/ietfec/e90-a.1.101