Discrete-Logarithm
與離散對數問題有關的問題
讓 $ G $ 是一個循環群的生成器，其中離散對數問題很困難，並且 $ x $ 和 $ u $ 是群的標量，使得 $ X = xG $ 和 $ U = uG $ ， 分別。我們要計算 $ J = x^{-1}U $ . 是否可以在不知道的情況下計算它 $ x $ , 即使我們知道 $ u $ ?
這個問題等價於 Computational Diffie Hellman 問題；即使我們知道，這仍然是正確的 $ u $ .
有關詳細資訊，請參閱本文；總之：
- 假設我們有一個預言機，給定 $ G $ , $ X = xG $ 或者（取決於 oracle 類型） $ U = uG $ 或者 $ u $ , 給我們價值 $ J = x^{-1}uG $ . 然後，我們可以使用這個 Oracle 來構造第二個 Oracle，給定 $ H, aH $ , 計算 $ a^2H $ （通過傳遞 $ G = aH $ , $ X = H = a^{-1}G $ , $ U=G $ （或者 $ u=1 $ )，並恢復 $ J = (a^{-1})^{-1} \cdot 1 \cdot aH = a^2H $ . 然後我們可以使用第二個 Oracle 來解決 CDH 問題（給定 $ G, aG, bG $ , 我們計算 $ (2ab)G = (a+b)^2G - a^2G - b^G $ ，然後做一個點減半。
- 假設我們有一個解決 CDH 問題的預言機，即給定 $ H, aH, bH $ , 給我們價值 $ abH $ . 然後，給定 $ G $ , $ xG $ ，我們可以計算 $ x^{-1}G $ 通過設置 $ H = xG $ , $ aH = bH = G = x^{-1}H $ 和 $ bH = H $ . 我們把它交給 Oracle，它給了我們價值 $ (x^{-1} \cdot x^{-1}) H = x^{-1}G $ . 然後，我們可以將該值轉換為 $ J $ 通過將其乘以 $ u $ （如果我們知道的話），或者使用輸入再次呼叫我們的 CDH Oracle $ G, x^{-1}G, uG $ .