International Association
for Cryptologic Research

In less than a decade fully homomorphic encryption has made significant advances. Despite all these improvements it is quite a challenge to reduce the parameter sizes and specifically evaluation keys. Eliminating the need for such prohibitively large evaluation keys and expensive noise management techniques has become a significant thrust among homomorphic encryption researchers. In a notable attempt, Gentry, Sahai, and Waters (GSW) introduced a scheme based on the approximate eigenvector problem that eliminates evaluation keys and costly key switching operations. In another very recent development, the Subfield Lattice Attack was introduced by Albrecht, Bai, and Ducas showing that the asymptotic security level with narrow key distributions may be far less than assumed in NTRU based FHE proposals. In this paper, we propose a new FHE scheme F-NTRU that adopts the flattening technique proposed in GSW to derive an NTRU based scheme that (similar to GSW) does not require evaluation keys or key switch- ing. Our scheme eliminates the decision small polynomial ratio (DSPR) assumption but relies only on the standard R-LWE assumption. Our scheme uses wide key distributions, and hence is immune to the Subfield Lattice Attack. We provide implementation results which show reason- able evaluation times compared to existing schemes while eliminating the need for storing and managing costly evaluation keys.