Cryptanalysis of a homomorphic encryption scheme from ISIT 2008

Author

Bi, Jingguo ; Liu, Mingjie ; Wang, Xiaoyun

Author_Institution

Lab. of Cryptographic Technol. & Inf. Security, Shandong Univ., Jinan, China

fYear

2012

fDate

1-6 July 2012

Firstpage

2152

Lastpage

2156

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.

Keywords

knapsack problems; public key cryptography; Aguilar Melchor; Castagnos; Gaborit; ISIT 2008; computational knapsack vector problem; cryptanalysis; homomorphic encryption scheme; lattice-based homomorphic encryption; public keys; reduced-dimension lattice; secret keys; secret linear relationship; Educational institutions; Encryption; Lattices; Noise measurement; Public key; Vectors; Homomorphic encryption; Key-recovery attack; Lattice-based;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on

Conference_Location

Cambridge, MA

ISSN

2157-8095

Print_ISBN

978-1-4673-2580-6

Electronic_ISBN

2157-8095

Type

conf

DOI

10.1109/ISIT.2012.6283832

Filename

6283832