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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
NTRUIdeal latticeCanonical embeddingCyclotomic fieldsRLWE
Contact author(s)
wangmingqiang @ sdu edu cn
History
2017-11-15: received
Short URL
https://ia.cr/2017/1104
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1104,
      author = {Yang Wang and Mingqiang Wang},
      title = {Efficient provable-secure NTRUEncrypt over any cyclotomic field},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1104},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1104}},
      url = {https://eprint.iacr.org/2017/1104}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.