Ledger Recoverの利用するシャミア秘密分散とは

2023年5月16日、ハードウェアウォレット最大手のLedger社がリカバリーフレーズを3分割しカストディアン3社で分散保管するバックアップサービス「Ledger Recover」を発表しました。この分割の過程でシャミアの秘密分散という方式が利用されているのですが、今回はこのシャミアの秘密分散という方式について技術解説しようと思います。

その前に、Ledger Recoverは大きく世間の関心事になっておりますので少しだけそのへんに触れようと思います。

このサービスの発表は、Ledger社からすると想定外にネガティブな反応を引き起こしました。自身で保管することが大事だよ、というコンセプトな商品を展開しているところが突如マネージドサービスを発表し、それが本人確認プロセスとセットだということで、ユーザーコミュニティの間で仕組みそのものへの懸念に加え、会社ポリシーへの不信感が高まる結果を招きました。結果、23日にはこのサービスのリリース延期を発表するに至っています。

リリース延期にあたってLedger社CEOのPascal Gauthierはレターの中で、

Ledger Recoverのようなサービスの必要性を心から信じている

とも語っており、引き続きリリースする方向を模索するようです。理解を得られるようオープンソース化への取り組みを加速させ、最初の一歩としてLedger Recoverプロトコルのホワイトペーパーを数日中には公開するとも同社CTOより言及されました。

このサービス発表に関しては様々な憶測や懸念が飛び交っており、ただただ不安を覚える方も多いかとは思いますが、直ちに何かが変わるわけではないです。一ユーザーとしては、何かアクションを起こすにしても少し様子を見て、腹落ちさせてからでもよいかと思います。

シャミアの秘密分散法

Ledger Recoverのホワイトペーパーはまだ公開されていないため技術詳細は憶測の域を出ませんが、シャミアの秘密分散法を利用してリカバリーフレーズを分割していることはLedger自体が言及しているので確度の高い話です。

実は、この技術自体は昨今の暗号資産やセキュリティ製品界隈で大変重宝されており、例えば同じくハードウェアウォレット大手のTrezorにおいてもシャミアバックアップ（Shamir backup）として採用されていたりします。

https://trezor.io/learn/a/what-is-shamir-backup

さてさて、今回はシャミアの秘密分散法がなんでそんなに重宝されているのかを技術面を理解することで探ってみましょう。

シャミアの秘密分散法

名前にある通り、この技術はRSAの"S"こと、Adi Shamirにより1979年に提唱されました。また、同時期にGeorge Blakleyも独立して同じ概念を提唱していたようです。

秘密分散とは、シークレット（秘密にしたいデータ）を何らかのグループのメンバーに分散させる手法の総称です。各メンバーにはシェア（シークレットを分割したデータ片）がそれぞれ渡されます。シェアはメンバー数分生成され、個々のシェアからは元のシークレットについて何もわからないという特徴があります。そして、十分な数のシェアを集めると元のシークレットを復元できます。

シークレットをn個に分割し、k個以上のシェアが集まったら復元出来る、という場合、(k,n)-しきい値秘密分散法といったりします。また、k-1個以下を集めてもシークレットを復元することはできません。

まとめると、(k,n)-しきい値秘密分散は次の性質を持ちます。

• シークレットをn個のシェアに分割する
• シェアをk個集めればシークレットを復元できる
• k-1個以下を集めてもシークレットは復元できない

シャミアの秘密分散法はこのような(k,n)-しきい値秘密分散を効率良く実現できる方式です。

シャミアはこれを高次多項式を用いて実現しました。高次多項式とは、高校生で習う2次関数、3次関数といったやつです。例えば、1次多項式はf(x) = 2x + 1といったやつで、横軸にx、縦軸にf(x)の値をプロットすると直線になります。また、2次多項式はf(x) = x^2 +3 といったもの（^は乗算）で、同様にプロットすると山や谷が1つだけある曲線になります。

t次多項式はt+1個の点を通る曲線として一意に定まります。つまり、

• 2点を通る1次式は1つに定まる
• 3点を通る2次式は1つに定まる
• 4点を通る3次式は1つに定まる

...

• t+1点を通るt次式は1つに定まる

といったかんじです。この性質を用いると、多項式の通る点をシェアと考えることで、y切片f(0)の値をシークレットとして取り出すことができます。

例えば、上図では2次式を描いています。この2次式は、緑色の3点（3つのシェア）を通るように描くと1つに定まります。y切片の青の点の値がシークレットとなります。つまり、この2次式は(3,3)-しきい値秘密分散に応用できます。

この曲線上に緑の点を余分に取れば、(3,4)-しきい値といったものも構成できますね。

以上より、例えばリカバリーフレーズを3分割して2つ揃えば復元できるようにしたい、という場合を考えてみると、次の構成を利用できそうです。

• リカバリーフレーズを128ビット（或いは256ビット）の情報量を持つシークレットとする（とてもでかい数です）
• 3分割したいのでn=3とする
• 2つ揃えば復元できるようにしたいのでk=2とする
• k=2より、1次多項式を用いる

安全性

暗号技術の安全性は大雑把に分類分けすると、

• 情報理論的安全性
• 計算量理論的安全性

の2つのクラスがあります。前者は、いくら高速な計算機が登場して総当たり攻撃を行ったとしても元のシークレットを復元できないものであり、後者はそうした計算機で復元できるものです。前者の情報理論的に安全なものが理想に思えますが、計算効率であったりストレージ効率が悪くなる場合が多いので、現実的には後者に属する暗号技術もたくさん実利用されています。

シャミアの秘密分散法は情報理論的安全性を持ちます。

実用性

シャミアの秘密分散法は情報理論的安全性を持ちますが、その対価としてシークレットとシェア1つ1つが同じサイズになってしまいます。つまり、例えば(8,10)-しきい値秘密分散を行うと、元のシークレットの10倍のサイズのデータを（分散するとはいえ）保管する必要があります。リカバリーフレーズを10分割すると、ぐちゃぐちゃなリカバリーフレーズが10個できるイメージですね。

まあ、リカバリーフレーズくらいの小ささのデータであればそんなに問題にはならないかと思いますが、これが動画データとかになるとストレージ容量が気になりそうです。

まとめ

本日はLedger RecoveryやTrezorのShamir Backupが利用するシャミアの秘密分散法について紹介しました。

高校生で習うような数学で実現できる点は面白いですね。もっとも実利用するのにあたってはとても大きな値を扱う必要があるため、少し実装上の工夫は必要です。

より掘り下げて勉強したい方はWikipediaのサンプルコードであったり、各種オープンソースの実装を眺めて見るとよいかもしれません。

また、今回調べてみて少し意外だったのですが、ちゃんとセキュリティ監査の入っている高品質なオープンソース実装はほとんどないようです。そうしたものを公開すると大変な人気になるかもですね。