Cryptology ePrint Archive: Report 2013/075

Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme

Joppe W. Bos and Kristin Lauter and 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.

Category / Keywords: public-key cryptography / Leveled homomorphic encryption, fully homomorphic encryption, ring learning with errors

Original Publication (with major differences): FOURTEENTH IMA INTERNATIONAL CONFERENCE ON CRYPTOGRAPHY AND CODING

Date: received 15 Feb 2013, last revised 30 Sep 2013

Contact author: mnaehrig at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20130930:221441 (All versions of this report)

Short URL: ia.cr/2013/075

Discussion forum: Show discussion | Start new discussion