Computing Logarithm using homomorphic encryption Let's say we have $Enc_{pub}(a)$, the encryption of an integer $a \in \mathbb{Z}^*$ under the public key pub with a Homomorphic encryption scheme that supports both addition and multiplication.

Is there an efficient way to compute $Enc_{pub}(log(a))$?

I tried with Taylor Series approximation, but this one won't work unless we have the Taylor  series of $log(x)$ about a point $b$ that is very close to $a$, which we cannot afford given that we don't know the value of $a$.
This answer is a bit messy, but it should work...

If we have access to a fully homomorphic encryption scheme $E(x)$ then we know that $E(x) + E(y) = E(x+y)$ and $E(x) \cdot E(y) = E(x \cdot y)$.

In addition we know that there exists an efficient Boolean circuit, $BC$, such that $BC(x_1,x_2,...,x_n) = y_1, y_2,...y_n$ where $x_i$ and $y_i$ are the bits of the binary string $x$ and $y$ respectively both of length $n$ and that $x = b^y$ for some base $b$.  Thus this is the circuit for $\log_b(x) = y$.

Now instead of being given $E(x)$ we can just as easily be given $E(x_1), E(x_2), ..., E(x_n)$.  When you want to encode a $0$ you map it to a random even number, $b$, then you encrypt that number, $E(b)$.  Likewise for $1$, except you map it to an even number.  Now all we do is evaluate the circuit and when we encounter an xor gate we do $E(I_1 \oplus I_2) = E(I_1) + E(I_2)$ and likewise for and gates $E(I_1 \wedge I_2) = E(I_1) \cdot E(I_2)$ where $I_1$ and $I_2$ are the inputs to the gate.  For all other gates convert them into $and$ and $xor$ gates.  At the end we will be left with $E(y_1), E(y_2),...,E(y_n)$ which is an encryption of the $\log_b(x)$.

One interesting benefit is that $x$ and $y$ could be represented in any way, not just a n-bit integer.  You would just need to use the correct circuit for the representation.  For example if $n = 64$ you could let $x_1,x_2,...,x_n$ be the IEEE 754 double-precision binary floating-point format representation of $x$ and with the correct circuit $y_1, y_2,...y_n$ would be a double-precision floating-point so you can do more precise calculations if you wanted.

See What does &quot;circuits&quot; mean in Cryptography? for more details on the Boolean circuit only using addition and multiplication.

Edit:

Since the question originally asked how to get from $E(x)$ to $E(log(x))$ and my answer only works if you have the bits and returns bits, I asked another question Fully Homomorphic Encryption: Going from an integer to bits to try to help.

They suggested using a Bit Extraction Circuit to go from $E(x)$ to $E(x_1), E(x_2), ..., E(x_n)$.  Then compute the above.  Now you have $E(y_1), E(y_2),...,E(y_n)$ which you can easily put back together by computing (assuming $y_1$ is the least significant bit) $E(log(x)) = E(y_1) + 2\cdot E(y_2) + 2^2\cdot E(y_3)+\dots+2^{n-1}\cdot E(y_n)$