加法同態加密：嚴格相等 - 處理同餘
是否有一種加法同態加密方案可以保證如果提供
$ E(v) $ , $ E(m_1) $ 和 $ E(m_2) $
和 $ E(v)=E(m_1).E(m_2) $ 然後 $ v=m_1+m_2 $
請注意這不是 $ v \equiv m_1+m_2 \pmod p $
為了說明，假設一組順序 $ p $ ，ElGamal 的加法版本似乎不符合標準。假設 $ v=m_1+m_2 $ , 存在值 $ m’_1 $ 和 $ m’_2 $ 這樣
$ m’_1+m’_2 = m_1+m_2+k(p-1) $ , $ k \in Z^* $
驗證 $ E(v)=E(m’_1)E(m’_2) $ 由於費馬小定理，雖然 $ v $ 不等於 $ m’_1+m’_2 $
一個簡單的數字範例是，假設順序 $ p=7 $ , 一個生成器 $ g=2 $ , $ v=4 $ , 一個共享的秘密 $ s $ ,
$ m_1=1 $ 和 $ m_2=3 $ 顯然驗證了 $ E(1)E(3)=E(4) = 2^4.s \pmod 7 \equiv 2.s \pmod 7 $
但也是如此 $ m_1=4 $ 和 $ m_2=6 $ 自從 $ 2^{10} \equiv 2 \pmod 7 $
我認為這種方案甚至無法構造，因為消息空間總是有限的，因此我們總是在某種模組化結構中工作。
如果我們這麼說 $ \mathcal{M} $ 有 $ n $ 元素並且它接近於總和，那麼對於所有 $ m \in \mathcal{M} $ , 添加 $ m $ 對自己產生 $ {m, 2m, 3m, …, nm, (n+1)m} \subset \mathcal{M} $ .
但是根據鴿洞原理，這些值中至少有兩個是相等的。所以，讓我們說 $ pm = qm $ 和 $ q > p $ ， 然後 $ (q - p)m = 0 $ .
因此，存在這個正數 $ k := (q - p) $ 這樣 $ E((k-1)m) \otimes E(m) = E(0) $ .
也就是說，通常所做的是以消息空間對應用程序足夠大的方式選擇參數，以便生成的值不會大於已知的模數（然後解密的值總是等於預期的一，不減）。