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$.

• You could try to compute the hyperbolic arctan instead using an approximation or CORDIC, then use the identity described in this question (stackoverflow.com/questions/25146321/…) to translate atanh to the natural log. – pg1989 Jun 21 '17 at 18:14
• I think that approximating the hyperbolic $arctan$ is the same as approximating $log$, there will be the same issue. As for CORDIC, I didn't go thoroughly into details, but it seems to me that this algorithm is quite costly in terms of needed operations to ensure the convergence. – Younes Jun 22 '17 at 0:23
• This is way off, but functionally speaking when I did enzyme assembly, we'd use the Lambert W function to solve something similar. – b degnan Jun 22 '17 at 0:46
• Maybe you can use some techniques from the MPC land. Say you have the encryption of the $a$'s bits: $E(a_0), \dots E(a_k)$ where $k=\log{a}$. Then you can obtain the $2$ base logarithm by taking the most significant bit i.e $E(\max(i \cdot a_i))$ where $a_i=1$. I guess you can extend this to different base logarithms. – Dragos Jun 22 '17 at 14:09
• Actually, it would be perfect if I can convert homomorphically $Enc(a)$, to the encryption of every single bit of the value of $a$ expressed in some base $b$ – Younes Jun 26 '17 at 19:01

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 "circuits" 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)$

• This solution seems to be efficient, but the context where I'm working does not allow me to provide the encryption of every bit of the message $x$, that's why i should compute $E(log(x))$ otherwise – Younes Jun 26 '17 at 18:55
• I'm wondering if it is possible to go from $E(x)$ to $E(x_1),E(x_2),...,E(x_n)$ using addition and multiplication. So I posted a new question Fully Homomorphic Encryption: Going from an integer to bits – edggy Jun 27 '17 at 15:30
• @edggy, are you sure that's how the bitwise addition and multiplication works? I think you need to simulate carries for the addition whereas for multiplication it is a bit more complicated. – Dragos Jun 27 '17 at 16:15
• @Dragos: Look at Introduction to Homomorphic Encryption. This is a good slideshow describing how to use homomorphic encryption to compute a binary circuit. Basically you map "0" to even integers and "1" to odd integers. Then "+" becomes the binary "xor" operator and "$\cdot$" becomes the binary "and" gate. You can create any logic circuit using only "xor" and "and" gates. – edggy Jun 27 '17 at 17:59
• I see. But I think @Younes was asking how would you implement the binary circuit which gives you bit-decomposed form of the logarithm. – Dragos Jun 27 '17 at 23:33