(k, n)しきい値秘密分散の数学的原理を数学の素人が解説

(k, n)しきい値秘密分散には次の特徴があることはお話しました。

• 分散ファイルがｋ個未満からは元の情報を再構築できない（機密性が高い）

• 分散ファイルがｎ個そろわなくてもｋ個以上あれば元の情報を再構築できる（信頼性が高い）

両立の難しい機密性と信頼性。
それを両立できる秘密は数学的原理にあります。

今回は、その数学的原理を紹介しましょう。

生成多項式

まず見ていただくのはこの生成多項式。

う～ん。
なんだか小難しいですよね。
なので、後半の「＋」より後ろの部分を書き換えてみましょう。

Σってなに？

$${\sum}$$ってなんでしょうか。
見慣れない記号を使ってはいますが、これはただの「足し算」なんです。

例えば、$${\displaystyle\sum_{j=1}^{10}j}$$は次のように解釈します。

ですから、$${\displaystyle\sum_{j=1}^{10}j}$$は次のような意味になるわけです。

生成多項式のΣの展開

そうしますと、先ほどの生成多項式の$${\sum}$$は次のように展開されるのです。

「k-1」というのは抽象的でわかりにくいですが、例えば「k-1＝2」とするとこの生成多項式は、なんと！
見慣れた2次方程式になるのです。

ｋ次方程式の特徴

一般に、ｋ次方程式には次のような特徴があります。

• （ｋ＋１）個の点が決まれば、方程式はたった１つ

• 点がｋ個より少なければ、方程式は無数

(k, n)しきい値秘密分散は、方程式のこの特徴を利用しているのです。

(k, n)しきい値秘密分散は、まず、（ｋ－１）次方程式を作成します。
方程式の係数はなんでもかまいません。
そこからｎ個の点を取り出します。
この点が分散データになります。
このｎ個のうちｋ個が集まれば方程式は解けます。
逆に、ｋ個が集まらなければ方程式は解けません。
また、ｎ個のうちｋ個の点はどれでも構わないのです。

例えば、
ｋ＝３
ｎ＝５
で秘密分散しましょう。
データｄは、ｄ１、ｄ２、ｄ３、ｄ４、ｄ５に分散されます。
ｄ１～ｄ５は、ｄとは全く異なる数値です。

このうち３つがあれば方程式は解けます。
３つは
ｄ１、ｄ２、ｄ３
でも
ｄ２、ｄ４、ｄ５
でも
ｄ１、ｄ３、ｄ５
でも、どれでも構わないのです。
これが信頼性の基本になります。

逆に３つが集まらなければ方程式は解けません。
ｄ１とｄ２だけ
とか
ｄ３とｄ５だけ
では方程式は解けないのです。
ここに機密性があります。

次回は

次回はこれらをグラフを使って説明してみましょう。
グラフを見ると、更に面白いですよ～。