Fully Homomorphic Encryption: Going from an integer to bits I was answering this question Computing Logarithm using homomorphic encryption and I came up with a solution if you had encryptions of the bits of the number that you wanted to take the log of.  But in that situation all they have is a fully homomorphic encryption of the number itself.

I was curious if there was a way to compute encryptions of the bits from an encryption of the number.  i.e. is there some $f$ such that $f(E(x)) = (E(x_1),E(x_2),...,E(x_n))$ where $x_i$ is the $i$th bit of x?
One possible solution for you is to use a Bit Extraction Circuit. The references are framed in terms of MPC but they should be applicable. If you want something more specific/efficient to homomorphic encryption, it will depend on the scheme.


O. Catrina and S. Hoogh, “Improved primitives for secure multiparty
integer computation,” in Security and Cryptography for Networks
(SCN’10), ser. LNCS, vol. 6280. Springer, 2010, pp. 182–199.
O. Catrina and A. Saxena, “Secure computation with fixed-point
numbers,” in Financial Cryptography and Data Security (FC’10), ser.
LNCS, vol. 6052. Springer, 2010, pp. 35–50.
I. Damgard, M. Fitzi, E. Kiltz, J. B. Nielsen, and T. Toft, “Unconditionally secure constant-rounds multi-party computation for equality,
comparison, bits and exponentiation,” in TCC’06, ser. LNCS, vol. 3876.
Springer, 2006, pp. 285–304.