關於訪問 Diffie Hellman 預言機
認為 $ g $ 是乘法群模素數的生成器 $ p $ .
假設我們知道 $ g^X\bmod p $ 和 $ g^{XY}\bmod p $ 並假設我們可以訪問 Diffie-Hellman 預言機。
我們能找到嗎 $ g^Y\bmod p $ 在多項式時間內？
如果我們知道如何計算 $ g^{X^{-1}}\bmod p $ 然後我們可以使用 oracle 來計算 $ g^Y\bmod P $ .
所以我相信問題減少到計算 $ g^{X^{-1}}\bmod p $ 給出了一個 Diffie-Hellman 預言。
我們配備了一個需要三個輸入的功能 $ \mathrm{CDH}(h,h^a,h^b) $ 返回 $ h^{ab} $ . 我們用輸入呼叫它 $ \mathrm{CDH}(g^x,g,g^{xy}) $ . 如果我們寫 $ a $ 對於殘留模型 $ p-1 $ 這樣 $ ax\equiv 1\pmod{p-1} $ 我們看到，如果我們定義 $ h $ 成為 $ g^x\mod p $ 然後 $ h^a=g^{ax}=g\mod p $ 和 $ h^y=g^{xy}\mod p $ . 因此對於這個選擇 $ h $ 我們有 $ \mathrm{CDH}(g^x,g,g^{xy})=\mathrm{CDH}(h,h^a,h^y)=h^{ay}=g^{axy}=g^y\mod p $ .
有輕微皺紋的時候 $ x $ 不是可逆模式 $ p-1 $ , 因為在這種情況下 $ y $ 不是唯一定義的 $ g^{xy} $ . 準確地說，如果 $ \mathrm{GCD}(x,p-1)=\ell $ 然後所有的值 $ y’=y+k\ell $ 為了 $ k=1,\ldots (p-1)/\ell $ 都會有 $ g^{xy}=g^{xy’}\mod p $ 以便 $ g^{y’} $ 將是任何一個合法的答案 $ y’ $ .
我們的 CDH 預言機可能被定義為不接受 $ g $ 作為第二個論點 $ h=g^x $ 和 $ x $ 有一個共同的因素 $ p-1 $ ， 因為 $ g $ 不在於 $ \langle h\rangle $ . 在這種情況下，我們可以任意取 $ \ell $ 的根 $ g^x $ 和 $ g^{xy} $ 並將它們用作第二個和第三個參數並像以前一樣繼續，但注意多個可能的答案。
順便說一句，如果我們有 Diffie-Hellman 交換的公共值和共享秘密，但不知道生成器（即我們知道 $ g^x $ , $ g^y $ 和 $ g^{xy} $ 但不是 $ g $ )，那麼這樣的預言機可以恢復 $ g $ 自從 $ \mathrm{CDH}(g^{xy},g^x,g^y)=g $ .