NTRU cryptosystem

recent developments and emerging mathematical problems in finite polynomial rings

Ron Steinfeld*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The NTRU public-key cryptosystem, proposed in 1996 by Hoffstein, Pipher, and Silverman, is a fast and practical alternative to classical schemes based on factorization or discrete logarithms. In contrast to the latter schemes, it offers quasi-optimal asymptotic efficiency and conjectured security against quantum computing attacks. The scheme is defined over finite polynomial rings, and its security analysis involves the study of natural statistical and computational problems defined over these rings. We survey several recent developments in both the security analysis and in the applications of NTRU and its variants, within the broader field of lattice-based cryptography. These developments include a provable relation between the security of NTRU and the computational hardness of worst-case instances of certain lattice problems, and the construction of fully homomorphic and multilinear cryptographic algorithms. In the process, we identify the underlying statistical and computational problems in finite rings.

Original languageEnglish
Title of host publicationAlgebraic curves and finite fields
Subtitle of host publicationcryptography and other applications
EditorsHarald Niederreiter, Alina Ostafe, Daniel Panario, Arne Winterhof
Place of PublicationBerlin, Germany
PublisherDe Gruyter
Pages179-212
Number of pages34
ISBN (Electronic)9783110317916
ISBN (Print)9783110317886
DOIs
Publication statusPublished - 2014
Externally publishedYes

Publication series

NameRadon Series on Computational and Applied Mathematics
PublisherWALTER DE GRUYTER GMBH
Volume16
ISSN (Print)1865-3707

Keywords

  • NTRU cryptosystem
  • lattice-based cryptography
  • fully homomorphic encryption
  • multilinear maps

Cite this