正式表明 DDH 硬度意味著 CDH 硬度
作為作業問題的一部分，我需要證明 DDH 硬度意味著 CDH 硬度。
認為 $ CDH $ 相對於某些組生成器來說很難。
直覺很清楚，所以我做了微不足道的簡化 - 讓 $ A_{CDH} $ 是一個 PPT 算法，計算 $ DH_g(h_1,h_2) $ 有機率 $ \epsilon $ ， 定義 $ A_{DDH} $ 如下：
1）給定 $ g^x $ , $ g^y $ 和 $ g^z $ , 返回 1 iff $ A_{CDH}(g^x,g^y)=g^z $
現在我看：
$ Pr[A_{DDH}(g^x,g^y,g^z) = 1] $ （隱含地給出組描述）
其中機率被接管 x、y 和 z 的獨立選擇。( $ D_G $ 是組的描述，一個生成器 $ g $ , 及其大小 $ q $ )
我想用以下形式表達上述機率 $ A_{CDH} $ ，所以我寫了：
$ Pr[A_{DDH}(g^x,g^y,g^z) = 1]=Pr[A_{CDH}(g^x,g^y) = g^z] $
但是我該如何分析呢？如果 $ g^{xy} \neq g^z $ 不知道機率 $ A_{CDH}(g^x,g^y) = g^z $ ，我只知道它給出（一些）錯誤答案的機率 $ 1-\epsilon $
如果細節不清楚，請告訴我，我盡量簡潔。提前致謝！
讓我陳述 DDH 的精確定義，以便更清楚地說明：假設一個組是一個生成器 $ g $ 是固定的，挑戰者擲硬幣。如果他得到0，他選擇 $ (x,y,z) $ 均勻隨機；如果他得到 1，他選擇 $ (x,y) $ 隨機均勻地設置 $ z = xy $ . 它返回 $ (g^x,g^y, g^z) $ . 如果你能找出拋硬幣的方式比隨機猜測具有不可忽略的優勢，那麼你就贏得了 DDH 遊戲。現在，你有這個對手 $ A $ 以機率打破 CDH $ \varepsilon $ ，並且您想用它來破壞 DDH。因此，挑戰者擲硬幣並向您發送 DDH 挑戰。
我寫過：
$ Pr[A_{DDH}(g^x,g^y,g^z) = 1]=Pr[A_{CDH}(g^x,g^y) > = g^z] $
但是我該如何分析呢？如果 $ g^{xy} \neq g^z $ 不知道機率 $ A_{CDH}(g^x,g^y) = g^z $ ，我只知道它給出（一些）錯誤答案的機率 $ 1-\epsilon $有兩種情況：要麼挑戰者被選中 $ 1 $ , 所以它認為 $ g^{xy} = g^{z} $ . 與輸入一樣 $ (g^x,g^y) $ , 對手返回 $ g^{xy} $ 有機率 $ \varepsilon $ , 在這種情況下它返回相同的 $ g^z $ 你從挑戰者那裡得到的機率 $ \varepsilon $ . 但如果挑戰者選擇了 $ 0 $ ，那麼根據 DDH 博弈的定義， $ z $ 是隨機均勻挑選的，特別是完全獨立於 $ x $ 和 $ y $ .
所以問題變成了：給定 $ g^x $ 和 $ g^y $ ，無論它如何工作，它有多強大，對手輸出的機會有多大 $ g^z $ ，哪個是敵手*不知道的均勻隨機群元素？*你應該很容易地說服自己答案是一個超過該組的順序 - 一個可以忽略不計的數量。
因此，當硬幣 $ 0 $ , 對手輸出 $ g^z $ 機率可以忽略不計；什麼時候 $ 1 $ , 他輸出 $ g^z $ 有機率 $ \varepsilon $ . 由於硬幣是隨機翻轉的，這兩種情況都完全有機率發生 $ 1/2 $ - 由此，您應該能夠通過回答來衡量您贏得 DDH 遊戲的機率 $ 0 $ 什麼時候 $ A $ 無法輸出 $ g^z $ ， 和 $ 1 $ 當他成功時。