本稿について
本稿では、DFINITY White Paper：Consensus Systemのうち第7章「DECENTRALIZED RANDOMNESS BEACON」の7.1「Background on Threshold Cryptography」の日本語訳を掲載します。
本章は数学的な表記が多く、やや表記に慣れていないと読み解くのが難しくなっています。しかし、単に文中に注を入れていくと冗長になるため、節が終わるごとに数学的表記を噛み砕いて平易な文章（緑字）に直した注記をまとめて入れるようにします。
原文はこちらになります。
スポンサードサーチ
7 非中央集権型ランダムビーコン
「非中央集権型のランダムビーコンプロトコル（decentralized random beacon protocol, DRB）」は、レプリカがVRFに合意し、各ラウンドでVRFの出力を1つ連帯して生成できるようする。VRFにより、決定論的な擬似乱数配列(ξr)r≥0にコミットメントしようとする。このような各アウトプットξrはそれより前のアウトプットξ0, ..., ξr-1が明らかになっているときでも予測不能であり、かつコミットメントに異議のある人は誰でも正当性について検証可能である。特に、VRFのアウトプットは決定論的な擬似乱数の性質のおかげでバイアスがかかりえない。DFINITYの非中央集権型プロトコルにおいては、少なくとも1つの誠実なレプリカがラウンドrに進む前に攻撃者がアウトプットξrを予測することはできない。
脅威モデルに関連して、第4章の2の仮定2で定めたように、全ての群について（4.2）を仮定した。説明を簡単にするため、|G| = nかつn > 2ƒ(G)であるような1つの群Gに関するランダムビーコンについて述べる。それから、第8章の1で述べるように、このプロトコルは変化していく群が実行する場合にも適合させることができる。
DRBプロトコルは、群Gがランダム性のソースとして生成するユニークなt-of-n閾値署名を用いる（第7章1を参照）。攻撃者は、ƒ ≤ t - 1であればこのような署名の結果を予測することができず、ƒ ≤ n - tであれば署名の生成を止めることができない。もし攻撃者が署名生成の妨害によりプロトコルをアボートできるならば、リスタートまたはフォールバックメカニズムにより不可避的にアウトプットの配列にバイアスが入り込んでしまう。8DFINITYでは、この2つの問題（つまり、署名結果の予測とプロトコルのアボート）を等価に扱う。従って、t ∈ [ƒ + 1,n − ƒ]であることが必要である。n = 2t - 1と置けばどちらの条件もƒ ≤ t - 1に等しいことに注目されたい。
DRBプロトコルで使う閾値署名スキームは分散型鍵生成メカニズム（第7章1の4を参照）を利用してセットアップされる。分散型鍵生成は信頼できる何者にも依存しない。それではまず、利用する閾値暗号理論についてのバックグラウンド情報を教えることから始めよう。
（脚注8）
既存のいくつかの提案は、単一パーティがプロトコルをアボートするせいで文字通りバイアスの影響を受けやすい。例えばAlgorand[8, 第5章2]はバイアスが入り込んでしまうのを避けられないフォールバックメカニズムについて説明している。RANDAO[1]はゲーム理論のインセンティブに基づいて悪意あるアクターがプロトコルをアボートするのを防いでいる。しかしながら実際のところ、悪意あるアクターがランダム性にバイアスをかけることで得られる利得は無制限であるのに対し、アボートによるペナルティは有限である。
（筆者注）
- （4.2）を仮定した ⇒ n > 2ƒ(G)を仮定した。DFINITYホワイトペーパー日本語訳4を参照されたい。
- t-of-n閾値署名、(t, n)閾値署名とは、n個のパーティのうちt個のパーティのシェアを必要とする（＝つまり、tが有効であるための閾値である）ような署名。
- シェアについては後ほどシェアというワードが出てくるのでそこで簡単に解説。
- ƒ ≤ t - 1であればこのような署名の結果を予測することができず
- ビザンチンな参加者（＝攻撃する可能性のある者, 攻撃者）の数が閾値tより小さければ、ビザンチンな参加者のみで署名を生成できない。従って、署名の生成には必ず誠実なレプリカの協力が必要となるので、ビザンチンなレプリカ側だけで署名の結果を予測することはできない。
- ƒ ≤ n - tであれば署名の生成を止めることができない
- 式変形をしてt ≤ n - ƒとするとわかりやすい。群のレプリカの総数からビザンチンなレプリカを全部排除しても閾値tよりも多くのレプリカ（誠実なレプリカ）が残っており署名を生成できる（＝すなわちビザンチンなレプリカを無視しても署名を作成できる）ので、ビザンチンなレプリカ側から見れば署名の生成を止めることができない。
- t ∈ [ƒ + 1,n − ƒ]であることが必要 ⇒ ƒ + 1以上でn − ƒ以下を満たすtであることが必要
7.1 閾値暗号理論のバックグラウンド
7.1.1 閾値署名（Threshold Signatures）
(t, n)閾値署名スキームでは、n個のパーティが連帯して「群の公開鍵（group public key）」をセットアップしつつ各パーティは個々の秘密「秘密鍵のシェア（secret key share）」を保有する。セットアップ後、n個のうちのt個のパーティがいれば、群の公開鍵を検証する「群の署名（group signature）」を生成するには必要十分である。
（筆者注）
- シェアとは分散情報のことと考えると分かりやすい。秘密鍵のシェアとは、秘密鍵の分散情報、つまり秘密鍵の断片のようなものとイメージするとよい。(t, n)閾値署名スキームは、n個の断片のうちt個の断片を集めれば署名できる、ということである。
7.1.2 ノンインタラクティ性（Non-interactiveness）
群の署名の生成プロセスが1ラウンドだけに関係するものであり、そのラウンドに参加するt個のパーティ全員が一方向のコミュニケーションをするとき、閾値署名スキームは「ノンインタラクティブである（non-interactive）」という。基本的にノンインタラクティブなスキームでは、参加パーティはそれぞれが持つ個々の秘密を使って署名シェアを生成し、サードパーティにその署名シェアを送信する。サードパーティがt個の有効なシェアを受け取ると、それ以上のインタラクションをせずに群の署名を復元できる。例えば、ECDSAは閾値署名スキームに変形することはできても（[6]）、ノンインタラクティブな特性は持たない。
（筆者注）
- ECDSAはElliptic Curve Digital Signature Algorithm。楕円曲線デジタル署名アルゴリズム。
7.1.3 ユニーク性（唯一性）（uniqueness）
全てのメッセージと全ての公開鍵について正しく検証する署名がただ一つだけあるとき、その署名スキームは「ユニークである（unique）」という。この特性は単一署名スキームに適用でき、それと似ている閾値署名システムにも用いることができる。しかし閾値スキームの設定においては、さらなる要件がある。すなわち、その署名は、署名の生成に参加したt個のパーティから作られる部分集合に依存してはならないというものである。換言すれば、ユニークな閾値署名スキームでは、誰が署名するかに関わらず、最終的に得られる群の署名は常に同じにならなければならない。
「ユニークであること」は「決定論的であること」よりも限定的で制約の強い特性である。「ユニークであること」は検証関数の特性であるのに対して「決定論的であること」は署名関数の特性であることに注目してほしい。ユニークであることは暗黙的に決定論的であることを指すが、その逆は成り立たない。例えばDSAやECDSAは、いわゆる「乱数k（random k-value）」をランダムに選ぶのではなくメッセージ＋秘密鍵から暗号ハッシュ関数を介して決定論的に導くように署名関数を再定義することで決定論的なものにすることができる。しかし、この手法を使ってもDSAやECDSAをユニークなものにすることはできない。なぜなら、この手法は乱数kを検証関数にさらすことができないからである。
7.1.4 分散型鍵生成（Distributed Key Generation, DKG）
所与の(t, n)閾値署名スキームについて、DKGプロトコルはn個のパーティからなる集合が信頼できるサードパーティの手を借りることなく共同で閾値署名スキームに必要な鍵を生成できるようにする。
DKGプロトコルは秘密分散プロトコルを超えるものである点に注目してほしい。秘密分散プロトコルでは秘密シェアを使って群の秘密を復元することができるが、これは一度しかできない。全員が群の秘密を知った後は、秘密シェアを再利用することはできない。DKGプロトコルでは群の秘密鍵を明示的に復元することさえせずに無数の群の署名について繰り返し秘密シェアを使うことができる。
DKGプロトコルは離散対数に基づく暗号システムに対して比較的単純で、基本的には検証可能な秘密分散プロトコル（verifiable secret sharing protocol, VSS）の複数のインスタンスを利用する。DFINITYでは、[7]で述べるように「Joint-Feldman DKG」9を用いる。
（脚注9）
- [6]から攻撃者はJoint-Feldman DKGにより生成される公開鍵の分布にバイアスをかけることが可能だということが知られている。だが、一般に個のバイアスは生成された公開鍵に関する離散対数問題の強度を弱めるものではない（[6, 第5章]）。そのため、Joint-Feldman DKGの変形版がバイアスを避けうるものであったとしても、DFINITYのプロトコルの単純化を考慮してオリジナルの変更を加えていないJoint-Feldman DKGを使用する。
（DFINITYホワイトペーパー日本語訳9 ←← 前）｜（次 →→ DFINITYホワイトペーパー日本語訳11）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。