C-DAC's computers, built on a sophisticated clustering of microprocessors, would use advanced software to securely network the machines, much like a high-voltage electricity grid.
Can anyone work out what they're trying to say here? Do high-voltage electricity grids use advanced security software? Perhaps they're saying that anyone who tries to tamper with the network will get shocked? Or...
Cadmium is also pretty damn toxic, yet we don't restrict NiCad batteries.
I think there's much more danger of someone cracking a NiCad battery open than there is of someone taking a plutonium RTG apart and breaking open the irridium shells which encase the plutonium.
We could have better batteries, if people weren't so paranoid about nuclear technology. It's quite possible to create safe, long-lived, batteries based on nuclear decay -- many smoke detectors are powered by americium decay, and about a decade ago there were plans to use plutonium to power pacemakers -- but there is too much of an anti-nuclear lobby to allow anything of the sort to happen now.
First, hardware fails occasionally. The probes would have to be able to send their signals back at least two hops in order to avoid having one failed probe "orphan" many others.
Second, the trajectories rely upon a particular alignment of planets. If we sent out probes year after year, they'd end up going in completely different directions.
A similar misconfiguration resulted in a mailing loop a couple years ago with asynchrony-projects.com: somehow members-bounce@ was rewritten to members@; the net result was that a single incorrect subscribed email address caused a about a hundred emails to be sent out to 1000+ subscribers to the mailing list.
These problems are easy to fix, but people make mistakes... personally I'm surprised the number of mistakes has been so limited thus far.
Personally, I'd rather have RC helicopters. Yes, I know their batteries wouldn't last long... but in an office environment, tiny cars aren't going to get very far, given the amount of clutter which would obstruct them. Helicopters, on the other hand, could fly over cubicle walls to attack people...
and time proportional to n^(1/3+o(1)) for signals to traverse the wires
Please. We can pipeline the bits; latency is not a critical issue here. I'll conceed that I hadn't considered the asymptotic cost of long wires, but I didn't claim to either. Using a million processors *does* increase the cost, but we still get a linear speedup.
The bottom line is that traditional computers [...] are not the right way to do extremely large factorizations.
And I never disputed that. Indeed, I'd say that, for a fixed (large) budget, custom silicon can probably perform factorizations 10^5 times faster than a system built out of commodity hardware.
But as long as the your FPUs constitute a fraction of the total price tag bounded away from zero, and you require the same number of FLOPs, you only get a constant factor improvement.
This may be a significant advance in factoring, but I notice that rsa-576 still hasn't been factored.
That's not security; that's apathy. RSA-576 is quite factorable right now, as soon as anyone gets around to it. The largest cause for it still standing unfactored is that GNFS requires rather more background knowledge than something like cracking DES.
If either RSA-576 or RSA-640 are both still standing three years from now I'll be very surprised; I'd be surprised if even RSA-704 is unfactored three years from now.
Each processor can easily sort its own numbers, but how do you merge the 16 lists?
Using a parallel merge-exchange, perhaps?
Seriously, I've always avoided non-oblivious algorithms as much as possible; I'll admit that you can play games to reduce the communication and memory costs; but even without any memory or communication costs, you still have to pay for your FLOPs.
Most universities expanded dramatically in the 60s... that faculty is retiring over the next five years. Many mathematics departments are losing 40% of their faculty within a five year window.
I have no idea how Mr. Computing DPhil arrived at the idea of putting vastly more memory than necessary into a single-processor computer: for example, using a million gigabytes of memory to sort a billion numbers. He is incorrect in claiming that such silly computers are the base for comparison in my paper.
I never suggested that you were comparing against a machine with excessive amounts of memory; I suggested that you were comparing against a single processor which addressed the same amount of memory as would normally be distributed among thousands. In the case of "using a million gigabytes of memory", that was in order to sort a million gigabytes of data; by splitting the petabyte of memory into a million pieces and attaching a cpu to each, one speeds up the sorting by a factor of a million.
Perhaps my argument could best be summarized as this: You're saving memory, but you're not saving MIPS. This technique of yours may make machines cheaper to build because you need less memory per processor, but you still need just as many processors (in fact, slightly more, the way you've described it).
You still need just as many floating-point operations, and the cost of those floating-point operations is enough to put anything beyond 1536 bits out of reach of the NSA for now.
I assume the memory required grows polynomially in these algorithms. Am I wrong?
Yes, you are wrong. The memory traditionally "necessary" grows with the same O( exp(c (ln n)^(1/3) (ln ln n)^(2/3)) ) rate as everything else (except with a different constant c).
The analysis is based on keylength per $ of hardware. It theoretically triples the keylength you can attack per $ spent.
It triples the keylength at the same cost, compared to a serial machine with a huge address space. But nobody was ever considering loading down a Pentium 4 with a few petabytes of memory; instead, people would stick a few gigabytes of memory on each of 10^6 Pentium 4 processors.
All DJB has done is reinvent the idea of scaling processors at the same time as scaling memory when attacking large problems.
Government security angencies have custom codebreaking hardware. We just need someone outside the government to figure out and announce the price tag. Then we'll know what's currently breakable.
If you use an RSA modulus smaller than 768 bits, I will laugh at you. If you use an RSA modulus smaller than 1280 bits, the Russian mafia will laugh at you. If you use an RSA modulus smaller than 1536 bits, the NSA will laugh at you.
Above those points, you're safe, because even if memory were free the cost of the necessary FPUs would be too high.
Hold on. A parallel implementation would normally just give an N times speedup.
Only for a fixed amount of parallelism. DJB is supposing that as the problem gets larger he is increasing the number of FPUs at the same rate as the amount of memory. Which is eminently reasonable, and hardly new.
This isn't really a big deal, nor is it surprising.
Basically, what DJB has done is translated the GNFS from its normal implementation on serial computers (where there is a great deal of available memory, but only one operation is performed at once) into a parallel implementation, where the number of processors more closely matches the available memory.
The "decreased cost" is misleading here, since it is calculated on the assumption that sieving would have been done by a single processor with access to a huge memory... this quite simply was never the case.
There is nothing here to suggest that factoring can be performed using any fewer FLOPS; all that is demonstrated is that by using several processors, each with a smaller memory, you can do better than with a single processor and a giant memory. Which we already knew.
The same thing sometimes happens to the BSDs, where a bug will be fixed (usually in Open) and nobody gets around to integrating the same fix into the others.
It seems to me that much of this could be automated... for each patch which gets added into the xBSD source tree, compare the contexts to the yBSD and zBSD source trees and alert a human if it looks like there's a match.
But for this to be effective, I think that patches would have to have labels attached, since it's really only bug fixes for which this is necessary.
It has come to our attention that you maintain a web site operating under the moniker "chillingeffects.org" and through that service are engaged in the provision of legal services.
Since you are not licensed to provide legal services, we respectfully ask that you cease and desist from providing such services.
[snip rant about subsidized internet access leading to rationing]
Who ever said anything about subsidizing internet access? A government-owned monopoly != a government-subsidized service.
I think that the government should run fiber-optics everywhere, but I also think people should pay to use it. (And that includes ISPs which want to lease fiber; while I think government should be involved in providing the raw fiber I am far from convinced that they should get involved in IP packet switching.)
Roughly speaking (and this is overly simplistic, I know), hooking up 422 towns just means having 422 times the amount of cable.
How do you figure that? Last time I looked at the question, the amount of cable it takes to connect N random points within a given region scales as approximately O(sqrt(N)). IOW, the cost would be cut by approximately a factor of 20.
Can't you just hear it coming: "The voting taxpayers has paid to build this information superhighway so therefore the community should have some say as to the things that are allowed to be sent over this highway. [...]"
I'm certain that some people would make such arguments. But are those arguments any more valid than would be arguments asserting that pornographic magazines should not be distributed via a publicly funded and owned highway system?
Public policy should be decided on the basis of what is right, not on the basis of the invalid arguments which might arise from such policy.
From a public policy perspective, I don't understand why there aren't more governments doing this. It is generally accepted that governments should provide and maintain a highway system; how is internet connectivity any different?
There are many things which governments get involved with (eg health care) which I think they should stay out of as much as possible; but when it comes to natural monopolies I certainly see that they have a role to play.
However, Road Runner can choose to discard mail because there are too many occurences of the letter "q," it's in all caps, or it was received at 7:31 PM.
IANAL, but I don't think you're right here. They probably have enough verbiage in their contract to cover this (of course, much of it wouldn't be legally enforceable...), but you might be able to hinge a case on the creation of reasonable expectation that email would not be arbitrarily blocked.
Slashdot Mirror
C-DAC's computers, built on a sophisticated clustering of microprocessors, would use advanced software to securely network the machines, much like a high-voltage electricity grid.
Can anyone work out what they're trying to say here? Do high-voltage electricity grids use advanced security software? Perhaps they're saying that anyone who tries to tamper with the network will get shocked? Or...
Cadmium is also pretty damn toxic, yet we don't restrict NiCad batteries.
I think there's much more danger of someone cracking a NiCad battery open than there is of someone taking a plutonium RTG apart and breaking open the irridium shells which encase the plutonium.
We could have better batteries, if people weren't so paranoid about nuclear technology. It's quite possible to create safe, long-lived, batteries based on nuclear decay -- many smoke detectors are powered by americium decay, and about a decade ago there were plans to use plutonium to power pacemakers -- but there is too much of an anti-nuclear lobby to allow anything of the sort to happen now.
Two major problems:
First, hardware fails occasionally. The probes would have to be able to send their signals back at least two hops in order to avoid having one failed probe "orphan" many others.
Second, the trajectories rely upon a particular alignment of planets. If we sent out probes year after year, they'd end up going in completely different directions.
NASA will attempt to contact the spacecraft today, (it was successfully contacted last year), but the round trip time is over 22 hours
How, exactly, is "today" defined? Do they send out a signal at 1AM and hope to get a reply back at 11PM?
A similar misconfiguration resulted in a mailing loop a couple years ago with asynchrony-projects.com: somehow members-bounce@ was rewritten to members@; the net result was that a single incorrect subscribed email address caused a about a hundred emails to be sent out to 1000+ subscribers to the mailing list.
These problems are easy to fix, but people make mistakes... personally I'm surprised the number of mistakes has been so limited thus far.
Personally, I'd rather have RC helicopters. Yes, I know their batteries wouldn't last long... but in an office environment, tiny cars aren't going to get very far, given the amount of clutter which would obstruct them. Helicopters, on the other hand, could fly over cubicle walls to attack people...
and time proportional to n^(1/3+o(1)) for signals to traverse the wires
Please. We can pipeline the bits; latency is not a critical issue here. I'll conceed that I hadn't considered the asymptotic cost of long wires, but I didn't claim to either. Using a million processors *does* increase the cost, but we still get a linear speedup.
The bottom line is that traditional computers [...] are not the right way to do extremely large factorizations.
And I never disputed that. Indeed, I'd say that, for a fixed (large) budget, custom silicon can probably perform factorizations 10^5 times faster than a system built out of commodity hardware.
But as long as the your FPUs constitute a fraction of the total price tag bounded away from zero, and you require the same number of FLOPs, you only get a constant factor improvement.
This may be a significant advance in factoring, but I notice that rsa-576 still hasn't been factored.
That's not security; that's apathy. RSA-576 is quite factorable right now, as soon as anyone gets around to it. The largest cause for it still standing unfactored is that GNFS requires rather more background knowledge than something like cracking DES.
If either RSA-576 or RSA-640 are both still standing three years from now I'll be very surprised; I'd be surprised if even RSA-704 is unfactored three years from now.
Each processor can easily sort its own numbers, but how do you merge the 16 lists?
Using a parallel merge-exchange, perhaps?
Seriously, I've always avoided non-oblivious algorithms as much as possible; I'll admit that you can play games to reduce the communication and memory costs; but even without any memory or communication costs, you still have to pay for your FLOPs.
Most universities expanded dramatically in the 60s... that faculty is retiring over the next five years. Many mathematics departments are losing 40% of their faculty within a five year window.
Jobs are going to be available.
I have no idea how Mr. Computing DPhil arrived at the idea of putting vastly more memory than necessary into a single-processor computer: for example, using a million gigabytes of memory to sort a billion numbers. He is incorrect in claiming that such silly computers are the base for comparison in my paper.
I never suggested that you were comparing against a machine with excessive amounts of memory; I suggested that you were comparing against a single processor which addressed the same amount of memory as would normally be distributed among thousands. In the case of "using a million gigabytes of memory", that was in order to sort a million gigabytes of data; by splitting the petabyte of memory into a million pieces and attaching a cpu to each, one speeds up the sorting by a factor of a million.
Perhaps my argument could best be summarized as this: You're saving memory, but you're not saving MIPS. This technique of yours may make machines cheaper to build because you need less memory per processor, but you still need just as many processors (in fact, slightly more, the way you've described it).
You still need just as many floating-point operations, and the cost of those floating-point operations is enough to put anything beyond 1536 bits out of reach of the NSA for now.
I assume the memory required grows polynomially in these algorithms. Am I wrong?
Yes, you are wrong. The memory traditionally "necessary" grows with the same O( exp(c (ln n)^(1/3) (ln ln n)^(2/3)) ) rate as everything else (except with a different constant c).
I don't know what language we're going to be using 25 years from now, but it's going to be called FORTRAN.
(sorry, someone had to say it.)
The analysis is based on keylength per $ of hardware. It theoretically triples the keylength you can attack per $ spent.
It triples the keylength at the same cost, compared to a serial machine with a huge address space. But nobody was ever considering loading down a Pentium 4 with a few petabytes of memory; instead, people would stick a few gigabytes of memory on each of 10^6 Pentium 4 processors.
All DJB has done is reinvent the idea of scaling processors at the same time as scaling memory when attacking large problems.
Government security angencies have custom codebreaking hardware. We just need someone outside the government to figure out and announce the price tag. Then we'll know what's currently breakable.
If you use an RSA modulus smaller than 768 bits, I will laugh at you. If you use an RSA modulus smaller than 1280 bits, the Russian mafia will laugh at you. If you use an RSA modulus smaller than 1536 bits, the NSA will laugh at you.
Above those points, you're safe, because even if memory were free the cost of the necessary FPUs would be too high.
Hold on. A parallel implementation would normally just give an N times speedup.
Only for a fixed amount of parallelism. DJB is supposing that as the problem gets larger he is increasing the number of FPUs at the same rate as the amount of memory. Which is eminently reasonable, and hardly new.
This isn't really a big deal, nor is it surprising.
Basically, what DJB has done is translated the GNFS from its normal implementation on serial computers (where there is a great deal of available memory, but only one operation is performed at once) into a parallel implementation, where the number of processors more closely matches the available memory.
The "decreased cost" is misleading here, since it is calculated on the assumption that sieving would have been done by a single processor with access to a huge memory... this quite simply was never the case.
There is nothing here to suggest that factoring can be performed using any fewer FLOPS; all that is demonstrated is that by using several processors, each with a smaller memory, you can do better than with a single processor and a giant memory. Which we already knew.
To summarize: DON'T PANIC!
The same thing sometimes happens to the BSDs, where a bug will be fixed (usually in Open) and nobody gets around to integrating the same fix into the others.
It seems to me that much of this could be automated... for each patch which gets added into the xBSD source tree, compare the contexts to the yBSD and zBSD source trees and alert a human if it looks like there's a match.
But for this to be effective, I think that patches would have to have labels attached, since it's really only bug fixes for which this is necessary.
Dear Sir,
It has come to our attention that you maintain a web site operating under the moniker "chillingeffects.org" and through that service are engaged in the provision of legal services.
Since you are not licensed to provide legal services, we respectfully ask that you cease and desist from providing such services.
Respectfully yours,
Joe Q. Lawyer and associates.
[snip rant about subsidized internet access leading to rationing]
Who ever said anything about subsidizing internet access? A government-owned monopoly != a government-subsidized service.
I think that the government should run fiber-optics everywhere, but I also think people should pay to use it. (And that includes ISPs which want to lease fiber; while I think government should be involved in providing the raw fiber I am far from convinced that they should get involved in IP packet switching.)
Roughly speaking (and this is overly simplistic, I know), hooking up 422 towns just means having 422 times the amount of cable.
How do you figure that? Last time I looked at the question, the amount of cable it takes to connect N random points within a given region scales as approximately O(sqrt(N)). IOW, the cost would be cut by approximately a factor of 20.
Can't you just hear it coming: "The voting taxpayers has paid to build this information superhighway so therefore the community should have some say as to the things that are allowed to be sent over this highway. [...]"
I'm certain that some people would make such arguments. But are those arguments any more valid than would be arguments asserting that pornographic magazines should not be distributed via a publicly funded and owned highway system?
Public policy should be decided on the basis of what is right, not on the basis of the invalid arguments which might arise from such policy.
I fail to see how broadband internet access can be called a natural monopoly
The cost of connecting 422 small towns is vastly smaller than 422 times the cost of hooking up one small town.
From a public policy perspective, I don't understand why there aren't more governments doing this. It is generally accepted that governments should provide and maintain a highway system; how is internet connectivity any different?
There are many things which governments get involved with (eg health care) which I think they should stay out of as much as possible; but when it comes to natural monopolies I certainly see that they have a role to play.
However, Road Runner can choose to discard mail because there are too many occurences of the letter "q," it's in all caps, or it was received at 7:31 PM.
IANAL, but I don't think you're right here. They probably have enough verbiage in their contract to cover this (of course, much of it wouldn't be legally enforceable...), but you might be able to hinge a case on the creation of reasonable expectation that email would not be arbitrarily blocked.