The main bottleneck of all known Fully Homomorphic Encryption schemes lies in the bootstrapping procedure invented by Gentry (STOC’09). The cost of this procedure can be mitigated either using Homomorphic SIMD techniques, or by performing larger computation per bootstrapping procedure.

In this work, we propose new techniques allowing to perform more operations per bootstrapping in FHEW-type schemes (EUROCRYPT’13). While maintaining the quasi-quadratic Õ(n2) complexity of the whole cycle, our new scheme allows to evaluate gates with Ω(log n) input bits, which constitutes a quasi-linear speed-up. Our scheme is also very well adapted to large threshold gates, natively admitting up to Ω(n) inputs. This could be helpful for homomorphic evaluation of neural networks.

Our theoretical contribution is backed by a preliminary prototype implementation, which can perform 6-to-6 bit gates in less than 10s on a single core, as well as threshold gates over 63 input bits even faster.

, , ,
Chair of Naval Cyber Defense & Lab-STICC/CID/IRISBrestFrance
Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence , Lecture Notes in Computer Science
International Conference on Cryptology in Africa
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Bonnoron, G., Ducas, L., & Fillinger, M. (2018). Large FHE Gates from tensored homomorphic accumulator. In AFRICACRYPT 2018: Progress in Cryptology – AFRICACRYPT 2018 (pp. 217–251). doi:10.1007/978-3-319-89339-6_13