Shamir Secret Sharing

k-of-n方式は同じ集合の有効で異なる任意のkシェアから復元できます。n−kシェアの紛失に耐える一方、協力するk人の保有者にも秘密の取得を許します。例えば3-of-5は2シェアの紛失に耐え、3シェアには耐えません。閾値は可用性と復元可能な集団の人数の折り合いです。 [Adi Shamir — How to Share a Secret (1979)]

秘密Sに対しf(x)=S+a1*x+…+a(k−1)*x^(k−1)を選びます。S以外の係数は独立で一様ランダムな体の要素です。シェアは互いに異なる非ゼロのxを持つ(x,f(x))で、x=0ならSを直接公開してしまいます。k点からのラグランジュ補間でf(0)を求めます。同じ点のコピー2枚は方程式を増やしません。 [Adi Shamir — How to Share a Secret (1979)]

教材としてのみS=5、f(x)=5+3*x mod 17とします。シェアは(1,8)、(2,11)、(3,14)です。最初の2点は傾き3、定数8−3=5を与え、3通りのペアすべてで5を復元します。(1,8)だけならa=8−S mod 17として0から16までどのSとも両立します。この小さな体はウォレット設計ではありません。 [Adi Shamir — How to Share a Secret (1979)]

理想方式ではk未満の完全なシェアからSの情報は得られず、無限の計算能力でも同じです。これは適切に選んだ独立係数と定めた観測モデルを前提にします。弱い乱数、係数の再利用、サイドチャネル、追加の検査データは別途分析が必要です。別の手段で推測できる弱い秘密を分散しても強くはなりません。 [Adi Shamir — How to Share a Secret (1979)] [SLIP-0039 — Shamir Secret-Sharing for Mnemonic Codes]

復元には同じ体、値の符号化、インデックス、集合の識別が必要です。素体GF(p)では小数の除算ではなく剰余の逆元を使い、GF(256)の演算はmodulo 256の余り計算と異なります。SLIP-39は具体的な単語リスト、メタデータ、グループ、暗号化、検査を加えます。Shamirと称する二つのソフトでもシェアが互換とは限りません。 [Adi Shamir — How to Share a Secret (1979)] [SLIP-0039 — Shamir Secret-Sharing for Mnemonic Codes]

基本的な補間はシェアの出所や配布者の誠実さを認証しません。壊れた点は不足を知らせるだけでなく別の秘密を返すことがあります。検出、誤り訂正、verifiable secret sharingは独自の前提を持つ追加構成です。例えばSLIP-39はchecksumとdigestを加えますが、すべてのShamir Secret Sharingに自動的に備わるわけではありません。 [SLIP-0039 — Shamir Secret-Sharing for Mnemonic Codes] [NIST — Multi-Party Threshold Cryptography]

通常の復元ではS全体が一つの環境に現れ、漏えいする可能性があります。Multisigと違い、Shamir Secret Sharingは独立した複数のオンチェーン署名鍵を設定しません。NISTが区別するように、閾値署名は追加のMPCプロトコルで鍵を組み立てずシェア上で計算できます。単なる分割と後の結合にはこの性質がありません。 [NIST — Multi-Party Threshold Cryptography]

同じアカウントの5ファイルは紛失や侵害リスクを分離しません。条件を記録し、信頼できる機器で復元を確認します。同じSで新しいランダム多項式を作れば別の集合になり、古いシェアと混ぜるべきではありません。しかし十分な古い集合は引き続きSを復元できます。再分散だけでは既に得られたシェアや漏えいした秘密は無効になりません。 [Adi Shamir — How to Share a Secret (1979)] [Trezor — Multi-share Backup]