Paper 2018/622

New techniques for Multi-value input Homomorphic Evaluation and Applications

Sergiu Carpov, Malika Izabachène, and Victor Mollimard


In this paper, we propose a new technique to perform several homomorphic operations in one bootstrapping call over a multi-value plaintext space. Our construction relies on the FHEW-based gate bootstrapping; we analyze its structure and propose a strategy we call multi-value bootstrapping which allows to bootstrap an arbitrary function in an efficient way. The security of our scheme relies on the LWE assumption over the torus. We give three possible applications: we first describe how to efficiently evaluate an arbitrary boolean function (LUT) and combine LUTs in circuits. We also explain how to apply our procedure to optimize the circuit bootstrapping from (Asiacrypt'2017) which allows to compose circuits in a leveled mode. And we finally present a simple method which makes use of the multi-value bootstrapping to evaluate a encrypted neural network. We have implemented the proposed method and were able to evaluate an arbitrary 6-to-6 LUTs under 1.6 seconds. Our implementation is based on the TFHE library but can be easily integrated into other homomorphic libraries based on the same structure, such as FHEW (Eurocrypt'2015). The number of LUT outputs does not influence the execution time by a lot, e.g. evaluation of additional 128 outputs on the same 6 input bits takes only 0.05 more seconds.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.CT-RSA 2019
lwe-based FHEmulti-value bootstrappinghomomorphic LUT
Contact author(s)
sergiu carpov @ cea fr
malika izabachene @ cea fr
victor mollimard @ ens-lyon fr
2019-03-09: revised
2018-06-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sergiu Carpov and Malika Izabachène and Victor Mollimard},
      title = {New techniques for Multi-value input Homomorphic Evaluation and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2018/622},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.