I am not a cryptography expert but I am interested in the field. Having said that: I am lately having an hard time understanding the actual strength of a crypto suite based on the underlying problem, the sized of the material and the computation strength needed to break it either via optimization and parallelism capabilities.
> The Web PKI deprecated 1024-bit RSA over a decade ago, and while I don’t know of anyone factoring a key of that size, it’s within the realm of possibility for a government or other organization with a large number of computers.
Is it? How do I verify such claim?
---
> Just a few days ago, someone factored the 862-bit RSA-260 key from the RSA factoring challenge.
Yeah, but how much time it required? and what about the resources? It is just a number, it is not all the 861 bits n numbers.
As you probably know, the computing time in the worst case scenario for brute forcing a cryptographic key generally doubles by each bit added. That is, it would take twice the effort to brute-force 129 bits compared 128 bits.
The security of RSA however depends on the factoring of very large numbers, and that means that for example, RSA-2048 doesn't translate into 2048 bits of security but 112 (roughly symmetric equivalent) bits based on the best factoring algorithms (for comparison, the RSA-512 the article mentions has an 56 bit equivalent and RSA-1024 has a 80 bit equivalent security, so RSA-1024 would take roughly 2^(80-56) ~= 17 million times to compute the worst-case scenario and RSA-2048 would take 2^(112-80) = 4.3 thousand million times more).
According to the Wikipedia article on RSA numbers, RSA-220 (66b) was factored in 2016, RSA-230 (69b) in 2018, RSA-240 (72b) in 2019 and RSA-260 (76b) this year, which is too close to RSA-1024 (80b) to be comfortable.
For RSA-250, the team reported it took "roughly 2,700 core-years, using Intel Xeon Gold 6130 CPUs at 2.1 GHz.". I am not going to (or feel qualified to) make estimates of how that would translate to RSA-1024, but it does sound plausible given enough resources.
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.
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.