On Constructing Homomorphic Encryption Schemes from Coding Theory

Frederik Armknecht 1 Daniel Augot 2, 3 Ludovic Perret 4 Ahmad-Reza Sadeghi 5
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
4 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We introduce a generic construction principle for homomorphic encryption schemes based on coding theory. These possess several non-standard positive features. First, they are not restricted to linear homomorphism but allow for evaluating multivariate polynomials up to a fixed (but arbitrary) degree μ on encrypted field elements. Second, they can be instantiated with various error correcting codes, even for codes with poor correcting capabilities. Third, depending on the deployed code, one can achieve very efficient schemes. As a concrete example, we present an instantiation based on Reed-Muller codes where for μ = 2 and μ = 3 and security levels between 80 and 128 bits, all operations take less than a second (after some pre-computation). However, our analysis reveals also limitations on this approach. For structural reasons, such schemes cannot be public-key, allow for a limited number of fresh encryptions only, and cannot be combined with the bootstrapping technique. We argue why such schemes are nonetheless useful in certain application scenarios and discuss possible directions on how to overcome these issues.
Type de document :
Communication dans un congrès
Liqun Chen. 13th IMA International Conference on Cryptography and Coding, Dec 2011, Oxford, United Kingdom. Springer, 7089, pp.23-40, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25516-8_3〉
Liste complète des métadonnées

Littérature citée [47 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00643774
Contributeur : Daniel Augot <>
Soumis le : mardi 22 novembre 2011 - 17:27:18
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 11:50:22

Fichier

CodeBasedHomEnc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frederik Armknecht, Daniel Augot, Ludovic Perret, Ahmad-Reza Sadeghi. On Constructing Homomorphic Encryption Schemes from Coding Theory. Liqun Chen. 13th IMA International Conference on Cryptography and Coding, Dec 2011, Oxford, United Kingdom. Springer, 7089, pp.23-40, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25516-8_3〉. 〈hal-00643774〉

Partager

Métriques

Consultations de la notice

625

Téléchargements de fichiers

617