Cryptology ePrint Archive: Report 2015/127

Adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes

Ricardo Dahab and Steven Galbraith and Eduardo Morais

Abstract: In this paper we present adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes. Among such schemes, we study the proposal by Bos et al [BLLN13] in 2013. Given access to a decryption oracle, the attack allows us to compute the private key for all parameter choices. Such attacks show that one must be very careful about the use of homomorphic encryption in practice. The existence of a key recovery attack means that the scheme is not CCA1-secure. Indeed, almost every somewhat homomorphic construction proposed till now in the literature is vulnerable to an attack of this type. Hence our result adds to a body of literature that shows that building CCA1-secure homomorphic schemes is not trivial.

Category / Keywords: public-key cryptography / NTRU-based homomorphic encryption, adaptive key recovery attack

Original Publication (in the same form): Accepted to the conference ICITS 2015

Date: received 17 Feb 2015

Contact author: eduardo morais at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150226:120818 (All versions of this report)

Short URL: ia.cr/2015/127