シャミールの秘密の共有

企業は金庫のセキュリティを確保する必要があります。金庫の暗証番号を知っているのが1人だけの場合、金庫を開ける必要が生じた際に暗証番号が紛失したり、利用できなくなったりする可能性があります。また、暗証番号を知っている人が複数いる場合、互いに常に誠実に行動するとは限らないため、信頼関係が崩れる可能性があります。

SSSは、このような状況において、保管庫のコードの共有部分を生成し、社内の承認された個人に配布するために使用できます。各個人に付与される共有部分の最小値と数を設定することで、保管庫へのアクセスを許可された個人（またはグループ）のみに限定できます。提示された共有部分が最小値に満たない場合は、保管庫を開くことはできません。

偶発的な事故、強制、あるいは反抗的な行為として、一部の個人が保有株式に関する誤った情報を提供する可能性があります。正しい株式の合計数が最低基準を満たさない場合、金庫はロックされたままとなります。

シャミアの秘密共有は、

• パスワードマネージャのルートキーを復号するためのキーを共有する、^{[ 2 ]}
• 暗号化された電子メールへのアクセス用のユーザーキーを復元する、^{[ 3 ]}
• マスターシークレットを再生成するために使用されるパスフレーズを共有し、それが暗号通貨ウォレットにアクセスするために使用されます^{[ 4 ]}
• 物理的な金庫の暗証番号を復元する。

共有する秘密が1234だと仮定します。${\displaystyle (S=1234)}$。

この例では、秘密は6つのシェアに分割されます。${\displaystyle (n=6)}$3つの株式の任意の部分集合${\displaystyle (k=3)}$秘密を復元するにはそれで十分だ。${\displaystyle k-1=2}$数字はランダムに選ばれます。仮に166と94としましょう。

これにより係数が得られます${\displaystyle (a_{0}=1234;a_{1}=166;a_{2}=94),}$どこ${\displaystyle a_{0}}$秘密は

したがって、秘密のシェア（ポイント）を生成する多項式は次のようになります。

${\displaystyle f(x)=1234+166x+94x^{2}}$

6ポイント${\displaystyle D_{x-1}=(x,f(x))}$多項式は次のように構成されます。

${\displaystyle D_{0}=(1,1494);D_{1}=(2,1942);D_{2}=(3,2578);D_{3}=(4,3402);D_{4}=(5,4414);D_{5}=(6,5614)}$

この制度の各参加者は異なるポイント（${\displaystyle x}$そして${\displaystyle f(x)}$）。 なぜなら${\displaystyle D_{x-1}}$の代わりに${\displaystyle D_{x}}$ポイントは${\displaystyle (1,f(1))}$そしてそうではない${\displaystyle (0,f(0))}$これは、${\displaystyle f(0)}$それが秘密です。

秘密を復元するには、3つのポイントがあれば十分です。

以下の3つのポイントの使用を検討してください${\displaystyle \left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)}$。

ラグランジュ基底多項式の計算：

${\displaystyle \ell _{0}(x)={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}\cdot {\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}}$

${\displaystyle \ell _{1}(x)={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot {\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}\cdot {\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5}$

${\displaystyle \ell _{2}(x)={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot {\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}\cdot {\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}}$

多項式補間の公式を用いて、${\displaystyle f(x)}$は：

${\displaystyle {\begin{aligned}f(x)&=\sum _{j=0}^{2}y_{j}\cdot \ell _{j}(x)\\[6pt]&=y_{0}\ell _{0}(x)+y_{1}\ell _{1}(x)+y_{2}\ell _{2}(x)\\[6pt]&=1942\left({\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}\right)+3402\left(-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5\right)+4414\left({\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}\right)\\[6pt]&=1234+166x+94x^{2}\end{aligned}}}$

秘密は自由係数であることを思い出してください。つまり、${\displaystyle S=1234}$そして、秘密は解明された。

多項式補間を使用してソース多項式の係数を求める${\displaystyle S=f(0)}$ラグランジュ多項式を用いる方法は、使用されない定数まで計算されてしまうため、効率的ではありません。

これを考慮すると、ラグランジュ多項式を使用して見つけるための最適化された式は次のようになります。${\displaystyle f(0)}$は次のように定義されます。

${\displaystyle f(0)=\sum _{j=0}^{k-1}y_{j}\prod _{\begin{smallmatrix}m\,=\,0\\m\,\neq \,j\end{smallmatrix}}^{k-1}{\frac {x_{m}}{x_{m}-x_{j}}}}$

上記で示した方法の簡略版（有限体演算ではなく整数演算を使用）は機能するものの、セキュリティ上の問題がある。イブは、${\displaystyle S}$あらゆる${\displaystyle D_{i}}$彼女が見つけたもの。

彼女がポイントを見つけたと仮定します${\displaystyle D=(2,1942)}$彼女はまだ持っていない${\displaystyle k=3}$ポイントなので、理論的には彼女はこれ以上情報を得るべきではなかった${\displaystyle S}$しかし彼女は、その地点からの情報と公開情報を組み合わせることができた。${\displaystyle n=6,k=3,f(x)=a_{0}+a_{1}x+\cdots +a_{k-1}x^{k-1},a_{0}=S,a_{i}\in \mathbb {Z} }$そうすることで、イブは以下の代数計算を実行できる。

1. 式を記入してください${\displaystyle f(x)}$と${\displaystyle S}$そしてその価値は${\displaystyle k:f(x)=S+a_{1}x+\cdots +a_{k-1}x^{k-1}\Rightarrow {}f(x)=S+a_{1}x+a_{2}x^{2}}$
2. （１）に以下の値を記入してください。${\displaystyle D}$の${\displaystyle x}$そして${\displaystyle f(x):1942=S+a_{1}2+a_{2}2^{2}\Rightarrow {}S=1942-2a_{1}-4a_{2}}$

それによって彼女はSが偶数であるという情報にたどり着く。

上記の攻撃は、多項式が構築された方法によって多項式が取り得る値に課せられた制約を利用します。多項式の係数は整数でなければならず、スキームで使用される各座標で評価されたときに多項式は整数値をとらなければなりません。これにより、結果として得られる秘密を含む未知の点での可能な値が、より少ない値で減少します。${\displaystyle k}$株。

この問題は有限体演算を用いることで解決できます。有限体は常にサイズが一定です。${\displaystyle q=p^{r}}$、 どこ${\displaystyle p}$は素数であり、${\displaystyle r}$は正の整数です。サイズ${\displaystyle q}$当該分野の要件を満たす必要がある${\displaystyle q>n}$そして、${\displaystyle q}$は秘密の値の可能な数よりも大きいが、後者の条件は秘密をより小さな秘密の値に分割し、それぞれの値にこの方式を適用することで回避できる。以下の例では、素体（つまりr = 1）を使用する。図は有限体上の多項式曲線を示す。

実際には、これは小さな変更にすぎません。フィールドのオーダーq（つまり、フィールドが持つ値の数）は、参加者の数と秘密の値の数よりも大きく選択する必要があります。${\displaystyle a_{0}=S}$時間がかかる場合があります。多項式を含むすべての計算は、体 (mod pの例では、${\displaystyle p=q}$（は素数とみなされる）を整数ではなく体として扱う。体の選択と、秘密をこの体の値にマッピングする方法は、どちらも公に知られているものとみなされる。

この例では、${\displaystyle p=1613}$多項式は次のようになる${\displaystyle f(x)=1234+166x+94x^{2}{\bmod {1613}}}$これにより、以下のポイントが得られます。${\displaystyle (1,1494);(2,329);(3,965);(4,176);(5,1188);(6,775)}$

今回はイヴは${\displaystyle D_{x}}$（彼女が${\displaystyle k}$ポイント）。

イブが再び発見したと仮定します${\displaystyle D_{0}=\left(1,1494\right)}$そして${\displaystyle D_{1}=\left(2,329\right)}$公開情報は以下のとおりです。${\displaystyle n=6,k=3,p=1613,f(x)=a_{0}+a_{1}x+\dots +a_{k-1}x^{k-1}\mod {p},a_{0}=S,a_{i}\in \mathbb {N} }$前述の攻撃を試みる場合、イブは以下のことが可能です。

1. 記入してください${\displaystyle f(x)}$-数式${\displaystyle S}$そしてその価値は${\displaystyle k}$そして${\displaystyle p}$:${\displaystyle f(x)=S+a_{1}x+\dots +a_{3-1}x^{3-1}\mod 1613}$
2. （１）に以下の値を記入してください。${\displaystyle D_{0}}$の${\displaystyle x}$そして${\displaystyle f(x):1494\equiv S+a_{1}1+a_{2}1^{2}{\pmod {1613}}\Rightarrow {}1494\equiv S+a_{1}+a_{2}{\pmod {1613}}}$
3. （１）に以下の値を記入してください。${\displaystyle D_{1}}$の${\displaystyle x}$そして${\displaystyle f(x):1942\equiv S+a_{1}2+a_{2}2^{2}{\pmod {1613}}\Rightarrow {}1942\equiv S+2a_{1}+4a_{2}{\pmod {1613}}}$
4. (3)-(2)を引く：${\displaystyle (1942-1494)\equiv (S-S)+(2a_{1}-a_{1})+(4a_{2}-a_{2}){\pmod {1613}}\Rightarrow {}448\equiv a_{1}+3a_{2}{\pmod {1613}}}$そしてこれを次のように書き換えます${\displaystyle a_{1}\equiv 448-3a_{2}{\pmod {1613}}}$

がある${\displaystyle p}$可能な値${\displaystyle a_{1}}$彼女はそれを知っている${\displaystyle [448,445,442,\ldots ]}$常に 3 ずつ減少するので、${\displaystyle p}$で割り切れる${\displaystyle 3}$彼女は結論づけることができた${\displaystyle a_{1}\in [1,4,7,\ldots ]}$。 しかし、${\displaystyle p}$は素数なので、彼女はこの結論を下すことはできません。したがって、有限体を使用することで、このような攻撃を回避できます。

また、イブは${\displaystyle S\equiv 1046+2a_{2}{\pmod {1613}}}$これは、上記の整数演算の例とは異なり、モジュラー演算の「ラップアラウンド」動作によって「Sは偶数である」という情報が漏洩するのを防ぐため、追加情報を提供しません。