秘密分散

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

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

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

具体的な例

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

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

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

• ${\displaystyle s}$ : 秘密の在りかを示すビット列（秘密情報）．
• ${\displaystyle v_{1},v_{2},v_{3}}$ : ランダムに選ばれた、秘密情報と同じ長さのビット列．
• ${\displaystyle v_{4}}$ : ${\displaystyle s=v_{1}\oplus v_{2}\oplus v_{3}\oplus v_{4}}$ を満たすビット列．（${\displaystyle \oplus }$はビットごとの排他的論理和）
• ${\displaystyle v_{1},v_{2},v_{3}}$ を3人の子供に、${\displaystyle v_{4}}$ を妻に渡しておく。

家族4人が合意すれば、${\displaystyle s=v_{1}\oplus v_{2}\oplus v_{3}\oplus v_{4}}$ を計算することで、A氏の財産を得ることができる。 一方、4人のうち誰か1人でも合意しなければ（一つの ${\displaystyle v_{i}}$ が未知であれば）、残りの家族は財産の在りかについて全く分からない。 このように、全てのシェアを足し合わせることで秘密情報を復元できるように分割する方法は、加法的秘密分散法と呼ばれる。

このシェアの生成方法では、A氏が妻との旅行中に災難に遭うと、子供たちは財産を得ることができない。もし「4人全員が合意したときのみ」という条件を「4人のうち3人以上が合意したときのみ」としたい場合は、(3,4)-しきい値法を用いればよい。(3,4)-しきい値法では、4つのシェアが生成され、3つのシェアからは秘密情報が復元でき、2つ以下のシェアを集めても秘密情報については何もわからない。同様に、(2,4)-しきい値法を用いれば、A氏は「4人のうち2人以上が合意したときのみ」隠し財産が得られるようにシェアを生成することができる。 （具体的なシェア生成手順は後述するシャミアの方法やブラークリーの方法を参照。）

また、「妻と子供一人以上」または「子供三人」が合意したときのみ、秘密情報を復元できるように設定することも可能である（妻だけ、あるいは子供二人だけでは、財産の横取りはできない）。

重要性

秘密分散法は、極めてセンシティブかつ重要な機密情報を保存するのに役立つ。このような重要な情報としては、暗号を復号するための鍵、ミサイル発射コード、暗証番号などが挙げられる。これらの機密情報は、漏洩した場合の被害が大きいだけでなく、紛失してしまった場合のダメージも大きい。いわゆる暗号化だけでは、高い機密性と信頼性を共に達成することはできない。（秘密分散を利用せずに）復号用の鍵の保存場所を考える場合、機密性を高めるために鍵を一か所で保管しておくか、あるいは信頼性を高めるために鍵のコピーを複数箇所に保存するか、どちらかを選ばざるを得ない。信頼性を高めるために多くの鍵のコピーを作ってしまうと、漏洩のリスクが高まり、機密性は低下する。秘密分散法は、この問題を解決することができる。すなわち、高い機密性と高い信頼性と同時に達成することができる。

秘密分散法は、クラウドコンピューティングにおいても重要である。しきい値秘密分散法を用いて、鍵をたくさんのクラウドサーバーの間で共有しておけば、必要な時に鍵を復元することができる。 また、センサーネットワークにおいて活用することも提案されている。センサーネットワークでは通信路が盗聴されやすいが、送信データをシェアに分割してから送信することによって、盗聴者が仕事をしにくくすることができる。このような環境では、シェアの生成方法を次々に変更していくことによって、安全性を高めることができる。

完全な秘密分散法

(t,n)-しきい値法と呼ばれる秘密分散法は、「t 人以上の参加者が集まったら秘密を復元可能」であり、 「t 人未満の参加者には秘密を全く漏らさない」ようにシェアが生成される。したがって、全参加者の部分集合は、秘密を復元できる[注釈 1]か、あるいは全く秘密が分からない[注釈 2]かの、いずれかである。 このように参加者の任意の部分集合が、秘密を復元できるか全く秘密が分からないかのいずれかである秘密分散法は、完全であると言う[注釈 3]。 下で紹介している秘密分散法は全て完全な秘密分散法である。

完全でない秘密分散法としては、ランプ法[3]がある。これはしきい値法を一般化したものであり、t 人以上の参加者は秘密を復元でき、t-d 人以下の参加者は秘密に対する情報を全く得ることができない。d >1 の場合、t -1 人の参加者は、秘密を完全には復元できないが、秘密に関して何らかの部分情報を得ることができる。d =1 とするとしきい値法となる。

制約

秘密分散法には、情報理論的に安全であるものと計算量理論的に安全であるものがある。

秘密分散法が情報理論的に安全であるとは、幾つかのシェアを見て秘密情報の復元を試みようとする者が無限の能力を持っていると想定した場合にも、必要な要件（幾つかのシェアを見ても秘密情報に関して何もわからない、といった初めにディーラーが設定した要件）が満たされることを言う。この安全性を持つ秘密分散法は、将来計算機の性能がどれだけ上がっても、秘密情報の機密性が損なわれることは無い。しかし、効率の観点で以下のような制約があることが知られている。

• シェアサイズの下限：秘密情報の候補が S 通りあるならば、各シェアも S 通り以上必要である（完全な秘密分散法の場合）[4]。この下限は、直感的には次のように示すことができる：t 個のシェアから秘密情報が復元でき、t − 1 個のシェアが秘密情報について何の情報も与えないということは、t 個目のシェアの候補は秘密情報の候補と同じだけ存在するはずである。この下限は、言い換えれば、各シェアのビット長は秘密情報のビット長と同じかそれより長くなってしまうことを示している。ただし、秘密情報が「偏りのある」情報である場合には、秘密情報を何らかの可逆圧縮で短くしてから秘密分散法を適用することで、シェアのサイズを短縮することは可能である。また、完全でない秘密分散法では、各シェアのビット長を秘密情報よりも短く（例えば半分に）できる場合がある[5]。

• 乱数生成：しきい値 t で分散したい場合、秘密情報一ビット当たり t − 1 ビットの乱数を生成する必要がある。

一方、計算量的に安全である秘密分散法は、何らかの暗号学的な仮定が成り立つときに限って、機密性が満たされる。例えば、128ビット安全であるブロック暗号を利用した秘密分散法は、当面の間は十分な安全性を持つ。将来的にはブロック暗号が危殆化して、秘密情報を復元できるべきでない人が復元できるようになってしまう可能性があるが、上述の制約を回避することができる。

簡単な秘密分散法

具体的な秘密分散法を紹介する。これらは全て情報理論的安全な方式である。

t = n の場合の (t, n)-しきい値法

1. 秘密情報がビット列 s で表現されている場合。一人以外の参加者のシェア v_i は s と同じ長さのランダムなビット列である。最後の参加者のシェアは (s XOR v₁ XOR v₂ XOR ... XOR v_n−1) とする。ただし、XORはビット毎の排他的論理和である。秘密情報は、全ての参加者のシェアをビット毎の排他的論理和を計算することで復元できる。
2. 秘密にしたい情報が曜日（つまり日曜～土曜のうちのどれか）である場合。秘密情報 s を 0～6 で表すことにする。n-1 個のシェア v_i は 0～6からランダムに選んだ整数。最後の n 番目のシェアは v_n = s - (v₁ + v₂ + ... + v_n-1) mod 7 と計算する。ただし、mod 7 は7で割ったあまりを意味する。秘密の復元は s = v₁ + v₂ + ... + v_n mod 7 で可能。
3. 一般に、同様のことが任意の有限体上での演算でできる。秘密情報を体 F の要素とすると、n-1 個のシェアは F の要素をランダムに選び、最後の1つは ${\displaystyle s-\sum _{i=1}^{n}v_{i}}$ を満たすように決定する。

明らかに、秘密情報と各シェアは同じサイズを持つ。（秘密が1MBならばシェアも1MB。）上で示したシェアサイズの下限により、これらの方式はシェアサイズの面で最も効率が良い。

1 < t < n の場合の (t, n)-しきい値法　

効率を無視した場合、t = n のしきい値法を利用して、簡単に (t, n)-しきい値法を構成することができる。 例えば、秘密情報 s をアリス、ボブ、キャロルの3人に (2,3)-しきい値法で分散させたいとする。 このときディーラーは、アリスとボブの二人に対して (2,2)-しきい値法を適用し、ボブとキャロルの二人に対して (2,2)-しきい値法を適用し、さらにキャロルとアリスの二人に対して (2,2)-しきい値法を適用すればよい。（それぞれのしきい値法では、秘密情報 s は共通で、乱数は独立に選ばなければならない。）3人は、それぞれ2つのシェアを渡され、秘密を復元するときには、誰と一緒に復元するかによって2つのシェアを使い分ける。

この方法では、人数 n が増えると、各参加者に渡されるシェアは非常に大きなものになってしまう。t=3, n=5 の場合（アリス、ボブ、キャロル、デイブ、エリザベスのうち、3人で秘密を復元可能にしたい）、アリスには6つのシェアが渡される。なぜなら、復元できる相手の組み合わせが6通り（ボブとキャロル、ボブとデイブ、ボブとエリザベス、キャロルとデイブ、キャロルとエリザベス、そしてデイブとエリザベス）あるのだから。 一般に、この方法で (t,n)-しきい値法を実現しようとすると、各参加者が持つ情報は、秘密情報の _(n-1)C_(t-1) 倍の長さになる。 もっと効率の良いシェアの作り方は、下を参照。

より一般の場合

t = n のしきい値法を利用すると、より一般的な設定に対応した秘密分散法も構成できる。 例えば、先に示した「妻と子供一人以上」または「子供三人」が合意したときのみ秘密情報を復元できるようにしたい、という設定に対しては、以下のようにすればよい。

1. 妻と子供1に対して (2,2)-しきい値法を適用する。同様に、妻と子供2、妻と子供3に対しても(2,2)-しきい値法を適用する。
2. 子供3人に対して (3,3)-しきい値法を適用する。

これによって、妻は3つのシェアを、子供たちはそれぞれ2つのシェアをA氏から受け取る。妻だけ、あるいは子供二人だけでは、財産の横取りはできない。

効率的な秘密分散法

シャミアのしきい値法

多項式補完を用いた秘密分散法である。(t-1)次曲線に乗っている t 個の点がわかれば、曲線を表す多項式が一意に定まるという性質を利用している。例えば、任意の2点を通る直線はちょうど一つしかない。同様に、任意の3点を通る放物線（二次曲線）はちょうど一つしかないし、任意の4点によって3次曲線がちょうど一つ決まる。一般の場合には、t 個の点によって（高々）t − 1 次の多項式が一つ決まる[注釈 4]。

シャミアの (t, n)-しきい値法では、ディーラーはまず、定数項が秘密の値 s、残りの係数がランダムである t − 1 次多項式 f(x) を決める。そして、多項式上の n 点 (x₁, f(x₁)), ..., (x_n, f(x_n)) を求め、参加者一人一人に一つの点 (x_i, f(x_i)) をシェアとして渡す。n 人の参加者のうち t 人以上が点（シェア）を持ち寄れば、元の (t − 1) 次多項式 f(x) が定まる。秘密情報はその多項式の定数項 f(0) として求められる。 x 座標の値 x₁, ... ,x_n は、互いに異なる0以外の値である。これらは秘密に隠しておく必要はなく、各参加者に番号が振られているならば、i 番目の参加者には f(i) を渡すのでも構わない。

厳密には、全ての演算は有限体 F_p の上で実行される。秘密情報として可能性のある値が S 通りある場合、体のサイズ p は p≧max(S, n+1) を満たしている必要がある。分散に用いる多項式の定数項以外の係数は、F_p からランダムに選ばれる。 秘密情報 s と各シェア f(x_i) は共に F_p の要素であるため、各シェアのサイズ（ビット長）は秘密情報のサイズと同じである。

ブラークリーのしきい値法

平面上の二つの（並行でない）直線は、必ず一つの点で交わる。また、3次元空間上の3枚の（平行でない）平面も、必ず一つの点で交わる。これを t 次元空間に一般化すると、t 枚の平行でない (t-1) 次元超平面は、必ず一つの点で交わる。ブラークリーのしきい値法は、このような性質を利用している。

例えば (2,n)-しきい値法の場合、ディーラーは (x-y)平面を考え、まず秘密情報 s から点 (r,s) を定める。x座標 r は乱数である。次に点 (r,s) を通るような直線をランダムに n 本用意し，それぞれの直線を各参加者へシェアとして渡す。二つのシェア（直線）から秘密を復元したいときには、二直線の交点を求めれば、その y 座標が秘密情報である。 交点の y 座標だけでなく x 座標にも秘密情報を埋め込みたくなるかもしれない。たとえば、4ケタの暗証番号のうち、上2桁を x 座標に、下2桁を y 座標に埋め込む、といったように。しかしそのようにしてしまうと、たった一つのシェア（直線）から、暗証番号の候補が狭まってしまい、必要な安全性が満たされない。

一般のしきい値 t の場合でも同様である。秘密情報 s は t 次元空間上の一点 (r₁,r₂,...,r_t-1, s) を定め（各 r_i は全てランダム）、シェアはその点を通るランダムな異なる (t-1) 次元超平面である。

3次元におけるブラークリーの方式。各シェアは 平面、秘密情報は３平面の交点である。2つの平面は秘密の一点を決定することができないが、範囲を「2面が共有する直線上」に狭めることが可能。

ブラークリーの方式は、シャミアの方式と比較して空間効率が悪い。シャミアの方式の場合は、各シェアは秘密情報と同じサイズであるが、ブラークリーの方式では、しきい値が 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 は、しきい値未満のシェアでは、データを復号できないことが保証されている。

脚注

注釈

1. このような部分集合は、アクセス集合(access set, qualified set)と呼ばれる。
2. このような部分集合は、非アクセス集合(non-access set, forbidden set)と呼ばれる。
3. したがって、完全な秘密分散法では、アクセス集合以外の部分集合は全て非アクセス集合であり、アクセス集合を指定すれば自動的に非アクセス集合も決まる。
4. (t-1) 次曲線は、t 次曲線の特殊な場合であることに注意。
5. 元のデータは5つの断片から復元できる必要があるので、原理的にこれ以上は短くできないことに注意。

出典

1. Shamir, Adi (1 November 1979). “How to share a secret”. Communications of the ACM 22 (11): 612–613. doi:10.1145/359168.359176. オリジナルの2017-08-10時点におけるアーカイブ。. https://web.archive.org/web/20170810232803/http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf. 
2. Blakley, G.R. (1979). “Safeguarding Cryptographic Keys”. Managing Requirements Knowledge, International Workshop on (AFIPS) 48: 313–317. doi:10.1109/AFIPS.1979.98. https://pdfs.semanticscholar.org/32d2/1ccc21a807627fcb21ea829d1acdab23be12.pdf. 
3. Blakley, G.B.; Meadows, C. Security of Ramp Schemes. CRYPTO 1984. pp. 242–268. doi:10.1007/3-540-39568-7_20。
4. Capocelli, R.M.; De Santis, A.; Gargano, L.; Vaccaro, U. On the size of shares for secret sharing schemes. Crypto '91. pp. 101–113. doi:10.1007/3-540-46766-1_7。
5. Ogata, Wakaha; Kurosawa, Kaoru; Tsujii, Shigeo. Nonperfect secret sharing schemes. AUSCRYPT 1992. pp. 56–66. doi:10.1007/3-540-57220-1_52。
6. Rabin, Tal; BEn-Or, Michael (1989). Verifiable secret sharing and multiparty protocols with honest majority. STOC '89.
7. Krawczyk, Hugo (1993). Secret Sharing Made Short (PDF). CRYPTO '93.
8. Rabin, Michael O. (1989). “Efficient dispersal of information for security, load balancing, and fault tolerance”. Journal of the ACM 36 (2): 335–348. doi:10.1145/62044.62050. 
9. Resch, Jason; Plank, James (15 February 2011). AONT-RS: Blending Security and Performance in Dispersed Storage Systems (PDF). Usenix FAST'11.

外部リンク

• Ubuntu Manpage: gfshare – explanation of Shamir Secret Sharing in GF(2^8)
• Description of Shamir's and Blakley's schemes
• Patent for use of secret sharing for recovering PGP (and other?) pass phrases アメリカ合衆国特許第 6,662,299号
• A bibliography on secret-sharing schemes
• Code signing systems using Shared Secret at the Wayback Machine (archived February 14, 2008)