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?

  • $\begingroup$ Why can't you use hidden group order? $\endgroup$
    – pg1989
    Dec 8, 2014 at 17:40
  • $\begingroup$ Would leveled additively homomorphic encryption suffice? $\:$ (key size grows linearly in the depth it must be able to handle) $\;\;\;\;$ $\endgroup$
    – user991
    Dec 8, 2014 at 17:42
  • $\begingroup$ I can't use hidden group order because I need to do some computations on the secret keys. $\endgroup$ Dec 8, 2014 at 17:51
  • $\begingroup$ 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. $\endgroup$ Dec 8, 2014 at 17:55
  • $\begingroup$ The idea is just using that FHE over the integers's "noise" increases far less quickly for addition than for multiplication. $\;$ $\endgroup$
    – user991
    Dec 8, 2014 at 18:20

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$ Dec 9, 2014 at 10:08
  • $\begingroup$ I wouldn't mind. $\;$ $\endgroup$
    – user991
    Dec 9, 2014 at 20:12
  • $\begingroup$ @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... $\endgroup$ Dec 11, 2014 at 20:19
  • $\begingroup$ You can find it here eprint.iacr.org/2014/670.pdf $\endgroup$ Jan 10, 2015 at 4:08

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.