Basis Reduction for Structured Lattices With Applications to Post-Quantum Cryptography

A lattice is a regular array of points in Euclidean space. Originally studied in number theory, lattices have found applications in various domains. In cryptography, lattices play a crucial role, as their complex structures offer promising security solutions against the emerging threats of quantum computing. Current public-key cryptographic schemes that rely on integer factoring and discrete logarithms would succumb to quantum computing attacks, notably Shor’s algorithm. This poses a significant concern for our modern data-driven society, prompting scrutiny from governments, companies, and research institutions. Standardization bodies such as the National Institute of Standards and Technology (NIST), ETSI, and ISO are actively developing post-quantum cryptography (PQC) standards. In particular, NIST’s PQC initiative has garnered widespread attention and participation globally. Among the prospective methods expected to be adopted for post-quantum cryptography, lattice-based cryptography stands out as the most promising approach.
The security of lattice-based cryptography hinges on the assumed hardness of certain lattice problems, such as the approximate shortest nonzero vector problem (SVP). The SVP is typically solved using lattice reduction algorithms, which aim to find a short basis for the lattice. The lattice reduction problem has a long history, capturing the attention of mathematicians as far back as Lagrange, Gauss, and Hermite. Today, it has evolved into a rich and vital field of study that plays a crucial role across many mathematical disciplines. To name a few applications, lattice reduction is widely used in solving Diophantine equations, factoring polynomials, Diophantine approximations, and tackling optimization problems such as sphere packing.
NIST’s PQC protocols leverage structured lattices to enhance efficiency, but the full extent of their security remains an active area of research. Current cryptanalysis often ignores these structures and treats them as regular lattices to evaluate their security level. This project seeks to delve into the reduction theory and algorithms of structured lattices, exploring their implications for the security of PQC systems. By harnessing the power of algebraic number theory, we aim to uncover novel, groundbreaking solutions to problems in PQC.
Modern cryptography is a key component of global cybersecurity systems. The worldwide IT outage in July 2024 caused travel chaos and severely impacted banking and healthcare services. This problem stemmed from an update to the antivirus software of cybersecurity firm CrowdStrike, which is designed to protect Microsoft Windows devices from malicious attacks. Although this incident was not related to cryptography, it highlights the critical importance of properly implementing cybersecurity systems. The security of NIST’s PQC protocols using structured lattices is not yet fully understood. We aim to conduct a thorough cryptanalysis of these PQC protocols by developing new theories and algorithms for lattice reduction. The goal of our cryptanalysis is not to compromise information security but to identify potential weaknesses in encryption protocols, thereby ensuring stronger long-term security.