假設 Diffie Hellman oracle 與離散對數相關的常見指數問題
讓G $ g $ 成為乘法群模的生成器p $ p $ 一個素數。
假設我們知道 G一個+ķ米1反對p$$ g^{a+km_1}\bmod p $$ Gb−ķ米2反對p$$ g^{b-km_2}\bmod p $$ G一個+ķ′米3反對p$$ g^{a+k’m_3}\bmod p $$ Gb−ķ′米4反對p$$ g^{b-k’m_4}\bmod p $$ 在哪裡米2米3−米4米1=φ(p) $ m_2m_3-m_4m_1=\phi(p) $ 在哪裡φ $ \phi $ 是完全和一個,b,ķ,ķ′ $ a,b,k,k’ $ 是唯一的未知和全部一個 $ a $ 通過米4 $ m_4 $ 有大小√p $ \sqrt p $ （我們知道米1 $ m_1 $ 通過米4 $ m_4 $ 超過從 $ \mathbb Z $ ) 我們可以辨識G一個 $ g^a $ ,Gb $ g^b $ 在多項式時間內？
我們可以假設一個 Diffie Hellman 預言機嗎？
我想不是。如果我們可以將這樣的構造擴展到黑盒組，它將給出一個q1/4 $ q^{1/4} $ 解決該組中離散對數的方法。還要注意，如果尺寸限制在一個 $ a $ ,b $ b $ ,ķ $ k $ 和ķ′ $ k’ $ 被刪除，問題沒有明確定義（即使在受約束的情況下也可能有多種解決方案；我不確定）。
如果忽略大小限制，則有多種解決方案
一般來說，我們可以認為這與指數中的線性代數問題同構。我們寫C1=一個+ķ米1 $ c_1=a+km_1 $ ,C一世=GC一世反對p $ C_i=g^c_i\mod p $ 等等。通過乘以項C一世Cj $ C_iC_j $ 或指數項Cd一世 $ C_i^d $ 我們可以添加C一世+Cj $ c_i+c_j $ 或將我們未知的指數乘以常數dC一世 $ dc_i $ , 這樣我們就可以找到GX $ g^x $ 在哪裡X $ x $ 是這些的任意線性組合C一世 $ c_i $ （一個 Diffie-Hellman 預言機將允許我們形成G是 $ g^y $ 在哪裡是 $ y $ 是一個任意多項式表達式C一世 $ c_i $ ）。將我們自己限制在這樣的線性組合中（就像黑盒組的情況一樣），問題就變成了找到我們的線性組合C一世 $ c_i $ 等於一個 $ a $ 或者b $ b $ .
我們有系統 (10米10010−米210米30010−米4)(一個bķķ′)=(C1C2C3C4)(反對φ(p))$$ \left(\matrix{1&0&m_1&0\ 0&1&0&-m_2\ 1&0&m_3&0\ 0&1&0&-m_4}\right)\left(\matrix{a\ b\ k\ k’}\right)=\left(\matrix{c_1\ c_2\c_3\c_4}\right)\pmod{\phi(p)} $$ 如果我們寫米 $ M $ 對於 4x4 矩陣和C $ \mathbf c $ 對於右手向量，我們可能希望從米−1C $ M^{-1}\mathbf c $ . 然而我們看到 d和噸(米)=米1米4−米2米3≡0(反對φ(p))$$ \mathrm{det}(M)=m_1m_4-m_2m_3\equiv 0\pmod{\phi(p)} $$ 所以我們的矩陣是不可逆的。
高中線性代數現在告訴我們，要麼沒有解，要麼有很多解。我們的構造定義了一個解決方案這一事實告訴我們有很多解決方案。減少一點行數告訴我們米2C1+米1C2−米3C3−米1C4≡0(反對φ(p)) $ m_2c_1+m_1c_2-m_3c_3-m_1c_4\equiv 0\pmod{\phi(p)} $ . 特別是如果例如米1 $ m_1 $ 互質於φ(p) $ \phi(p) $ ，我們可以確定C4 $ C_4 $ 給定C1 $ C_1 $ ,C2 $ C_2 $ 和C3 $ C_3 $ 所以第四個等式沒有給我們額外的資訊。在沒有進一步退化的情況下，例如，我們可以選擇任意G一個 $ g^a $ 然後找到Gķ≡(C1/G一個)1/米1(反對p) $ g^k\equiv(C_1/g^a)^{1/m_1}\pmod p $ ,Gb≡C2(Gķ)米2(反對p) $ g^b\equiv C_2(g^k)^{m_2}\pmod p $ 和Gķ′≡(C3/G一個)1/米3 $ g^{k’}\equiv(C_3/g^a)^{1/m_3} $ 產生C1 $ C_1 $ ,C2 $ C_2 $ ,C3 $ C_3 $ 和C4 $ C_4 $ 我們看到的。但是，那一個 $ a $ ,b $ b $ ,ķ $ k $ 和ķ′ $ k’ $ 與這些相關的不一定滿足大小限制。
黑盒模型中的禁忌
現在假設我們可以將這樣的求解器擴展到黑盒乘法組。假設給定一個生成器的離散對數問題G $ g $ 有秩序的q $ q $ 和元素C1 $ C_1 $ 就是這樣一個群體。我們任意選擇米1 $ m_1 $ 並且通過計數論證，很有可能C1 $ c_1 $ 可以寫成形式C1≡一個+ķ米1(反對q) $ c_1\equiv a+km_1\pmod q $ 和一個,ķ≤q1/2 $ a,k\le q^{1/2} $ . 寫d=[q1/2] $ d=[q^{1/2}] $ . 我們現在呼叫我們的求解器C1=C1 $ C_1=C_1 $ ,C2=Gd/C1 $ C_2=g^d/C_1 $ ,C3=C1G米1 $ C_3=C_1g^{m_1} $ 和C4=Gd/C3 $ C_4=g^d/C_3 $ 和米1=米2=米3=米4 $ m_1=m_2=m_3=m_4 $ （對應於值b=d−一個 $ b=d-a $ 和ķ′=ķ+1 $ k’=k+1 $ 滿足大小約束）。我們的求解器將返回G一個 $ g^a $ 我們可以從中恢復一個 $ a $ 使用 baby-steps/giant-steps 方法○(4√q) $ O(\root 4\of q) $ 腳步。同樣我們可以恢復Gķ=(C1/G一個)1/米1 $ g^k=(C_1/g^a)^{1/m_1} $ 和ķ $ k $ 在另一個○(4√q) $ O(\root 4\of q) $ 腳步。這允許我們計算C1 $ c_1 $ 和○(4√q) $ O(\root 4\of q) $ 黑盒組無法進行的組操作。