Paper 2022/1664

NTRU+: Compact Construction of NTRU Using Simple Encoding Method

Jonghyun Kim, Korea University
Jong Hwan Park, Sangmyung University
Abstract

NTRU was the first practical public key encryption scheme constructed on a lattice over a polynomial-based ring and has been considered secure against significant cryptanalytic attacks over the past few decades. However, NTRU and its variants suffer from several drawbacks, including difficulties in achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms compared to other lattice-based schemes. In this work, we propose a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes nearly all existing drawbacks. NTRU+ is constructed based on two new generic transformations: $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ (a variant of the Fujisaki-Okamoto transform). $\mathsf{ACWC}_{2}$ is used to easily achieve worst-case correctness error, while $\overline{\mathsf{FO}}^{\perp}$ is used to achieve chosen-ciphertext security without re-encryption. Both $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ are defined using a randomness-recovery algorithm and an encoding method. In particular, our simple encoding method, the semi-generalized one-time pad (SOTP), allows us to sample a message from a natural bit-string space with an arbitrary distribution. We provide four parameter sets for NTRU+ and present implementation results using NTT-friendly rings over cyclotomic trinomials.

Note: This work is submitted to ‘Korean Post-Quantum Cryptography Competition’ (www.kpqc.or.kr). This work was supported by Institute of Information \& communications Technology Planning \& Evaluation (IITP) grant funded by the Korea government(MSIT) (No.2021-00518, Blockchain privacy preserving techniques based on data encryption).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. https://ieeexplore.ieee.org/document/10194960
DOI
10.1109/TIFS.2023.3299172
Keywords
NTRURLWELattice-based cryptographyPost-quantum cryptography
Contact author(s)
yoswuk @ korea ac kr
jhpark @ smu ac kr
History
2023-08-11: last of 2 revisions
2022-11-30: received
See all versions
Short URL
https://ia.cr/2022/1664
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1664,
      author = {Jonghyun Kim and Jong Hwan Park},
      title = {NTRU+: Compact Construction of NTRU Using Simple Encoding Method},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1664},
      year = {2022},
      doi = {10.1109/TIFS.2023.3299172},
      note = {\url{https://eprint.iacr.org/2022/1664}},
      url = {https://eprint.iacr.org/2022/1664}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.