Trillion White
Optimisation in BKZ: An analysis of dynamic block size
Lattice-based cryptography is a cornerstone of post-quantum cryptography. Many of these schemes rely on the presumed hardness of lattice problems, such as the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) which have been studied now for decades. Lattice basis reduction algorithms, such as the Lenstra-Lenstra Lov´asz (LLL) algorithm, and Block Korkine-Zolotarev (BKZ), are essential tools for solving these problems and for analysing the security of lattice-based cryptosystems.
BKZ yields a much higher-quality basis but at a much higher computational cost. It is therefore interesting
to see what changes can be made to BKZ in terms of optimisation. This proposal introduces a novel approach to optimising the BKZ algorithm by dynamically changing the block size. At the moment, a larger block size leads to a higher-quality basis but an exponential increase in computation time. A smaller block size is faster but may not provide a sufficient reduction for solving hard lattice problems. The challenge is to design a dynamic strategy for adjusting the block size that can achieve a better balance, leading to a more efficient and practical BKZ algorithm.
Trillion White
Deakin University
Trill is currently a third-year student studying the Bachelor of Cybersecurity program at Deakin University. She is driven by a profound interest in applied mathematics, specifically exploring its intersection with optimisation and cryptography.
A high achieving student, during her first two years at Deakin she used the time to explore different fields of interest, and contributed to four research projects within her university before realising her true passion, in maths. Her work last year in Bayesian regression was published in Deakins Maths Yearbook of 2024, and she is now focusing on mathematical optimisation techniques in cryptography.
Her project as part of AMSI looks at possible optimisations within BKZ-(LLL) algorithm, which is a lattice reduction algorithm used to solve systems like the LWE problem. She is looking forward to presenting her work and learning from the other students.
She is planning on starting Honours next year.
