Paper 2013/075

Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme

Joppe W. Bos, Kristin Lauter, Jake Loftus, and Michael Naehrig

Abstract

In 1996, Hoffstein, Pipher and Silverman introduced an efficient lattice based encryption scheme dubbed NTRUEnc. Unfortunately, this scheme lacks a proof of security. However, in 2011, Stehle and Steinfeld showed how to modify NTRUEnc to reduce security to standard problems in ideal lattices. In 2012, Lopez-Alt, Tromer and Vaikuntanathan proposed a fully homomorphic scheme based on this modified system. However, to allow homomorphic operations and prove security, a non-standard assumption is required. In this paper, we show how to remove this non-standard assumption via techniques introduced by Brakerski and construct a new fully homomorphic encryption scheme from the Stehle and Steinfeld version based on standard lattice assumptions and a circular security assumption. The scheme is scale-invariant and therefore avoids modulus switching and the size of ciphertexts is one ring element. Moreover, we present a practical variant of our scheme, which is secure under stronger assumptions, along with parameter recommendations and promising implementation results. Finally, we present an approach for encrypting larger input sizes by extending ciphertexts to several ring elements via the CRT on the message space.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. FOURTEENTH IMA INTERNATIONAL CONFERENCE ON CRYPTOGRAPHY AND CODING
Keywords
Leveled homomorphic encryptionfully homomorphic encryptionring learning with errors
Contact author(s)
mnaehrig @ microsoft com
History
2013-09-30: revised
2013-02-20: received
See all versions
Short URL
https://ia.cr/2013/075
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/075,
      author = {Joppe W.  Bos and Kristin Lauter and Jake Loftus and Michael Naehrig},
      title = {Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2013/075},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/075}},
      url = {https://eprint.iacr.org/2013/075}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.