465 – SPEED: Statistical Computing: Methods, Implementation, and Application, Part 1
Predicting Lattice Reduction on Ideal Lattices (PeRIL)
Scott Batson
Bryan Ek
Naval Information Warfare Systems Center Atlantic
Jamie Lyle
Emily Nystrom
Bryan Williams
The shortest vector problem (SVP) is at the core of many applications of lattices. Lattice reduction algorithms output a lattice basis containing a short vector and are a common approach to the SVP. The research conducted by the PeRIL team supports an investigation of the performance of lattice reduction algorithms when applied to lattices from the ideal case versus lattices from the general case. The foundational work of Gama and Nguyen provided empirical results for the case of general lattices. Since their 2008 publication, experimental results have been published for various aspects of lattice reduction algorithms, including some results for the case of ideal lattices (only). Although the implications of understanding the impact of lattice class on lattice reduction algorithms have been referenced in the literature, to our knowledge, a systematic, empirical investigation of the impact of the class of lattices (e.g., ideal vs. general), in relation to its impact on lattice reduction algorithm performance, has not been previously published. We address that gap in this paper. This research was supported by the DoD section 219 Naval Innovative Science and Engineering Program.