eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2017/996

Large FHE gates from Tensored Homomorphic Accumulator

Guillaume Bonnoron, Léo Ducas, and Max Fillinger


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 $\tilde O(n^2)$ complexity of the whole cycle, our new scheme allows to evaluate gates with $\Omega(\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 $\Omega(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 $10$ seconds on a single core, as well as threshold gates over $63$ input bits even faster.

Note: Africacrypt version

Available format(s)
Publication info
Published elsewhere. Minor revision. AFRICACRYPT 2018
Fully Homomorphic EncryptionLarge GatesThreshold GatesIdeal lattices
Contact author(s)
guillaume bonnoron @ imt-atlantique fr
2018-02-26: last of 2 revisions
2017-10-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Guillaume Bonnoron and Léo Ducas and Max Fillinger},
      title = {Large FHE gates from Tensored Homomorphic Accumulator},
      howpublished = {Cryptology ePrint Archive, Paper 2017/996},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/996}},
      url = {https://eprint.iacr.org/2017/996}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.