Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Phong Q. Nguyen Connect in order to contact the contributor
Submitted on : Wednesday, December 25, 2013 - 9:52:31 AM
Last modification on : Friday, January 21, 2022 - 3:14:57 AM




Jingguo Bi, Mingjie Liu, Xiaoyun Wang. Cryptanalysis of a homomorphic encryption scheme from ISIT 2008. ISIT 2012 - IEEE International Symposium on Information Theory, IEEE, Jul 2012, Cambridge, United States. pp.2152 - 2156, ⟨10.1109/ISIT.2012.6283832⟩. ⟨hal-00922226⟩



Record views