Building Lattice Reduction (LLL) Intuition

https://kel.bz/post/lll/ [kel.bz]

2020-01-24 07:49

The Lenstra–Lenstra–Lovász (LLL) algorithm is an algorithm that efficiently transforms a “bad” basis for a lattice L into a “pretty good” basis for the same lattice. This transformation of a bad basis into a better basis is known as lattice reduction, and it has useful applications. For example, there is attack against ECDSA implementations that leverage biased RNGs that can lead to private key recovery. However, my experience learning why LLL works has been pretty rough. Most material covering LLL seems targeted towards mathematicians and I had to (I guess I wanted to) spend a lot of time trying to weasel out the intuition and mechanics of the algorithm. This blog post is a semi-organized brain dump of that process. My goal is to cover LLL in such a way that slowly ratchets down the hand-waving, so feel free to read until you are happy with your level of understanding.