Minimizing the Number of Bootstrappings in Fully Homomorphic Encryption
| Autor: | Marie Paindavoine, Bastien Vialla |
|---|---|
| Přispěvatelé: | Orange Labs [Caen], Orange Labs, Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Exact Computing (ECO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), ANR-11-BS02-0013,HPAC,Calcul Algébrique Haute-Performance(2011), ANR-12-BS02-0001,CATREL,Cribles: Améliorations Théoriques et Résolution Effective du Logarithme Discret.(2012) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Homomorphic secret sharing
Theoretical computer science Linear programming Bootstrapping Homomorphic encryption Reduction (complexity) [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Fully Homomorphic Encryption Complexity Analysis Mixed Integer Linear Programming Simple (abstract algebra) Boolean satisfiability problem Mathematics Electronic circuit |
| Zdroj: | 22nd International Conference on Selected Areas in Cryptography SAC: Selected Areas in Cryptography SAC: Selected Areas in Cryptography, Aug 2015, Sackville, NB, Canada. pp.25-43, ⟨10.1007/978-3-319-31301-6_2⟩ Lecture Notes in Computer Science ISBN: 9783319313009 SAC |
| DOI: | 10.1007/978-3-319-31301-6_2⟩ |
| Popis: | International audience; There has been great progress regarding efficient implementations of fully homomorphic encryption schemes since the first construction by Gentry. However, evaluating complex circuits is still undermined by the necessary resort to the bootstrapping procedure. Minimizing the number of times such procedure is called is a simple yet very efficient way to critically improve performances of homomorphic evaluations. To tackle this problem, a first solution has been proposed in 2013 by Lepoint and Paillier, using boolean satisfiability. But their method cannot handle the versatility of fully homomorphic encryption schemes. In this paper, we go one step forward providing two main contributions. First, we prove that the problem of minimizing bootstrapping is NP-complete with a reduction from a graph problem. Second, we propose a flexible technique that permits to determine both such minimal number of bootstrappings and where to place them in the circuit. Our method is mainly based on linear programming. Our result can advantageously be applied to existing constructions. As an example, we show that for the Smart-Tillich AES circuit, published on the Internet in 2012, we find about 70% less bootstrappings than naive methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|