命題(DLinear)の証明 - 暗号理論教室

命題(DLinear)の証明のアイデア

• DHタプル： (g, g^x, g^y, g^xy)
• 線形タプル： (g₁, g₂, z, g₁^r1, g₂^r2, z^r1+r2)

命題(DLinear)の証明

判定線形問題を解くアルゴリズムAを仮定し判定DH問題を解くアルゴリズムBを構成する：

アルゴリズムB: (g, g^x, g^y, g^z)を入力として、

• r, r' ← Z_q
• (g, g^x, g^r, g^y, (g^z)^r', (g^y)^r(1+r'))を入力としてアルゴリズムAを実行する。
• Aの出力を自身の出力として終了する。

(g, g^x, g^r, g^y, (g^z)^r', (g^y)^r(1+r'))が線形組
⇔ (g^y)^r(1+r') = (g^r)^{y + zr'/x}
⇔ y(1+r') = y + zr'/x
⇔ y = z/x
Q.E.D.

上へ

---