Paper 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 $$ is chosen in order to mitigatte the attack.

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.