NTRU prime: reducing attack surface at low cost

D.J. Bernstein, C. Chuengsatiansup, T. Lange, C. van Vredendaal

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

Abstract


Several ideal-lattice-based cryptosystems have been broken by recent attacks that exploit special structures of the rings used in those cryptosystems. The same structures are also used in the leading proposals for post-quantum lattice-based cryptography, including the classic NTRU cryptosystem and typical Ring-LWE-based cryptosystems.

This paper (1) proposes NTRU Prime, which tweaks NTRU to use rings without these structures; (2) proposes Streamlined NTRU Prime, a public-key cryptosystem optimized from an implementation perspective, subject to the standard design goal of IND-CCA2 security; (3) finds high-security post-quantum parameters for Streamlined NTRU Prime; and (4) optimizes a constant-time implementation of those parameters. The resulting sizes and speeds show that reducing the attack surface has very low cost.


Keywords
Post-quantum cryptography Public-key encryption Lattice-based cryptography Ideal lattices NTRU Ring-LWE Security Soliloquy Karatsuba Software implementation Vectorization Fast sorting
Original languageEnglish
Title of host publicationSelected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers
EditorsCarlisle Adams, Jan Camenisch
Place of PublicationBerlin
PublisherSpringer
Pages235-260
Number of pages26
ISBN (Electronic)978-3-319-72565-9
ISBN (Print)978-3-319-72564-2
DOIs
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10719

Keywords

  • Fast sorting
  • Ideal lattices
  • Karatsuba
  • Lattice-based cryptography
  • NTRU
  • Post-quantum cryptography
  • Public-key encryption
  • Ring-LWE
  • Security
  • Software implementation
  • Soliloquy
  • Vectorization

Fingerprint Dive into the research topics of 'NTRU prime: reducing attack surface at low cost'. Together they form a unique fingerprint.

  • Cite this

    Bernstein, D. J., Chuengsatiansup, C., Lange, T., & van Vredendaal, C. (2017). NTRU prime: reducing attack surface at low cost. In C. Adams, & J. Camenisch (Eds.), Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers (pp. 235-260). (Lecture Notes in Computer Science; Vol. 10719). Springer. https://doi.org/10.1007/978-3-319-72565-9_12