CAREER: Concrete Hardness in Lattice-based Cryptography

With recent advances in quantum computing, cryptosystems tailored to be quantum-safe are of great interest. One of the most promising candidates for post-quantum cryptography is lattice-based cryptography. The security of lattice-based cryptography however relies on the computational hardness of certain lattice-based assumptions.

The central goal of this project is to understand the concrete hardness of these assumptions, investigating algorithms for the worst-case and average-case lattice problems. The project aims to provide new insights into the concrete behavior of lattice algorithms and understand their detailed resource requirements. The integrated educational component of the project involves a combination of mentoring, course (re)-design and science communication activities, contributing to the development of a diverse STEM workforce.

The main research activities in the project include: (1) understand and improve the lattice reduction algorithms, including the underlying enumeration and sieving algorithms, with a focus on their concrete complexities; (2) investigate the impacts of deploying classical and quantum algorithms in lattice reduction, and estimate their detailed resource requirement; (3) develop robust models to guide the parameter selection for lattice-based cryptographic systems. The research findings provide a systematic approach to quantitatively understand the intrinsic hardness of lattice assumptions.

These results contribute to the standardization process for post-quantum cryptography, guide the parameter selection, and provide a systematic tool to the developers and end-users of lattice-based cryptography. The research outcomes are to be published in peer-reviewed publications for the academic community and to be disseminated to a broader audience through the education and outreach activities.

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.