# Is there an additively homomorphic encryption scheme that supports calculating a square root on the ciphertext?

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?

• @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. Commented Oct 23, 2015 at 13:50
• OK, I see. Sorry for the inconvenience. Commented Oct 23, 2015 at 15:31
• no worries. It happens often on SE sites. Commented Oct 23, 2015 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:

$$\sqrt{\sqrt{a+a+b+b}}$$

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.

• 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$. Commented Oct 22, 2015 at 18:21
• @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) Commented Oct 22, 2015 at 18:29
• 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 Commented Oct 22, 2015 at 19:34
• @JanLeo: how is that any better than decrypting the (unsquarerooted) ciphertext, and then halving the plaintext yourself? Why isn't that an appropriate solution? Commented Oct 22, 2015 at 20:17
• 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$
– tylo
Commented Oct 23, 2015 at 14:33