You are provided with the abstract of a scientific paper and the abstracts of the papers it references. Your task is to write a Related Work section for the main paper. This section should concisely summarize and integrate the key points from the cited abstracts, reflecting how they relate to the main paper's contributions and context. In your summary, use numerical citation markers like [1], [2], etc., to refer to the corresponding papers.

Main Abstract:
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.

Cited Abstract(s):
[1]: 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 @math at every gate of the circuit. To ensure that property, it is possible to perform an operation called 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 , we design a polynomial-time @math -approximation algorithm using a novel method of rounding of a linear program, and we show a matching hardness result: @math -inapproximability for any @math .

[2]: We propose a method to compute the exact minimal number of bootstrappings required to homomorphically evaluate any circuit. Given a circuit (typically over ( F _2 ) although our method readily extends to circuits over any ring), the maximal noise level supported by the considered fully homomorphic encryption (FHE) scheme and the desired noise level of circuit inputs and outputs, our algorithms return a minimal subset of circuit variables such that boostrapping these variables is enough to perform an evaluation of the whole circuit. We introduce a specific algorithm for 2-level encryption (first generation of FHE schemes) and an extended algorithm for l max -level encryption with arbitrary l max ≥ 2 to cope with more recent FHE schemes. We successfully applied our method to a range of real-world circuits that perform various operations over plaintext bits. Practical results show that some of these circuits benefit from significant improvements over the naive evaluation method where all multiplication outputs are bootstrapped. In particular, we report that a circuit for the AES S-box put forward by Boyar and Peralta admits a solution in 17 bootstrappings instead of 32, thereby leading to a 88 faster homomorphic evaluation of AES for any 2-level FHE scheme.

[3]: In this work we present Armadillo a compilation chain used for compiling applications written in a high-level language (C++) to work on encrypted data. The back-end of the compilation chain is based on homomorphic encryption. The tool-chain further automatically handle a huge amount of parallelism so as to mitigate the performance overhead of using homomorphic encryption.
The work [3] is an effort to find a good circuit representation of a function, in order to minimize the total computation time. Bootstrapping is an operation that refreshes the so-called noise in FHE ciphertexts. It is an essential yet expensive operation. The two papers [2] and [1] aim at minimizing the total number of bootstrapping operations in a circuit, while keeping the noise from overflowing in order to ensure the final result is correct. In their work, the authors implicitly assume the relinearization is done after every multiplication. Similarly, we will make a simplifying assumption that the boostrapping time is a constant, so that it does not factor into our optimizatoin problem. It will be interesting to combine these works in order to achieve an overall optimization that targets both operations. Acknowledgement The author thanks Rebecca Hoberg and Mohit Singh for helpful discussions in preparing this work. We modify the usual definition of the arithmetic circuits to include the squaring operations in FHE.