みなさまお疲れ様です、ゆうぴっぴ(@_yu_pippi_)です
2020アドベントカレンダー2日目に秘密分散について書いたので、今回はそれに関連したことを書こうと思います
そもそも秘密分散って？
みんなで秘密情報を管理して、リスクを減らそうという考えに基づく技術です
詳しくは自分が以前書いた記事や、Wikipediaなどを参考にしていただけると幸いです
事前知識
今回必要となる事前知識について軽く説明を行います
多項式補間
多項式補間とは、与えられたデータ点からその点全てを通る多項式を求めることをいいます
具体的にいうとある2点が与えられたとき、一次式
y={a_1}x+{a_0}
の係数を求めることが出来ますね！しかし、1点だけでは求めることは出来ません。
同様に、3点が与えられたときには二次式が求められますが、2点からは求めることは出来ません
一般に、n点が与えられたときn-1次の多項式
y={a_n}x^{n-1}+{a_{n-1}}x^{n-2}+{\cdots}+a_1x+a_0
が定まりますが、n-1点からは求めることが出来ません(厳密な証明は省きます)
今回はそのうちのラグランジュ補間という方法を使います
x座標の異なるn個のデータ点に対してn-1次式が以下の式から求められます
L(x)={\sum_{i=0}^{n}}f(x_i)l_i(x) \\
l_i(x)={\prod_{j=1,j{\neq}i}^{n}}{\frac{x-{x_j}}{{x_i}-{x_j}}}
有限体
これは説明しようとするとだいぶ長くなってしまう(めちゃくちゃ数学)ので簡単に説明しますと加減乗除ができる有限の数の集合のことです(絶対怒られる)
modの計算を思い浮かべてもらうとわかりやすいかもしれません
今回使うGF(p)(pは素数)は整数をpで割ったあまりの数を集めた集合のことを指します
Shamirの秘密分散(法)
それでは本題に入りましょう！
加法的秘密分散が(n,n)しきい値法と呼ばれるのに対してこの方法は(k,n)しきい値法とも呼ばれ、n個のシェアのうちk個が集まれば秘密情報の復元ができます
まず以下を定義します
S:秘密情報 \\
k:秘密情報を復元できるシェアの個数(しきい値) \\
n:生成するシェアの個数
分散(シェア生成)
まずS<pかつn<pを満たす素数pを選びます
次にディーラーは秘密情報を定数項とするk-1次式を生成します
ただし、多項式の係数はGF(p)の中から選びます
f(x)={a_{k-1}}x^{k-1}+{a_{k-2}}x^{k-2}+{\cdots}+a_1x+a_0 \\
a_0=S
次に互いに異なるx座標(これもGF(p)の中から選ぶ)を用いてシェア
(x_1,f(x_1)),(x_2,f(x_2)),{\cdots},(x_n,f(x_n))
を生成しn人の参加者に配布します
このときもf(x)はGF(p)上で選びます
ただし、1 <= k <= nとなるように生成します
再構築(復元)
しきい値以上の数のシェアを集め、生成した多項式にシェアの値を代入して連立方程式を立てます
その連立方程式を解くことで多項式の定数項、すなわち秘密情報が得られます
このときも有限体上で計算しますのでmod計算をしますね！
定数項ということはx座標が0のときの関数の値ですので
前述したラグランジュ補間とx=0という情報を用いると定数項がわかります(このためにラグランジュ補間の話をしました)
また、1 <= k <= nとなるように生成したので、必ず補間がうまくいきます
実装例は[こちら]
2021/4/26追記
自分の研究リポジトリ以下に置いていたので非公開にさせていただきました...
ただ、そこまで難しい実装ではないので式をソースコードに落とし込められればなんとかなります！(多分)
質問等あればTwitterなどで連絡いただければ答えられる範囲でお答えします
なかなか端折った説明となってしまいましたが読んでいただきありがとうございました