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 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 quantum worst-case hardness of classical problems over ideal lattices. Recently, Yu, Xu and Wang constructed pNE variants over prime cyclotomic rings. In this paper, we further extend the previous results to the case of general prime power cyclotomic rings, which allows a more flexible choice of parameters. We discover a potential trade-off between the power exponent of the ring order and the minimal magnitude of modulus.
Moreover, we discuss the case of pNE over general rings assuming the hardness of corresponding RLWE, and propose three attributes of the ring mattering to parameter selection.
Category / Keywords: public-key cryptography / Lattice-based cryptography, NTRU, Learning With Errors, Provable security.
Date: received 5 Apr 2017
Contact author: y-y13 at mails tsinghua edu cn
Available format(s): PDF | BibTeX Citation
Version: 20170410:135341 (All versions of this report)
Short URL: ia.cr/2017/304
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]