CDH求解器算法建構

如果 $ A $ 是一種解決計算 Diffie-Hellman 問題的有效算法 $ \frac{1}{2} $ 輸入並返回其餘的特殊符號，我該如何使用 $ A $ 構造另一個算法 B 解決 $ CDH $ 有更高的機率（ $ 1 -\frac{1}{2^k} $ ) ?

認為 $ C_k: (g, g^a, g^b) \mapsto g^{ab} $ 是您的 CDH 求解器，它以機率求解 $ 1 - \frac{1}{2^k} $ 否則特殊符號。讓我們從 $ C_1 $ 遞歸地。

的建設 $ C_{k+1} $ :

1. 計算 $ C_k(g, g^a, g^b) $ . 如果它返回 $ g^{ab} $ ，輸出它（這個機率是 $ 1 - \frac{1}{2^k} $ ）。否則，進行第二步。
2. 生成兩個獨立的隨機數 $ x $ 和 $ y $ 從 1 到 $ p-1 $ .
3. 計算 $ g^{ax} $ 和 $ g^{by} $ . 請注意，它們獨立於 $ g^a $ 和 $ g^b $ .
4. 計算 $ C_1(g, g^{ax}, g^{by}) $ . 如果它返回特殊符號，則輸出它（它的機率是 $ \frac{1}{2^{k+1}} $ ）。否則已經計算 $ g^{abxy} $ . 轉到第五步。
5. 使用擴展歐幾里得算法求 $ z $ , 這樣 $ xyz \equiv 1 (\mod p-1) $ .
6. 計算 $ g^{abxyz} = g^{ab} $ 並輸出它（它的機率是 $ \frac{1}{2^{k+1}} $ ).

不難看出，輸出的總機率 $ g^{ab} $ 是 $ 1 - \frac{1}{2^k} $ 現在。

引用自：https://crypto.stackexchange.com/questions/92122