  In 2009, Gentry proposed the first Fully Homomorphic Encryption (FHE) scheme,
an extremely powerful cryptographic primitive that enables to perform
computations, i.e., to evaluate circuits, on encrypted data without decrypting
them first. This has many applications, in particular in cloud computing.
  In all currently known FHE schemes, encryptions are associated to some
(non-negative integer) noise level, and at each evaluation of an AND gate, the
noise level increases. This is problematic because decryption can only work if
the noise level stays below some maximum level $L$ at every gate of the
circuit. To ensure that property, it is possible to perform an operation called
\emph{bootstrapping} to reduce the noise level. However, bootstrapping is
time-consuming and has been identified as a critical operation. This motivates
a new problem in discrete optimization, that of choosing where in the circuit
to perform bootstrapping operations so as to control the noise level; the goal
is to minimize the number of bootstrappings in circuits.
  In this paper, we formally define the \emph{bootstrap problem}, we design a
polynomial-time $L$-approximation algorithm using a novel method of rounding of
a linear program, and we show a matching hardness result:
$(L-\epsilon)$-inapproximability for any $\epsilon>0$.
