秘密分散とは - わかりやすく解説 Weblio辞書

索引トップランキングカテゴリー

秘密分散

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/06 17:03 UTC 版)

秘密分散（ひみつぶんさん、英: secret sharing）とは暗号技術の一つであり、秘密情報を何らかのグループのメンバーに分散する手法の総称である。各メンバーには、秘密情報から生成されたシェアと呼ばれる情報がそれぞれ渡される。シェアはメンバー数だけ生成され、個々のシェアを見ても元の秘密情報について何もわからないように、なおかつ、十分な数のシェアを集めれば秘密情報を復元することができるように生成される。このため、秘密情報を情報漏洩と紛失のリスクから守ることができる。

秘密分散は、秘密情報からシェアを生成するディーラーと、シェアを受け取って保管する n 人の参加者によって実行される。ディーラーは、「どの参加者（シェア）が集まったら秘密を復元できるようにしたいか？」「どの参加者（たち）には秘密を全く知らせたくないか？」をあらかじめ設定し、その設定に従ってシェアを生成する。秘密分散の典型的な設定はしきい値構造と言われるものである。t をしきい値としたとき（t≦n）、n 人の参加者のうち t 人以上が集まったら秘密を復元できるが、t 人未満が集まっても秘密は全く分からないようにシェアが生成される。このようなシェアの作成方法は、(t,n)-しきい値秘密分散法，あるいは (t,n)-しきい値法と呼ばれる。

秘密分散は、1979年にアディ・シャミア^[1] とジョージ・ブラークリー（英語版）^[2]によって独立に提唱された概念である。

具体的な例

秘密分散の具体的なシナリオは以下のようなものである。

妻と3人の子供を持つA氏は、自分に何かあったときのために、隠し財産の在りかを家族に教えておきたいと思っているが、妻や子供たちそれぞれにその情報を教えてしまったら、誰かが勝手に財産を使ってしまうかもしれない、と危惧している。自分に何かがあったときに限って、家族が合意の上で財産を手に入れられるようにすることはできないだろうか？

もし、妻と全ての子供が合意した時のみ、財産の在りかが分かるようにしたいならば、A氏は次のようにすればよい。（A氏がディーラー、妻と三人の子供が参加者、各 $v_{i}$

ブラークリーの方式は、シャミアの方式と比較して空間効率が悪い。シャミアの方式の場合は、各シェアは秘密情報と同じサイズであるが、ブラークリーの方式では、しきい値が t ならば各シェアは秘密情報の t 倍の長さになる。ブラークリーの方式は、シェアとして使える平面に対して制約を設けることで、効率を上げることができる。この効率化によって得られる方式は、多項式補完を用いたシャミアの方式と等価である。

プロアクティブ秘密分散

シェアをあまり安全でないコンピュータシステムに保管すると、シェアが漏洩する可能性がある。しきい値以上のシェアが漏洩すれば秘密情報を復元されてしまうことは自明であるが、それより少ない数のシェアが漏洩した場合でも、実質のしきい値が減少してしまうため、安全性は低下してしまう。安全性を再度高めるためには、新しく秘密情報を選択しなおして（例えば秘密情報がパスワードのような場合）分散し直せばよいが、変更が困難は秘密情報もある。

シャミアのしきい値法の場合、秘密情報は変更しないまま、漏洩していないシェアを更新することができる。これを行うには、0を秘密情報としてシェアを計算し（すなわち、定数項が0であるランダム多項式を選ぶ）、シェアを各参加者へ秘密裏に配布する。各参加者は、元から持っていたシェアに新しいシェアを加算することで、シェアの更新を行う。これによって，漏洩した更新前のシェアは役に立たなくなる。更新前と更新後では、秘密情報のシェア生成の多項式が異なるため、たとえ更新前のシェアと更新後のシェアを合わせてしきい値分だけ集めたとしても、秘密情報が漏洩することはない。この方法で、しきい値も変更することができる。ただし、更新前のシェアを消さずに取っておくと、更新の意味がなくなるので注意が必要である。

検証可能秘密分散法

秘密を分散したり復元したりする段階で、参加者の誰かが手順に従わず、不正に情報を得たり他者を混乱に陥れようとするかもしれない。検証可能秘密分散法（verifiable secret sharing, VSS）は、他の参加者が手順に従っていることを（十分小さいエラー確率を除き）検証することのできる秘密分散法である。 Tal RabinとMichael Ben-Orは、ディーラーまたは1/3未満の参加者による不正行為を検出可能なマルチパーティ計算プロトコル(MPC)を考案した^[6]。このプロトコルは、適応的(adaptive)な攻撃者、すなわち、プロトコル中で明かされる情報に依存して結託する参加者を決定するような攻撃者に対しても、安全性を保つことができる。

計算量理論的安全な秘密分散法

情報理論的安全な（完全な）秘密分散法の欠点は、n 個のシェアを保存するのに必要なストレージサイズが、秘密情報をそのまま保存する場合の n 倍になってしまうことである。また、シェアを秘密裏に送る際の通信量も同様である。例えば、秘密情報が1GBであり、シェア数が10のとき、10GBのデータを（10か所に分けて）保存しなければならない。秘密分散法の効率を大幅に改善する方法としては、安全性を計算量的なものに緩和させることが提案されている。

代表的な計算量理論的安全な秘密分散法は、Krawczykによる (t,n)-しきい値法である^[7]。この方式は、ラビンのIDA（Information Dispersal Algorithm）^[8] をシャミアのしきい値法と組み合わせてできている。秘密のデータは、まず何らかの共通鍵暗号で暗号化される。用いる暗号鍵はランダムに選ぶ。次に、暗号文をIDAで n 個の断片に分ける。IDAは、しきい値法と同様に n 個に分けた断片のうち t 個集まれば元のデータを復元できるが、しきい値法と違って各断片のサイズ（ビット長）は分ける前のデータの 1/t になる。例えば、しきい値が5のときは、各断片は元のデータの 1/5 である^{[注釈 5]}。最後に、暗号化に使った鍵をシャミアのしきい値法で分散する。各参加者には、しきい値法のシェア1つとIDAの断片1つを渡す。暗号鍵の各シェアは鍵と同じ長さであるが、通常、鍵の長さは16～20バイトと小さいため、参加者に必要なストレージサイズは、ほぼIDAの断片の分だけである。

関連したアプローチとして、AONT-RSと呼ばれる^[9]では、IDAで処理するまでのステップとして、All-or-nothing transformを使っている。All-or-nothing transform は、しきい値未満のシェアでは、データを復号できないことが保証されている。