4 ms·

could this be a problem for the security of Falcon (aka FN-DSA) post quantum signature scheme?

mswphd 2mo ago
not really. The hardness of SVP is relevant, but this is a paper giving improved provable bounds for SVP algorithms. heuristically (which people use to choose parameter sizes etc) people assume SVP is much easier to solve, closer to 2^{.29n + o(n)}. So it's tangentially related, but does not itself imply an improvement on the (heuristically assumed) SOTA for these problems.
- GracefullyShot 2mo ago
  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.
- glitchc 2mo ago
  > people assume SVP is much easier to solve, closer to 2^{.29n + o(n)}. Since when? Can you cite the relevant paper(s)?
  - mswphd 2mo ago
    that's the running time of the BDGL16 sieve. see the intro of e.g. https://eprint.iacr.org/2022/922.pdf https://eprint.iacr.org/2022/922.pdf for some history
glitchc 2mo ago
Faster solutions to SVP impact the security of all lattice-based schemes.

not really. The hardness of SVP is relevant, but this is a paper giving improved provable bounds for SVP algorithms. heuristically (which people use to choose parameter sizes etc) people assume SVP is much easier to solve, closer to 2^{.29n + o(n)}. So it's tangentially related, but does not itself imply an improvement on the (heuristically assumed) SOTA for these problems.

GracefullyShot 2mo ago
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.
glitchc 2mo ago
> people assume SVP is much easier to solve, closer to 2^{.29n + o(n)}. Since when? Can you cite the relevant paper(s)?
- mswphd 2mo ago
  that's the running time of the BDGL16 sieve. see the intro of e.g. https://eprint.iacr.org/2022/922.pdf https://eprint.iacr.org/2022/922.pdf for some history

glitchc 2mo ago

Faster solutions to SVP impact the security of all lattice-based schemes.