标题：Provably Secure NTRUEncrypt over Any Cyclotomic Field
作者：Wang, Yang ;Wang, Mingqiang
作者机构：[Wang, Y] School of Mathematics, Shandong University, Jinan, Shandong 250100, China;[ Wang, M] School of Mathematics, Shandong University, Jinan, Sha 更多
会议名称：25th International Conference on Selected Areas in Cryptography, SAC 2018
会议日期：15 August 2018 through 17 August 2018
来源：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
关键词：Canonical embedding; Cyclotomic fields; Ideal lattices; NTRU; Ring-LWE
摘要：NTRUEncrypt is generally recognized as one of candidate encryption schemes for post quantum cryptography, due to its moderate key sizes, remarkable performance and potential capacity of resistance to quantum computers. However, the previous provably secure NTRUEncrypts are only based on prime-power cyclotomic rings. Whether there are provably secure NTRUEncrypt schemes over more general algebraic number fields is still an open problem. In this paper, we answer this question and present a new provably IND-CPA secure NTRUEncrypt over any cyclotomic field. The security of our scheme is reduced to a variant of learning with errors problem over rings (Ring-LWE). More precisely, the security of our scheme is based on the worst-case approximate shortest independent vectors problem (SIVP) over ideal lattices. We prove that, once the field is fixed, the bounds of the reduction parameter and the modulus q in our scheme are less dependent on the choices of plaintext spaces. This leads to that our scheme provides more flexibility for the choices of plaintext spaces with higher efficiency under stronger security assumption. Furthermore, the probability that the decryption algorithm of our scheme fails to get the correct plaintext is much smaller than that of the previous works. © 2019, Springer Nature Switzerland AG.