[Resource Topic] 2022/1664: NTRU+: Compact Construction of NTRU Using Simple Encoding Method

Welcome to the resource topic for 2022/1664

NTRU+: Compact Construction of NTRU Using Simple Encoding Method

Authors: Jonghyun Kim, Jong Hwan Park


NTRU was the first practical public-key encryption scheme constructed on a lattice over a polynomial-based ring, and has been still considered secure against significant cryptanalytic attacks in a few decades. Despite such a long history, NTRU and its variants proposed to date suffer from several drawbacks, such as the difficulty of achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms than other lattice-based schemes.

In this work, we suggest a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes almost all existing drawbacks. NTRU+ is constructed based on two new generic transformations called \mathsf{ACWC}_{2} and \overline{\mathsf{FO}}^{\perp}. \mathsf{ACWC}_{2} is used for easily achieving a worst-case correctness error, and \overline{\mathsf{FO}}^{\perp} (as a variant of the Fujisaki-Okamoto transform) is used for achieving chosen-ciphertext security without re-encryption. \mathsf{ACWC}_{2} and \overline{\mathsf{FO}}^{\perp} are all defined using a randomness-recovery algorithm and an encoding method. Especially, our simple encoding method, called \mathsf{SOTP}, allows us to sample a message from a natural bit-sting space with an arbitrary distribution. We provide four parameter sets for NTRU+ and give implementation results, using NTT-friendly rings over cyclotomic trinomials.

ePrint: https://eprint.iacr.org/2022/1664

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .