# How could Fully Homomorphic Encryption support power operations?

Fully Homomorphic Encryption (FHE) enables arbitrary functions computed on encrypted data, because it supports both addition and multiplication. But I wonder if FHE supports power operations. For example:

$$C \leftarrow E(m)$$

$$y \leftarrow 2^C$$

$$2^m \leftarrow D(y)$$

I went over some FHE schemes like DGHV, it seems they don't support that.

– D.W.
Apr 7, 2014 at 16:33

The answer is yes. Say we have an FHE scheme that supports addition and multiplication over an underlying field (so we are not limited to just 0,1). As in your question, assume we want to compute $Y=2^C$ where $C$ is encrypted and $Y$ is encrypted such that $y=D(Y)=2^m$.

We can do this using a basic square and multiply algorithm. Assume that we can do a bit decomposition on encrypted values. In other words, assume that given $C$ we can compute $C_1,C_2,\dots,C_n$ which are encrypted values (either 0 or 1) of the bits of the plaintext encrypted by $C$.

Then to compute $Y$ we would do:


A = E(1) # A is our accumulator
B = E(2) # 2 here since the base is 2
for i from 1 to n:
A = (A*B*C_i) + A*(~C_i) # typical code for square-and-multiply puts this
# step in an if-block. If C_i==1: A = A*B. Since
# we can't know the value of C_i, we must do it this
# way. The end result is the same. If C_i=0, A=A.
# If C_i=1, A=A*B (the multiply step in square-and-multply
B = B*B  # This is the square step
Y = A
return Y


where ~ is the NOT operation.

Therefore, all we need is bit-decomposition and NOT. The NOT operation is pretty simple. Since $C_i$ encrypts $0$ or $1$, $~C_i$ is computed as $(1-C_i)$.

Bit decomposition is harder. For an example of how it may be done, see the BGV paper.

• Thanks, it make sense now. BTW, do you know which FHE scheme supports addition and multiplication over an underlying field (not limited to just 0,1)? Apr 7, 2014 at 15:05
• @JianLiu BGV does. I'm not sure about others. Apr 7, 2014 at 15:11
• It's not that helpful if you have to fall back on the complexity of BGV for the bit decomposition. But thanks for the approach, it's the first time I see it explained this clearly. Sep 19, 2021 at 15:45
• @frogeyedpeas, still works for me. Dec 14, 2021 at 0:32

The addition and Multiplication are at bit level , which are nothing but XOR and AND gates. Where XOR is bit level addition and AND is bit level multiplication.

Since XOR and AND form universal gates, In theory all operations like all possible arthimetic operations could be done . More here

Can Add and Multiply On Cipher Text achieve all operations?

• While the conclusions are correct, it turns out that the details are a bit more complicated than "ADD==XOR". The problem is that if we want to limit are internal data to the values $(0,1)$, the simple computation $A+B$ may result a result 2 which is outside of that. One way to obtain an universal gate is to compute the NAND function by encrypting the values $1$ and $-1$, and computing $NAND(A,B) = 1 + (-1 \times A \times B)$, where $+$ and $\times$ are the FHE operations. Apr 7, 2014 at 13:22
• @poncho, I don't understand your comment. This answer looks correct to me. The answer never says "ADD==XOR", does it? XOR and AND are universal; no need for NAND.
– D.W.
Apr 7, 2014 at 16:35
• @D.W.: in my opinion, the answer needed to be sketched out in greater detail. If sashank didn't mean "addition == XOR" and instead he meant that + and $\times$ can be considered to be made up of XOR and AND gates, and we can use the embedded gates in a universal way, well, that doesn't obviously follow, After all, + and - can also be considered combinations of XOR and AND gates, however that pair is not a universal set, hence we cannot use the embedded gates from those two operators in a universal way. Apr 7, 2014 at 17:09
• My perspective: The answer says that XOR and AND are universal, and thus any operation, including addition and multiplication, can be built out of XOR and AND gates. That is a correct statement. So the answer seems fine to me. But we can agree to disagree (or have a slightly different reaction) -- nothing wrong with that!
– D.W.
Apr 7, 2014 at 18:15
• @RickyDemer: with FHE, we have the additional operation of taking any value, and encrypting it with the public key. Hence, we can take the value 1 and encrypt it; that encrypted value can be used just like any other encrypted value. When you add possible constant '1' values, XOR and AND are indeed universal. Apr 7, 2014 at 21:09