Provably Secure NTRU Instances over Prime Cyclotomic Rings

详细信息    查看全文

• 关键词：Lattice ; based cryptography ; NTRU ; Learning with errors ; Provable security
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10174
• 期：1
• 页码：409-434
• 丛书名：Public-Key Cryptography ?PKC 2017
• ISBN：978-3-662-54365-8
• 卷排序：10174

文摘

Due to its remarkable performance and potential resistance to quantum attacks, \(\mathsf {NTRUEncrypt}\) has drawn much attention recently; it also has been standardized by IEEE. However, classical \(\mathsf {NTRUEncrypt}\) lacks a strong security guarantee and its security still relies on heuristic arguments. At Eurocrypt 2011, Stehlé and Steinfeld first proposed a variant of \(\mathsf {NTRUEncrypt}\) with a security reduction from standard problems on ideal lattices. This variant is restricted to the family of rings \(\mathbb {Z}[X]/(X^n+1)\) with n a power of 2 and its private keys are sampled by rejection from certain discrete Gaussian so that the public key is shown to be almost uniform. Despite the fact that partial operations, especially for \(\mathsf {RLWE} \), over \(\mathbb {Z}[X]/(X^n+1)\) are simple and efficient, these rings are quite scarce and different from the classical \(\mathsf {NTRU}\) setting. In this work, we consider a variant of \(\mathsf {NTRUEncrypt}\) over prime cyclotomic rings, i.e.\(\mathbb {Z}[X]/(X^{n-1}+\cdots +X+1)\) with n an odd prime, and obtain \(\mathsf {IND\text {-}CPA}\) secure results in the standard model assuming the hardness of worst-case problems on ideal lattices. In our setting, the choice of the rings is much more flexible and the scheme is closer to the original \(\mathsf {NTRU}\), as \(\mathbb {Z}[X]/(X^{n-1}+\cdots +X+1)\) is a large subring of the \(\mathsf {NTRU}\) ring \(\mathbb {Z}[X]/(X^{n}-1)\). Some tools for prime cyclotomic rings are also developed.