定理(Okamoto)の証明 - 暗号理論教室

定理(Okamoto)の証明のアイデア

pk = (q, g₁, g₂, X), sk = (q, g₁, g₂, x₁, x₂)に関する、
岡本プロトコルのトランスクリプトは

• コミットメント (Y), チャレンジ (c), レスポンス (z₁, z₂).

これについて、

• g₁^z1g₂^z2 =^? YX^c

が成り立てば、検証者Vは受理。

コンカレントな攻撃者Aを用いて、
離散対数問題 (q, g₁, g₂) を解くアルゴリズムBを構成できる。
Bは、

• x₁, x₂ ← Z_q, X = g₁^x1g₂^x2

として秘密鍵sk = (q, g₁, g₂, x₁, x₂)を知った状態でシミュレートできることがポイント。

定理(Okamoto)の証明

岡本プロトコルに対する任意のコンカレントな攻撃者をA=(A₁ , A₂)とする。
Aを用いて、GenGに関する離散対数問題アルゴリズムBを構成する：

B: (q, g₁, g₂)を入力として、

• ※ Bは g₂ = g₁^w となるwを求めたい。
• x₁, x₂ ← Z_q, X = g₁^x1g₂^x2
• pk = (q, g₁, g₂, X)を入力として、A₁を起動する。
  • A₁が証明者クローンとのやりとりを要求したら、
    • 秘密鍵sk = (q, g₁, g₂, x₁, x₂)を用いてオネストに対応する。
• A₁の出力stを受け取り、A₂をstを入力として起動する。
• ※ ここで、A₂(st)は決定的としてよい。（stにランダムテープが含まれているとしてよい。）
  • A₂からYを受け取ったら、c ← {0,1}^l を返す。
  • A₂から(z₁,z₂)を受け取ったら、
    • g₁^z1g₂^z2 = YX^c でないならばアボート。
• A₂を再びstを入力として起動する。
  • A₂からYを受け取り、c' ← {0,1}^l を返す。　※ A₂(st)は決定的なので、必ず前と同じY.
  • A₂から(z'₁,z'₂)を受け取ったら、
    • g₁^z'1g₂^z'2 = YX^c' でないならばアボート。
• c = c' ならばアボート。
• (c - c')x₂ = z₂ - z'₂ ならばアボート。
• w = （z₁ - z'₁ - (c - c')x₁）／（(c - c')x₂ - (z₂ - z'₂)） を出力して停止。
  • ※ g₁^z1g₂^z2 =^? YX^c
  • g₁^z'1g₂^z'2 =^? YX^c'
  • よって、
  • g₁^z₁-z'₁g₂^z₂-z'₂ = X^c-c'.
  • X = g₁^x1g₂^x2 より, w = DLog_g1(g₂)とおくと、
  • z₁-z'₁ + w (z₂-z'₂) = (c-c')(x₁ + w x₂)
  • よって、
  • w = （z₁ - z'₁ - (c - c')x₁）／（(c - c')x₂ - (z₂ - z'₂)）.

[Bの解析]:
明らかに、Bがアボートしなければ、その出力wは離散対数問題(q, g₁, g₂)の正しい解。よって、

• Pr[Bが離散対数問題を解く] = Pr[Bがアボートしない].

一方、BのAに対するシミュレーションは完ぺきなので、

• Pr[Bがアボートしない] ≧ Pr[証明者Q=A₂(st)に対し、イベントRESが成立] - Pr[(c - c')x₂ = z₂ - z'₂].

補題(Reset)より

• Pr[RES] ≧ (Pr[Aがなりすましに成功] - 1/2^l)².

また、AのviewはXのみに依存し、x₂とは独立なので、

• Pr[(c - c')x₂ = z₂ - z'₂] ≦ 1/2^l.

以上より、

• Pr[Bが離散対数問題を解く] ≧ (Pr[Aがなりすましに成功] - 1/2^l)² - 1/2^l.

仮定より、

• l はスーパーログなので、1/2^lはネグリジブル。
• Pr[Bが離散対数問題を解く]もネグリジブル。

よって、Pr[Aがなりすましに成功]もネグリジブル。（ただし、ネグリジブルの「度合い」は半分。）

Q.E.D.

上へ

---