# Exponentiation with fully homomorphic encryption [duplicate]

I have often heard that because a fully homomorphic encryption scheme allows for both additions and multiplications on encrypted data, most other operations can be simulated. I don't understand how exponentiation can be done, i.e., how to build $E(x^y)=E(x)^{E(y)}$ ?

If it can't be done, is there a FHE that support $E(x) . E(y) = E(x^y)$ where the operation on encrypted data is not necessarily exponentiation?

• If you know the maximum number of bits in $y$, you can get the binary expansion of $y$ and then do the traditional square-and-multiply. – mikeazo Feb 27 '15 at 2:58
• – Thomas Feb 27 '15 at 5:12
• Calculating $y-1$ times the product $E(x)E(x)$ gives us $E(x)^{E(y)}$. And it decrypts to $x^y$, since $E(x) \cdot E(x) \cdot .. \cdot E(x) = E(x \cdot x \cdot .. \cdot x) = E(x^y)$. – Hilder Vitor Lima Pereira Feb 27 '15 at 16:14
• @VitorLima, the problem with "y-1 times the product E(x)E(x)" is that you don't know when you reach zero, i.e., you don't know when to stop. This question is very related to this discussion. – mikeazo Feb 27 '15 at 20:36
• @VitorLima I don't think you need to know $y$ to do what you suggested, if encryption is FHE, you can do $E(y-1)$. I think the point mikeazo was making is that at some point, you will get E(0), however, due to semantic security, you wouldn't be able to tell E(0) from E(something else). – nullgraph Feb 27 '15 at 21:35