# Partially homomorphic encryption (on addition modulo N) not based on prime factorization

A cryptographic function is homomorphic on some operation if that operation is preserved in the encrypted data.

Such a function is homomorphic on addition modulo if the following holds for some cryptographic function $E$:

$E(x)\cdot E(y) = E(x+y\mod N)$

and on xor:

$E(x)\cdot E(y) = E(x \oplus y)$

This is called a partially homomorphic encryption.

http://en.wikipedia.org/wiki/Homomorphic_encryption

However, all the partially homomorphic schemes on XOR and addition modulo are based on prime factorization.

Are there partially homomorphic encryption methods on XOR or addition modulo that do not are not based on prime factorization (other than the fully homomorphic system proposed by Gentry based on lattice cryptography).

This paper by Mykletun, Girao and Westhoff suggests the El-Gamal method:

Typical ElGamal is homomorphic with respect to multiplication. You can get an additively-homomorphic variant by encrypting $g^m$ instead of $m$. When you decrypt, however, you will get back $g^m$, not $m$. Therefore, you have to solve a discrete log to get $m$ back. This is feasible if we place certain restrictions on $m$ (e.g., the space from which $m$ is drawn is small enough to brute-force the discrete log). Security of ElGamal relates to solving discrete logs.