逆離散對數問題
讓[Math Processing Error] $ \mathbb G $ 是一個循環的有序群[Math Processing Error] $ q $ . 給定離散對數問題 (DLP)[Math Processing Error] $ g, g^x \in \mathbb G $ ， 計算[Math Processing Error] $ x \in \mathbb Z_q $ .
我很想知道是否存在如下已知的 DLP 變體：
給定[Math Processing Error] $ g, g^x, g^{x^{-1}\bmod q} \in \mathbb G $ , 計算[Math Processing Error] $ x \in \mathbb Z_q $
很明顯，這個變體不會比 DLP 更難，因為可以使用 DLP 求解器來解決這個問題，只需忽略第三個輸入。
這個問題似乎等同於[Math Processing Error] $ k $ -強離散對數問題。
讓[Math Processing Error] $ \mathbb G $ 是一個循環的有序群[Math Processing Error] $ q $ . 這[Math Processing Error] $ k $ -強離散對數問題（[Math Processing Error] $ k $ -DLP) 是，給定[Math Processing Error] $ h, h^x, h^{x^2}, .., h^{x^k} \in \mathbb G $ ， 計算[Math Processing Error] $ x \in \mathbb Z_q $ . 對變數進行簡單的更改 ( $ h^x = g $ )，得到問題的等價版本，如下所示：
給定[Math Processing Error] $ g^{x^{-1}\bmod q}, g, g^x, …, g^{x^{k-1}} \in \mathbb G $ , 計算[Math Processing Error] $ x \in \mathbb Z_q $
可以看出，問題中的問題是 $ k=2 $ .
這[Math Processing Error] $ k $ -例如，Goyal、O’Neill 和 Rao在Correlated-Input Secure Hash Functions中討論了強離散對數問題。