数理解析研究所講究録1093 巻 1999 年 182-187

182

ハイパーキ r–フ ‘上の安全な情報伝達$\backslash$中村雅子 (Noriko Nakamura), 酒井秀晃 (Hideaki Sakai),
西谷泰昭 (Yasuaki), H+嵐善英 (Yoshihide Igarashi)$\mathrm{N}\mathrm{i}\mathrm{s}\mathrm{l}_{1}\mathrm{i}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{i}$群馬大学工学部情報工学科〒 376-8515 桐生市天神町 1-5-1

tel: 0277301829
email: igarashi@comp.cs.gunma-u.ac.jp
本論文では,$?l$次元ハイパーキ$D_{-}^{-}$フ ‘ において,メッセージが完全に安全である確率, すなわち盗聴者にメッセージに以上であるという条件を満たす通信量の少ない情報伝達法

ついての情報が全く洩れない確率がある定数 ,{$3(0<\ovalbox{\tt\small REJECT}\{’<1)$を提案する。 我々の提案する方法は, 大きく分けて, 送信者から受信者への内素なパスを用いる方法と, リレーによる方法である。 そのそれぞれにおいて, メッセージをピースに分割する方法として, しきい藩法を用いる方法と情報伝播アルゴリズム (Illfol.lnatiQn Dispersal Algorithm, IDA) を拡張した方法を用いる方法を提案する。 計算機実験の結果, 送信者から受信者への内素なパスによって情報伝達を行なう場合, しきい値法を用いる場合の通信量に比べて, 拡張 IDA をがある範囲である場合に限られていることがわかった。 しが大きく, かつ用いる場合の通信量が少なくなるのは,が大きいときには常にしきい値法を用いる場合の通信量に比べて, 拡張
リレーによって情報伝達を行なう場合,
かし,を用すべての方法の中でも拡張が大きいときには,
IDA
また,を用いる場合の通信量が少ないことがわかった。
’IDA
$n$

$\beta$$\mathit{7}l$$n$

いてリレーによって情報伝達を行なう場合の通信量が–番少ないことがわかった。

1

はじめに

安全でないネットワーク上での送信者から受信者への安全な情報伝達について考える。 これまで, 安全な情報伝達のた
イパーキ $=-$ 7 上で情報伝達を行なった時の安全性と通信量をめの方法はいくつも提案されている $[1, 3]$ 。本稿では,$\mathrm{I}\backslash$考察する。 我々が考える情報伝達では, メッセージをピースに分割して, それぞれのピースをハイパーキューブ上のパスを使って伝達する。 メッセージを分割する方法としては, しきい条法と IDA を拡張した方法を用いる。
2 節において, 準備としで IDA を拡張した方法について説明する。 次に, 3 節において, \イパーキ $f$ –j 上においての安全な情報伝達について考える。 ここで, 各辺において; ピースが盗聴されない確率を定数 $a(0<\alpha<1)$ であるとす安全という概念を定義する。 ある情報伝達法が,\beta - 安全である。 このモデルにおいて安全性について議論するために,$\beta-$るというのは,盗聴者が送信されたメッセージについての情報を得ることができない確率が$\beta(0<\rangle \mathit{6}<1)$以上であるということを意味する。 .3 が 1 に近いほど安全であるということを意味する。 我々の目標は, ハイパ一 *=–7‘上で /3- 安
全であり, かっ通信量の少ない情報伝達法を提案することである。

2

IDA の拡張を $m$. $<|l$ である正整数とする。
最初に Informatioli Dispersal Algoritlun (IDA) について簡単に説明する。
そのピースを伝達し, これらのピー$S$
個のピースに分割し,$\log|S|$を)
IDA は集合 の要素であるメッセージ (大きさはスのうち任意の $m$ 個のピースを獲得できれば, 元のメッセージを復元できるという方法である。 このとき各ピースの大$n\iota.,$

$n$

$n$

きさは素 $\log|S|$ である。
次に IDA の安全性について述べる。 伝達された$n$個のうち $m$. 個のピースを獲得することでメッセージを復元できると$n-m$. 個のピースを紛失してもかまわないということであり, この意味で IDA は安全であるといえる。 しかし, 獲得したピースの個数が $m$. より小さい場合にも可能なメッセージの個数をしぼることができるという意味で IDAの安全性は高いとは言えない。 つまり, 盗聴者の獲得したピースの個数が $r(r<m)$ であれば, メッセージを完全に復元いうことは,

することはできないが, その候補は$|S|^{\frac{m-r}{m}}$個となり, ヒ o– スを全く獲得しないときの候補数 $|S|$ より減ずることができる。 このように, メッセージ解読の可能性が増加するために IDA の安全性は低いと考えられる。 そこで, 解読の可能性を減らすために解読に必要とされるピースの個数を増やす方法が考えられる。 具体的には, $S$ の要素であるメッセージにである。 この対応付けされた $S’$ の要を拡張した集合 $S’$ の要素を複数対応付ける。 ここで,個のピースに分割して伝達する。
素から 1 個をランダムに選び, それを通常の IDA によってこのような拡張 IDA について次のような性質をもつ情報伝達法が示されている対して,$|S’|=|S|^{\frac{m+k}{\tau n}}$

$S$

$n$

$[7]_{0}$$\log|S|$$H(S|r)=\{$$(1- \frac{\mathrm{r}-k}{\nu r\iota})\log|S|$$0$

if $r\leq k$. $+k$
if .
if $m+k\leq r$$k$$\leq r\leq\cdot n|$

183

嫁ま盗聴者が獲得した. スの個数, $.H(S|r)$ は盗聴者がピースをめに必要な情報量 (エントロピー) を示す。 この結果より $r\leq k$ の場合には
ここで,$\text{ヒ^{}\dot{\text{。}}}-$$r$

個獲得した場合にメッセージを特定するた$H(S|r)=\dot{1}\mathrm{o}\mathrm{g}|S|$を盗聴されても盗聴者はメッセージに関して何も情報を得ることになる。 また,であるので,$k$$k\leq r\leq m+k$ の場合には,

個のピース
メッセージ

が復元されてしまうわけではないが, 盗聴者にだけ情報が洩れていることがわかる。
また送信者から受信者への長さ 1 の 本のパスを用いた場合の通信量は, ピース 1 個あたりの大きさが蓋 $\log|S|$ であ$\frac{r-k}{rr\iota}\log|S|$

$n$

ることから

$\frac{n}{m}$となる。 –方,$\log|S|$

通信量はしきい値法を用いた場合のしきい値法を用いた場合の通信量は $n\log|S|$ であるため, IDA を拡張した方法のになっている。

$\frac{1}{rn}$上で示した方法を用いて, 我々は, ピース

$n$

個中

$k$

個からは元のメッセージに関して何も情報を得ることができず,

個からは完全にメッセージを復元できるようなピースにメッセージを分割することができる。 以後,
IDA と呼ぶことにする。

3’$\iota\iota$

この方法を $(k, w, n)-$ハイパーキューブにおける安全な情報伝達と通信量であるため, 任意の頂点から別の任意の頂点の間には, 内素な
本のパスが存在する。 したがって, しきい値法や 2 節において説明した IDA を拡張した方法を用いてメッセージを個に分割して,$n$次元ハイパ一 $\text{キ}=-$ フは連結度が$r\iota$$n$$n$

それぞれを内素なパスを用いて送信するという方法が考えられる。 ここでしきい値法とは, 一般には ( , 1 小しきい値法$k$と呼ばれる, もとの情報を任意の個から復元できるように.n 個のピースに分割するものである。 このとき, 各ピースの大きさはもとのメッセージと同じである。
のパスが長さ本存在するようなネットワ一クがあるとき,個のピースが盗聴されても, 盗聴者が, 送信されたメッセージに関する情報を得ることができないように, かっなるべく情報量を少なくするという問題を考える。 このとき, しきい万法を用いる場合には, $(k+1, k+1)-$ しきい筆法を用いればよい。 また, IDA を拡張した方法を用いる場
合にはを用いればよい。 2 つの場合の通信量を比べると, しきい値法を用いた場合には, ひとつのピースの大きさは $\log|S|$ であるので通信量は $(k+1)\cdot n\log|S|$ であり, IDA を拡張した方法を用いた場合には, ひと
$k$

$n$

$k$

$7\downarrow$$(k., m+k., rr\iota+k)- \mathrm{I}\mathrm{D}\mathrm{A}$

つのピースの大きさは蓋である。 $1\leq rn\leq n-k$ であるので, IDA を拡張した方法の場合の通信量は $m=1$ の場合にはしきい値法を用いた場合と等しく, $m$ が大きくなるにしたがってしきい値法を用い$|S|$であるので通信量は$\frac{k+m}{m}r\iota|s|$た場合よりも少なくなっていく。 したがって, この場合にはしきい値下を用いるよりも IDA を拡張した方法を用いた方が明らかに優れていることがわかる。
しかし個のヒ 6– が盗聴されたとしても, 送信されたメッセージに関する情報を, 盗聴者が何も得ることができない$k$$\text{ス}$ようにするという要求があるとは考えにくい。 むしろ, 盗聴者がメッセージについての情報を得ることができない確率をある定数 ,$\theta(0<\beta<1)$ 以上にしたい, という要求の方が自然である。
そこで我々は, ハイパーキューブ上で,.

しきい値法と IDA を拡張した方法を用いて, 盗聴者がメッセージについての情報を得ることができない確率がある定数 $\beta(0<\beta^{:}<1)$ 以上であって, かつ通信量の少ない情報伝達法を提案する。

31

モデル

我々が考えるモデ馴糧\iota - 次元ハイパーキ $=-$ フ ‘.n-HHC である。 送信者はノード 00. . . であり, 受信者はノード 11. . . 1
であるとする。 各辺において盗聴されない確率を $\alpha(0<\alpha<1)$ とする。 このようなハイパーキ $=-$ フ ‘ を以後 n-HC$0$$(\alpha\cdot)$と呼ぶ。

送るメッセージの集合を $S$ と表す。 したがって, メッセージの大きさ ?訓 og $|S|$ である。 盗聴者はピースがどのような方法で作成されたものか知っていて, 各辺で盗聴に成功したピースを集めてメッセージに関する情報を得ようと務めるものとする。

情報伝達法の安全性を議論する為に次の定義をする。
定義 1 ある情報伝達法を用いてメッセージを送信した時, 盗聴者にメッセージについての情報が全く洩れない確率が定安全 ( -secure) であるという。

数 $\beta(0<\beta<1)$ 以上であるならば, その情報伝達法は各方法の評価に用いる通信量は,(情報伝達に用いた辺の数)

また, この節で確率を計算する時に, 次の Cliernoff

Chernoff Bound
である任意の定数$\epsilon$$\beta-$$\mathrm{b}_{\mathrm{o}\mathrm{l}1}11\mathrm{d}$$\beta$$\cross$(ピースの大きさ) で求める。

の式を用いる。

を成功確率が であるベルヌーイ試行を回行なったときの成功回数であるとする。 $0<\epsilon<1$に対して, 成功回数が回以下である確率は次の不等式を満たす。
$X$$\sim’\backslash jr$$P$$\epsilon pN$.

$Prob\{X\leq\epsilon pi\backslash ^{-};\}$$Prob\{x\leq\epsilon pN\}\leq e^{-l-}1-\xi)^{2}t?,4i/2$

(1)

184

送信者から受信者への内素なパスを用いる方法

32n-HC には送信者から受信者へ
いて,

$n$

本の内素なパスが存在し, それぞれのパスの長さはピースをひとつずつ送信した場合を考える。
個の辺からなっているので, 各パスの盗聴されない確率は

各パスは$a^{n}$$n$$r\iota$である。 それぞれのパスを用である。 表記を簡単にする為,$\wedge(^{=a^{n}}$とおく。

しきい値法を用いた場合について次の定理を得る。 証明は省略する。
定理 1$\beta’\leq 1-(1-\wedge|.)^{n}$

n-HC

ならば,

$(C\mathfrak{r})$において,$\lceil\frac{1_{11}(1-j)}{1_{11}(1-\wedge)\prime’},\cdot,\rceil\leq t$

である

$t$

$(t.t)-$ しきい値法を用いた情報伝達は ,j3- 安全である。 但し,に対して,$\gamma=\alpha^{n}$。

通信量については, 定理 1 より, 次の定理が得られる。

定理 2tz-HC$c_{T}^{l}s(t)$とすると,における, 定理 1 で構成された $(t, t)-$ しきい値法を用いた情報伝達の通信量を$(\alpha)$$C_{T}’.s(t)=t\cdot n\log|s|$である。 $C\tau s(t)$ は$t= \mathrm{r}\frac{\ln(1-\beta)}{\ln(1-\gamma)}\rceil$のとき最小であり, その値は$\mathrm{r}\frac{1_{11}(1-\{?)}{1_{11}(1-\wedge\prime)1}.\rceil_{l}l\log|s|$である。 但し,$(k, u|, w)$$\wedge t=\alpha^{n_{\circ}}$-IDA を用いた場合の情報伝達について次の定理を得る。

定理 3n-HC$(\alpha\cdot)$において,$/\mathit{3}<1-e^{-\frac{1}{2}\gamma n}$

であれば,$.uj \geq\lfloor\frac{-\mathit{2}1\iota 1(1-\beta)}{\gamma\prime}\rfloor+1$$k+1=\lceil?l,’(1-\wedge\tau’)+\sqrt{-2_{1^{\prime uJ}}^{\wedge}111(1-\iota 9)}\rceil$

である

(証明)

’と

$.\mathrm{t}L$

$k$

に対して

は

$(k, \tau v, \cdot \mathrm{t}b.)-IDA$$\mathcal{B}<1-e^{-\frac{1}{2}\gamma n}$より,$\beta-$

安全な情報伝達法である。 但し,$\frac{-2\ln(.1-\beta)}{\gamma}<r\downarrow$. であるので$\wedge’=\alpha^{n}$$\lfloor^{-2\ln(}\wedge’\rfloor\underline{1-\beta)}+1\leq n$

このような $w,$
$1\leq k+1<\cdot 1‘ i$ であるから,

に対して

。

が成り立つ。 したがって, 条件を満た安が存在する。. 次に’ が存在する。 また,全であることを示す。 $P(X)$ を $w$ 個のピースのうち $X$ 個のピースの盗聴に失敗する確率とする。 盗聴者がメッセージにすなわち, 盗聴に失敗するピースの個数
ついての情報を得るためには $k+1$ 個以上のピースを盗聴しなければならな
安全であることがわ
が $w-(k+1)$ 以下でなければならない。 したがって, $1-P(X\leq w-(k+1))\geq$ {; であればす$\tau\iota$$k$$|,.\text{・}$$\beta-$$(k, w, w)-\mathrm{I}\mathrm{D}\mathrm{A}$。

$\beta-$かる。 ここでとおくと,$\epsilon=1-\sqrt{\frac{-2\ln(1-\beta)}{\gamma \mathrm{t}\mathrm{t}:}}$,$\epsilon^{\wedge\prime},^{\tau L}$

$=$

$=$

$\geq$である。 また,$-2\mathrm{l}\mathrm{n}1,1\wedge’\underline{-‘\theta)}<\cdot\iota\iota^{;}$

より,$\wedge t^{rv}-\sqrt{-2_{f}^{\wedge}u111(1-\theta)}$$w-\{w(1-\gamma)+\sqrt{-2_{7’}w\ln(1-\beta)},\}$$w-(k+1)$$0<\epsilon<1$である。 したがって Chernoff Bound の式を用いることができ,$P(X\leq w-(k+1))$$\leq$$P(x\leq\epsilon^{\wedge}\prime u1)$$\exp\{-\frac{(1-\epsilon)^{2_{\wedge}}\prime\cdot\iota\iota}{\mathit{2}},\}$$\leq$

を得る。 よって $1-P(X\leq w-(k+1))\geq.(\mathit{3}$ であるから,通信量については, 定理 3 より次の定理を得る。

$=$$\exp(\ln(\mathrm{i}-\beta))$$=$$1-.\theta$$’\theta-$

安全である。

口

185

定理 4 定理 3 で構成される$(h^{\sim}.w, \{:)- IDA$の通信量を

$C_{ID.4}(\tau\iota\cdot)$とすると, 次の式が成り立つ。

$\frac{1}{\wedge\gamma(\prime 1-\delta)+\frac{1}{u^{\backslash }}}r\iota\log|S|\leq C_{IDA}’(w)<\frac{1}{\wedge j(1-\delta)}n\log|S|$

但し,$\delta=\sqrt{\frac{-2\ln l1-\beta)}{-\mathit{1}^{1pi}}}$33,$\wedge(=\alpha^{n}$。

リレーによる方法

リレーによる方法は, 図 1 にあるように, 送信者から受信者ヘメッセージを送信する途中で,メッセージの復元と分割を何度も行なうものである。

送信者から受信者へのひとつのパスを考え (図 1 では 00000, 00001, 00011, 00111, 01111, 11111), そのパスに含まれるノードをリレーノードと呼ぶことにする。 任意のリレーノードから隣接するリレーノードへは, 図 1 のように, 長さ 3
$n-1$ 本の内素なパスが存在する。

のあるリレーノードから隣接するリレーノードへは, 内素なパスを用いる方法と同様の方法を用いてメッセージを送信す
る。.

図 1:

in ) -dimensional hypercube 5-HC.
$\vee$)$\mathrm{R}\mathrm{e}\mathrm{l}\mathrm{a}$$r\mathrm{i}\mathrm{n}\mathrm{g}$$\mathrm{i}$各リレーにおける各パスは 3 個の辺からなっているので, 各パスの盗聴されない確率は為,$\wedge f^{J}=\alpha\cdot 3$

定理 5

および

$\beta’=/\theta^{\frac{1}{n}}$$a^{3}$である。 表記を簡単にする

とおくと, 内素なパスを用いる方法と同様の結果を得ることができる。 証明は省略する。

$\beta^{l}\leq 1-(1-\gamma’)^{n}-1$ならば,$r\iota- \mathrm{H}\mathrm{c}(\alpha)$

において,$\lceil\frac{1_{1}\iota(1-_{l}:s\prime)}{1_{11}(1-\gamma’)}\rceil\leq t$

である

定理 6

$t$

に対して,

n-HC

$(\alpha)$

しきい値法を用いた情報伝達は$(t, t)-$$\beta-$安全である。 但し,$\wedge,’=\alpha^{\mathrm{J}}’$,$\beta’=-\theta^{\frac{1}{n}}$。

における, 定理 5 で構成された $(t, t)-$ しきい値法を用いた情報伝達の通信量を$c_{\tau}^{\mathrm{t}\prime}S(t)$$c_{Ts(t)}’’=3t.n\log|s|$である。 $C_{TS}’’(t)$ は$t= \mathrm{r}\frac{\ln(1-\theta’)}{\ln(1-\gamma)},\rceil$のとき最小であり, その値は3である。 但し,$\wedge=l^{J}\alpha^{3}$,$\lceil\frac{1_{11}(1-\beta;)}{1_{\mathrm{I}}\iota(1-\wedge f’)}1n\log|s|$$\theta’=\beta^{\frac{1}{n}}$,定理 7n-HC $(a’)$ において,。

$\beta’<1-c^{-\frac{1}{2}\gamma)}’(n-1$であれば,$w \geq\lfloor\frac{-2\bm{\mathrm{i}}(1-\theta\prime)}{\gamma},\rfloor+1$

である $w$ と$k$に対して $(k.\cdot w, w)-IDA$ は.\theta - 安全な情報伝達法である。 但し,$\wedge\prime’=\alpha 3$,$\theta’=\beta^{\perp}n$
。

とすると,

186

定理 8 定理 7 で構成される $(k, \tau‘ j, \cdot w)-IDA$ の通信量を)) とすると, 次の式が成り立つ。

$c_{rDA(?}^{l}\mathrm{t}$$\frac{3}{\wedge(’(1-\delta’)+\frac{1}{u\backslash }}n\log|s|\leq c_{\tau}’’DA(w)<.\frac{3}{[^{J}(1-\delta’)}n\log|s|$

但し,$\delta’=\sqrt{\frac{-2\mathrm{l}\mathrm{n}11-\beta’)}{\gamma w}},$

34

比較$\alpha=0.99$,$\beta=0.9$を表し,$c_{\tau S}’$$\beta’=\prime \mathit{3}^{\frac{1}{n}}$。

としたときの,(しきい値法) とあるのがるのが,$c_{\tau s}^{1}$$r\iota$と通信量 ($C\tau s$を表し, 内素なパス (, CIDA,) の関係を図 2, 3 に示す。 図中, 内素なパスを表し, リレー (しきい値法) とあ-IDA) とあるのが$c_{\tau S}^{J},$ $c_{IDA}^{1\prime}$$(k,$ $u|,$ $w)$

$C^{t},\tau DA$,を表す。 図 2 はリレー ( $(k,$ $w,$ $w)$ -IDA) とあるのが $C_{IDA}’$.

$n$

が 200 まで, 図 3 は$n$が 1000 まで計算したものである。
’
よりも CIDA の方が小さくなっている。 しが 40 以上のとき, $C_{TS}$と $C’rDA$ を比較する。 図 2 では,
まず,.
の方が小さくなっている。
よりもが 350 以上のとき, $C_{IDA}$
かし, 図 3 では,の方がに対して計算した結果, } が大きくて, かつがある範囲にある場合には $C,s$ よりもいくつかの$C’\tau s$$n$$C’\tau s$$n$$a\cdot,$

$3$

$/3$

$C\prime rDA$$‘ t$

小さいが, 全体的に見ると $C\tau s$ (しきい値法を用いた情報伝達の通信量) の方が小さいことがわかった。
次に,.

$C_{TS}’$た, 図 3 では,
いくつかのと $C”,.4$ を比較する。 図 2 では,$C^{l}\ovalbox{\tt\small REJECT}\tau s’ C.\prime roA$$\alpha\cdot,$$,\theta$$?\mathrm{I}$が 60 以上のとき,$n$$C_{tDA}’$の方が小さくなっている。 ま.

よりも $C_{IDA}’((k, uj, w)$ -IDA.

ともにあまり増減しない。

に対して計算した結果, 常に,c.’ 蝕よりも .

がある値よりも大きくなると,$C_{TS}’$を用いた情報伝達の通信量) の方が小さいことがわかった。

図 2:

4

$n$

と通信量の関係 $(1\leq ll\leq 200)$

まとめ. 我々は ,$\theta-$

対して,

$n$

安全という概念を定義し, ハイパーキ $=-j$ 上で ,i3- 安全である情報伝達を提案した。 その各情報伝達法にと通信量 $(c_{Ts,C_{I}c^{t\prime}}^{t}.DA,,TS\cdot C_{ID}’)A$ の関係を調べ, それぞれの方法の通信量が少なくなる条件を実験により調べた。 その結果, 送信者から受信者への内素なパスによって情報伝達を行なう場合,量に比べて,$(k. uy, w)$ -IDA

限られている。 しかし,を用いる揚合の通信量が少なくなるのは,リレーによって情報伝達を行なう場合,$n$

しきい値法を用いる場合の通信./3 が大きく, かつ$n$がある範囲である場合にが大きいときにはしきい値法を用いる場合の通信量が大きいときには, すべての方法の中で$(k, w, w)$ -IDA を用いる場合の常に通信量が少ないこと。 また,-IDA を用いてリレーによって情報伝達を行なう場合に通信量が少ないことがわかった。 しきい値法を用いる場
合の通信量に比べて,-IDA を用いる場合の通信量が少なくなる –般的な条件を導くのは今後の課題である。
に比べて,

$n$

$(k, \tau\iota., \cdot \mathrm{t}\mathrm{l}.\cdot)$$(k. w, \iota v)$

また, 我々の解析は, すべてのパスの長さが等しい状況を考えたため, すべてのパスの盗聴確率が等しい場合であった。 用いるパスの盗聴確率が等しくない場合の解析は今後の課題である。

187

図 3:

$n$

と通信量の関係 $(1\leq n\leq 1000)$

参考文献[1] F. Bao, Y.
, Y. Hamada, and Y.
’‘Reliable broadcasting and secure distribution in challnel
networks”, IEICE Trans. on Fundamentals., vol. E81-A, pp. 796-806, 1998.
$\mathrm{F}\mathrm{u}\mathrm{n}\}^{-\mathrm{u}}’$$\mathrm{I}\mathrm{g}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{S}\iota \mathrm{i},$[2] M. Carpentieri, A. De Santis, and U. Vaccaro, “Size of shares and probability of cheating in threshold schemes’,
Eurocrypt’93, Lecture Notes in Computer Science, vol. 765, Springer-Verlag, Berlin, pp. 118-125, 1994.
[3] D. Dolev, C. Dwork, O. Waarts, and M. Yung, :‘Perfectly secure message transmission”, J. of $ACM$, vol. 40,
pp. 17-47, 1993.

[4] M. O. Rabin, ‘Efficient dispersal of information for security, load balance, and fault toleral]ce’, J. of $ACM$,
vol. 36, pp. 335-348, 1989.

[5] A. Shalnir, “How to sbare a secret”, CACM,$1^{\gamma}01$.

$-^{\underline{9}},$, pp. 612-613, 1979.

[6] D. R. Stinson, Cryptography: Theory and Practice, CRC Press, Boca Raton, Florida, 1995.
[7] H. Sakai, N.
, Y.
and Y. Igaraslti, ’.‘Secure Message Transmissions by the Information
Dispersal Algorithm”, 電子情報通信学会技術研究報告, COMP98-47, pp. 73-80, 1998 年 10 月.
$\mathrm{N}\mathrm{a}\mathrm{k}^{\prime \mathrm{a}\ln}\mathrm{u}1^{\backslash }\mathrm{a}$$\mathrm{N}\mathrm{i}\mathrm{s}\mathrm{l}_{1}\mathrm{i}\mathrm{t}\mathrm{a}.\mathrm{I}\dot{\mathrm{u}}$[8] F. Bao, Reliable and Secure Message Transmissions in Distributed Systems, Ph.D. Thesis, Gunma University,

1996.