zbMATH — the first resource for mathematics

On key recovery attacks against existing somewhat homomorphic encryption schemes. (English) Zbl 1370.94495
Aranha, F. (ed.) et al., Progress in cryptology – LATINCRYPT 2014. Third international conference on cryptology and information security in Latin America, Florian√≥polis, Brazil, September 17–19, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-16294-2/pbk; 978-3-319-16295-9/ebook). Lecture Notes in Computer Science 8895, 239-258 (2015).
Summary: In his seminal paper at STOC 2009, C. Gentry [Proc. 41st annual ACM symposium on theory of computing. New York, NY: ACM, 169–178 (2009; Zbl 1304.94059)] left it as a future work to investigate (somewhat) homomorphic encryption schemes with IND-CCA1 security. At SAC 2011, J. Loftus et al. [Lect. Notes Comput. Sci. 7118, 55–72 (2012; Zbl 1292.94106)] showed an IND-CCA1 attack against the somewhat homomorphic encryption scheme presented by C. Gentry and S. Halevi at Eurocrypt 2011 [Lect. Notes Comput. Sci. 6632, 129–148 (2011; Zbl 1281.94026)]. At ISPEC 2012, Zhang, Plantard and Susilo [Z. Zhang et al., Lect. Notes Comput. Sci. 7232, 353–368 (2012; Zbl 1291.94176)] showed an IND-CCA1 attack against the somewhat homomorphic encryption scheme developed by M. van Dijk et al. at Eurocrypt 2010 [Lect. Notes Comput. Sci. 6110, 24–43 (2010; Zbl 1279.94130)].
In this paper, we continue this line of research and show that most existing somewhat homomorphic encryption schemes are not IND-CCA1 secure. In fact, we show that these schemes suffer from key recovery attacks (stronger than a typical IND-CCA1 attack), which allow an adversary to recover the private keys through a number of decryption oracle queries. The schemes, that we study in detail, include those by Z. Brakerski and V. Vaikuntanathan at Crypto 2011 [Lect. Notes Comput. Sci. 6841, 505–524 (2011; Zbl 1290.94051) and Efficient fully homomorphic encryption from (standard) LWE. In: Proc. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, 97–106 (2011)], and that by Gentry, Sahai and Waters at Crypto 2013 [C. Gentry et al., Lect. Notes Comput. Sci. 8042, 75–92 (2013; Zbl 1310.94148)]. We also develop a key recovery attack that applies to the somewhat homomorphic encryption scheme by van Dijk et al. (loc. cit.), and our attack is more efficient and conceptually simpler than the one developed by Zhang et al. (loc. cit.). Our key recovery attacks also apply to the scheme by Brakerski, Gentry and Vaikuntanathan at ITCS 2012 [Z. Brakerski et al., Proc. 3rd conference on innovations in theoretical computer science, ITCS 2012, New York, NY: ACM, 309–325 (2012; Zbl 1347.68120) and ACM Trans. Comput. Theory 6, No. 3, Article No. 13, 36 p. (2014; Zbl 1347.68121)], and we also describe a key recovery attack for the scheme developed by Z. Brakerski at Crypto 2012 [Lect. Notes Comput. Sci. 7417, 868–886 (2012; Zbl 1296.94091)].
For the entire collection see [Zbl 1319.94001].

94A60 Cryptography
Full Text: DOI