シャミールの秘密分散法の仕組み

13時間前原文(ente.com)

概要

重要な秘密 を複数人で管理する必要性
Shamir's Secret Sharing による秘密分割の原理
閾値k で秘密を守る数学的仕組み
実用例 としてEnteのLegacy Kitでの応用
追加資料や参考文献の紹介

1人では守れない秘密の分割と共有

1人だけに秘密を託すリスク 回避のための分割管理
- 例：会社のマスターキー利用に 3人の役員 が必要
- 例：家族のアカウント復旧に 複数封筒 を要求
- 例：チームで 誰かが欠けても復元可能 なバックアップ
Adi Shamir （RSAのS）が1979年に発表した手法
- 秘密を複数の断片 に分割
- 指定数（閾値k）以上 が揃えば復元可能
- 閾値未満 では 一切情報が漏れない
「解読が難しい」ではなく、「 全く情報が得られない」性質

Shamir's Secret Sharingの基本原理

2点が直線を決定 する数学的性質
- 1点だけでは 無限に多くの直線 が通り、秘密は特定不能
- 例：秘密を y軸との交点 （例：7）に設定
  - ランダムな傾きで直線を描き、各人に 直線上の1点 を配布
  - 1点だけでは 全ての秘密が可能性として残る
  - 2点が揃うと 直線が一意に決定 し、秘密が復元可能
2-of-n方式 （n人中2人の協力で復元可能）

閾値を増やす場合の仕組み

3人必要なら 「放物線」（2次式）、 4人なら 「三次式」
- k人必要 なら 次数k-1の多項式 を利用
  - 2人→直線
  - 3人→放物線
  - 4人→三次曲線
実装では有限体演算 （整数の世界で計算）を使用
- 秘密は「 多項式の定数項（x=0の値）」
- ランダムな係数 が秘密を隠す役割
- 各人の断片は「 多項式上の1点（x, y）」
閾値未満では 「全ての秘密が等確率であり得る」ため 絶対に情報が漏れない

応用例：EnteのLegacy Kit

Ente ではShamir's Secret Sharingを 一要素 として活用
- 課題：単に秘密を分割するだけでなく、「 復旧時に断片が直接復旧キーにならない」仕組み
- Legacy Kitでは カードが復旧キーを保持しない
  - カードで 一時的な秘密 を復元し、その後 サーバー経由で復旧
  - カードの無効化や紛失時の安全性 を確保

参考文献・さらなる学び

Adi Shamir 「How to Share a Secret」
Bruce Schneier 「Sharing Secrets Among Friends」
Max Levchin のPayPalでの事例
Ente のソースコード

Hackerたちの意見

ここにEnteの実装があるよ: (https://2of3.ente.com/)

└

ほとんどのLinuxディストリビューション用にパッケージ化された実装があるよ: http://point-at-infinity.org/ssss

└

オンラインで使えるブラウザベースのバージョンがいくつかあるよ、オフラインでもダウンロードして使えるし。https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

これめっちゃクールな技術だね！ポリノミアルを使ってコンピュータサイエンティストができる面白いこととして、中学校で教えることもできるかも。

└

私は中学校の数学の先生で、学生たちとまさにこれをやってるよ。アフィン関数の式を取り出す作業をしている時に、シャミールの話をして、彼らに傾きを秘密のPINとして選ばせて、2つの点を生成させて、その点を他の2人の学生に渡して、ペアになってPINを再度見つけてもらうんだ。学生たちはいつもすごく熱心に取り組んでるよ。

ルートDNSキーを持ってる人たちは、こういうことをやってるのかな？それとも、安全な部屋の金庫が効果的なバックアップになるから、複雑すぎるってこと？

└

似たようなことをやってるよ。基本的に、DNSルートキーにアクセスするには5人が必要で、さらに管理者や証人も必要なんだ。スマートカードでHSMを解除する3人の暗号担当者と、HSMを含む金庫とスマートカードが入った安全金庫を解除する2人の役人が必要。暗号担当者は7人いて、その中の3人がいれば大丈夫だよ。 https://www.cloudflare.com/learning/dns/dnssec/root-signing-...

これはすごい技術だよ。これに出会ったとき、キーを「本当に」渡さずに渡す方法を考えるのが変わったんだ。このおかげで、自分のプロジェクト「eternalvault.app」に自信が持てた。

ブルース・シュナイアが彼の名著『Applied Cryptography』でこれを説明してたし、HashiCorp VaultはGoでの実装もあったよ。実用的な観点から、シェアのサイズはビットでどれくらいがいいのか、ずっと気になってた。ニュースグループで得た答えは「実際のキーの長さより1ビット多い」だった。最近は、量子コンピュータの脅威が1) シェアサイズの選択や2) シークレットシェアリングの利点・欠点にどう影響するのか気になってる。誰か知ってる？

└

HashiCorpはまだ金庫のシール/アンシールプロセスの実装を持ってると思うよ。もちろん、何かが変わったなら別だけど。

└

1ビット多い理由、覚えてる？

└

秘密共有は有限体でやることが多いんだ。コンピュータは実数が苦手だからね。シェアの大きさは点 (x, y) で、xは小さくて（通常は参加者がnの時はlog n）、yはフィールド内のランダムな点だよ。シャミールの秘密共有は情報理論的に安全だから（k点を知らなければ、k-out-of-nの秘密は全て同じくらいあり得るから、ブルートフォースしても無駄）、フィールドのビットサイズは好きな大きさにできる（でも秘密のビットサイズよりは大きくないとダメ、5つの要素の有限体では100ビットは隠せないからね）。通常、攻撃者に秘密をブルートフォースされるのは避けたいから（スキームはITSだけど、秘密はそうじゃないことが多い、例えばウォレットのシードとか）、秘密にランダム性を加えて、フィールドのビットサイズを大きくして攻撃を防ぐんだ。攻撃モデルによっては、80ビットや128ビットのフィールドで十分安全だから、シェアのビットサイズは80ビットか128ビットを少し超えるくらいが理想だね。量子コンピュータに関しては、スキームがITSだから攻撃は存在しないよ。

└

プレーンなシャミールは情報理論的に安全で、量子コンピュータには完全に耐性があるよ。1バイトの秘密を取って、そこから「閾値10」のシャミールシェアを作って、1バイトのシェアを9つ渡しても、宇宙のどんなコンピュータもその秘密を特定できないんだ。（実際には、シャミールシステムは整合性チェックのためにMACやチェックサムを追加する必要があるから、現実ではもう少し大きくなるけどね。）

└

一つのポイントは、全体のシークレットが基礎となるフィールドの一要素である必要はないということです。むしろ、小さいフィールドのn-タプルであることも可能です。GF(2^8)は、シェアの数が極端に多くない場合には、かなり明白な選択肢です。大きな数の計算を扱う必要もありません。

これめっちゃクールなトリックだね！Vibeが秘密を生成したり、多項式を見たり、秘密を組み合わせたり、遊べるちょっとしたプレイグラウンドを作ったみたいだよ。ここで遊べるよ: https://shamirs-secret-sharing.pagey.site

数年前にブラウザでシャミール秘密共有を実行するための小さなツールを作ったんだ（オフラインでもフルに使えるよ、ページをダウンロードするだけでOK）: https://simon-frey.com/s4/

2つの直線から曲線や放物線に行く代わりに、別の次元を追加することもできない？

私たちのチームでは、この技術を使って、セカンダリーのシークレットストア（プライマリーのシークレットストアへのアクセス方法が書かれている）にパスフレーズを「民主的に安全に」配布しています。https://packages.debian.org/trixie/ssss は、シンプルで使いやすい実装です。

私の修士論文はこれについてでした！データを一般的なストレージサービス（Dropbox、Google Drive、OneDriveなど）に保存できるアプリを作成し、暗号化にはシークレットシェアリングを使いました。利点は以下の通りです：

彼らはあなたのデータを読めなくなる
追加の冗長性（2つだけが利用可能であればOK）
マスターパスワードに依存する他のセキュアストレージアプリと比べて、もしパスワードを忘れても、通常のアカウント回復方法が使える

└

いいアイデアですね！製品化したり、オープンソースのアプリを作ったりしましたか？

ハクソク