Paper 2016/785

Optimization of Bootstrapping in Circuits

Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, and Hang Zhou


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 _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$.

Note: 2016-11-17: publication information + minor editorial improvements

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. SODA 2017
DAGcircuitapproximation algorithmsinapproximabilitylinear programmingroundingfully homomorphic encryption (FHE)
Contact author(s)
fabrice benhamouda @ ens fr
2016-11-17: revised
2016-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabrice Benhamouda and Tancrède Lepoint and Claire Mathieu and Hang Zhou},
      title = {Optimization of Bootstrapping in Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2016/785},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.