# 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?

• Why can't you use hidden group order? – pg1989 Dec 8 '14 at 17:40
• Would leveled additively homomorphic encryption suffice? $\:$ (key size grows linearly in the depth it must be able to handle) $\;\;\;\;$ – user991 Dec 8 '14 at 17:42
• I can't use hidden group order because I need to do some computations on the secret keys. – Florian Bourse Dec 8 '14 at 17:51
• Ricky, I am curious to see a leveled additively homomorphic encryption. In my case I don't think it would be sufficiant but maybe I can work out something from this. – Florian Bourse Dec 8 '14 at 17:55
• The idea is just using that FHE over the integers's "noise" increases far less quickly for addition than for multiplication. $\;$ – user991 Dec 8 '14 at 18:20

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

• Thanks for your answer, I think it would benefit a lot if you used more math mode though. Would you mind if I edit it for readability? – Florian Bourse Dec 9 '14 at 10:08
• I wouldn't mind. $\;$ – user991 Dec 9 '14 at 20:12
• @RickyDemer Where did you find this scheme? I ask because it seems very close to one that I found on the paper Fully-Homomorphic Encryption over Integers and I really want to find other texts in this direction... – Hilder Vitor Lima Pereira Dec 11 '14 at 20:19
• You can find it here eprint.iacr.org/2014/670.pdf – absinthe_minded Jan 10 '15 at 4:08