Rendered at 06:44:46 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
hyperhello 3 days ago [-]
For those who don’t have math extensions in the browser, if that is 2^0.6039, then why don’t math extensions just detect math syntax and style it directly?
tikhonj 3 days ago [-]
I mean, in this case, it's 2^{0.6039n}, and the n is pretty important. I can see why trying to automatically detect cases like this would run into a bunch of wrong behaviors (either styling text that was not meant to be math notation, or parsing the implied math notation incorrectly).
hyperhello 3 days ago [-]
Okay, I had the problem going the other way. I assumed the n was a symbol on the previous number, like an f suffix in C. But even still, 2^(0.6039n) could have been rendered in a nice way stripping out the parenthesis, leaving the core text mathematically correct.
altairprime 2 days ago [-]
Email the mods to have the title edited, hn@ycombinator.com; it’s a worthwhile change here.
“in 2^[0.6039n+o(n)] time” could be a better edit than the paper’s provided title, though I selected [] rather than {} for human use. I defer to experts in the field on whether it matters to declare O(n) or not.
traes 2 days ago [-]
Changing {} to [] seems like a very strange suggestion to me. {} is used here because it's the way you group things in LaTeX. If you were going to change it for human use, why not just use parenthesis? What's wrong with {} in the first place?
altairprime 2 days ago [-]
Sure, that’s fine too. Whatever makes more sense than the current title is an improvement, and I can’t judge what’s best for this audience.
shiandow 2 days ago [-]
You'll want small o, not big O. Otherwise there's no point in mentioning the constant factor 0.6039.
And yes the o(n) is relevant. Though I guess implied to some extent.
altairprime 2 days ago [-]
Oops, fixed!
teddyh 2 days ago [-]
You mean 2⁰·⁶³⁹ⁿ
3 days ago [-]
GracefullyShot 3 days ago [-]
could this be a problem for the security of Falcon (aka FN-DSA) post quantum signature scheme?
mswphd 3 days 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.
glitchc 2 days 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 3 hours ago [-]
that's the running time of the BDGL16 sieve. see the intro of e.g.
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 2 days ago [-]
Faster solutions to SVP impact the security of all lattice-based schemes.
abetusk 2 days ago [-]
Could someone summarize what the main idea is for this method?
pretzellogician 3 days ago [-]
Wow, just yesterday I was thinking this exact problem would be a good candidate for AI. Seems it is!
slwvx 3 days ago [-]
I was very happy to see an "AI use disclosure" right on the title page under the abstract.
It's not clear if this is solely a possible theoretical result or if it has any practical value. I.e. is it only useful on lattices that are so large as to not be of use, or could it be used for cryptanalysis? If one is using AI to generate a theory paper such as this, why not use the AI to also generate code that uses it, put it on GitHub, and show the results, say against fplll and the tool in the paper below?
“in 2^[0.6039n+o(n)] time” could be a better edit than the paper’s provided title, though I selected [] rather than {} for human use. I defer to experts in the field on whether it matters to declare O(n) or not.
And yes the o(n) is relevant. Though I guess implied to some extent.
So it's tangentially related, but does not itself imply an improvement on the (heuristically assumed) SOTA for these problems.
Since when? Can you cite the relevant paper(s)?
https://eprint.iacr.org/2022/922.pdf
for some history
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.
It's not clear if this is solely a possible theoretical result or if it has any practical value. I.e. is it only useful on lattices that are so large as to not be of use, or could it be used for cryptanalysis? If one is using AI to generate a theory paper such as this, why not use the AI to also generate code that uses it, put it on GitHub, and show the results, say against fplll and the tool in the paper below?
https://ir.cwi.nl/pub/35237/35237.pdf