Cryptanalysis of a homomorphic encryption scheme over integers. (English) Zbl 1379.94031

Bi, Jingguo; Liu, Jiayang; Wang, Xiaoyun

Chen, Kefei (ed.) et al., Information security and cryptology. 12th international conference, Inscrypt 2016, Beijing, China, November 4–6, 2016. Revised selected papers. Cham: Springer (ISBN 978-3-319-54704-6/pbk; 978-3-319-54705-3/ebook). Lecture Notes in Computer Science 10143, 243-252 (2017).

Summary: In [Eurocrypt 2010, Lect. Notes Comput. Sci. 6110, 24–43 (2010; Zbl 1279.94130)] M. van Dijk et al. described a fully homomorphic encryption scheme (abbreviated as DGHV) over integers. It is conceptually simple but the public key size is large. After DGHV scheme was proposed, many variants of DGHV schemes with smaller public key size were proposed. In this paper, we present a multi-ciphertexts attack on a variant of the DGHV scheme with much smaller public key (abbreviated as \(HE^{RK}\)), which was proposed by Y. Govinda Ramaiah and G. Vijaya Kumari [“Efficient public key generation for homomorphic encryption over the integers”, in: Proceedings of the 3rd international conference on advances in communication, network, and computing, CNC 2012. Lect. Notes Inst. Comput. Sci. Social Inf. Telecommun. Eng. (LNICST) 108, 262–268 (2012; doi:10\.1007/978-3-642-35615-5_40)]. Multi-ciphertexts attack considers the security of the schemes when the attacker captures a certain amount of ciphertexts. It is a common phenomena that the attacker can easily obtain enough ciphertexts in most of practical applications of fully homomorphic encryptions (even for public-key schemes). For all the four groups of the recommended parameters of \(HE^{RK}\), we can recover the plaintexts successfully if we only capture five ciphertexts. Our attack only needs to apply LLL algorithm

•  Wikipedia
•  Wolfram MathWorld

twice on two small dimension lattices, and the data show that the plaintexts can be recovered in seconds.
For the entire collection see [Zbl 1358.94004].

MSC:

94A60	Cryptography
11Y16	Number-theoretic algorithms; complexity

Keywords:

homomorphic encryption; LLL algorithm; multi-ciphertexts attack; lattice; cryptanalysis

Citations:

Zbl 1279.94130

Software:

NTL; fhe; fpLLL

References:

[1]	Alperin-Sheriff, J., Peikert, C.: Faster bootstrapping with polynomial error. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 297–314. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-44371-2_17 · Zbl 1336.94034 · doi:10.1007/978-3-662-44371-2_17
[2]	Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: FOCS 2011 · Zbl 1292.94038 · doi:10.1109/FOCS.2011.12
[3]	Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-22792-9_29 · Zbl 1290.94051 · doi:10.1007/978-3-642-22792-9_29
[4]	Cheon, J.H., Coron, J.-S., Kim, J., Lee, M.S., Lepoint, T., Tibouchi, M., Yun, A.: Batch fully homomorphic encryption over the integers. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 315–335. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-38348-9_20 · Zbl 1306.94040 · doi:10.1007/978-3-642-38348-9_20
[5]	Cohn, H., Heninger, N.: Approximate common divisors via lattices, Cryptology ePrint Archive, Report 2011/437 (2011). http://eprint.iacr.org/
[6]	Coron, J.-S., Lepoint, T., Tibouchi, M.: Scale-invariant fully homomorphic encryption over the integers. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 311–328. Springer, Heidelberg (2014). doi: 10.1007/978-3-642-54631-0_18 · Zbl 1335.94041 · doi:10.1007/978-3-642-54631-0_18
[7]	Coron, J.-S., Mandal, A., Naccache, D., Tibouchi, M.: Fully homomorphic encryption over the integers with shorter public keys. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 487–504. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-22792-9_28 · Zbl 1290.94059 · doi:10.1007/978-3-642-22792-9_28
[8]	Chen, Y., Nguyen, P.Q.: Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 502–519. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29011-4_30 · Zbl 1297.94059 · doi:10.1007/978-3-642-29011-4_30
[9]	Coron, J.-S., Naccache, D., Tibouchi, M.: Public key compression and modulus switching for fully homomorphic encryption over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 446–464. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29011-4_27 · Zbl 1297.94062 · doi:10.1007/978-3-642-29011-4_27
[10]	Cad \[ \acute{e} \] , D., Pujol, X., Stehl \[ \acute{e} \] , D.: FPLLL library, version 3.0, Sep 2008. http://perso.ens-lyon.fr/damien.stehle
[11]	Cheon, J.H., Stehlé, D.: Fully homomophic encryption over the integers revisited. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 513–536. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46800-5_20 · Zbl 1370.94496 · doi:10.1007/978-3-662-46800-5_20
[12]	Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13190-5_2 · Zbl 1279.94130 · doi:10.1007/978-3-642-13190-5_2
[13]	Gentry, C.: A fully homomorphic encryption scheme. Ph.D. Thesis, Stanford University (2009). http://crypto.stanford.edu/craig · Zbl 1304.94059
[14]	Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178. ACM, New York (2009) · Zbl 1304.94059 · doi:10.1145/1536414.1536440
[15]	Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-14623-7_7 · Zbl 1280.94059 · doi:10.1007/978-3-642-14623-7_7
[16]	Gentry, C., Halevi, S.: Implementing gentry’s fully-homomorphic encryption scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 129–148. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-20465-4_9 · Zbl 1281.94026 · doi:10.1007/978-3-642-20465-4_9
[17]	Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40041-4_5 · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5
[18]	Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 51–66. Springer, Heidelberg (2001). doi: 10.1007/3-540-44670-2_6 · Zbl 1006.94528 · doi:10.1007/3-540-44670-2_6
[19]	Lenstra, A.K., Lenstra Jr., H.W., Lov \[ \acute{a} \] sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982) · Zbl 0488.12001 · doi:10.1007/BF01457454
[20]	Nguyen, P., Stern, J.: Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 198–212. Springer, Heidelberg (1997). doi: 10.1007/BFb0052236 · Zbl 0882.94025 · doi:10.1007/BFb0052236
[21]	Nguyen, P.Q., Stehl \[ \acute{e} \] , D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874–903 (2009) · Zbl 1214.11139 · doi:10.1137/070705702
[22]	Rivest, R., Adleman, L., Dertouzos, M.: On data banks and privacy homomor- phisms. In: Foundations of Secure Computation, pp. 169–180 (1978)
[23]	Ramaiah, Y.G., Kumari, G.V.: Efficient public key generation for homomorphic encryption over the integers. In: Das, V.V., Stephen, J. (eds.) CNC 2012. LNICSSITE, vol. 108, pp. 262–268. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-35615-5_40 · doi:10.1007/978-3-642-35615-5_40
[24]	Ramaiah, Y.G., Kumari, G.V.: Towards practical homomorphic encryption with efficient public key generation, pp. 10–17. ACEEE Int. J. Netw. Secur. 03(04), 1–8 (2012)
[25]	Shoup, V.: NTL, Number Theory C++ Library. http://www.shoup.net/ntl/
[26]	Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13013-7_25 · Zbl 1281.94055 · doi:10.1007/978-3-642-13013-7_25