破壞 CDH 也會破壞 DHI
我試圖證明，通過打破計算 Diffie-Hellmann (CDH) 假設，也打破了Diffie-Hellmann 逆假設。不幸的是，我有點卡住了，不知道該去哪裡。我懷疑來自配對組的雙線性屬性由 $ PGGen $ 有錯，但我不太清楚如何進一步解決這個問題。定義如下。
使用由 PPT advarsery A 定義的計算 Diffie-Hellman (CDH)，其中： $ Adv^{cdh}_{PGGen,A}(n) $ 可以忽略不計，並且：
$ Adv^{cdh}_{PGGen,A}(n) := Pr[Z = g^{xy} \mid PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x, g^y)] $
以及由 PPT 對手 A 定義的 Diffie-Hellmann 逆假設 (DHI)，其中： $ Adv^{q-dhi}_{PGGen,A}(n) $ 可以忽略不計，並且：
$ Adv^{q-dhi}_{PGGen,A}(n) := Pr[Z = g^{1/x} \mid PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x)] $
任何和所有的幫助將不勝感激。
如果你能打破 CDH，這意味著你可以有效地創建所有 $ g^{x^u} $ 對所有人 $ i $ 通過將快速求冪與 CDH oracle 相結合，可以得到肯定的結果。
$$ g^{1/x} = \begin{cases} EXP(G’,u) = g & \text{if } u=0 \ EXP(CDH(G’),u/2) & \text{if } u \text{ is even}\ CDH(G’, EXP(G’,u-1)) & \text{if } u \text{ is odd}
\end{cases} $$然後，我們可以計算 $ g^{x^{p-2}}= g^{x^{p-2} \mod p}= g^{x^{p-2}}= g^{\frac{1}{x} \mod p} $ . 然後你可以打破DHI。