證明同態求和密文解密的正確性？
我想採用一些加法同態密碼系統 - 現在不太關心哪個 - 並用它加密一系列數字。然後我想（公開地）把這些數字加起來，解密總和，讓每個人相信我做對了。
這似乎毫無意義，因為我自己一開始就加密了這些數字，但我正在考慮投票應用程序，實際上加密數字的一方與解密總和的一方不同，並且被求和/解密的數字是都在公共公告板上。
我知道投票在文獻中是一個經過充分研究的問題，但到目前為止，我讀過的所有論文都沒有以我感興趣的方式進行投票，所以我認為這是一個探索的好機會。
到目前為止，我了解使用正常 Paillier 加密，為了證明正確的解密，您可以揭示隨機性，但是如果您將密文加在一起，這將不起作用。指數 ElGamal 可能適用於我的案例，但我不確定它是否可以讓我做我需要的事情……另外我不確定普通電腦實際上可以多快地在消息空間中強制離散日誌幾億種可能性。我知道這是完全有可能的，但是“可能”和“足夠快以可用”之間存在差距，我不清楚如何計算出這一點，而不僅僅是自己實施並憑經驗嘗試。
對於指數 ElGamal，如果所有單個密文都是公開的（您提到它們在公共公告板上），這很容易。讓我們打電話 $ (c_1,c_2)=(g^my^r,g^r) $ 和對應的密文 $ m $ 同態求和後的所有單個加密消息（與 $ y=g^x $ 是公鑰）。解密方只是提供了一個非互動式的知識證明（知識簽名- $ SoK $ ) 的私鑰 $ x $ （表示 $ \alpha $ 下面），即：
$$ \pi \gets SoK{(\alpha): c_1=g^mc_2^\alpha
\landy=c_2^\alpha } $$ 隨著 $ m $ （這 $ SoK $ 可以通過使用 Fiat-Shamir 將各自的 sigma 協議轉換為非互動式證明來有效地實現）。現在每個人都可以檢查同態添加所有密文是否會產生 $ (c_1,c_2) $ 並採取 $ (c_1,c_2) $ 也 $ m $ 和 $ y $ 證據 $ \pi $ 驗證。如果這一切都成功，那麼每個人都會相信解密方的行為是誠實的。 如果您有幾百萬種可能性，您可以使用預先計算的查找表、蠻力或使用一些合適的、更複雜的方法來計算離散對數，例如 Pollards lambda 方法（因為您知道在哪裡搜尋）。什麼更適合您取決於您的設置，即您的實體、組設置等資源受限程度如何。您可以對任何其他加法同態加密方案（例如 Paillier）使用類似的方法。