分岐補題

分岐補題は、暗号研究における関連する補題の 1 つです。この補題は、ある分布から抽出された入力に対して、敵対者 (通常は確率的チューリング マシン) が、無視できない確率で何らかの特性を持つ出力を生成する場合、敵対者が新しい入力で同じランダム テープを使用して再実行されると、無視できない確率 で、2 番目の出力にも特性が含まれることを述べています。

この概念は、David PointchevalとJacques SternがEurocrypt 1996の議事録で発表した「署名方式のセキュリティ証明」で初めて使用しました^{。[1] [2]彼らの論文では、}ランダム オラクルモデルでインスタンス化されたデジタル署名方式を 攻撃する敵対者の観点から、分岐補題が指定されています。彼らは、敵対者が無視できない確率で署名を偽造できる場合、同じランダム テープを持つ同じ敵対者が別のランダム オラクルを使用した攻撃で 2 番目の偽造を作成できる可能性も無視できないことを示しています。^{[3]分岐補題は、後に}Mihir Bellareと Gregory Neven によって一般化されました。 ^[4]分岐補題は、さまざまなデジタル署名方式やその他のランダム オラクル ベースの暗号構造のセキュリティを証明するために使用され、さらに一般化されました。^{[2] [5] [6]}

この補題の一般化バージョンは次のように述べられる。^[4] A を確率アルゴリズムとし、入力 ( x , h 1 _, ..., h _q ; r ) から ( J , y )のペアを出力するものとする。ここでr はAのランダムテープ(つまり A が行うランダムな選択) を指す。さらにIGはxが抽出される確率分布であり、H はh _iの各値が均一分布に従って抽出されるサイズhの集合であるとする。acc は、説明のように分布する入力に対して、 Aによって出力されるJ が1 以上になる 確率とする。

次に、入力xに対して次のように進行する「フォークアルゴリズム」 F _{A を}定義できます。

1. Aのランダムなテープr を選択します。
2. Hからh ₁ , ..., h _{q を}一様に選択します。
3. 入力( x , h ₁ , ..., h _q ; r )に対してAを実行し、 ( J , y )を生成します。
4. J = 0の場合は(0, 0, 0) を返します。
5. Hからh' _J、...、 h' _{q を}一様に選択します。
6. 入力( x , h1 ,..., hJ ₋₁ , h'J , ..., h'q ; r )_に対してAを実行し、₍ J ', y ')_を生成します。
7. J' = Jかつh _J ≠ h' _Jの場合は(1, y , y ') を返し、それ以外の場合は (0, 0, 0) を返します。

IGからランダムに選ばれた入力xに対して、 F _Aが1から始まる3つ組を出力する確率をfrkとする。すると、

${\displaystyle {\text{frk}}\geq {\text{acc}}\cdot \left({\frac {\text{acc}}{q}}-{\frac {1}{h}}\right).}$

ここでの考え方は、A が関連する実行で 2 回実行され、入力の一部が検査されたが全部は検査されていない特定の時点でプロセスが「分岐」すると考えることです。代替バージョンでは、残りの入力は再生成されますが、通常の方法で生成されます。プロセスが分岐するポイントは、おそらく最初のAの動作に基づいて、後でのみ決定する必要がある場合があります。これが、補題ステートメントがAの出力に基づいて分岐ポイント ( J ) を選択する理由です。 h _J ≠ h' _Jという要件は、補題の多くの用途で必要な技術的な要件です。( h _Jとh' _{J の}両方がHからランダムに選択されるため、通常のようにhが大きい場合、2 つの値が区別されない確率は非常に小さいことに注意してください。)

たとえば、A をランダム オラクルモデルのデジタル署名スキームを破るアルゴリズムとします。この場合、x はAが攻撃している公開パラメータ (公開鍵を含む) となり、h _{i は}i番目の異なる入力に対するランダム オラクルの出力となります。分岐補題は、同じメッセージの 2 つの異なるランダム署名が与えられれば、何らかの根本的な難問を解くことができる場合に有用です。ただし、一度偽造する攻撃者は、分岐補題により、無視できない確率で同じメッセージを 2 回偽造する攻撃者を生み出します。A がメッセージm を偽造しようとする場合、 Aの出力は( J , y ) とみなします。ここで、 yは偽造であり、J はmがランダム オラクルへのJ番目の一意のクエリであったものです( A が無視できない確率で成功するには、 A がある時点でm をクエリすると想定できます)。 （Aが誤った偽造を出力した場合、出力は（0、y）であるとみなします。）

分岐補題により、同じメッセージで異なるランダムオラクル出力（つまり、h _J ≠ h' _J ）を持つ2 つの優れた偽造yとy' を取得する確率（ frk ）は、 accも無視できない場合は無視できません。これにより、根本的な困難な問題が実際に困難である場合、敵対者は署名を偽造できないことを証明できます。

これは、適応的な敵対者に対する 修正されたElGamal 署名方式について Pointcheval と Stern が示した証明の本質です。

フォーク補題によって提供される還元は厳密ではない。PointchevalとSternはフォーク補題を用いたデジタル署名とブラインド署名のセキュリティ議論を提案した。^[7] Claus P. SchnorrはブラインドSchnorr署名方式に対する攻撃を^[8]提案したが、これは同時実行以上の攻撃である（PointchevalとSternによって研究され、安全であることが証明されたケース）。同時実行に対する多項式時間攻撃は、2020年にBenhamouda、Lepoint、Raykova、およびOrrùによって示された。Schnorrは、離散対数問題に基づくブラインド署名方式のセキュリティ強化も提案した。^[9]${\displaystyle ポリログ(n)}$${\displaystyle \オメガ (n)}$