ハイブリッド議論（暗号）

暗号学において、ハイブリッド論証は、 2 つの分布が計算上区別できないことを示すために使用される証明手法です。

歴史

ハイブリッド議論の起源は、1982年のアンドリュー・ヤオの論文と、 1983年のシャフィ・ゴールドワッサーとシルヴィオ・ミカリの論文にあります^。[1]

正式な説明

形式的には、2つの分布D ₁とD _{2が計算的に区別できないことを示すために、}ハイブリッド分布 の列D ₁  := H ₀ , H ₁ , ..., H _t =: D ₂を定義することができる。ここで、tはセキュリティパラメータnの多項式である。任意の確率的効率（多項式有限時間）アルゴリズムAの利点を次のように 定義する。

${\displaystyle {\mathsf {Adv}}_{H_{i},H_{i+1}}^{\mathsf {dist}}(\mathbf {A} ):=\left|\Pr[x{\stackrel {\$}{\gets }}H_{i}:\mathbf {A} (x)=1]-\Pr[x{\stackrel {\$}{\gets }}H_{i+1}:\mathbf {A} (x)=1]\right|,}$

ここで、ドル記号 ($) は、分布から要素をランダムにサンプリングすることを示します。

三角不等式より、任意の確率多項式時間アルゴリズムAに対して、

${\displaystyle {\mathsf {Adv}}_{D_{1},D_{2}^{\mathsf {dist}}(\mathbf {A} )\leq \sum _{i=0}^{t-1}{\mathsf {Adv}}_{H_{i},H_{i+1}}^{\mathsf {dist}}(\mathbf {A} ).}$

したがって、 0 ≤ k < t(n)を満たすk st が存在し、

${\displaystyle {\mathsf {Adv}}_{H_{k},H_{k+1}}^{\mathsf {dist}}(\mathbf {A} )\geq {\mathsf {Adv}}_{D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )/t(n).}$

tは多項式有界なので、任意のそのようなアルゴリズムAについて、分布H _iとH _{i +1}の間の任意のiに対して固定された無視できる利点関数ε(n)を持つことを示すことができれば、特に、

${\displaystyle \epsilon (n)\geq {\mathsf {Adv}}_{H_{k},H_{k+1}}^{\mathsf {dist}}(\mathbf {A} )\geq {\mathsf {Adv}}_{D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )/t(n),}$

すると、分布D ₁ = H ₀とD ₂ = H _tを区別する利点も無視できるほど小さくなることがわかります。

アプリケーション

ハイブリッド論証は暗号学で広く用いられています。ハイブリッド論証を用いた簡単な証明には以下のようなものがあります。

• ある乱数生成器の出力の次のビットを効率的に予測できない場合、この生成器は疑似乱数生成器（PRG）と呼ばれます。^[2]
• 1ビット出力のPRGをnビット出力のPRGに安全に拡張することができます。^[3]

参照

• インタラクティブな証明システム
• 普遍的な構成可能性

注記

1. Bellare, Mihir, Phillip Rogaway. 「コードベースのゲームプレイング証明と三重暗号化の安全性」Cryptology ePrint Archive (2004)
2. Dodisのノートの定理1。
3. Passのノートの補題80.5、系81.7。

参考文献

• Dodis, Yevgeniy. 「暗号入門講義5 ノート」(PDF)。2014年12月25日時点のオリジナル(PDF)からのアーカイブ。
• パス、ラファエル。「暗号化講座」（PDF）。
• マーク・フィシュリン。ミッテルバッハ、アルノ。 「ハイブリッド議論の概要」(PDF)。