通用組黑盒模型是否禁止離散對數的 MSB？

黑盒通用模型禁止計算有序組中的離散對數 $ q=2p+1 $ 在哪裡 $ p,q $ 是隨機素數 $ \Omega(\sqrt{p}) $ 步驟（請參閱通用組模型中的離散對數很難 - Shoup 定理）。

黑盒通用模型是否也禁止離散對數的 MSB $ \Omega(\sqrt{p}) $ 步驟或者是否有可能黑盒通用算法可以獲得離散對數的 MSB $ polylog(p) $ 腳步？

請注意，一旦您知道 MSB 微不足道但存在互動作用（取決於 MSB 的分支是 $ 0 $ 或者 $ 1 $ ) 我不確定黑盒模型是否禁止。

我不確定黑盒模型是否禁止”

黑盒模型禁止對組元素執行除特定操作集之外的任何操作。在您的情況下，允許的操作是：

• 組操作（給定 $ A $ 和 $ B $ ， 返回 $ A \times B $ )
• 組反轉操作。
• 比較兩個組元素是否相等。
• 您的 msbit oracle（因為您正在擴展黑盒模型以包含此操作）。

禁止對組元素進行任何其他操作。

另一方面，任何操作都是非組元素的東西，都是公平的遊戲。例如，您的 msbit oracle 返回位；該位不是組元素，因此可以執行以下操作：

if (oracle_returned_a_one) {
    do_this();
} else {
    do_that();
}

完美髮揮。

所以，除非素數剛好在 2 的冪次以上，也就是說， $ p = 2^k + \ell $ 為了 $ 2^k / \text{polylog}(p) < \ell < 2^k $ ，很明顯，您可以使用多項式查詢來計算離散對數（具體而言， $ k + \text{polylog}(p) $ 查詢）

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