指數 ElGamal 的正確性證明

我有一個任務來證明 ElGamal 和指數 ElGamal 同態特徵（分別為乘法和加法）的正確性。我已經設法證明了前者，但在證明後者方面正在努力。我已經到了添加兩個密文的地步 $ c_1 $ 和 $ c_2 $ 獲得 $ c_3 $ ， 在哪裡：

$$ c_3 = (a^{r_1} + a^{r_2}, m_1+m_2(b^{r_1} + b^{r_2})) $$ 我完全錯了嗎？

是的，你在這個上弄錯了。最重要的是，ElGamal 通常是在一個組上定義的，但是您將加法符號與乘法符號混合在一起。

首先，在乘法群上寫 ElGamal 時 $ (\mathbb{G},\times) $ 正如您所做的那樣，我們通常不會在組結構之上假設任何其他結構 - 因此編寫 $ a^{r_1} + a^{r_2} $ 一般沒有意義。

其次，在乘法符號中，密文如下所示： $ c_1 = (a^{r_1},b^{r_1}\cdot a^m) $ . 你可以寫 $ (r_1\cdot a, (r_1\cdot b)+(m \cdot a)) $ 如果您想改用加法符號，但這些符號都不會導致 $ c_3 $ 你得到了。

解決方案提示：使用組操作“合併”組元素，不要嘗試將表單的對象相加 $ a^{r_1} $ 和 $ a^{r_2} $ ，這不會帶你到任何地方。使用乘法符號，您應該使用以下觀察： $ a^{m}\cdot a^{m’} = a^{m+m’} $ .

引用自：https://crypto.stackexchange.com/questions/57825