(k,n)しきい値法とシャミアの秘密分散法

秘密分散法とは，隠したい情報をいくつかに分割してばらばらに保存しておく方法のことです。

特にこの記事では $(k,n)$ しきい値法というものを考えます。

$(2,3)$ しきい値法の例です：

1. 秘密情報を3つに分割して東京，大阪，北海道に置いておく。

2. 二つ使えば秘密情報が復元できる（三つのデータのうち一つ壊れても復元できる！）

3. 一つだと秘密情報が復元できない（一つ盗まれても大丈夫！）

このように，$(k,n)$ しきい値法は 「故障に強い」かつ「漏洩に強い」という素晴らしい方法なのです。

$(k,n)$ しきい値法を具体的に実現する方法としてシャミア(Shamir)の秘密分散法を紹介します（よく分からない場合は後述の例参照）。

〜秘密分散の実現〜

• 秘密情報を $s$ とする
• 定数項が $s$ である $k-1$ 次多項式 $f(x)$ を適当に作る
• 通る点の座標 $(i,f(i))\:(i=1,2,\cdots,n)$ をシェアとする

〜復元方法〜

$k$ 個以上のシェアが手元にある
→ $f(x)$ が通る点が $k$ 個以上分かる
→多項式補間により $f(x)$ が分かる（→注）
→秘密情報 $f(0)$ を特定できる

注： $k$ 点を通る $k-1$ 次多項式は一つに決まります。→二次関数の決定とその背景

〜漏洩に強いこと〜

$k-1$ 個以下の通る点からは $f(x)$ は分からない。秘密情報 $f(0)$ に関する情報は全く得られない。

具体例として $(2,3)$ しきい値法をやってみます。秘密情報は7とします。

〜秘密分散の実現〜

定数項が $7$ である $1$ 次多項式を適当に作る： $f(x)=-3x+7$

通る点 $(1,4),(2,1),(3,-2)$ をシェアとする。

〜復元方法〜

三つのシェアのうち二つ，例えば $(1,4)$ と $(2,1)$ が分かれば，その2点を通る直線の方程式 $f(x)=-3x+7$ が求まる。つまり秘密情報 $f(0)=7$ が復元できる。

〜漏洩に強いこと〜

一つのシェアがバレても，通る一点からは直線は特定できない（切片に関する情報は全く得られない）ので秘密情報は守られる。