# Additive homomorphic encryption: strict equality - handling congruence

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$

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)$.