Key Recovery Attacks Against NTRU-Based Somewhat Homomorphic Encryption Schemes

A key recovery attack allows an attacker to recover the pri-
vate key of an underlying encryption scheme when given a number of
decryption oracle accesses. Previous research has shown that most exist-
ing Somewhat Homomorphic Encryption (SHE) schemes su er from this
attack. In this paper, we propose e cient key recovery attacks against
two NTRU-based SHE schemes due to Lopez-Alt et al. (2012) and Bos et
al. (2013), which have not gained much attention in the literature. Paral-
lel to our work, Dahab, Galbraith and Morais (2015) have also proposed
similar attacks but only for speci c parameter settings. In comparison,
our attacks apply to all parameter settings and are more e cient.