趣味の数学とプログラム。楽しい数学の世界へようこそ!

シャミアの秘密分散法


暗号化の技術を用いて、データ保存時や通信での暗号化が実現されても、データ処理時の復号すれば、データ漏洩の危険があります。

秘密計算システムは、暗号化したままデータ解析を行う方法です。

秘密計算の方式の一つである「秘密分散」は、元データを断片情報(シェア)に分けて無意味化します。シェア単体からは、元データの情報はわからず、復元するために必要なシェアの数の調整も可能で、故障や漏洩に強いというメリットがあります。

シャミアの秘密分散法

\((k,n)\)閾値法とも呼ばれ、\(n\)個のシェアのうち\(k\)個集まれば、元のデータを復元できます。

【秘密分散】

秘密情報:\(s\)

定数項\(s\)の \(k-1\)次多項式\(f(x)\)を適当に作る

通る点の座標 \((i,f(i))(i=1,2,\cdots,n)\)をシェアとする
 
【復元方法】

シェアは\(k\)個以上ある

\(f(x)\)が通る点が\(k\)個以上ある

多項式補間で\(f(x)\)がわかり、秘密情報\(s=f(0)\)がわかる

定理
\(n+1\)個の点\((x_i,y_i)\)
\((i=1,2,\cdots,n+1、ただしx_iは互いに異なる)\)を通る\(n\)次以下の関数がただ一つ存在する
\(n+1\)点を通る\(n\)次以下の関数は多くても一つ
もし2個あるとすると
\(y=f(x),y=g(x)\)なら \(f(x_i)=g(x_i) (i=1,2,\cdots,n+1)\)なので
\(f(x)-g(x)=a(x-x_1)(x-x_2)\cdots(x-x_{n+1})\)と表すことができ
\(a\neq0\)なら、右辺が\(n+1\)次になるので\(a=0\) すなわち \(f(x)=g(x)\)
 
\(n+1\)点を通る\(n\)次以下の関数を構成する方法がある
ラグランジュの補間公式
\(x\)座標が異なる\(n+1\)点\((x_1,y_1),(x_2,y_2),\cdots,(x_{n+1},y_{n+1})\)を通る\(n\)次以下の関数\(P(x)\)が1つ定まり、以下の式で表せる
\(P(x)=\displaystyle \sum_{i=1}^{n+1} y_i\frac{f_i(x)}{f_i(x_i)}\) ただし \(f_i(x)=\displaystyle \prod_{k \neq i}(x- x_k)\)

無料イラスト【イラストAC】

コメントを残す

メールアドレスが公開されることはありません。