Is there an additive homomorphic encryption scheme which guarantees that if provided with

$E(v)$, $E(m_1)$ and $E(m_2)$

and $E(v)=E(m_1).E(m_2)$ then $v=m_1+m_2$

Please note this is not $v \equiv m_1+m_2 \pmod p$

To illustrate, assuming a group of order $p$, the additive version of ElGamal does not seem to match the criteria. Assuming $v=m_1+m_2$, there exists values $m'_1$ and $m'_2$ such that

$m'_1+m'_2 = m_1+m_2+k(p-1)$, $k \in Z^*$

which verifies $E(v)=E(m'_1)E(m'_2)$ due to Fermat's little theorem although $v$ is not equal to $m'_1+m'_2$

A simple numeric example is, assuming order $p=7$, a generator $g=2$, $v=4$, a shared secret $s$,

$m_1=1$ and $m_2=3$ obviously verifies that $E(1)E(3)=E(4) = 2^4.s \pmod 7 \equiv 2.s \pmod 7$

but so does $m_1=4$ and $m_2=6$ since $2^{10} \equiv 2 \pmod 7$


1 Answer 1


I think this kind of scheme can't even be construct, because the message space is always finite, thus we are always working in some kind of modular structure.

If we say that $\mathcal{M}$ has $n$ elements and that it is closed to the sum, then for all $m \in \mathcal{M}$, adding $m$ to itself generates $\{m, 2m, 3m, ..., nm, (n+1)m\} \subset \mathcal{M}$.

But by the Pigeon hole principle, at least two of those values are equal. So, let's say $pm = qm$ with $q > p$, then $(q - p)m = 0$.

Therefore, there exists this positive number $k := (q - p)$ such that $E((k-1)m) \otimes E(m) = E(0)$.

That said, what was typically done was to chose parameters in a way that the message space is large enough for the application, so that the generated values don't get bigger than the known modulus (then the decrypted value is always equal to the expected one, without being reduced).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.