10
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – pg1989
    Jun 21, 2017 at 18:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Younes
    Jun 22, 2017 at 0:23
  • $\begingroup$ This is way off, but functionally speaking when I did enzyme assembly, we'd use the Lambert W function to solve something similar. $\endgroup$
    – b degnan
    Jun 22, 2017 at 0:46
  • $\begingroup$ 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. $\endgroup$
    – Dragos
    Jun 22, 2017 at 14:09
  • $\begingroup$ 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$ $\endgroup$
    – Younes
    Jun 26, 2017 at 19:01

1 Answer 1

1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Younes
    Jun 26, 2017 at 18:55
  • $\begingroup$ 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 $\endgroup$
    – edggy
    Jun 27, 2017 at 15:30
  • $\begingroup$ @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. $\endgroup$
    – Dragos
    Jun 27, 2017 at 16:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – edggy
    Jun 27, 2017 at 17:59
  • $\begingroup$ I see. But I think @Younes was asking how would you implement the binary circuit which gives you bit-decomposed form of the logarithm. $\endgroup$
    – Dragos
    Jun 27, 2017 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.