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 <- E(m)

y <- 2^C

2^m <- D(y)

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

-
You already answered your own question. "It enables arbitrary functions..." Power is a function. – D.W. Apr 7 '14 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)? – Jan Leo Apr 7 '14 at 15:05
@JianLiu BGV does. I'm not sure about others. – mikeazo Apr 7 '14 at 15:11

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. – poncho Apr 7 '14 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 '14 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. – poncho Apr 7 '14 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 '14 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. – poncho Apr 7 '14 at 21:09