Attack on Recent Homomorphic Encryption Scheme over Integers
At CDCIEM 2012, Yang et al. proposed a new construction of somewhat homomorphic encryption scheme over integers, which is quite efficient in the perspective of the key size. In this paper, we present an effective lattice reduction attack on Yang et al.’s
- PDF / 1,735,239 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 208 Views
Abstract At CDCIEM 2012, Yang et al. proposed a new construction of somewhat homomorphic encryption scheme over integers, which is quite efficient in the perspective of the key size. In this paper, we present an effective lattice reduction attack on Yang et al.’s scheme, where it is easy to recover the plaintext by applying LLL algorithm. Keywords Homomorphic encryption computing
LLL algorithm
Lattice
Cloud
1 Introduction Fully homomorphic encryption (FHE) can operate the arbitrary plaintext information homomorphically, just by operating ciphertexts, without decryption. However, how to construct an efficient FHE scheme has been still an open problem for over 30 years. In 2009, the old open problem was solved by the breakthrough work of Gentry [1]. At the same time, Gentry still gave a construction framework that a fully homomorphic scheme could be transformed from a ‘‘somewhat’’ homomorphic scheme.
H. Yang College of Computer Science and Engineering, UEST of China, Chengdu 610054, China H. Kim (&) Department of Cyber Security, Kyungil University, Kyungpook, Kyungsansi 712-701, Korea e-mail: [email protected] D. Tang Science and Technology on Communication Security Laboratory, Chengdu 610041, China
J. J. (Jong Hyuk) Park et al. (eds.), Multimedia and Ubiquitous Engineering, Lecture Notes in Electrical Engineering 240, DOI: 10.1007/978-94-007-6738-6_34, Springer Science+Business Media Dordrecht(Outside the USA) 2013
269
270
H. Yang et al.
Gentry’s somewhat scheme originally worked with ideal lattices. At 2010, Dijk et al. proposed a very simple somewhat homomorphic scheme only over the integers, which had owned merit of conceptual simplicity [2]. However, this simplicity came at the cost of public key size in O(k10). Although at 2011, Coron et al. reduced the public key size to O(k7), it was still too large for practical applications [3]. At 2012, Yang et al. further reduce the public key size to O(k3) by encrypting with a new form [4]. In this paper, based on LLL algorithm, we present an effective attack on Yang et al.’s scheme. Our attack shows that it is easy to recover the plaintext by using lattice reduction: it is a matter of applying LLL in a lattice of dimension 3.
2 Recent Somewhat Homomorphic Encryption Scheme For convenience, the same notations are used as in [4]. The construction of Yang et al.’s somewhat homomorphic encryption scheme is as follows. • KGðkÞ: Choose randomly an odd g-bit integer p 2 ½2g1 ; 2g Þ. Choose randomly four integers l0 ; l1 2 Z \ ð0; 2c =pÞ, h 0 ; h 1 2 ð2q ; 2q Þ. Compute xi ¼ pli þ 2hi ; i ¼ 0; 1. Assume that jx0 j [ jx1 j. Set public key pk ¼ hx0 ; x1 i, and secret key sk ¼ p. • Encðpk; mÞ: To encrypt a bit m 2 f0; 1g, choose randomly two integers r 2 q0 q0 2 ; 2 ; r1 2 ð2q ; 2q Þ and compute the ciphertext c ¼ m þ 2r þ r1 x1 mod x0 . • Evalðpk; C; ~ cÞ: The function is the same as in [2]. • Decðsk; cÞ: Output m ¼ ðc mod pÞ mod 2, where ðc mod pÞ is the integer in ðp=2; p=2Þ. To foil various attacks, a convenient parameter set is q ¼ k; q0 ¼ 2k;
Data Loading...
