秘密分散
多項式補完を用いた秘密分散法である。(t-1)次曲線に乗っている t 個の点がわかれば、曲線を表す多項式が一意に定まるという性質を利用している。例えば、任意の2点を通る直線はちょうど一つしかない。同様に、任意の3点を通る放物線(二次曲線)はちょうど一つしかないし、任意の4点によって3次曲線がちょうど一つ決まる。一般の場合には、t 個の点によって(高々)t − 1 次の多項式が一つ決まる。
シャミアの (t, n)-しきい値法では、ディーラーはまず、定数項が秘密の値 s、残りの係数がランダムである t − 1 次多項式 f(x) を決める。そして、多項式上の n 点 (x1, f(x1)), ..., (xn, f(xn)) を求め、参加者一人一人に一つの点 (xi, f(xi)) をシェアとして渡す。n 人の参加者のうち t 人以上が点(シェア)を持ち寄れば、元の (t − 1) 次多項式 f(x) が定まる。秘密情報はその多項式の定数項 f(0) として求められる。 x 座標の値 x1, ... ,xn は、互いに異なる0以外の値である。これらは秘密に隠しておく必要はなく、各参加者に番号が振られているならば、i 番目の参加者には f(i) を渡すのでも構わない。
厳密には、全ての演算は有限体 Fp の上で実行される。秘密情報として可能性のある値が S 通りある場合、体のサイズ p は p≧max(S, n+1) を満たしている必要がある。分散に用いる多項式の定数項以外の係数は、Fp からランダムに選ばれる。 秘密情報 s と各シェア f(xi) は共に Fp の要素であるため、各シェアのサイズ(ビット長)は秘密情報のサイズと同じである。
(t,n)-しきい値法と呼ばれる秘密分散法は、「t 人以上の参加者が集まったら秘密を復元可能」であり、 「t 人未満の参加者には秘密を全く漏らさない」ようにシェアが生成される。したがって、全参加者の部分集合は、秘密を復元できるか、あるいは全く秘密が分からないかの、いずれかである。 このように参加者の任意の部分集合が、秘密を復元できるか全く秘密が分からないかのいずれかである秘密分散法は、完全であると言う。 下で紹介している秘密分散法は全て完全な秘密分散法である。
完全でない秘密分散法としては、ランプ法がある。これはしきい値法を一般化したものであり、t 人以上の参加者は秘密を復元でき、t-d 人以下の参加者は秘密に対する情報を全く得ることができない。d >1 の場合、t -1 人の参加者は、秘密を完全には復元できないが、秘密に関して何らかの部分情報を得ることができる。d =1 とするとしきい値法となる。
この下限は、言い換えれば、各シェアのビット長は秘密情報のビット長と同じかそれより長くなってしまうことを示している。ただし、秘密情報が「偏りのある」情報である場合には、秘密情報を何らかの可逆圧縮で短くしてから秘密分散法を適用することで、シェアのサイズを短縮することは可能である。また、完全でない秘密分散法では、各シェアのビット長を秘密情報よりも短く(例えば半分に)できる場合がある。
乱数生成:しきい値 t で分散したい場合、秘密情報一ビット当たり t − 1 ビットの乱数を生成する必要がある。
一方、計算量的に安全である秘密分散法は、何らかの暗号学的な仮定が成り立つときに限って、機密性が満たされる。例えば、128ビット安全であるブロック暗号を利用した秘密分散法は、当面の間は十分な安全性を持つ。将来的にはブロック暗号が危殆化して、秘密情報を復元できるべきでない人が復元できるようになってしまう可能性があるが、上述の制約を回避することができる。