Paper 2017/1104

Efficient provable-secure NTRUEncrypt over any cyclotomic field

Yang Wang and Mingqiang Wang

Abstract

NTRUEncrypt is a fast lattice-based cryptosystem and a probable alternative of the existing public key schemes. The existing provable-secure NTRUEncrypts are limited by the cyclotomic field it works on - the prime-power cyclotomic field. This is worth worrying, due to the subfield attack methods proposed in $2016$. Also, the module used in computation and security parameters rely heavily on the choice of plaintext space. These disadvantages restrict the applications of NTRUEncrypt. In this paper, we give a new provable secure NTRUEncrypt in standard model under canonical embedding over any cyclotomic field. We give an reduction from a simple variant of RLWE - an error distribution discretized version of RLWE, hence from worst-case ideal lattice problems, to our NTRUEncrypt. In particular, we get a union bound for reduction parameters and module for all choices of plaintext space, so that our NTRUEncrypt can send more encrypted bits in one encrypt process with higher efficiency and stronger security. Furthermore, our scheme's decryption algorithm succeeds with probability $1-n^{\o(\sqrt{n\log n})}$ comparing with the previous works' $1-n^{-\o(1)}$, making our scheme more practical in theory.