ブラークリーのしきい値法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/06 17:03 UTC 版)
「秘密分散」の記事における「ブラークリーのしきい値法」の解説
平面上の二つの（並行でない）直線は、必ず一つの点で交わる。また、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 次元空間上の一点 (r1,r2,...,rt-1, s) を定め（各 ri は全てランダム）、シェアはその点を通るランダムな異なる (t-1) 次元超平面である。 3次元におけるブラークリーの方式。各シェアは 平面、秘密情報は３平面の交点である。2つの平面は秘密の一点を決定することができないが、範囲を「2面が共有する直線上」に狭めることが可能。 ブラークリーの方式は、シャミアの方式と比較して空間効率が悪い。シャミアの方式の場合は、各シェアは秘密情報と同じサイズであるが、ブラークリーの方式では、しきい値が t ならば各シェアは秘密情報の t 倍の長さになる。ブラークリーの方式は、シェアとして使える平面に対して制約を設けることで、効率を上げることができる。この効率化によって得られる方式は、多項式補完を用いたシャミアの方式と等価である。
※この「ブラークリーのしきい値法」の解説は、「秘密分散」の解説の一部です。
「ブラークリーのしきい値法」を含む「秘密分散」の記事については、「秘密分散」の概要を参照ください。
- ブラークリーのしきい値法のページへのリンク
