2 ms·

i would really like to understand what you wrote. I thought SVP was O(2^n)

• mswphd 2mo ago
  SOTA for SVP is BDGL16. You can find discussion of it in many places, see for example https://eprint.iacr.org/2022/922.pdf https://eprint.iacr.org/2022/922.pdf it's hard to precisely analyze BDGL16, but to leading order it takes ~ (3/2)^n time, which is roughly 2^{.292n} time. When I say it takes roughly this amount of time, this is likely modulo several heuristics. With the caveat that I'm not a lattice cryptanalyst, my understanding of the heuristics is the following. BDGL16 is a "sieving" algorithm. To find a short vector v, you 1. start with many long vectors v1, ..., vn. 2. take their pairwise differences. this may produce shorter vectors (and if vi are suitably randomly distributed, this is provably true). 3. repeat there are other tricks on top of that you do, but that's the conceptual core. As I mentioned, if the 1. initial vi were suitably randomly distributed, and 2. you could prove the pairwise differences were also suitably randomly distributed you could likely get a provable running time bound on things. At least the 2nd likely breaks down (maybe the first as well though), so you instead only get a running time bound under the above 1+2 heuristic assumptions. In cryptanalysis this is typically viewed as good enough, as long as the heuristics are solid (for example, SOTA for factoring, the Number Field Sieve, only has heuristically understood running time iirc). This paper is instead about provable algorithms. They can be conceptually interesting, and useful if there is not community consensus that the heuristics are solid. But in lattice cryptography everyone thought BDGL16 used reasonable heuristics, so SVP took 2^{0.292n} time practically, even if it was too difficult to formally prove this.