Predicting Lattice Reduction on Ideal Lattices (PeRIL)

• Activity Number: 531 - SPEED: Statistical Computing: Methods, Implementation, and Application, Part 2
• Type: Contributed
• Date/Time: Wednesday, July 31, 2019 : 11:35 AM to 12:20 PM
• Sponsor: Section on Statistical Computing
• Author(s): Bryan Ek* and Bryan Williams and Emily Nystrom and Jamie Lyle and Peter Curry and Scott Batson
• Companies: Space and Naval Warfare Systems Center Atlantic and Space and Naval Warfare Systems Center Atlantic and Naval Information Warfare Center Atlantic and Space and Naval Warfare Systems Center Atlantic and Space and Naval Warfare Systems Center Atlantic and Space and Naval Warfare Systems Center Atlantic
• Keywords: lattice reduction; shortest vector problem; experimental; root hermite factor; runtime; LLL/BKZ

Abstract

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.