Elgamal-Encryption
用於電子投票的同態加法的 Paillier 與 Lifted ElGamal
我希望創建一個匿名電子投票系統，該系統將在投票期間為每個候選人分配一定數量的比特，例如 Alice 為 010000，Bob 為 000100，Charlie 為 000001。它適用於較小規模的 ElGamal，但是當我嘗試在較大規模上進行時（添加更大的數字），它會超時。另一方面，Paillier 似乎更有效地添加更大的數字。
由於我不是加密專家，因此我對此有幾個問題：
- ElGamal 是否真的有添加更大數字的問題，或者這是由於實施限制？這是有道理的，因為它使用冪，但我想確認一下。
- 此外，由於 Paillier 允許加法和乘法，它是否使它比 ElGamal 更“可塑性”和更不安全？我在他們的比較安全分析中找不到任何指標，但我確實發現 ElGamal 應該更有效，因此我最初的問題是。
更新： 本文說：“例如，為了達到 128 位安全級別，ElGamal 中通常使用 4096 位 p 和 256 位 q，而在 Paillier 中，n 的大小通常選擇為4096 位。”
這是否意味著Paillier較弱？
所以總的來說，ElGamal 加密只是同態的。乘法。然而，幾個星期後，人們可以將 ElGamal 轉換為指數 ElGamal（我猜這就是你所指的）。
ElGamal 和指數 ElGamal 之間的主要區別在於，而不是消息： $ m $ 你必須加密 $ g^{m} $ . 解密意味著必須解決離散對數問題才能獲得 $ m $ . 對於小數字，這根本沒有問題（因此它在投票方案中工作得非常好，累積的數字通常不是那麼大），但你是對的，當 $ m $ 變得更大，事情會變得混亂和緩慢。
據我所知，Paillier 沒有這個限制。
這些算法的安全性來自不同的假設。雖然 El-Gamal 依賴於 Diffie-Hellman（分別為Decisional-Diffie-Hellman），但 Paillier 則基於決策複合殘留假設。
我沒有查看各自的論文以查看它們提供了哪些安全證明，但我認為當您使用它們的正確實現和適當的參數時，對於電子投票系統來說，兩者都是完全可以的。