秘密分散
秘密分散の具体的なシナリオは以下のようなものである。
妻と3人の子供を持つA氏は、自分に何かあったときのために、隠し財産の在りかを家族に教えておきたいと思っているが、 妻や子供たちそれぞれにその情報を教えてしまったら、誰かが勝手に財産を使ってしまうかもしれない、と危惧している。 自分に何かがあったときに限って、家族が合意の上で財産を手に入れられるようにすることはできないだろうか?
もし、妻と全ての子供が合意した時のみ、財産の在りかが分かるようにしたいならば、A氏は次のようにすればよい。 (A氏がディーラー、妻と三人の子供が参加者、各 v i {\displaystyle v_{i}} がシェアである。)
s {\displaystyle s} : 秘密の在りかを示すビット列(秘密情報).
v 1 , v 2 , v 3 {\displaystyle v_{1},v_{2},v_{3}} : ランダムに選ばれた、秘密情報と同じ長さのビット列.
v 4 {\displaystyle v_{4}} : s = v 1 ⊕ v 2 ⊕ v 3 ⊕ v 4 {\displaystyle s=v_{1}\oplus v_{2}\oplus v_{3}\oplus v_{4}} を満たすビット列.( ⊕ {\displaystyle \oplus } はビットごとの排他的論理和)
v 1 , v 2 , v 3 {\displaystyle v_{1},v_{2},v_{3}} を3人の子供に、 v 4 {\displaystyle v_{4}} を妻に渡しておく。
効率を無視した場合、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) 倍の長さになる。 もっと効率の良いシェアの作り方は、下を参照。
秘密分散法には、情報理論的に安全であるものと計算量理論的に安全であるものがある。
秘密分散法が情報理論的に安全であるとは、幾つかのシェアを見て秘密情報の復元を試みようとする者が無限の能力を持っていると想定した場合にも、必要な要件(幾つかのシェアを見ても秘密情報に関して何もわからない、といった初めにディーラーが設定した要件)が満たされることを言う。この安全性を持つ秘密分散法は、将来計算機の性能がどれだけ上がっても、秘密情報の機密性が損なわれることは無い。しかし、効率の観点で以下のような制約があることが知られている。
シェアサイズの下限:秘密情報の候補が S 通りあるならば、各シェアも S 通り以上必要である(完全な秘密分散法の場合)。この下限は、直感的には次のように示すことができる:t 個のシェアから秘密情報が復元でき、t − 1 個のシェアが秘密情報について何の情報も与えないということは、t 個目のシェアの候補は秘密情報の候補と同じだけ存在するはずである。