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?

  • 3
    $\begingroup$ 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. $\endgroup$ – mikeazo Feb 27 '15 at 2:58
  • 1
    $\begingroup$ crypto.stackexchange.com/questions/15436/…? $\endgroup$ – Thomas Feb 27 '15 at 5:12
  • $\begingroup$ 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)$. $\endgroup$ – Hilder Vitor Lima Pereira Feb 27 '15 at 16:14
  • 2
    $\begingroup$ @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. $\endgroup$ – mikeazo Feb 27 '15 at 20:36
  • 1
    $\begingroup$ @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). $\endgroup$ – nullgraph Feb 27 '15 at 21:35