Shamir 秘密分散と閾値暗号の原理

解きたい問題：1つの秘密を、誰も単独で握らせず守る

ルート鍵やマスターパスワードのような最重要の秘密は、二つの相反する要求に挟まれます。失われては困る（可用性）一方で、1人が単独で使えても困る（機密性・内部不正対策）。単純なコピー配布は紛失に強いが漏洩面が増え、1か所に隔離すると単一障害点になります。

Shamir 秘密分散（SSS）はこのジレンマを数学で解きます。秘密 S を n 個のシェアに分割して別々の保管者へ配り、あらかじめ決めた閾値 k 個を集めたときだけ S を復元できる。k 個未満では、秘密について一切の情報が漏れないように設計します。これが (k,n) 閾値秘密分散です。

数理：多項式は k 点でちょうど決まる

中核は、高校でも習う多項式補間の一意性です。k-1 次の多項式は、相異なる k 個の点を指定すればただ一つに定まる。逆に点が k 個未満なら、その点をすべて通る k-1 次多項式は無数に存在します。Shamir はこの非対称性をそのまま機密性に使います。

分割（ディーラ）の手順はこうです。秘密 S を多項式の定数項に置き、残りの係数を乱数で埋めます。

有限体 GF(p)（p は十分大きな素数）上で計算する
秘密 S を a0 に置く: f(x) = a0 + a1·x + a2·x^2 + ... + a(k-1)·x^(k-1)
  a0 = S, a1..a(k-1) は CSPRNG で一様乱数として選ぶ
シェア i (i = 1..n): (x_i, y_i) = (i, f(i) mod p) を保管者 i に配る
  ※ x = 0 は f(0) = S なので絶対に配らない

復元は逆向きです。任意の k 個のシェア (x, y) が集まれば、それらを通る k-1 次多項式 f が一意に決まり、f(0) = a0 = S を取り出せます。実装では多項式全体を求めず、x = 0 での値だけをラグランジュ補間で直接計算します。

k 個のシェア {(x_1,y_1), ..., (x_k,y_k)} から S = f(0) を復元:

S = Σ_j  y_j · L_j(0)  (mod p)

L_j(0) = Π_{m≠j}  x_m / (x_m - x_j)   ← ラグランジュ基底を x=0 で評価

割り算は GF(p) 上のモジュラ逆元（フェルマーの小定理 a^(p-2) など）で行う

情報理論的安全性：計算では破れない

SSS の安全性は、公開鍵暗号 のように「逆算が計算的に困難」だから守られるのではありません。情報理論的に完全です。k-1 個のシェアしか持たない攻撃者を考えます。あと1点を (0, S) のどんな値に取っても、その k 点を通る k-1 次多項式は必ずちょうど1つ存在します。つまりどの秘密 S も等しく起こり得る。

k-1 個のシェアを固定したとき:
  秘密候補 S を任意に選ぶ → (0,S) を加えた k 点を通る f が必ず一意に存在
  → 体内のどの S も「ありうる」確率が等しい

⇒ k-1 個のシェアは S について 0 ビットの情報しか持たない（完全秘匿）

これはワンタイムパッドと同じ強度で、攻撃者の計算力が無限でも秘密を絞り込めないことを意味します。後述する派生方式の多くは効率や検証のため計算量的仮定を導入しますが、素の Shamir 分散それ自体は計算量に依存しません。代償として、各シェアのサイズは秘密と同程度になります（情報理論的秘匿の宿命）。

閾値暗号へ：秘密を一度も復元せずに使う

素の SSS には弱点があります。使うときに S を1か所で復元する瞬間、そのマシンが単一障害点になるのです。ここで発展するのが閾値暗号（threshold cryptography）。鍵を分割したまま、各保管者が自分のシェアで部分的な計算を行い、結果を合成して署名や復号を得ます。秘密鍵が完全な形でメモリ上に現れません。

代表例が閾値署名です。例えば BLS 署名は、各参加者が自分の鍵シェアで部分署名を作り、それらをラグランジュ係数で重み付けして合成すると、ちょうど元の秘密鍵による正規の署名と一致します。署名検証側は通常の単一鍵の署名と区別できない――この透過性が運用上の利点です。各署名スキームの内部 の数理がそのまま閾値版へ拡張されます。

閾値署名（概念）:
  鍵生成: 秘密鍵 sk を (k,n) でシェア sk_i に分割
  部分署名: 参加者 i が σ_i = Sign(sk_i, m) を計算
  合成: k 個の σ_i をラグランジュ係数で結合 → σ = Sign(sk, m) と等価
  ⇒ sk は一度も1か所に集まらない

分散鍵生成（DKG）：ディーラさえ信用しない

閾値署名でも、最初に1人のディーラが完全な S を知って分割するなら、その瞬間にディーラが単一信頼点になります。**分散鍵生成（DKG）**はこれを排除します。誰も完全な秘密鍵を知らないまま、参加者全員の協調で鍵ペアを生成する仕組みです。

仕組みは Shamir の重ね合わせです。各参加者 i が自分の乱数秘密 s_i を自前の多項式で分散し、互いにシェアを配り合う（VSS で検証付き）。最終的な秘密鍵は各 s_i の総和 Σ s_i に対応し、各人のシェアもその総和になります。どの単独参加者も全体の秘密鍵を計算できず、公開鍵だけが全員に共有されます。Pedersen DKG はこの古典的な構成です。DKG は本質的に秘密計算（MPC） の一種で、入力（各自の乱数）を秘匿したまま共同で関数（鍵生成）を評価していると見なせます。

応用：ルート鍵・コールドウォレットの分割保管

最も古典的かつ重要な応用が、最上位の秘密（ルート鍵・CA の秘密鍵・マスターキー）の分割保管です。例えば認証局のルート鍵や HSM のマスターキーは、Shamir 分散で複数の役員・拠点に配り、鍵の起動（セレモニー）時にだけ規定人数を集めて復元します。これにより、1人の内部不正者や1拠点の物理侵害では鍵を悪用できません。

暗号資産のコールドウォレットや、クラウドの シークレット管理 基盤の自動アンシール（例: 複数のアンシールキーで保管庫を解錠する方式）も同じ発想です。閾値署名や DKG を併用すれば、復元の瞬間すら作らずに鍵を運用できます。

まとめ

Shamir 秘密分散は、秘密を k-1 次多項式の定数項に埋め、n 個の点をシェアとして配る方式です。k 個集めればラグランジュ補間で f(0) = S を復元でき、k-1 個以下ではどの秘密も等確率にあり得るため情報理論的に完全に秘匿されます。閾値 k（機密性）と冗長度 n-k（可用性）を独立に設計できる点が、単純なコピー配布や1か所隔離にない強みです。

同じ多項式の構造から、秘密鍵を一度も復元せずに署名する閾値署名、ディーラすら信用しない**分散鍵生成（DKG）**が派生し、これらは秘密計算（MPC） の一族として理解できます。実務ではルート鍵や CA 鍵、コールドウォレットの分割保管に使われ、能動的攻撃者を想定する場面では検証可能秘密分散（VSS）が前提になります。鍵そのものの保護機構は HSM と鍵保護、署名の数理は 署名スキームの内部 と併せて押さえると全体像がつながります。