Cryptology ePrint Archive: Report 2014/898

A key recovery attack to the scale-invariant NTRU-based somewhat homomorphic encryption scheme

Eduardo Morais and Ricardo Dahab

Abstract: In this paper we present a key recovery attack to the scale-invariant NTRU-based somewhat homomorphic encryption scheme proposed by Bos et al~\cite{NTRUbasedFHE} in 2013. The attack allows us to compute the private key for $t>2$ and when the private key is chosen with coefficients in $\{-1,0,1\}$. The efficiency of the attack is optimal since it requires just one decryption oracle query, showing that if we don't look for this kind of vulnerabilities in homomorphic encryption constructions we are likely to choose insecure parameters. 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 this kind of attack, hence our result indicates that building CCA1-secure homomorphic schemes is not trivial. We also provide tables showing how the multiplicative depth is affected when the critical parameter $\Bkey$ is chosen in order to mitigatte the attack.

Category / Keywords: NTRU somewhat homomorphic scheme key recovery attack

Date: received 16 Oct 2014, last revised 12 Mar 2015

Contact author: eduardo morais at gmail com

Available format(s): PDF | BibTeX Citation

Note: A new paper was posted as report 2015/127 (https://eprint.iacr.org/2015/127), providing a complete analysis of NTRU-based SHE schemes with respect to key recovery attacks.

Version: 20150312:194835 (All versions of this report)

Short URL: ia.cr/2014/898

Discussion forum: Show discussion | Start new discussion