Elliptic-Curves
指數中的不同模數
給定兩個值 $ g^{a_1}, g^{a_2} $ 在哪裡 $ a_1, a_2 \in \mathbb{Z}_q $ 和 $ g $ 是群的生成器 $ \mathbb{G} $ 有秩序的 $ q $ . 假設離散對數很難 $ \mathbb{G} $ .
有沒有辦法找到價值 $ g^x $ 這樣 $ x = a_1 + a_2 \text{ mod } p $ 與 p < q。我們也知道， $ a_1, a_2 < p $ . 這裡 $ p,q $ 是大素數，例如 $ 128, 256 $ 分別位。
讓 $ \mathbb G $ 帶發電機 $ g $ , 它是 256 位素數順序 $ q $ , 和 128 位素數 $ p $ 是已知的和固定的。
假設我們得到一個算法 $ \mathcal A $ 哪個在輸入 $ (h_1,h_2)\in\mathbb G^2 $ ， 和 $ h_1=g^{a_1} $ , $ h_2=g^{a_2} $ 對於隨機 $ a_1,a_2\in\mathbb Z_q $ , 輸出 $ h_3=g^{a_1+a_2\bmod p} $ 與問題一樣，具有非消失的機率。
定義算法 $ \mathcal A’ $ 在輸入 $ h\in\mathbb G $ 嘗試輸出 $ y $ 和 $ g^y=h $ ，並為此：
- 畫 $ u $ 隨機輸入 $ \mathbb Z_q $ , 計算 $ h_1=g^u;h $ ，現在是隨機的 $ \mathbb G $ ; 因此有一個獨特的（至今未知，隨機） $ a_1\in\mathbb Z_q $ 和 $ g^{a_1}=h_1 $
- 畫 $ a_2 $ 隨機輸入 $ \mathbb Z_q $ , 計算 $ h_2=g^{a_2} $
- 執行 $ \mathcal A $ 帶輸入 $ (h_1,h_2) $ , 得到 $ h_3 $ 假設為（具有非消失機率） $ g^{a_1+a_2\bmod p} $
- 發現 $ x\in\mathbb Z_q $ 和 $ 0\le x<p<2^{128} $ 這樣 $ g^x=h_3 $ ，這需要按順序 $ 2^{66} $ 使用Polard 的 rho進行分組操作，具有顯著的點，可能的記憶體很少，並且易於分佈
- 計算 $ r=x-a_2\bmod p $ ; 它擁有 $ a_1\equiv r\bmod p $ ， 和 $ 0\le a_1<q $ ; 讓（sd但未知） $ s\in\left[0,\left\lfloor q/p\right\rfloor\right] $ 是這樣的 $ a_1=r+s,p $ ， 因此 $ g^{r+s,p}=h_1 $ ， 因此 $ g^{s,p}=h_1,g^{q-r} $ ， 因此 $ g^s=(h_1,g^{q-r})^{p^{-1}\bmod q} $
- 計算 $ h_4=(h_1,g^{q-r})^{p^{-1}\bmod q} $ ; 它擁有 $ g^s=h_4 $ 和 $ s<2^{129} $
- 發現 $ s $ 通過基本相同的方法 $ x $
- 計算 $ a_1=r+s,p $ ，因此是這樣的 $ g^{a_1}=h_1 $
- 計算和輸出 $ y=a_1-u\bmod q $ , 就是這樣 $ g^y=h $ .
我們的算法 $ \mathcal A’ $ 因此能夠計算離散對數 $ y $ 基地 $ g $ 任何給定元素的 $ h $ 在 $ \mathbb G $ 具有非消失的機率，並且可行的工作很少。這是假設不可能的。因此我們的假設是 $ \mathcal A $ 存在是假的。
因此，我們否定地回答了這個問題。