Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems

Abstract : In lattice cryptography, worst-case to average-case reductions rely on two problems: Ajtai’s SIS and Regev’s LWE, which both refer to a very small class of random lattices related to the group G=Znq. We generalize worst-case to average-case reductions to all integer lattices of sufficiently large determinant, by allowing G to be any (sufficiently large) finite abelian group. Our main tool is a novel generalization of lattice reduction, which we call structural lattice reduction: given a finite abelian group G and a lattice L, it finds a short basis of some lattice L¯ such that L⊆L¯ and L¯/L≃G. Our group generalizations of SIS and LWE allow us to abstract lattice cryptography, yet preserve worst-case assumptions: as an illustration, we provide a somewhat conceptually simpler generalization of the Alperin-Sheriff-Peikert variant of the Gentry-Sahai-Waters homomorphic scheme. We introduce homomorphic mux gates, which allows us to homomorphically evaluate any boolean function with a noise overhead proportional to the square root of its number of variables, and bootstrap the full scheme using only a linear noise overhead.
Type de document :
Communication dans un congrès
Marc Fischlin; Jean-Sébastien Coron. 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part II - EUROCRYPT 2016, May 2016, Vienna, Austria. Springer, Lecture Notes in Computer Science, 9666, pp.528-558, Advances in Cryptology – EUROCRYPT 2016. 〈http://ist.ac.at/eurocrypt2016/〉. 〈10.1007/978-3-662-49896-5_19〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01382384
Contributeur : Phong Q. Nguyen <>
Soumis le : lundi 17 octobre 2016 - 06:54:29
Dernière modification le : vendredi 28 septembre 2018 - 04:28:03

Identifiants

Citation

Nicolas Gama, Malika Izabachène, Phong Q. Nguyen, Xiang Xie. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems. Marc Fischlin; Jean-Sébastien Coron. 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part II - EUROCRYPT 2016, May 2016, Vienna, Austria. Springer, Lecture Notes in Computer Science, 9666, pp.528-558, Advances in Cryptology – EUROCRYPT 2016. 〈http://ist.ac.at/eurocrypt2016/〉. 〈10.1007/978-3-662-49896-5_19〉. 〈hal-01382384〉

Partager

Métriques

Consultations de la notice

264