Paper 2016/315

Flattening NTRU for Evaluation Key Free Homomorphic Encryption

Yarkın Doröz and Berk Sunar


We propose a new FHE scheme {\sf 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 switching. Our scheme eliminates the decision small polynomial ratio (DSPR) assumption but relies only on the standard R-LWE assumption. It uses wide key distributions, and hence is immune to the Subfield Lattice Attack. In practice, our scheme achieves competitive timings compared to the existing schemes. We are able to compute a homomorphic multiplication in $24.4$~msec and $34.3$~msec for $5$ and $30$ levels, respectively, without amortization. Furthermore, our scheme features small ciphertexts, e.g. $1152$~KB for $30$ levels, and eliminates the need for storing and managing costly evaluation keys. In addition, we present a slightly modified version of F-NTRU that is capable to support integer operations with a very large message space along with noise analysis for all cases. The assurance gained by using wide key distributions along with the message space flexibility of the scheme, i.e. bits, binary polynomials, and integers with a large message space, allows the use of the proposed scheme in a wide array of applications.

Available format(s)
Publication info
Preprint. MINOR revision.
Homomorphic EncryptionFlatteningNTRUDSPRSubfield Lattice Attack
Contact author(s)
ydoroz @ wpi edu
2016-12-20: last of 3 revisions
2016-03-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yarkın Doröz and Berk Sunar},
      title = {Flattening NTRU for Evaluation Key Free Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2016/315},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.