シャミアのしきい値法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/06 17:03 UTC 版)
多項式補完を用いた秘密分散法である。(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 の要素であるため、各シェアのサイズ（ビット長）は秘密情報のサイズと同じである。
※この「シャミアのしきい値法」の解説は、「秘密分散」の解説の一部です。
「シャミアのしきい値法」を含む「秘密分散」の記事については、「秘密分散」の概要を参照ください。
- シャミアのしきい値法のページへのリンク
