Shamir Secret Sharing
Shamir の秘密分散は 1979 年に提案された (t,n) しきい値方式である。GF(p) 上の多項式補間に基づき、情報理論的に安全である。
目的
秘密を n 個のシェアへ分割し、そのうち t 個で復元できる一方、t-1 個が結託しても何も漏えいないようにする。しきい値暗号の事実上の標準である。
メカニズム
素数 p を選び、次数 t-1 の多項式 f(x) = S + a_1 x + ... + a_{t-1} x^{t-1} (mod p) を構成する。シェアは (i, f(i)) である。復元にはラグランジュ補間を用い、f(0) = Σ f(i)·λ_i (mod p) を計算する。
ユースケース
- 暗号通貨ウォレットのバックアップ
- CA 秘密鍵のしきい値保護
- MPC プロトコルの基盤