Shamirの秘密分散：多項式の数学

Shamir秘密分散（1979年）では、有限体上のランダムな次数(k-1)の多項式のy切片（f(0)）として秘密を符号化します。任意のk個の点で多項式を一意に決定でき（ラグランジュ補間）、k個未満の点からは何も分かりません。

秘密Sをしきい値kでn人に分散するには、Sとnより大きい素数pを選びます。ランダムな係数a_1, ..., a_{k-1}を選びます。f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p) を定義します。参加者iはシェア(i, f(i))を受け取ります。

秘密S=7、p=17、k=2（1次多項式）とします。a_1=3を選びます。f(x)=7+3x mod 17です。シェアは(1,10)、(2,13)、(3,16)です。任意の2点で直線を決定できます。f(0)=7です。1点だけでは、可能な直線が無限に存在するため、Sについての情報はゼロです。

k個の点(x_1,y_1),...,(x_k,y_k)が与えられたとき、ラグランジュ補間を使ってf(0)を復元します: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p。すべての計算はモジュラー演算です。浮動小数点は使わず、有限体上で正確に復元します。

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

k-1個のシェアについて、可能な秘密値 S ごとに、それらk-1個の点を通る次数k-1の多項式は正確に1つ存在します。したがって、k-1個のシェアを知っていても、[0, p-1] に含まれるSの各値は等しい確率で生じます。つまり、情報は一切明らかになりません。

p は秘密値と n より大きくなければなりません。一般的な選択は、128ビットの秘密に対する p = 2^127-1（メルセンヌ素数）です。これにより、すべてのシェアが128ビットに収まり、演算も効率的になります。別の選択肢として、512ビットの秘密には p=2^521-1 を使用します。

基本的なSSSにはシェアの完全性を保証する仕組みがありません。悪意のあるシェア保有者が偽のシェアを提出すると、秘密の復元結果が誤る可能性があります。Feldman VSS（Verifiable Secret Sharing）は g^{a_i} mod p のコミットメントを公開し、多項式を明らかにすることなくシェアを検証できるようにします。

シェアは定期的に更新できます。同じ秘密 S を持つ新しい多項式を生成して新しいシェアを再配布すると、古いシェアは無効になります。更新後にシェア保有者を侵害した攻撃者が入手できる古いシェアは役に立ちません。長期間運用する鍵管理システムで使用されます。

ssss（Linuxコマンドライン）、python-secret-sharing、hashicorp/vault はシール機構にSSSを使用し、TrezorハードウェアウォレットはウォレットシードのバックアップにSSS（SLIP-39）を使用します。いずれも大きな素数体上で動作します。

SSSでは、シェアを生成して配布する信頼できるディーラーが必要です（ディーラーは秘密を知ることになります）。ディーラーを置かない場合は、DKG（Distributed Key Generation）が必要です。復元時には、k個のシェアを持つ人に秘密が明らかになります。この問題はMPCや閾値署名によって解消できます。

ShamirのSSSは秘密を多項式の y 切片として符号化します。ラグランジュ補間により、k個のシェアから秘密を復元できます。k個未満のシェアに対して、完全な情報理論的安全性を実現します。次は、視覚秘密分散と加法的秘密分散について学びます。