I need an additively homomorphic encryption scheme that satisfies: $D(\sqrt{E(m)}) \approx \sqrt{m}$. It seems that the lifted ElGamal satisfies this, but it is hard to do decryption if the message space is large. Is there any other scheme that satisfies this?

  • $\begingroup$ @JanLeo I know you realized you made a mistake in the notation and meant to have $\approx m/2$ instead of $\approx\sqrt{m}$, but since there was already an answer to the first version and changing the equation is really a significant change, we have decided to revert back to the original form of the question so that the answer is still valid. I suggest you, after addressing some of the questions in the comments, ask a new question relating to the $\approx m/2$ version of the question. $\endgroup$ – mikeazo Oct 23 '15 at 13:50
  • $\begingroup$ OK, I see. Sorry for the inconvenience. $\endgroup$ – Jan Leo Oct 23 '15 at 15:31
  • $\begingroup$ no worries. It happens often on SE sites. $\endgroup$ – mikeazo Oct 23 '15 at 15:36

I believe that such a system (with Homomorphic addition and approximate squareroots) is likely to be Fully Homomorphic, and hence it is unlikely that you could find an efficient candidate among existing systems (or, if you did, well, that's a Really Significant result).

Let us assume that:

  • Subtraction (as well as addition) can be done homomorphically

  • The approximate squareroot of 2 is 1.

Then, we can compute the "or" of two encrypted values $a$ and $b$ (which are both encrypted versions of either 0 or 1), by computing:


It is easy to verify that the result will be an encrypted 0 if both $a$ and $b$ are 0, and 1 if either (or both) are 1.

That, with homomorphic subtraction, is a complete set, and so we have a FHE system on our hands.

| improve this answer | |
  • $\begingroup$ Can I use the lifted ElGamal Encryption, so that I can get $a = g^\sqrt{m}$ after decryption. Then I try all possible plaintexts $m'$, calculate all $b = g^\sqrt{m'}$, and see which $m'$ can lead to a small value of $a-b$. $\endgroup$ – Jan Leo Oct 22 '15 at 18:21
  • 2
    $\begingroup$ @JanLeo: I don't see how lifted ElGamal allows you to compute squareroots (except by having the decryptor decrypt $m$ and then computing the squareroot on the plaintext) $\endgroup$ – poncho Oct 22 '15 at 18:29
  • 2
    $\begingroup$ Lifted ElGamal does allow you to perform exact halving; however logic similar to what I gave shows that approximate halving (e.g. 3/2 -> 1) also gives you FHE $\endgroup$ – poncho Oct 22 '15 at 19:34
  • 2
    $\begingroup$ @JanLeo: how is that any better than decrypting the (unsquarerooted) ciphertext, and then halving the plaintext yourself? Why isn't that an appropriate solution? $\endgroup$ – poncho Oct 22 '15 at 20:17
  • 2
    $\begingroup$ There is a substantial difference in using square roots over reals (with approximations, etc.) and square roots in finite rings and fields. $2^{1/2}$ mod $7$ equals both $3$ and $4$. It has nothing to do with $\sqrt{2}\approx 1.414$ $\endgroup$ – tylo Oct 23 '15 at 14:33

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.