How could Fully Homomorphic Encryption support power operations?

Question

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.

Answer 1

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.

Answer 2

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?