AF: Small: Algorithms and Complexity of Ideal and Structured Lattices

Although quantum computers capable of breaking traditional cryptosystems have not yet been realized, it is essential to prepare for this potential disruption through research and education. This award aims to advance the understanding of the security of existing quantum-safe cryptosystems and guide the design of future systems. The investigator will develop accessible educational materials on the subject and integrate the mathematical foundation into a course offered at the University of Oklahoma. Additionally, the project will support the training of one doctoral student, equipping them with expertise in computational lattice theory and preparing them for impactful contributions to the field. Hard ideal lattice problems underpin the security of many versatile and widely used primitives in post-quantum cryptography. However, recent advancements have led to faster algorithms for solving the Shortest Vector Problem (SVP) using principal ideal lattices, along with attempts to extend these attacks to non-principal ideals and other structured lattices. In this project, the investigator focuses on three key areas: (1) novel algorithmic approaches to SVP and related problems in ideal lattices, particularly those with broad cryptographic applications; (2) complexity questions arising from ideal lattices constructed in group rings; and (3) the explicit construction of dense centers for structured lattices. 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.