Paper 2017/304

Provably Secure NTRUEncrypt over More General Cyclotomic Rings

Yang Yu and Guangwu Xu and Xiaoyun Wang

Abstract

NTRUEncrypt is a fast and standardized lattice-based public key encryption scheme, but it lacks a solid security guarantee. In 2011, Stehlé and Steinfeld first proposed a provably secure variant of NTRUEncrypt, denoted by pNE, over power-of-2 cyclotomic rings. The IND-CPA security of pNE is based on the worst-case quantum hardness of classical problems over ideal lattices. Recently, Yu, Xu and Wang constructed a pNE variant over prime cyclotomic rings, but it requires the parameters to be of rather larger sizes. In this paper, working with canonical embedding, we modify the key generation algorithm of pNE scheme to make it applicable to general cyclotomic rings and provide asymptotical parameters of pNE over prime power cyclotomic rings. In particular, our result allows tighter parameters for prime cyclotomic rings and improves the existing result. Furthermore, we also discuss a generalization to more general polynomial rings and point out several attributes that affect the selection of parameters. This discussion may be of some value in choosing the underlying ring for cryptographic applications.