Looking For Additively Homomorphic Encryption I have a construction that requires as primitive an Additively Homomorphic Encryption scheme that does not rely on hidden group order, meaning I can't use Paillier.

I now have two different instantiations of that primitive:


Additive ElGamal, with its issue of small message space.
Regev scheme based on LWE, which have bad parameters once you try to do homomorphic additions with a modulus bigger than 2.


My question is the following:

Do you know of some Encryption scheme which is not based on hidden group order and is additively homomorph for a bigger message space?
This probably doesn't actually qualify as leveled-homomorphic, since it doesn't extend nicely.

For integers $n$ and positive integers $m$, define $\operatorname{smod}$ ("signed mod" or "symmetric-ish mod")

by $\;\;\;\;\; (q\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)+r \: \operatorname{smod} \: m \;\; = \;\; r \;\;\;\;\;$ for integers $r$ such that $\;\; -(m\hspace{.02 in}/2) &lt; r \leq m\hspace{.02 in}/2 \;\;\;$.

(B and $m$ are  positive integers; B is a parameter, and vertical bars represent absolute value.)


The following is an encryption scheme that is significantly-additively-homomorphic over $\: \mathbb{Z}\hspace{.02 in}/m\mathbb{Z} \:$:



the secret/private key is a natural number $s$ that is coprime to $m$, and each reduction value is generated as $m \cdot e + s \cdot r$, where $e$ is a random element of {-B,-(B-1),...,B-1,B} and $r$ is a random element of a somewhat-large range of positive integers.

The decryption of a ciphertext $\:$ctext$\:$ is $\;\;($ctext $\operatorname{smod} s) \operatorname{mod} m \;\;\;$.

The secret/private key-holder can encrypt by outputting  $m \cdot e + s \cdot r + $ plaintext $ \operatorname{smod} m$, where $e$ is a random element of {-B,-(B-1),...,B-1,B} and $r$ is a random element of a somewhat-large range of positive integers. 
The "noise" of such a ciphertext is at most $\:($B$\cdot \hspace{.02 in}m)+\big|$plaintext $\operatorname{smod} m\big|\;$.

Anyone with a large-enough set of reduction values can encrypt by sampling a subset $S$ of the reduction values such that $S$ does not have too many elements, choosing a non-zero integer $a_s$ for each element $s$ of $S$, and outputting 
$\sum_{r\in S}s\cdot a_s+$ plaintext. 
The "noise" of such a ciphertext is at most $|S|\cdot $B$ \cdot m + |$ plaintext $\operatorname{smod} m |$.


Homomorphing is done by applying the same integer linear combination to the ciphertexts as is desired on the plain texts. 
The "noise"s of the resulting ciphertexts are at most $\sum_{\text{ctext}}\text{ctext}$'s noise $\cdot |\text{ctext}$'s coefficients$|$.

The reduction of a ciphertext $\text{ctext}$ by a reduction value $r$ is $\text{ctext} \operatorname{smod} r \;$.  The "noise" of such a reduced ciphertext is at most $\text{ctext}$'s noise $+$ B$\cdot m \cdot \lceil \frac{\text{ctext}}{r}-\frac{1}{2} \rceil$

As long as the upper bound on noise given by the relevant [[sentence about noise] in the previous paragraph] is less than $s/2$, decryption of the outputted ciphertext will yield the right plaintext.