  Fully homomorphic encryption (FHE) allows an untrusted party to evaluate
arithmetic cir- cuits, i.e., perform additions and multiplications on encrypted
data, without having the decryp- tion key. One of the most efficient class of
FHE schemes include BGV and FV schemes, which are based on the hardness of the
RLWE problem. They share some common features: ciphertext sizes grow after each
homomorphic multiplication; multiplication is much more costly than addition,
and the cost of homomorphic multiplication scales linearly with the input
ciphertext sizes. Furthermore, there is a special relinearization operation
that reduce the size of a ciphertext, and the cost of relinearization is on the
same order of magnitude as homomorpic multiplication. This motivates us to
define a discrete optimization problem, which is to decide where (and how much)
in a given circuit to relinearize, in order to minimize the total computational
cost. In this paper, we formally define the relinearize problem. We prove that
the problem is NP-hard. In addition, in the special case where each vertex has
at most one outgoing edge, we give a polynomial-time algorithm.
