什麼是離散對數假設以及為什麼使用 Shank 的嬰兒步/巨人步不容易
當我閱讀 DLP 時，似乎假設通常不可能在多項式時間內解決它。但我也讀到有幾種算法 $ \mathcal{O}(\sqrt{n}) $ ，例如，小腿的嬰兒步/巨人步，所以我一定有一些誤解。
- 假設是什麼？
如果我正確理解了這個問題，我們會得到一個具有模數的組和該組的生成器。問題是：
- 給定一個元素 $ x $ 組的，找到號碼 $ a $ 使發電機 $ g $ 會產生 $ x $ 經過$$ x = g^a \bmod q. $$假設是我們不能在多項式時間內對問題的隨機或最壞實例執行此操作，但我一定誤解了，因為我讀到了確定性算法，例如 Shank 的嬰兒步/巨人步，它解決了問題 $ \mathcal{O}(\sqrt{|G|}) $ 這相當快，不是嗎？
我的錯誤在哪裡？
當我閱讀 DLP 時，似乎假設通常不可能在多項式時間內解決它。
實際上，我們是否認為它很難取決於群體。肯定有一些組很容易（例如，在 $ \mathbb{Z}_q^* $ 在哪裡 $ q-1 $ 是光滑的）。
但我也讀到 O(sqrt(n)) 中有幾種算法，例如大步/小步，所以我一定有一些誤解。
這就是你的誤解；當我們說“多項式時間”時，我們的意思是“多項式時間” $ \log(n) $ “; $ \sqrt{n} $ 不是多項式 $ \log(n) $ （實際上，它是指數的），所以這並不矛盾。
問題是：給定一個元素 $ x $ 組的，找到號碼 $ a $ 使發電機 $ g $ 會產生 $ x $ 經過 $ x = g^a \bmod q $ .
實際上，有許多概括，它們有時都稱為 DLP：
- 也許我們不需要 $ g $ 成為整個集團的發電機；我們仍然堅持 $ x $ 是子組的成員 $ g $ 生成（不會有 $ a $ 否則）。這實際上比您的意思更常見；在哪裡 $ g $ 可能會生成一個素數大小的子群。
- 也許我們不會將自己局限於形式的組 $ \mathbb{Z}_q^* $ , 而是有 $ g $ 和 $ x $ 是不同組的成員（例如，橢圓曲線組）。有時這被稱為 ECDLog 問題；有時，我們並不那麼具體。
我閱讀了諸如 Shank 之類的確定性算法，它解決了 O(sqrt(|G|) 中的問題，速度相當快，不是嗎？
不是如果 $ |G| > 2^{256} $ ，它不是（是的，這就是我們在實踐中使用的組的大小）
但我也讀到 O(sqrt(n)) 中有幾種算法，例如大步/小步，所以我一定有一些誤解。
你提到的算法及時執行 $ O(\sqrt{|G|}) $ 並且這些組通常是這樣選擇的 $ |G|\approx 2^{\lambda} $ 對於一些安全參數 $ \lambda $ . 因此，算法的執行時間為 $ O(2^{\lambda/2}) $ ，它仍然是安全參數的指數。
假設是什麼？
對於循環群 $ G $ 順序素數 $ p $ （在哪裡 $ |p|\approx 2^\lambda $ ) 和發電機 $ g $ 離散對數問題定義如下：
輸入： $ g^a\in G $ 為了 $ a\leftarrow \mathbb{Z}_q $ （即，隨機選擇 $ a $ )
解決方案： $ a\in\mathbb{Z}_q $
假設是對於任何在時間多項式中執行的（機率）算法都很難解決這個問題 $ \lambda $ . 還可以定義 DLP，其中生成器也是隨機均勻選擇的：您可以閱讀更多關於
$$ BMZ $$.
並且假設我們不能在多項式時間內對問題的隨機或最壞實例進行此操作，
離散對數問題有一個很好的特性，即它是隨機自約的，因此解決隨機實例至少與解決最壞情況實例一樣難。
$$ BMZ $$：Bartusek、Ma 和 Zhandry連結，基於組的假設中固定和隨機生成器之間的區別，Crypto'19