當指數來自二項分佈時，為什麼離散對數問題很容易？
我在http://epubs.surrey.ac.uk/7219/2/esorics06.pdf中讀到指數 El Gamal 中用於恢復的離散對數問題 $ m $ 從 $ g^m $ 可以變得易於處理 $ m $ 是從二項分佈中得出的。為什麼是這樣？
這是交易。離散對數問題在已知指數來自小範圍的可能性（例如，指數不太大）的特殊情況下是可行的。
假設我們得到 $ y=g^m $ ，我們想找到 $ m $ . 假設我們還知道 $ m $ 是小： $ 0 \le m < 2^{30} $ ， 說。然後事實證明很容易恢復 $ m $ ，沒有太多的計算時間。
- 一種非常簡單的方法是簡單地嘗試所有可能的值 $ m $ : 我們計算 $ g^0 $ , $ g^1 $ , $ g^2 $ , \點, $ g^{2^{30}-1} $ 看看其中哪一個匹配 $ y $ . 這總會找到 $ m $ , 大約需要 $ 2^{30} $ 計算。這是可行的，但不是超快的：可能需要幾個小時的計算。
- 更聰明的方法是使用平方根算法。事實證明，有一些方法可以解決這個問題 $ 2^{15} $ 計算。（這裡 $ 2^{15} = \sqrt{2^{30}} $ ，這就是為什麼這被稱為平方根方法。如果我們知道 $ 0 \le m < M $ ，那麼這些方法將需要大約 $ \sqrt{M} $ 計算。）這是非常可行的，而且非常快：可能需要幾分鐘的計算。
有幾種平方根方法可以實現這種執行時間，包括嬰兒步巨步算法（有時也稱為 Shanks 方法）或Pollard 的袋鼠算法（有時也稱為 Pollard 的 lambda 方法）。
有關從小範圍的可能性中選擇指數時的有效離散對數算法的更多資訊，請參閱從子集中提取指數時攻擊者贏得離散對數遊戲的機率。
這和你的問題有什麼關係？好吧，假設我們知道指數 $ m $ 取自二項式 $ (2^{30},1/2) $ 分配。然後我們知道 $ 0 \le m \le 2^{30} $ ，所以我們 $ m $ 來自小範圍的可能性，我們可以恢復 $ m $ 使用上述方法。因此，二項式分佈並沒有什麼特別之處，除了已知二項式分佈是有界的，如果這個界足夠小，那麼我們就可以應用上面的方法。
這種情況經常出現在電子投票中。假設有 $ N $ 不同的選民。讓我勾勒出一種使用同態密碼學進行安全電子投票的方法。
我們將讓每個選民對他們的投票進行加密，並將生成的密文發佈到某個地方供所有人查看。每個選民的選票將按如下方式加密：對於某些特定的候選人（例如，史密斯），我們加密 $ m_i $ 使用合適的公鑰加密方案，其中 $ m_i=0 $ 如果 $ i $ 選民沒有投票給史密斯並且 $ m_i=1 $ 如果 $ i $ 那個選民確實投票給了史密斯。選民的加密選票是所有這些密文的串聯，每個候選人一個，但現在讓我們關注史密斯的部分。每一個 $ N $ 選民這樣做並發布結果密文。
我們選擇一個合適的同態公鑰加密算法使得 $ E(m_1) \times E(m_2) = E(m_1 + m_2) $ . 實現此目的的一種標準方法是加密 $ g^{m_i} $ 使用 El Gamal 加密，所以 $ E(m_i) = (g^{r_i}, h^{r_i} g^{m_i}) $ ， 在哪裡 $ r_i $ 是隨機的，由選民選擇 $ i $ . 每位選民公佈他們的加密投票；因此，對於選民 $ i $ , $ E(m_i) $ 已發布。
由於加密方案是同態的，所以每個人都可以計算出 $ m_1+\dots+m_N $ , 使用關係 $ E(m_1+\cdots +m_N) = E(m_1) \times \cdots \times E(m_N) $ . 請注意 $ m_1+\dots+m_N $ 是投票給候選人史密斯的選民總數的統計，這是我們想要恢復的；我們有一個加密的公開副本。
讓 $ m=m_1+\dots+m_N $ ，所以我們有 $ E(m) $ 我們想要恢復 $ m $ 完成選票列表。在製表過程中，當局（擁有私鑰副本，以門檻值形式共享）將使用門檻值 El Gamal 解密來解密 $ E(m) $ ，這會產生值 $ g^m $ . 最後當局需要恢復 $ m $ . 幸運的是，他們可以通過獲取離散對數來做到這一點 $ g^m $ . 這是可行的，因為我們知道 $ m $ 在範圍內 $ 0 \le m \le N $ , 和數 $ N $ 投票者的數量不能太大（例如，我們不會有超過十億的投票者），因此在這種特殊情況下，可以應用上述方法來計算這個離散對數。我希望這是有道理的。