秘密分散のソースを表示

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

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

秘密分散は、1979年に[[アディ・シャミア]]<ref>{{cite journal |last1=Shamir |first1=Adi |title=How to share a secret |journal=Communications of the ACM |date=1 November 1979 |volume=22 |issue=11 |pages=612–613 |doi=10.1145/359168.359176 |url=https://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf |url-status=live |archiveurl=https://web.archive.org/web/20170810232803/http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf |archivedate=2017-08-10}}</ref> と {{仮リンク|ジョージ・ブラークリー|en|George Blakley}}<ref>{{cite journal |last1=Blakley |first1=G.R. |title=Safeguarding Cryptographic Keys |journal=Managing Requirements Knowledge, International Workshop on (AFIPS) |volume=48 |pages=313–317 |date=1979 |doi=10.1109/AFIPS.1979.98 |url=https://pdfs.semanticscholar.org/32d2/1ccc21a807627fcb21ea829d1acdab23be12.pdf}}</ref>によって独立に提唱された概念である。

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

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

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

* <math>s</math> : 秘密の在りかを示すビット列（秘密情報）．
* <math>v_1, v_2, v_3</math> : ランダムに選ばれた、秘密情報と同じ長さのビット列．
* <math>v_4</math> : <math>s=v_1 \oplus v_2 \oplus v_3 \oplus v_4</math> を満たすビット列．（<math>\oplus</math>はビットごとの排他的論理和）
* <math>v_1, v_2, v_3</math> を3人の子供に、<math>v_4</math> を妻に渡しておく。

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

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

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

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

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

秘密分散法（特に(t,n)-しきい値法）では、''t'' これを4つのシェア「pa------」「--ss----」「----wo--」「------rd」に分割したとする。シェアを一つも知らない人は、パスワードが英数字8文字であることしかわからず、パスワードの候補は　26<sup>8</sup> = 208 billion 個ある。
しかしシェアを一つ知っている人は、8文字中2文字が分かっているため、パスワードの候補は 26<sup>6</sup> = 308 million個になる。結果として、この "secure" secret sharing scheme, because a player with fewer than ''t'' secret shares is able to reduce the problem of obtaining the inner secret without first needing to obtain all of the necessary shares.

In contrast, consider the secret sharing scheme where ''X'' is the secret to be shared, ''P<sub>i</sub>'' are public [[Public-key cryptography|asymmetric encryption]] keys and ''Q<sub>i</sub>'' their corresponding private keys. Each player ''J'' is provided with {{nowrap|{''P''<sub>1</sub>(''P''<sub>2</sub>(...(''P<sub>N</sub>''(''X'')))), ''Q<sub>j</sub>''}.}} In this scheme, any player with private key 1 can remove the outer layer of encryption, a player with keys 1 and 2 can remove the first and second layer, and so on. A player with fewer than ''N'' keys can never fully reach the secret ''X'' without first needing to decrypt a public-key-encrypted blob for which he does not have the corresponding private key – a problem that is currently believed to be computationally infeasible. Additionally we can see that any user with all ''N'' private keys is able to decrypt all of the outer layers to obtain ''X'', the secret, and consequently this system is a secure secret distribution system.
-->
== 完全な秘密分散法 ==
(''t'',''n'')-しきい値法と呼ばれる秘密分散法は、「''t'' 人以上の参加者が集まったら秘密を復元可能」であり、
「''t'' 人未満の参加者には秘密を全く漏らさない」ようにシェアが生成される。したがって、全参加者の部分集合は、秘密を復元できる{{Efn|このような部分集合は、アクセス集合(access set, qualified set)と呼ばれる。}}か、あるいは全く秘密が分からない{{Efn|このような部分集合は、非アクセス集合(non-access set, forbidden set)と呼ばれる。}}かの、いずれかである。
このように参加者の任意の部分集合が、秘密を復元できるか全く秘密が分からないかのいずれかである秘密分散法は、'''完全'''であると言う{{Efn|したがって、完全な秘密分散法では、アクセス集合以外の部分集合は全て非アクセス集合であり、アクセス集合を指定すれば自動的に非アクセス集合も決まる。}}。
下で紹介している秘密分散法は全て完全な秘密分散法である。

'''完全でない'''秘密分散法としては、ランプ法<ref>{{Cite conference | conference = CRYPTO 1984 |pages = 242-268 | title = Security of Ramp Schemes | first1 = G.B.| last1 = Blakley | first2 = C. | last2 = Meadows | doi = 10.1007/3-540-39568-7_20}}</ref>がある。これはしきい値法を一般化したものであり、''t'' 人以上の参加者は秘密を復元でき、''t-d'' 人以下の参加者は秘密に対する情報を全く得ることができない。''d'' >1 の場合、''t'' -1 人の参加者は、秘密を完全には復元できないが、秘密に関して何らかの部分情報を得ることができる。''d'' =1 とするとしきい値法となる。

== 制約 ==
秘密分散法には、[[情報理論的安全性|情報理論的]]に安全であるものと[[計算量的安全性を持つ暗号|計算量理論的]]に安全であるものがある。

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

* シェアサイズの下限：秘密情報の候補が ''S'' 通りあるならば、各シェアも ''S'' 通り以上必要である（完全な秘密分散法の場合）<ref>{{Cite conference | first1 = R.M.| last1 = Capocelli| first2 = A.| last2 = De Santis| first3 = L.| last3 = Gargano| first4 = U. | last4 = Vaccaro | title = On the size of shares for secret sharing schemes | conference = Crypto '91 | pages = 101–113 | doi = 10.1007/3-540-46766-1_7}}</ref>。この下限は、直感的には次のように示すことができる：''t'' 個のシェアから秘密情報が復元でき、{{nowrap|''t'' − 1}} 個のシェアが秘密情報について何の情報も与えないということは、''t'' 個目のシェアの候補は秘密情報の候補と同じだけ存在するはずである。この下限は、言い換えれば、各シェアのビット長は秘密情報のビット長と同じかそれより長くなってしまうことを示している。ただし、秘密情報が「偏りのある」情報である場合には、秘密情報を何らかの[[可逆圧縮]]で短くしてから秘密分散法を適用することで、シェアのサイズを短縮することは可能である。また、完全でない秘密分散法では、各シェアのビット長を秘密情報よりも短く（例えば半分に）できる場合がある<ref>
{{Cite conference | first1 = Wakaha | last1 = Ogata | first2 = Kaoru | last2 = Kurosawa | first3 = Shigeo | last3 = Tsujii | title = Nonperfect secret sharing schemes | conference  = AUSCRYPT 1992 | pages = 56-66 | doi = 10.1007/3-540-57220-1_52}}</ref>。

* 乱数生成：しきい値 ''t'' で分散したい場合、秘密情報一ビット当たり {{nowrap|''t'' − 1}} ビットの乱数を生成する必要がある。<!--
しきい値法で１ビットだけ分散する場合は効率がさらに悪くなるので，ここではビット当たりの事のみ記述 -->

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

== 簡単な秘密分散法  ==
具体的な秘密分散法を紹介する。これらは全て情報理論的安全な方式である。<!-- 自明すぎるのでカット
=== しきい値''t''が1のしきい値法 ===
秘密情報をそのまま全ての''n''人の参加者に渡せばよい。
-->
=== ''t'' = ''n'' の場合の (''t'', ''n'')-しきい値法 ===
<!-- There are several {{nowrap|(''t'', ''n'')}} secret-sharing schemes for {{nowrap|1=''t'' = ''n''}}, when all shares are necessary to recover the secret:-->
# 秘密情報がビット列 ''s'' で表現されている場合。一人以外の参加者のシェア ''v<sub>i</sub>'' は ''s'' と同じ長さのランダムなビット列である。最後の参加者のシェアは (''s'' XOR ''v''<sub>1</sub> XOR ''v''<sub>2</sub> XOR ... XOR ''v''<sub>''n''−1</sub>) とする。ただし、XORはビット毎の[[排他的論理和]]である。秘密情報は、全ての参加者のシェアをビット毎の排他的論理和を計算することで復元できる。
# 秘密にしたい情報が曜日（つまり日曜～土曜のうちのどれか）である場合。秘密情報 ''s'' を 0～6 で表すことにする。''n''-1 個のシェア ''v<sub>i</sub>'' は 0～6からランダムに選んだ整数。最後の ''n'' 番目のシェアは ''v<sub>n</sub> = s - (v<sub>1</sub> + v<sub>2</sub> + ... + v<sub>n-1</sub>)'' mod 7 と計算する。ただし、mod 7 は7で割ったあまりを意味する。秘密の復元は ''s = v<sub>1</sub> + v<sub>2</sub> + ... + v<sub>n</sub>'' mod 7 で可能。
# 一般に、同様のことが任意の[[有限体]]上での演算でできる。秘密情報を体 ''F'' の要素とすると、''n''-1 個のシェアは ''F'' の要素をランダムに選び、最後の1つは <math>s - \sum_{i=1}^n v_i</math> を満たすように決定する。

明らかに、秘密情報と各シェアは同じサイズを持つ。（秘密が1MBならばシェアも1MB。）上で示したシェアサイズの下限により、これらの方式はシェアサイズの面で最も効率が良い。
=== 1 < ''t'' < ''n'' の場合の (''t'', ''n'')-しきい値法　===
<!--
The difficulty lies in creating schemes that are still secure, but do not require all ''n'' shares. For example, imagine that the Board of Directors of a company would like to protect their secret formula. The president of the company should be able to access the formula when needed, but in an emergency any 3 of the 12 board members would be able to unlock the secret formula together. This can be accomplished by a secret sharing scheme with ''t'' = 3 and ''n'' = 15, where 3 shares are given to the president, and 1 is given to each board member.
-->効率を無視した場合、''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)-しきい値法を実現しようとすると、各参加者が持つ情報は、秘密情報の <sub>(''n''-1)</sub>''C''<sub>(''t''-1)</sub> 倍の長さになる。
<!--
The trivial approach quickly becomes impractical as the number of subsets increases, for example when revealing a secret to any 50 of 100 players, which would require <math>\binom{100}{50} \approx 1.009\times 10^{29}</math> schemes to be created and each player to maintain <math>\binom{99}{49} \approx 5.04\times 10^{28}</math> distinct sets of shares for each scheme. In the worst case, the increase is exponential. This has led to the search for schemes that allow secrets to be shared efficiently with a threshold of players.
-->
もっと効率の良いシェアの作り方は、下を参照。
=== より一般の場合 ===
''t'' = ''n'' のしきい値法を利用すると、より一般的な設定に対応した秘密分散法も構成できる。
例えば、先に示した「妻と子供一人以上」または「子供三人」が合意したときのみ秘密情報を復元できるようにしたい、という設定に対しては、以下のようにすればよい。

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

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

== 効率的な秘密分散法 ==
=== シャミアのしきい値法 ===
[[ラグランジュ補間|多項式補完]]を用いた秘密分散法である。(''t''-1)次曲線に乗っている ''t'' 個の点がわかれば、曲線を表す多項式が一意に定まるという性質を利用している。例えば、任意の2点を通る直線はちょうど一つしかない。同様に、任意の3点を通る放物線（二次曲線）はちょうど一つしかないし、任意の4点によって3次曲線がちょうど一つ決まる。一般の場合には、''t'' 個の点によって（高々）{{nowrap|''t'' − 1}} 次の多項式が一つ決まる{{Efn|(t-1) 次曲線は、''t'' 次曲線の特殊な場合であることに注意。}}。

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

厳密には、全ての演算は[[有限体]] '''F'''<sub>p</sub> の上で実行される。秘密情報として可能性のある値が ''S'' 通りある場合、体のサイズ ''p'' は ''p≧max(S, n+1)'' を満たしている必要がある。分散に用いる多項式の定数項以外の係数は、'''F'''<sub>p</sub> からランダムに選ばれる。
秘密情報 ''s'' と各シェア ''f(x<sub>i</sub>)'' は共に '''F'''<sub>p</sub> の要素であるため、各シェアのサイズ（ビット長）は秘密情報のサイズと同じである。
=== ブラークリーのしきい値法 ===
平面上の二つの（並行でない）直線は、必ず一つの点で交わる。また、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''<sub>1</sub>,''r''<sub>2</sub>,...,''r''<sub>''t''-1</sub>, ''s'') を定め（各 ''r<sub>i</sub>'' は全てランダム）、シェアはその点を通るランダムな異なる (''t''-1) 次元超平面である。
<div align="center">
{| border="0" cellspacing="2px" style="margin-left: auto; margin-right:auto;" width="600px"
| [[File:Secretsharing 1.svg|250px|One share]]
| [[File:Intersecting Planes 2.svg|250px|二つのシェアは直線を共有する]]
| [[File:Secretsharing 3-point.svg|250px|三つのシェアは一点を共有する]]
|-
| colspan="3" | ''3次元におけるブラークリーの方式。各シェアは [[平面]]、秘密情報は３平面の交点である。2つの平面は秘密の一点を決定することができないが、範囲を「2面が共有する直線上」に狭めることが可能。
|}
</div>
ブラークリーの方式は、シャミアの方式と比較して空間効率が悪い。シャミアの方式の場合は、各シェアは秘密情報と同じサイズであるが、ブラークリーの方式では、しきい値が ''t'' ならば各シェアは秘密情報の ''t'' 倍の長さになる。
ブラークリーの方式は、シェアとして使える平面に対して制約を設けることで、効率を上げることができる。この効率化によって得られる方式は、多項式補完を用いたシャミアの方式と等価である。
<!-- 出典未確認のため，コメントアウト
=== 中国人の剰余定理を用いた方式 ===

[[中国人の剰余定理]]も秘密分散法として利用することができる。
中国人の剰余定理は、''k''個の[[互いに素]]な正整数 <math>m_1, m_2, ..., m_k</math> と k 個の剰余 <math>(S \bmod m_1), \ldots, (S \bmod m_k)</math> が与えられたとき、 <math> 0\leq S < \prod_{i=1}^k m_i</math>を満たす整数がただ一つ定ることを示し、またその S の効率的な求め方を与える。

中国人の剰余定理にもとづく秘密分散法は、Mignotteの方式とAsmuthとBloomによるものがあり、共にしきい値法である。シェアは整数<math>m_i</math>で割った余りの計算をして生成され、秘密情報の復元では中国人の剰余定理に基づく連立合同式を解く。
-->
== プロアクティブ秘密分散 ==
シェアをあまり安全でないコンピュータシステムに保管すると、シェアが漏洩する可能性がある。しきい値以上のシェアが漏洩すれば秘密情報を復元されてしまうことは自明であるが、それより少ない数のシェアが漏洩した場合でも、実質のしきい値が減少してしまうため、安全性は低下してしまう。安全性を再度高めるためには、新しく秘密情報を選択しなおして（例えば秘密情報がパスワードのような場合）分散し直せばよいが、変更が困難は秘密情報もある。

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

== 検証可能秘密分散法 ==
秘密を分散したり復元したりする段階で、参加者の誰かが手順に従わず、不正に情報を得たり他者を混乱に陥れようとするかもしれない。検証可能秘密分散法（verifiable secret sharing, VSS）は、他の参加者が手順に従っていることを（十分小さいエラー確率を除き）検証することのできる秘密分散法である。
<!-- Such schemes cannot be computed conventionally; the players must collectively add and multiply numbers without any individual's knowing what exactly is being added and multiplied.-->
[[Tal Rabin]]とMichael Ben-Orは、ディーラーまたは1/3未満の参加者による不正行為を検出可能なマルチパーティ計算プロトコル(MPC)を考案した<ref>{{cite conference |url=https://dl.acm.org/doi/abs/10.1145/73007.73014 |title=Verifiable secret sharing and multiparty protocols with honest majority |first1=Tal|last1=Rabin |first2=Michael |last2=BEn-Or |year=1989 |conference=STOC '89 }}</ref>。このプロトコルは、適応的(adaptive)な攻撃者、すなわち、プロトコル中で明かされる情報に依存して結託する参加者を決定するような攻撃者に対しても、安全性を保つことができる。

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

代表的な計算量理論的安全な秘密分散法は、Krawczykによる (''t'',''n'')-しきい値法である<ref>{{cite conference |url=http://www.cs.cornell.edu/courses/cs754/2001fa/secretshort.pdf |title=Secret Sharing Made Short |first=Hugo|last=Krawczyk|author= |authorlink=  |year=1993 |conference=CRYPTO '93 }}</ref>。
この方式は、ラビンのIDA（Information Dispersal Algorithm）<ref>{{cite journal |last1=Rabin |first1=Michael O. |year=1989 |title=Efficient dispersal of information for security, load balancing, and fault tolerance |journal=Journal of the ACM  |volume=36 |issue=2 |pages= 335–348|doi= 10.1145/62044.62050 |citeseerx=10.1.1.116.8657 }}</ref> をシャミアのしきい値法と組み合わせてできている。
秘密のデータは、まず何らかの共通鍵暗号で暗号化される。用いる暗号鍵はランダムに選ぶ。次に、暗号文をIDAで ''n'' 個の断片に分ける。IDAは、しきい値法と同様に ''n'' 個に分けた断片のうち ''t'' 個集まれば元のデータを復元できるが、しきい値法と違って各断片のサイズ（ビット長）は分ける前のデータの 1/''t'' になる。例えば、しきい値が5のときは、各断片は元のデータの 1/5 である{{Efn|元のデータは5つの断片から復元できる必要があるので、原理的にこれ以上は短くできないことに注意。}}。最後に、暗号化に使った鍵をシャミアのしきい値法で分散する。各参加者には、しきい値法のシェア1つとIDAの断片1つを渡す。暗号鍵の各シェアは鍵と同じ長さであるが、通常、鍵の長さは16～20バイトと小さいため、参加者に必要なストレージサイズは、ほぼIDAの断片の分だけである。

関連したアプローチとして、AONT-RSと呼ばれる<ref>{{cite conference |url=http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf |title=AONT-RS: Blending Security and Performance in Dispersed Storage Systems |first=Jason |last=Resch |author= |authorlink= |author2=Plank, James  |date=February 15, 2011 |conference=Usenix FAST'11 |conferenceurl=http://www.usenix.org/events/fast11/ }}</ref>では、IDAで処理するまでのステップとして、[[All-or-nothing transform]]を使っている。All-or-nothing transform は、しきい値未満のシェアでは、データを復号できないことが保証されている。
<!--
== 複数秘密に対する空間効率の良い秘密分散 ==
An information-theoretically secure ''k''-of-''n'' secret-sharing scheme generates ''n'' shares, each of size at least that of the secret itself, leading to the total required storage being at least ''n''-fold larger that the secret. 
In multi-secret sharing designed by [[Matthew K. Franklin]] and [[Moti Yung]],<ref>{{cite journal |last1=Franklin |first1=Matthew |last2=Yung |first2=Moti |title=Communication Complexity of Secure Computation (extended abstract) |journal=STOC '92 Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing |date=4 May 1992 |pages=699–710 |doi=10.1145/129712.129780 |url=http://dl.acm.org/citation.cfm?doid=129712.129780|isbn=0897915119 }} (also available at [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2764])</ref> multiple points of the polynomial host secrets; the method was found useful in numerous applications from coding to multi-party computations. In space efficient secret sharing, devised by Abhishek Parakh and [[Subhash Kak]], each share is roughly the fraction (k-1) of the size of the secret.<ref>{{cite journal |last1=Parakh |first1=Abhishek |last2=Kak |first2=Subhash |title=Space efficient secret sharing for implicit data security |journal=Information Sciences |date=January 2011 |volume=181 |issue=2 |pages=335–341 |doi=10.1016/j.ins.2010.09.013}}</ref>

This scheme makes use of repeated polynomial interpolation and has potential applications in secure information dispersal on the Web and in
[[sensor networks]]. This method is based on data partitioning involving the roots of a polynomial in finite field.<ref>{{cite journal |last1=Parakh |first1=Abhishek |last2=Kak |first2=Subhash |title=Online data storage using implicit security |journal=Information Sciences |date=September 2009 |volume=179 |issue=19 |pages=3323–3331 |doi=10.1016/j.ins.2009.05.013}}</ref> Some vulnerabilities of related ''space efficient'' secret sharing schemes were pointed out later.<ref>{{cite journal |last1=Sahasranand |first1=K.R. |last2=Nagaraj |first2=N. |last3=Rajan |first3=S. |title=How not to share a set of secrets |journal=International Journal of Computer Science and Information Security |date=2010 |volume=8 |pages=234–237 |arxiv=1001.1877 |bibcode=2010arXiv1001.1877S }}</ref> They show that a scheme based on interpolation method cannot be used to implement a {{nowrap|(''k'', ''n'')}} scheme when the ''k'' secrets to be distributed are inherently generated from a polynomial of degree less than {{nowrap|''k'' − 1}}, and the scheme does not work if all of the secrets to be shared are the same, etc.<ref>{{cite journal |last1=Liu |first1=Yanhong |last2=Zhang |first2=Futai |last3=Zhang |first3=Jie |title=Attacks to some verifiable multi-secret sharing schemes and two improved schemes |journal=Information Sciences |date=February 2016 |volume=329 |pages=524–539 |doi=10.1016/j.ins.2015.09.040}}</ref>

==Other uses and applications==
A secret sharing scheme can secure a secret over multiple servers and remain recoverable despite multiple server failures. The dealer may act as several distinct participants, distributing the shares among the participants. Each share may be stored on a different server, but the dealer can recover the secret even if several servers break down as long as they can recover at least ''t'' shares; however, [[Security cracking|cracker]]s that break into one server would still not know the secret as long as fewer than ''t'' shares are stored on each server.

This is one of the major concepts behind the [[Vanish (computer science)|Vanish]] computer project at the [[University of Washington]], where a random key is used to encrypt data, and the key is distributed as a secret across several nodes in a [[Peer-to-peer|P2P]] network. In order to decrypt the message, at least ''t'' nodes on the network must be accessible; the principle for this particular project being that the number of secret-sharing nodes on the network will decrease naturally over time, therefore causing the secret to eventually ''vanish''. However, the network is vulnerable to a [[Sybil attack]], thus making Vanish insecure.<ref>{{cite web | url=http://z.cs.utexas.edu/users/osa/unvanish/home | title = Unvanish: Reconstructing Self-Destructing Data |url-status=dead |archiveurl=https://web.archive.org/web/20120320161926/http://z.cs.utexas.edu/users/osa/unvanish/home |archivedate=2012-03-20}}</ref>

Note also that any shareholder who ever has enough information to decrypt the content at any point is able to take and store a copy of X. Consequently, although tools and techniques such as Vanish can make data irrecoverable within their own system after a time, it is not possible to force the deletion of data once a malicious user has seen it. This is one of the leading conundrums of [[Digital Rights Management]].

A dealer could send ''t'' shares, all of which are necessary to recover the original secret, to a single recipient. An attacker would have to intercept all ''t'' shares to recover the secret, a task which is more difficult than intercepting a single file, especially if the shares are sent using different media (e.g. some over the [[Internet]], some mailed on [[Compact Disc|CD]]s).

For large secrets, it may be more efficient to encrypt the secret and then distribute the key using secret sharing.

Secret sharing is an important primitive in several protocols for [[secure multiparty computation]].

== 関連項目 ==
{{columns-list|colwidth=36em|
* [[Access structure]]
* [[Byzantine fault tolerance]]
* [[Erasure code]] – When the data to be reconstructed is not a secret
* [[準同型秘密分散法]] – A simplistic decentralized voting protocol.
* [[Orthogonal array#Applications|Orthogonal array]] – Used to construct some threshold schemes.
* [[Secret sharing using the Chinese remainder theorem]]
* [[マルチパーティ計算]]
* [[シャミアのしきい値法]]
* [[Visual cryptography]]}}
-->
==脚注==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist|2}}
=== 出典 ===
{{Reflist|2}}

==外部リンク==
* [http://manpages.ubuntu.com/manpages/zesty/en/man7/gfshare.7.html Ubuntu Manpage: gfshare – explanation of Shamir Secret Sharing in GF(2<sup>8</sup>)]
* [http://www.rsasecurity.com/rsalabs/node.asp?id=2259 Description of Shamir's and Blakley's schemes]
* Patent for use of secret sharing for recovering PGP (and other?) pass phrases {{US patent|6662299}}
* [http://www.cacr.math.uwaterloo.ca/~dstinson/ssbib.html A bibliography on secret-sharing schemes]
* {{webarchive |url=https://web.archive.org/web/20080214135432/http://www.xml-dev.com/blog/index.php?action=viewtopic&id=130 |date=February 14, 2008 |title=Code signing systems using Shared Secret }} 
<!-- * {{cite web|last=Beimel|first=Amos|title=Secret-Sharing Schemes: A Survey|year=2011|url=http://www.cs.bgu.ac.il/~beimel/Papers/Survey.pdf}} -->

{{デフォルトソート:ひみつふんさん}}
[[Category:暗号技術]]