シャミアの秘密分散法
概要
秘密情報をN個に分割する(シェア)
そのうちのk個を集めると復元することができる
加法準同型なので、シェアの状態で加算ができる
乗算も計算量が増えるが可能
仕組み
https://gyazo.com/22437cca9e7688618b8ba5621a979a99
ざっくり理解として
多項式の連立方程式を解くことで秘密情報を復元することができる
多項式の形状がわかると切片がわかる
切片が秘密情報を表している
以下手順
「秘密情報 s を N 個のシェアに分け、k 個のシェアで復元することを目指す」
シェアの作成
定数項が s である k-1 次多項式を適当に作成
e.g. $ f(x) = 2x^2 - 5x + s ただし k = 3
f(x) 上の任意の点をシェアとする
N 個選ぶ
復元方法
k 個の点を通る多項式 f(x) を求めることは簡単
連立方程式を解くことで求まる
f(0) = s であるので、秘密情報 s が得られる
e.g. $ f(0) = 2*0^2 - 5*0 + s = s
加法準同型写像
シャミアの秘密分散法は線形写像なので、加法準同型写像。
$ f(kx) = kf(x)
$ f(x + y) = f(x) + f(y)
異なるデータから生成されたシェアを全て加算すればいい
乗算
https://gyazo.com/c0adb7d8b61397a21d3d092a8b98cdd8
計算まとめ
https://gyazo.com/a6226d75dcc3cbb29f33af768294f61c
実装
SSSS(Shamir's Secret Share Scheme)
ライセンスはGNU GPL
参考資料
スライド
マルチパーティ計算の理論
藤崎英一郎 北陸先端科学技術大学大学院
Web
(k,n)しきい値法とシャミアの秘密分散法
高校数学の美しい物語