秘密情報分散法： 宝の地図の断片を集めて宝物をゲット（１／３）
１．金庫の鍵を安全に管理するには？
ある銀行に、毎日開けなければならない金庫があります。この金庫の鍵を一人で管理するとします。鍵を紛失したら金庫は開けられなくなり、困りますね。そこで、スペアーキーを作り、複数人で1本ずつ持つことにします。これで、誰か一人が鍵を紛失しても、金庫を開けることができますね。でも、1本でも鍵が悪い人の手に渡ったら、金庫の中のお金は盗まれてしまいます。
そこで、金庫の鍵を3桁の暗証番号方式にして、三人の管理者が1桁ずつ管理することにします。金庫の暗証番号は一日に一度しか入力できず、当てずっぽうで適当な数字を入力するとエラーとなり翌日まで暗証番号を入力することができません。これで、管理者の誰か一人の暗証番号が悪い人に知られても、金庫は無事ですね。でも、誰か一人でも暗証番号を忘れてしまったら、金庫を開けることはできません。
三人が金庫を開ける権利を有し、三人中任意の二人が合意した場合のみ、金庫が開けられるようにしたい。このような問題を解決する方法が、2. 秘密情報分散法です。
このような状況は実際にあります。英文週刊ニュース誌Time Magazine (1992年5月4日, p.13) によると、ロシアの核兵器の制御は、同じような「三人のうちの二人」の利用方法になっています。この三人は、大統領・国務大臣・国防省を意味しています。
２．秘密情報分散法とは
秘密情報分散法は、1979年にBlakleyとShamirによって独立に提案されました。現在も活発に研究されており、情報セキュリティの重要な一分野を担っています。
秘密情報分散法は、複数の管理者が共同して、一つの情報を秘密に保管する方法です。秘密にしたい元の情報を「秘密情報」、各管理者が持っている一つ一つの情報を「シェア情報（分散情報）」と呼びます。秘密情報分散法では、秘密情報から各管理者が保管するシェア情報をつくる方法と、集めたシェア情報から元の秘密情報を復元する方法の二つがセットになっています。
Shamirは、1979年に、(k, n)-しきい値法と呼ばれる特定の型の秘密情報分散法を提案しました。(k, n)-しきい値法とは、n人中k人以上の管理者が集まれば秘密情報を復元できるような分散方法です。(k-1)人集まっても、何も情報は得られない仕組みになっています。先に紹介した「三人中任意の二人が合意した場合のみ、金庫が開けられるようにしたい」という問題は、(2, 3)-しきい値法を用いると解決できますね。
では、(k, n)-しきい値法とはどんな仕組みなのでしょう？
秘密情報分散法は、複数の管理者が共同して、一つの情報を秘密に保管する方法です。秘密にしたい元の情報を「秘密情報」、各管理者が持っている一つ一つの情報を「シェア情報（分散情報）」と呼びます。秘密情報分散法では、秘密情報から各管理者が保管するシェア情報をつくる方法と、集めたシェア情報から元の秘密情報を復元する方法の二つがセットになっています。
Shamirは、1979年に、(k, n)-しきい値法と呼ばれる特定の型の秘密情報分散法を提案しました。(k, n)-しきい値法とは、n人中k人以上の管理者が集まれば秘密情報を復元できるような分散方法です。(k-1)人集まっても、何も情報は得られない仕組みになっています。先に紹介した「三人中任意の二人が合意した場合のみ、金庫が開けられるようにしたい」という問題は、(2, 3)-しきい値法を用いると解決できますね。
では、(k, n)-しきい値法とはどんな仕組みなのでしょう？
