Title: NTRU: a lattice based public key cryptosystem and digital
signature scheme

Speaker: Jill Pipher, Brown University

When/where: Thursday, April 15th, 4:15PM, Room 200 AKW

Abstract: We discuss the NTRU PKC and signature scheme - the underlying
hard
problem is the closest vector problem in an integer lattice. The best
known means for producing short bases in an integer lattice is the LLL
algorithm and its variants: this polynomial time algorithm produces
moderately short vectors, but finding the shortest vector in an integer
lattice remains an exponentially hard problem. Since NTRU key sizes grow
linearly with dimension, it is possible to choose parameters that yield
efficient implementations and which simultaneously result in lattice
bases of a size well beyond the
capabality of LLL type algorithms to reduce.