M.: Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme

Abstract. In 1996, Hoffstein, Pipher and Silverman introduced an ef-ficient lattice based encryption scheme dubbed NTRUEncrypt. Unfortu-nately, this scheme lacks a proof of security. However, in 2011, Stehlé and Steinfeld showed how to modify NTRUEncrypt to reduce security to standard problems in ideal lattices. In 2012, López-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 assump-tions 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 rec-ommendations 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.