Collaborative Research: Short Vectors in Lattices

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

The main focus of this project is to rebuild the literature on lattice algorithms on a foundation of modern computer architecture. This means going beyond counting textbook operations, and instead investigating the time required on a parallel machine with realistic limits on communication, so as to obtain the ultimate implementation efficiency on current and future chips. Major project activities include the following: 1. Fast constant-time implementations of fundamental arithmetic operations such as integer multiplication, Euclid's algorithm, and modular inversion. 2. A scalable parallelized implementation of the LLL lattice-basis-reduction algorithm for large-rank lattices. 3. Improvements to algorithms for finding shorter vectors in lattices, including sieving, enumeration, and multiplicative techniques from algebraic number theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.