決策離散對數問題？

是否在某處研究過離散對數問題的決策版本？我的意思是，眾所周知 $ G $ 在一個群體中，區分 $ xG $ 和 $ Y $ 對於未知整數 $ x $ 和組元素 $ Y $ ?

標準離散對數假設要求，給定一組 $ \mathbb{G} $ 有秩序的 $ p $ 帶發電機 $ G $ ， 計算 $ x $ 給定 $ xG $ ， 在哪裡 $ x $ 是隨機的。這意味著 $ {xG : x \gets \mathbb{Z}_p} $ 跨越整個組，所以 $ xG $ 正好是均勻隨機群元素。您不可能希望將其與隨機區分開來，因為它作為隨機組元素完美分佈。

話雖如此，離散對數問題存在“決策變體”：

• 區分 $ xG $ 對於一個隨機的偶數 $ x \gets \mathbb{Z}_p $ 和 $ xG $ 對於隨機奇數 $ x \gets \mathbb{Z}_p $ （偶數和奇數通過查看來定義 $ x $ 作為之間的整數 $ 0 $ 和 $ p-1 $ ）。這個決策問題等價於計算離散對數（證明是一個標準練習，至少當成功機率被假設為 1 時 - 在一般情況下更難）。
• 區分 $ xG $ 來自一個隨機群元素，當 $ x $ 是一個隨機的短元素（例如 $ 0 $ 和 $ 2^k $ 對於一些 $ k $ 與安全參數有關，例如 $ 2^k $ 遠小於 $ p $ ）。這個問題實際上歸結為計算“短指數離散對數假設”，它要求找到 $ x $ 給定 $ xG $ 隨機短 $ x $ （證明在這裡）。

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