分散鍵生成(DKG)とは何か?
What is distributed Key Generation (DKG)? (stoffelmpc.com)
要約
分散鍵生成(DKG)は、マルチパーティ計算(MPC)の応用例として、単一の信頼できる第三者なしに共有秘密鍵を生成する手法です。各参加者が自身の乱数の一部を秘密分散し、それらを合計することで、誰も秘密鍵全体を保持することなく、秘密鍵の生成を分散して行うことができます。この技術は、仮想通貨ウォレットの生成や、MPCプロトコルにおけるディーラーの代替などに利用されます。
全文翻訳
分散鍵生成(DKG)とは何か?
過去の記事では、どのようにしてシェアを作成し、それらのシェアを使って算術演算を行うかを説明してきました。具体的な例を通して、MPCの基本をどのようにニーズに合わせて活用できるか、感覚を掴んでいただけたかと思います。しかし、まだ非常に抽象的に感じられるかもしれません。そこで、解決策があり、MPCの実際のユースケースである分散鍵生成(DKG)を紹介するのに良い時期です。この記事では、非常にシンプルでナイーブなDKGプロトコルを解説します。
あなたとあなたの友人たちが、仮想通貨ウォレット(あるいはGitHubのSSHキーでも同じ考え方です)を共有したいとしましょう。しかし、仲間たちが集まって鍵を生成し、それをシェアに分割することができません。そこで、鍵全体を単一の個人が保持することなく共有鍵を生成する方法が必要になります。友人グループの一定数が鍵を再構築できれば良いのです。
このシナリオは、現実世界の多くのユースケースを模倣しています。分散鍵生成は以下のような場合に役立ちます。
- プライベートキー全体を単一の場所に置くことなく、新しい仮想通貨ウォレットを生成する
- 基盤となる秘密を変更せずに、秘密共有された秘密のシェアを変更する(シェアのリフレッシュとして知られる)
- MPCプロトコルにおけるディーラーを置き換える
この記事の目的のため、公開/秘密鍵暗号システムに見られるような鍵にのみ焦点を当てます。しかし、ここで説明する概念は、鍵ではないあらゆる基盤となる秘密に適用できます。
より形式的には、rをℤ内のランダムな整数、Gを何らかのジェネレータとして、鍵 ← rG を計算したいと考えています。具体的には、MPCでは実際に [r]G を計算したいのです。もし以前の記事を読んでいれば、これを行うのに十分な知識があります。
根本的には、単に [r] を生成しているのです。Gは既知のスカラー要素なので、[r]G は公開定数によるスカラー乗算にすぎません。したがって、[r] を取得する方法を示すことができれば十分です。
具体的に、プロトコルは次のように機能します。
- 各パーティは、ローカルマシン上のTRNGや/dev/urandomを使用して、自身の乱数 rᵢ を生成します。
- 彼らは rᵢ を他のパーティに秘密共有して [rᵢ] を取得します。つまり、パーティ i は自身の rᵢ と、パーティ j(i と異なる)の他のパーティからの [rⱼ] を持ちます。
- [r] を取得するために、各パーティは Σ[rᵢ] を計算します。加算は秘密シェア上で線形であるため、この合計にはパーティ間の通信は必要ありません。
- その後、各パーティは自身で [r]G を計算できます。
これで、鍵が分散方式で生成されました。
[画像: 分散鍵生成の概念図]
具体例を見てみましょう。3つのパーティと閾値2で ℤ₁₇ で作業します。つまり、全員が次数1の多項式で共有します。
- パーティ1は r₁ = 5 を選び、多項式 f₁(x) = 5 + 3x を使います。シェア: f₁(1) = 8, f₁(2) = 11, f₁(3) = 14
- パーティ2は r₂ = 11 を選び、多項式 f₂(x) = 11 + 7x を使います。シェア: f₂(1) = 1, f₂(2) = 8, f₂(3) = 15
- パーティ3は r₃ = 9 を選び、多項式 f₃(x) = 9 + 2x を使います。シェア: f₃(1) = 11, f₃(2) = 13, f₃(3) = 15
各パーティは受け取ったシェアを合計します。
- パーティ1: 8 + 1 + 11 = 20 = 3 (mod 17)
- パーティ2: 11 + 8 + 13 = 32 = 15 (mod 17)
- パーティ3: 14 + 15 + 15 = 44 = 10 (mod 17)
これらは、定数項が r = 5 + 11 + 9 = 25 = 8 (mod 17) である f(x) = 8 + 12x のシェアに他なりません。任意の2つのパーティが補間して r = 8 を復元でき、各パーティは自身のシェアに G を掛けて公開鍵 rG を共同で導出できます。r を見た人は誰もいません。
このプロトコルについて、いくつかの点に注意してください。
- シェアの送信以外のパーティ間の通信は不要です
- 同期ネットワークを前提としています
- 全てのパーティが半数誠実(semi-honest)であることを前提としています
実際には、ネットワークは複雑で予測不可能です。当社の非同期DKGソリューションは、ネットワークが非同期であり、パーティが悪意を持つ可能性のある状況に対応します。デモをスケジュールすることで、秘密を分散させましょう。