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 _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 _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$.Category / Keywords: public-key cryptography / DAG, circuit, approximation algorithms, inapproximability, linear programming, rounding, fully homomorphic encryption (FHE) Original Publication (in the same form): SODA 2017 Date: received 16 Aug 2016, last revised 17 Nov 2016 Contact author: fabrice benhamouda at ens fr Available format(s): PDF | BibTeX Citation Note: 2016-11-17: publication information + minor editorial improvements Version: 20161117:145319 (All versions of this report) Short URL: ia.cr/2016/785 Discussion forum: Show discussion | Start new discussion