離散日誌問題，當我們有很多例子時
假設我有很多離散對數問題的實例，都使用相同的未知指數。這個問題比標準離散對數問題更容易嗎？
哦，見鬼，我應該更準確。讓 $ p $ 是一個大素數，選擇得足夠大，使得離散對數問題取模 $ p $ （大概）很難。從這裡開始的一切都將在整數的乘法組中 $ p $ . 假設我們得到 $ a=(a_1,\dots,a_n) $ 和 $ b=(b_1,\dots,b_n) $ ， 在哪裡 $ b=a^k $ ，我們想找到 $ k $ . 換句話說， $ b_i = a_i^k $ 對全部 $ i $ （對於每個相同的整數指數 $ n $ 實例），我們想要找到指數 $ k $ .
尋找的難度是多少 $ k $ ? 是否更容易找到 $ k $ ，鑑於這些 $ n $ 實例，而不是只給出一個實例？（比如說，大於 $ n $ -fold 加速可用？）
$ \newcommand{\Z}{\mathbb{Z}} $ 我懷疑特別關註三個案例是有意義的，這取決於 $ a $ 的被選中：
- *隨機選擇。在這個變體中， $ a_i $ ’s 均勻且獨立地分佈在 $ (\Z/p\Z)^ $ .
- *非自適應對抗性選擇。*在這種變體中，對手選擇所有 $ a_i $ 的提前，在看到任何 $ b_i $ 的。
- *自適應對抗選擇。*最後，我們可以考慮一個自適應變體，攻擊者選擇 $ a_1 $ , 可以看到 $ b_1=a_1^k $ , 那麼攻擊者可以選擇 $ a_2 $ ， 看 $ b_2=a_2^k $ ， 等等。
它是否有助於對手顯著地看到 $ n>1 $ 對 $ (a_i,b_i) $ ? 當然，當 $ n=1 $ 這只是簡化為標準的離散對數問題。什麼時候 $ n>1 $ ，這個問題比基本的離散對數問題容易得多嗎？
關於第三種情況，我有意見。第三個預言機可以幫助對手使用Cheon 算法解決 DL 問題。
讓 $ q $ 是子群的素數 $ \mathbb{G} $ 的 $ (\mathbb{Z}/p\mathbb{Z})^{\times} $ .
在第三種情況下，對手有一個預言機 $ a \mapsto a^k $ 對於任何 $ a $ . 因此，可以獲得 $ g^{k^i} $ 從 $ g^{k^{i-1}} $ 等等。什麼時候 $ d \mid q-1 $ , Cheon 的算法解決了增廣 DL 問題 $ (g,g^k,g^{k^d}) $ 在小組之上 $ \mathbb{G} $ 有秩序的 $ q $ 和 $ O(\sqrt{q/d} + \sqrt{d}) $ 算術計算。如果存在除數 $ d = O(q^{1/3}) $ 的 $ q-1 $ , 對手可以解決 DL 問題 $ O(\sqrt{q^{2/3}}+\sqrt{q^{1/3}}+q^{1/3}) = O(q^{1/3}) $ 算術計算。
第三個神諭會增強對手的力量，如果 $ O(\sqrt{q}) $ -time 算法是針對 DL 問題的最佳攻擊。
在實踐中，這種觀點是不，它並沒有變得更容易。事實上，許多流行的部署方案都依賴於它。例如Boneh-Franklin IBE 方案中的 Trusted Authority有一個主密鑰
s，並以 形式向使用者頒發私鑰s.ID_i，其中ID_i是橢圓曲線上的一個點，與第 - 個使用者ID_i的身份相關。從這樣的私鑰i中查找是一個標準的 DL 問題。s儘管如此，Boneh-Franklin 計劃被認為是強大的反對多個使用者的陰謀，這些使用者可以匯集他們的秘密以試圖找到主秘密s。