秘密分散法
Secret Sharing Schemes

１．秘密を「守る」って何？

情報セキュリティ技術の大きな 目的の一つは「秘密を守る」 ということです（当たり前ですが）．金庫に鍵を掛けるように， データを適切な暗号技術を用いて，暗号化することで重要な情報を敵から守る ことができます．

しかし，それで終りというわけではないのです．暗号化するための鍵を敵から守 るためにはどうすればいい でしょう？…そう考えると，「秘密を守る」ことにおいて, 「秘密を守 る鍵をどうするか」という問題は極めて重要であることがわかります．

もう少し具体的にいうと，例えば…

こんなことは例えば銀行のATMのパスワードなどでみなさん日常的に経験されて いることと思います． しかし，このような目標は「あちらを立てればこちらが立たぬ」ようになってい ます…そう，矛盾しているのです．どういう事かというと， さあ，困ってしまいます．

２．そこで「秘密分散法」

こんな困った状況を解決する一つの方法が，このページのテーマである 「秘密分散法」 です．秘密分散法とは一口でいう と，

というものです．なお，ここから先は鍵などのような特別大事な情報を「秘密情 報」 と書くことにします．上の条件をもう少し，正確に書きましょう： このような秘密分散法を( K , N ) しきい値法 といいます．このような方式は， となって，めでたし，めでたし，となります．しかし，言うは易く，行うは何と かです． さて，またややこしくなって来ました．ゴールはあと少しですので，頑張ってく ださい．

３．どうやって作るの？

問題はそんな都合のいいことが実現できるか，ですが，実は答えは中学生で ならう「連立方程式」にあります．

秘密情報を S （数字）とします．適当に（こっそり）数字 a を決定し，一次関数

F(X)=aX+S

を考えます． N 人（参加者といいます） のうち i 番目の人に，１次関数の値 F ( i ) を配付 します．その後，こっそり a を 消してしまいましょう．これから分かるのは， fig ということです．この方式は ( 2 , N ) しきい値法になってい ることがお分かりかと思います．２つのコメントは「１点では直線は決まらな いが，２点が決まれば直線が 決定する」（右図参照）という事 実と同じことです．連立方程式を 解くことで解が得られる仕組みで す．



詳細は省略しますが，( K , N ) しき い値法を実 現するためには，一般に K-1 次多項 式， F ( X )を用意し， i 番目の人に，関数の値 F ( i ) を配付 すればよいことが分かります．上記の ( 2 , N )しきい値法と同様に，

ことが示されます．結局，連立方程式を解くことが できるかどうかが焦点で，それは Vandermonde（ファンデルモンド） の行列式が０にならないことから証明されま すが，Vandermondeの行列式に関しては，線型代数の教科書を御覧下さい．

さて，これで一応の目的が達成できました．

４．さらに深く知りたい方へ

もちろん，上記で示したアイデアは最も基本的なものです．秘密分散法に関して は現在，さらにいろいろな事が知られています．そのうちいくつかを 簡単に一問一答の形にしてみました．

  1. しきい値法以外にも秘密情報の復元方法はありますか？
    • しきい値法は分散情報の個数に対して秘密情報が復元できるか否かがきめられて いますが，より一般に，秘密を復元できる/出来ない集合を任意に定めることが できます．このような秘密分散法を一般アクセス構造に対す る秘密分散法といいます．

  2. 秘密分散法の欠点は？
    • 安全性は高いのですが，非常にメモリを食うという欠点があります．そこで，安 全性と符号化効率（メモリ量）との間のトレードオフを考えたランプ型秘密分散法があります．

  3. 秘密分散法の応用にはどのようなものがありますか？
    • 理論的には，Metering, Kerberos, 紛失通信などが知られています．また，最近 では秘密分散法を応用したUSBメモリやソフトウェアなど，いくつかの製品が市 販されています．

  4. 不正者に対しての耐性はありますか？
    • 上に示した簡単な方法では不正は防げません．しかし，不正者の存在を明らかに する可検証秘密分散法が研究されています．

  5. 大事な情報ってパソコンなどの計算機が無くて, 計算が困難な状況 でも保存したいものだと思 いますが…．
[TOP]