離散對數問題還是整數求冪問題？
在閱讀以下論文時，
https://ai2-s2-pdfs.s3.amazonaws.com/35eb/afbaab34223bca50a7be2f5915fddf918fc7.pdf
生成兩個素數 $ p $ 和 $ q $ 這樣 $ q|p-1 $ . 選擇發電機 $ g $ 的 $ Z_p^{*} $ . $ g $ 被宣佈為公開。
$ c_1=g^r $ 在哪裡 $ r \in Z_q^{*} $
據我所理解， $ g $ 是從 0 到 p 的整數。如果還有別的意思 $ Z_p^{*} $ ， 請告訴我。
給定 $ g,c_1 $ ， 尋找 $ r $ .
是離散對數問題嗎？還是只是整數求冪問題？
正如您在他們的摘要中看到的那樣，他們假設“標準的計算 Diffie-Hellman 問題是棘手的”，因此這意味著您可能必須通過解決離散對數問題來打破他們的方案，因為計算 Diffie-Hellman (CDH)如果可以解決 DLP，問題就可以輕鬆解決。
CDH 問題如下： $ G $ 一個循環的秩序群 $ q $ ， 和 $ g $ 它的生成器之一，給定 $ (g,g^a,g^b) $ 和 $ a,b \in {0, \ldots, q-1} $ 隨機選擇，想要計算值 $ g^{ab} $ .
如果計算離散日誌 $ G $ 很容易，那麼 CDH 問題就會得到解決，因為可以計算：
- $ b $ 通過取離散對數 $ g^b $ ;
- $ g^{ab} $ 通過指數： $ g^{ab} = (g^a)^b $
但是，需要注意的是，CDH 和 DLP 問題不一定是等價的！因此，有可能一次解決 CDH 問題而無法解決 DLP，或者也有可能有一天兩者都被證明是等價的，因為 Maurer 已經證明在整數平滑度的某些條件下它是正確的在給定的時間間隔內。
因此，如果您想將他們的方案視為 DLP 的一個實例，您可以，但它可能比 DLP 更簡單。
另一方面，你所陳述的問題，被給予 $ c_1, g $ ， 尋找 $ r $ 為了 $ c_1=g^r \mod p $ 是 DLP 的一個實例。
所以是的，如果 DLP 很簡單，您可以直接反轉他們的公鑰。
$ \mathbb Z_p^* $ 是乘法群模 $ p $ ，即（因為 $ p $ 是素數） $ \mathbb Z_p $ 少元素 $ 0 $ 模組 $ p $ .
問題陳述和論文的 Setup() 過程中暗示或缺失的是 $ g $ 是有序的 $ q $ ; 那是， $ g $ 是這樣的 $ q $ 是最小的正整數 $ j $ 驗證 $ g^j\equiv1\pmod p $ .
發現 $ r $ 給定 $ g $ , $ c_1 $ 是原型離散對數問題。對於隨機參數和足夠大的情況，它被認為是困難的 $ p $ 和 $ q $ （例如，2048 位 $ p $ 和 256 位 $ q $ ).