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 '14 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 '14 at 17:42
  • $\begingroup$ I can't use hidden group order because I need to do some computations on the secret keys. $\endgroup$ – Florian Bourse Dec 8 '14 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$ – Florian Bourse Dec 8 '14 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 '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.

| improve this answer | |
  • $\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$ – Florian Bourse Dec 9 '14 at 10:08
  • $\begingroup$ I wouldn't mind. $\;$ $\endgroup$ – user991 Dec 9 '14 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$ – Hilder Vitor Lima Pereira Dec 11 '14 at 20:19
  • $\begingroup$ You can find it here eprint.iacr.org/2014/670.pdf $\endgroup$ – absinthe_minded Jan 10 '15 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.