david wong

Hey! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

About the easiness of SVP

posted November 2015

First of all, we stress that SVP and its variants should all be considered easy when the lattice dimension is less than 70. Indeed, we will see in Section 4 that exhaustive search techniques can solve SVP within an hour up to dimension 60. But because such techniques have exponential running time, even a 100-dimensional lattice is out of reach. When the lattice dimension is beyond 100, only approximation algorithms like LLL, DEEP and BKZ can be run.

I can't remember from what article I got that from. Must have been something Phong Nguyen wrote.

It states that a lattice of dimension 60 could be easily solved, in an hour, by an exhaustive search (or similar techniques (enumeration?)). Something to dig into.

Well done! You've reached the end of my post. Now you can leave me a comment :)