ssss: Shamir’s Secret Sharing Scheme

--

Ethereumでmultisig実装をリサーチするにあたり、シャミアの秘密分散法というものを調査する機会がありましたので、今回は シャミア秘密分散法(ssss: Shamir’s Secret Sharing Scheme)について、その調査した結果を書いていきたいと思います。また、シャミア秘密分散法に触れる前に、秘密分散法(sss: Secret Sharing Scheme)について説明します。

1. 秘密分散法 とは?

(sss: Secret Sharing Scheme)

秘密情報を分散管理するための方法としてAdi Shamir氏とGeorge Blakley氏によって1979 年に考案された暗号化アルゴリズムになります、秘密分散管理のアルゴリズムはいくつか提案されており、代表的なのは下記の3つ

* シャミア秘密分散法 (ssss: Shamir’s Secret Sharing Scheme)* 視覚復号秘密分散法(vsss: Visual Secret Sharing Scheme)* 聴覚複合型秘密分散法 (asss: Audio Secret Sharing Scheme)

これらは扱うデータフォーマットが違うだけで、全て秘密分散法に基づいて設計(閾値法)されています。

秘密分散法を端的にいうと、一つの情報を分散し,定まった集合のみから秘密情報が復元できる暗号技術のことをいいます。

例えば、 一つの情報をt個に分散しs個を集めると復元できる、といったもので、この考え方を閾値法(t/s) とも言います。また、tsの関係はt>sであり、これは、Seed値の分散管理などに利用するといった記事をよく見かけます、bip-0011 Multisigのプロトコルにそっくりですね。

また、余談ではありますがAdi Shamir氏とは、Ethereum関連でよく聞くプロトコル『zk-SNARK』で利用されている暗号化技術 ゼロ知識証明(zero-knowledge proof)の提案者でもあります。

2. シャミア秘密分散法とは?

(ssss: Shamir’s Secret Sharing Scheme)

考えかたそのものは、それほど難しいものではなく、上述したとおり閾値法に基づき秘密情報を分割し、ある一定の分割情報が集めれば、復元できるアルゴリズムのこと。

例を挙げると、家族構成 お父さん、お母さん、子供二人の家族で保管してる金庫があり、その金庫にはお父さんが持っている資産が全て保管されている状態をイメージしてください。

その金庫を開けるためのパスワードが必要だとして、そのパスワードをお父さん、お母さん、そして、子供二人に秘密分散法に基づき閾値3で分散します。

数年後、お父さんが不慮の事故でお亡くなりにりました。家族の一人が金庫の資産を盗もうとしても、一人では金庫は開けられません。閾値が3なので、家族のうち3人が集まらないと金庫が開けられないのです。

また、逆のリスクもあります。家族4人のうち2名が行方不明になった場合、分散されたその他2つの情報からでは金庫が開けられません。これは、リスクと利便性のバランスの難しさでもあります。

3. それでは、実際に検証してみましょう

以下はシャミア秘密分散法のデモができるサイトです。

: 各パラメータの設定

パラメータの説明
* Threshold = t/sの閾値法のt(分子)
* shares = t/sの閾値法のs(分母)
* Secret = 秘密情報
パラメータの設定値
* Threshold = 3
* shares = 4
* Secret = 1234567890

: 分散結果

1-eca9cd900953b3bf64e7
2-3c1ee46e0bd7d118b814
3-b554286c81202bde2cfe
4-fbb93d8de532ce0aed10

上記分散情報のうち1〜3を選択し、複合すると…

: 復号結果

復元できまきましたね! また、ご覧のとおりbtc, bch, ethの3コインであればサイト作成者へ寄付できそうです。よろしければ是非

これをLinux上で実装するためのライブラリーも作られているようです。http://point-at-infinity.org/ssss/

次回は、Golangを利用した実装例を書きたいと思います。

--

--