Paper 2019/015

More Efficient Algorithms for the NTRU Key Generation using the Field Norm

Thomas Pornin, NCC Group
Thomas Prest, PQShield Ltd.
Abstract

NTRU lattices are a class of polynomial rings which allow for compact and efficient representations of the lattice basis, thereby offering very good performance characteristics for the asymmetric algorithms that use them. Signature algorithms based on NTRU lattices have fast signature generation and verification, and relatively small signatures, public keys and private keys. A few lattice-based cryptographic schemes entail, generally during the key generation, solving the NTRU equation: $$ f G - g F = q \mod x^n + 1 $$ Here $f$ and $g$ are fixed, the goal is to compute solutions $F$ and $G$ to the equation, and all the polynomials are in $\mathbb{Z}[x]/(x^n + 1)$. The existing methods for solving this equation are quite cumbersome: their time and space complexities are at least cubic and quadratic in the dimension $n$, and for typical parameters they therefore require several megabytes of RAM and take more than a second on a typical laptop, precluding onboard key generation in embedded systems such as smart cards. In this work, we present two new algorithms for solving the NTRU equation. Both algorithms make a repeated use of the field norm in tower of fields; it allows them to be faster and more compact than existing algorithms by factors $\tilde O(n)$. For lattice-based schemes considered in practice, this reduces both the computation time and RAM usage by factors at least 100, making key pair generation within range of smart card abilities.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2019
Keywords
lattice techniques public-key cryptography quantum cryptography NTRU Falcon
Contact author(s)
thomas pornin @ nccgroup com
thomas prest @ pqshield com
History
2022-06-27: revised
2019-01-09: received
See all versions
Short URL
https://ia.cr/2019/015
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/015,
      author = {Thomas Pornin and Thomas Prest},
      title = {More Efficient Algorithms for the NTRU Key Generation using the Field Norm},
      howpublished = {Cryptology ePrint Archive, Paper 2019/015},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/015}},
      url = {https://eprint.iacr.org/2019/015}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.