所報 107

31/46

In 1979, Blakley and Shamir independently introduced the concept of secret sharing. The basic idea of secret sharing is that a dealer distributes a piece of information (called a share) about a secret to each participant such that authorized subsets of participants can reconstruct the secret but unauthorized subsets of participants cannot determine the secret. In Shamir’s (k, n)-threshold scheme, every k participants can recover the secret K, but no group of less than k participants cannot get any information about the secret. The collection of all authorized subsets is called the access structure. A (k, n)-threshold scheme can only realize particular access structures that contain all subsets of k or more participants. In 1987, Ito, Saito and Nishizeki proposed a secret sharing scheme realizing general access structures, called the multiple assignment secret sharing scheme (MASSS). Their scheme can realize an arbitrary access structure. In the implemen-tation of secret sharing schemes, an important issue is the number of shares distributed to each participant. Obviously, a scheme constructed by small shares is desirable. However, MASSS’s are impractical in this respect when the size of the access structure is very large. In this paper, we propose new MASSS’s which are perfect secret sharing schemes and include Shamir’s (k, n)-threshold schemes as a special case. Furthermore, the proposed schemes are more efficient than the original MASSS from the viewpoint of the number of shares distributed to each participant.Keywords: (k, n)-threshold scheme, multiple assignment secret sharing scheme, general access structure　1979年にBlakleyとShamirはそれぞれ独自に秘密分散方法の概念を発表した。秘密分散方法では，ある秘密情報を複数個の分散情報に分割して情報の管理者に分配する。秘密情報を復元する権限のある管理者のグループは，分散情報を集めることにより秘密情報を復元することができ，また，秘密情報を復元する権限のない管理者のグループでは，秘密情報に関する情報を得ることができないという手法である。秘密情報を復元する権限を持つ管理者のグループの集合をアクセス構造と呼ぶ。(k, n)しきい値法では，アクセス構造はn人の管理者のうちk人以上のグループの集合という特別な場合を実現していることになる。1987年に伊藤，斎藤，西関は複数割り当て法(MASSS)と呼ばれる一般アクセス構造を実現する秘密分散法を提案した。彼らの手法は任意のアクセス構造を実現することができる。秘密分散方式を実現するとき，各管理者に配布する分散情報の数は重要な課題である。当然ながら，少ない分散情報で構成される手法が望ましい。しかしながら，アクセス構造のサイズが非常に大きい場合，MASSSはこの点で実用的ではない。本論文では，Shamirの(k, n)しきい値法を特別な場合として含む完全な秘密分散法である新しいMASSSを提案する。提案手法は各参加者に配布される分散情報の数の観点から，従来のMASSSよりも効率的である。Kouya TOCHIKUBOキーワード：(k,n)しきい値法，複数割り当て法，一般アクセス構造Journal（掲載誌）IEICE Transaction on Fundamentals, E87-A, No. 7, pp. 1788-1797, Jul. 2004.－　　－29効率のよい一般アクセス構造を実現する秘密分散法Efficient secret sharing schemes realizing general access structuresPublished Paper