Cryptanalysis of a homomorphic encryption scheme from ISIT 2008

Jingguo Bi 1, 2 Mingjie Liu 1 Xiaoyun Wang 2, 1
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : At ISIT 2008, Aguilar Melchor, Castagnos and Gaborit presented a lattice-based homomorphic encryption scheme (abbreviated as MCG). Its security is based on the Computational Knapsack Vector Problem. In this paper, we explore a secret linear relationship between the public keys and the secret keys, which can be used to construct a reduced-dimension lattice, and then we obtain a group of equivalent private keys by solving the Closest Vector Problem of the lattice. Moreover, our attack is practical on all the three settings of recommended parameters, and the running time to recover the equivalent private keys is only several hours on a single PC.
Type de document :
Communication dans un congrès
ISIT 2012 - IEEE International Symposium on Information Theory, Jul 2012, Cambridge, United States. IEEE, pp.2152 - 2156, 2012, Proceedings of the 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, USA, July 1-6, 2012. 〈10.1109/ISIT.2012.6283832〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00922226
Contributeur : Phong Q. Nguyen <>
Soumis le : mercredi 25 décembre 2013 - 09:52:31
Dernière modification le : vendredi 25 mai 2018 - 12:02:06

Identifiants

Collections

Citation

Jingguo Bi, Mingjie Liu, Xiaoyun Wang. Cryptanalysis of a homomorphic encryption scheme from ISIT 2008. ISIT 2012 - IEEE International Symposium on Information Theory, Jul 2012, Cambridge, United States. IEEE, pp.2152 - 2156, 2012, Proceedings of the 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, USA, July 1-6, 2012. 〈10.1109/ISIT.2012.6283832〉. 〈hal-00922226〉

Partager

Métriques

Consultations de la notice

306