離散対数に対する特定の攻撃の強化
私は次の主張を証明しようとしています:
しましょう $(G,*)$ サイズの巡回群である $m$ 発電機付き $g$。敵がいると仮定します$A'$ サイズの $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$、 いくつかのための $T$、 そのような $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ 敵が存在することを示す $A$ サイズの $T$ そのような $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ 乗算を仮定します $G$ が必要 $O(1)$ 回路。
この主張をどのように証明できますか?直感的に、以来$A$ より大きい $A'$ 約で $O(\log m)$、構築は、二分探索の場合のように、問題を再帰的に半分に分割することに基づいている必要があります。しかし、私はそれを行うための賢い方法を考えることはできません...
回答
より強力な保証があったとします。 $A'$ はランダム化されたアルゴリズムであり、 $b$、 $\Pr[A'(b) = \log_g b] > 1/2$、アルゴリズムのランダム性について。その場合、あなたは構築します$A$ 実行することによって $A'$ 数回、満足するものが得られるまで各出力をチェックします $g^{A'(b)} = b$。
ここで、保証が $\Pr_b[A'(b) = \log_g b] > 1/2$。どういうわけか「独立したサンプル」を取得したい$A'(b)$。ランダム化された自己還元性を使用してそれを達成できます。それはあなたの運動なので、私はあなたにそれを記入させます。結果のアルゴリズムはランダム化されますが、最適なランダム性を選択することにより、同じ保証を持つ決定論的(ただし不均一)なアルゴリズムが得られます。