A Successful Subfield Lattice Attack on a Fully Homomorphic Encryption Scheme

  • Martha Norberg Hovd


We present the application of a known subeld lattice attack on a fully homomorphic
encryption scheme based on NTRU. It is known that for this attack to be successful, a
parameter of the scheme must satisfy a lower bound. We derive a second lower bound
on the same parameter and show that this bound must be respected if the scheme is to
be functional, and furthermore that, in all practical instances of the scheme, the derived
second lower bound is greater than the lower bound required for the attack to be applicable.
Hence, the scheme is shown to be susceptible to the subeld lattice attack, and furthermore
that this susceptibility is inevitable given the current structure of the scheme.