On the Minimal Number of Bootstrappings in Homomorphic Circuits

Tancrède Lepoint 1, 2, 3 Pascal Paillier 3
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We propose a method to compute the exact minimal number of bootstrappings required to homomorphically evaluate any circuit. Given a circuit (typically over although our method readily extends to circuits over any ring), the maximal noise level supported by the considered fully homomorphic encryption (FHE) scheme and the desired noise level of circuit inputs and outputs, our algorithms return a minimal subset of circuit variables such that boostrapping these variables is enough to perform an evaluation of the whole circuit. We introduce a specific algorithm for 2-level encryption (first generation of FHE schemes) and an extended algorithm for ℓ max -level encryption with arbitrary ℓ max ≥ 2 to cope with more recent FHE schemes. We successfully applied our method to a range of real-world circuits that perform various operations over plaintext bits. Practical results show that some of these circuits benefit from significant improvements over the naive evaluation method where all multiplication outputs are bootstrapped. In particular, we report that a circuit for the AES S-box put forward by Boyar and Peralta admits a solution in 17 bootstrappings instead of 32, thereby leading to a 88% faster homomorphic evaluation of AES for any 2-level FHE scheme.
Type de document :
Communication dans un congrès
Adams, Andrew A. and Brenner, Michael and Smith, Matthew. Workshop on Applied Homomorphic Cryptography, Apr 2013, Okinawa, Japan. Springer, 7862, pp.189-200, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-41320-9_13〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00872833
Contributeur : Tancrède Lepoint <>
Soumis le : lundi 14 octobre 2013 - 14:49:16
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Tancrède Lepoint, Pascal Paillier. On the Minimal Number of Bootstrappings in Homomorphic Circuits. Adams, Andrew A. and Brenner, Michael and Smith, Matthew. Workshop on Applied Homomorphic Cryptography, Apr 2013, Okinawa, Japan. Springer, 7862, pp.189-200, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-41320-9_13〉. 〈hal-00872833〉

Partager

Métriques

Consultations de la notice

227