秘密情報分散法

秘密情報分散法は、秘密の値sをn人で分散して管理する方法です。 良く知られているShamirの秘密情報分散法について考えてみます。

Shamirの秘密情報分散法

n人の管理者に分散情報を分け与え、n人の内k−1人分以下の分散情報からは秘密について何も分からないが、ｋ人分以上の分散情報があれば秘密を復元できる方法です。 n人で分散管理している秘密の復元の可否がk人をしきい値にして代わるため、(k,n)しきい値法と呼ばれます。

1. Shamirの秘密分散法は素数pを用いた法pの剰余演算上で考えるのが普通ですが、動作を理解する上では通常の四則演算で考えれば十分ですので法pでの剰余演算のことは考えないことにします。
2. 簡単のためしきい値が2の場合を想定します。2次元のxy平面(ユークリッド空間)上の直線を考えてみます。
3. 秘密の直線Lを一つ定め、その直線Lがy軸と交差する点のy座標Sを秘密とします。
4. 直線はその直線が通る2点が分かれば特定できるので、Lの通る2点が分かればLを特定でき、秘密Sが分かります。
5. Lの通る点が1点Pのみしか分からない場合には、Lはｙ軸上のどの点であってもその点とPを通る直線は必ず引けますので、Pだけからは秘密の値Sについて何も分かりません。
6. Lの通るy軸上にない異なるn個の点P₁,…,P_nを選び、n人の管理者にその座標を分散情報として一つずつ与えておけば、一人分の分散情報ではLを特定できず、二人分の分散情報があればLを特定でき、Sを求められます。これで(2,n)しきい値法が実現できたことになります。
7. 直線は1次の方程式により定まり、2個の点を指定すれば直線を一意に定めることができました。ｋ−1次の方程式で定まるk−1次曲線は、k個の点を指定すれば一意に定めることができるので、同様にして(k,n)しきい値法を構成できます。
8. (k,n)しきい値法の場合はk−1次の秘密の曲線Cを一つ定めて、その曲線Cがy軸と交差する点のy座標Sを秘密とすれば良いことになります。