Cryptology ePrint Archive: Report 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 rst 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.

Category / Keywords: Lattice-based cryptography, NTRU, Learning With Errors, Provable security.

Date: received 5 Apr 2017, last revised 23 May 2017

Contact author: y-y13 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20170523:070411 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]