Cryptology ePrint Archive: Report 2018/622

New techniques for Multi-value input Homomorphic Evaluation and Applications

Sergiu Carpov and Malika Izabachène and Victor Mollimard

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

Category / Keywords: public-key cryptography / lwe-based FHE, multi-value bootstrapping, homomorphic LUT

Original Publication (with minor differences): CT-RSA 2019

Date: received 20 Jun 2018, last revised 9 Mar 2019

Contact author: sergiu carpov at cea fr,malika izabachene@cea fr,victor mollimard@ens-lyon fr

Available format(s): PDF | BibTeX Citation

Version: 20190309:144812 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]