Bernstein's NFS analyzed by Lenstra and Shamir 168
kousik writes "The analysis of Bernstein's NFS by Arjen Lenstra,
Adi Shamir, Jim Tomlinson, Eran Tromer has been
put up on cryptosavvy.
Seems interesting it comes from Lenstra and Shamir.
Lenstra lead the 1994 factorisation of RSA 129.
From the abstract: ... We also propose an improved circuit design based on a new mesh
routing algorithm, and show that for factorization of 1024-bit integers
the matrix step can, under an optimistic assumption about the matrix
size, be completed within a day by a device that costs a few thousand
dollars..."
errrrr NFS? (Score:5, Informative)
Result doesn't imply weak keys (Score:2, Informative)
As they clearly state in the paper, "the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve." - The speedup that Bernstein proposed just makes the stuff surrounding that step a bit more efficient.
Re:It's 1.17, not 3.01... your keys less compromis (Score:2, Informative)
Even if it is 3.01 times larger, that's still an effective strength of at least 1022 bits.
(For what it's worth, I've only read the abstract.)
Re:Is factoring hard (Score:1, Informative)
Re:Quotes from the paper (Score:3, Informative)
Even if you remove the matrix side, it takes a VERY long time to find all of the relations needed to make the matrix in order to solve it.
Re:Mesh routing is really the way to go (Score:1, Informative)
Trust me, I will be watching for you in metamod.
Re:yeah... (Score:2, Informative)
I'd say it does:
a color-coded simulation of the mesh routing algorithm [weizmann.ac.il] (16MB)
Re:Is factoring hard (Score:2, Informative)
>in your head that a given number is prime? For that matter,
>can you prove using a computer that a given large number
>(if you go for any) is prime? For some reason, I don't think so...
It depends on how much time you are willing to afford. A trivial algorithm is to try every (prime) number sqrt(N) to see if it divides N, if there is none, N is prime. But in practice this is too slow to let you get much beyond N ~20 digits.
Elliptic Curve Primality Proving is state of the art for general primality proofs today, try Primo [freesurf.fr] which has been used to prove a 5020 digit number prime.
Integer factoring is much harder than proving primality, the current record for a GNFS factorization is a 158 digit composite, see here [ercim.org].
Alex
Re:Cliff notes version (Score:2, Informative)
Background. To review the undisputed facts:
Carl Pomerance has pointed out that a slightly different conventional NFS implementation takes time L^(1.754...+o(1)) on a machine of size L^(1.006...+o(1)), or time L^(1.656...+o(1)) on a machine of size L^(1.104...+o(1)), but this is still vastly less cost-effective than a circuit for large numbers. The NFS cost ratio between conventional computers and circuits grows as a quite noticeable power of the cost itself.
There are two basic reasons for this improvement. First, for large numbers, using conventional computers (or TWINKLE) for NFS sieving is a bad idea, because the low-memory smoothness-testing circuits described in my paper are much more cost-effective. Second, for large numbers, using conventional computers for NFS linear algebra is a bad idea, because the linear-algebra circuits described in my paper are much more cost-effective.
3 versus 1.17: why there is a dispute. This Lenstra-Shamir-Tomlinson-Tromer paper observes, correctly, that reasonably fast low-memory smoothness-testing techniques have been known for decades. (Of course, my paper says the same thing.)
The Lenstra-Shamir-Tomlinson-Tromer paper then leaps to the incorrect conclusion that the cost-effectiveness of those techniques for large numbers was widely known before my paper.
If this fact was known before, why didn't it appear in the aforementioned Silverman and Lenstra-Shamir papers two years ago? Both of those papers were discussing the cost of state-of-the-art integer factorization.
As for the Coppersmith paper cited by Lenstra et al.: As mentioned in my paper, Coppersmith suggested ECM in a context where RAM sieving would have meant looking at many more numbers. He didn't observe that ECM was better than RAM sieving in other contexts. In fact, for the first step of his algorithm, he specifically suggested RAM sieving!
The simple fact is that papers before mine optimized their machines purely for operation count. The resulting machines are far less cost-effective than the circuits described in my paper.
The Lenstra-Shamir-Tomlinson-Tromer paper does not claim that circuits are less cost-effective (slower or larger) than stated in my paper. It also does not claim that conventional implementations are competitive. It does not claim that circuits are actually not so scary. What it claims is that we already had fairly scary circuits. This is revisionist history, not a technical dispute.
Simple versus optimized. My paper is a grant proposal. It explains a very simple circuit, enough to prove the L^(1.185...+o(1)),L^(0.790...+o(1)) result. It then briefly points out several ways that the circuit can be changed and improved. The objective of the grant is to find the most cost-effective circuit. The simplest circuit is certainly not the best one; finding the best one is a huge project.
Treating the simplest algorithm as if it were my final result, with every trivial improvement worth pointing out, is a serious misrepresentation of my work.
In particular, the use of mesh routing in this context is one of many obvious possibilities, and is already mentioned in my paper as an alternative to mesh sorting. Lenstra et al. claim that this is an ``improvement'' over my paper; that claim is false.
I described a counterclockwise mesh routing algorithm in an email message to one of those authors in mid-April, as part of explaining why conventional implementations aren't cost-effective. (On a 20x20 mesh: ``Take a batch of, say, 1000 hits generated by each processor; route the hits 19 steps down, then 19 steps right, then 19 steps up, then 19 steps left, to reach the proper memory locations. ... The point is that the time ratio grows linearly with the 20, while the cost ratio is simply 1 plus overhead. The overhead can be dramatically reduced with special-purpose circuitry, allowing the 20 to be raised by half as many orders of magnitude.'')
I am astonished that anyone would publish this obvious use of mesh routing as if it were an interesting new result.
The balance between sieving and linear algebra. There are many parameters in NFS: dials that can be adjusted to affect the speed of the algorithm in complicated ways. The most important parameter is the ``prime bound,'' usually called y.
As y increases from ``tiny'' to ``standard,'' the cost of sieving drops down to a smallest possible value, while the cost of linear algebra rises. As y increases past standard, the cost of sieving starts rising again, and keeps rising, while the cost of linear algebra also rises.
In the context of TWINKLE, Lenstra and Shamir claimed that sieving speedups had limited value, because linear algebra by itself was a bottleneck. That claim is obviously false: one can always decrease y to reduce the cost of linear algebra until sieving and linear algebra are in balance.
The Lenstra-Shamir-Tomlinson-Tromer paper now makes the opposite claim, that linear-algebra speedups have limited value, because sieving by itself is a bottleneck. That claim is also false, at least for large numbers: the optimal value of y is substantially smaller than standard, as stated in my paper, so one can increase y to reduce the cost of sieving until sieving and linear algebra are in balance.
Perhaps someday we'll discover better linear-algebra methods. Perhaps the cost of linear algebra will become unnoticeable for standard values of y; then sieving by itself will be a bottleneck. However, as stated in my paper, the current situation for large numbers is that linear algebra is relatively difficult; as a consequence, when parameters are chosen properly, sieving and linear algebra are in balance.
Large numbers versus small numbers, and the cost of sieving. Figuring out that one NFS approach is much better than another for large numbers is much easier than figuring out the situation for small numbers, such as 1024 bits or 1536 bits.
Analogy: It's easy to prove that merge sorting is much faster than insertion sorting for large arrays. You don't have to worry about all the different variations of the sorting algorithms; these changes can make big differences in speed, but those differences are unnoticeable next to the gigantic speed gap between merge sorting and insertion sorting for large arrays. It's much more difficult to figure out the fastest method for small arrays, such as arrays of size 16.
The Lenstra-Shamir-Tomlinson-Tromer paper has one paragraph (Section 5.2) on the cost of sieving for a specific input size, namely 1024 bits. That paragraph estimates that RAM sieving would take about a year on 30 million large-memory PCs. It implicitly assumes that conventional RAM sieving is the most cost-effective approach to sieving for 1024-bit numbers. In particular, it implicitly assumes that circuits (mesh sorting, mesh routing, early-abort Pollard+ECM, etc.; see my paper) wouldn't be much less expensive. It concludes that sieving by itself is a bottleneck for 1024-bit numbers.
There is no justification for these assumptions and conclusions. The authors claim to understand, and to have understood for a decade, that conventional RAM sieving is much less cost-effective than circuits for large numbers; however, when faced with 1024-bit numbers, they don't even consider the possibility of 1024 being large and of conventional RAM sieving being the wrong approach. This is a gaping hole in the Lenstra-Shamir-Tomlinson-Tromer analysis.
Maybe special-purpose circuits will have a dramatic impact on the difficulty of 1024-bit and 1536-bit and 2048-bit factorizations. Maybe they'll have no impact at all. I don't know yet. I do know that ignoring the question doesn't help us find the answer.