We have updated our pre-print titled “On the Complexity of the BKW Algorithm on LWE” on ePrint.
There are two main changes and the reasons why I am mentioning this update here.
- We included a more thorough comparison with other approaches, in particular, with lattice reduction (reducing LWE to SIS). To our surprise, BKW is quite competitive even in relatively modest dimensions. For Regev’s and Lindner-Peikert’s parameter sets (as interpreted here) we get that BKW is at least as fast as BKZ starting in dimension , which I find very low (see Table 4 on page 19).
- We also provide an alternative approximating for the running time of BKZ. The standard estimate due to Lindner-Peikert is where is the targeted root hermit factor. Interpolating estimates from the BKZ 2.0 simulator and reflecting on the doubly exponential running time of BKZ in the blocksize we found: . However, since this might be controversial, we include estimates for both models.