Re: CDR: Slashdot | 3D Microfluid Computers Used To Solve NP Problems
At 09:58 PM 03/24/2001 -0800, Ray Dillinger wrote: On Sat, 24 Mar 2001, Jim Choate wrote: http://slashdot.org/articles/01/03/24/1840252.shtml Cryptographically interesting. It looks like starting now, the highest-end threat facing a cryptosystem involves liters of fluid performing molecular computation. Cryptographically *un*interesting. [Good discussion of key lengths, deleted...] The microfluid computers were solving small instances of NP problems; larger volumes would let them solve larger instances, but not blazingly large, though you could get respectably large by using an ocean-full of the stuff. That gets you a few extra bits of solution. But it's not solving general-purpose computing - it's solving specialized problems which may be somewhat useful for small instances of NP-hard problems, so it may be useful for possibly-NP-hard problems like factoring and discrete logs. Adding a few bits of key length to those problems is less annoying than adding them to most symmetric-key algorithms, where there's more likely to be structure to the key length (e.g. adding a few key bits to RC4 is no problem, as long as you're below 255, but adding them to DES doesn't work.) Judging from the abstract, it's still cool stuff, even if it's not all that practical.
Re: CDR: Slashdot | 3D Microfluid Computers Used To Solve NP Problems
purposes. There are about 2^167 atoms in planet earth, about 2^30 nanoseconds per second, and 2^39 seconds till the ^ Most proofs of security have a problem, this one was just easy to spot :-) __ Do You Yahoo!? Get email at your own domain with Yahoo! Mail. http://personal.mail.yahoo.com/
Re: CDR: Slashdot | 3D Microfluid Computers Used To Solve NP Problems
On Sun, 25 Mar 2001, Morlock Elloi wrote: purposes. There are about 2^167 atoms in planet earth, about 2^30 nanoseconds per second, and 2^39 seconds till the ^ Most proofs of security have a problem, this one was just easy to spot :-) Groan. Right you are, that is serious doofus mode. However, it only throws the estimate off by ten bits, and I picked up almost thirty when I rounded it up to 256 bits. The point that currently-available key lengths are adequate to deal with the problem stands. Bear
Re: CDR: Slashdot | 3D Microfluid Computers Used To Solve NP Problems
On Sat, 24 Mar 2001, Jim Choate wrote: http://slashdot.org/articles/01/03/24/1840252.shtml Cryptographically interesting. It looks like starting now, the highest-end threat facing a cryptosystem involves liters of fluid performing molecular computation. The kick is that these molecular computers aren't all that hard to design and they scale. Which means someone can have a 1000-liter computer with somewhere near the same ease they can set up a milliliter computer. So we need to revise the recommended key lengths for security purposes. There are about 2^167 atoms in planet earth, about 2^30 nanoseconds per second, and 2^39 seconds till the next ice age. So, if a tenth of that mass were made into ten-atom computing units that could complete a calculation every ten nanoseconds, I get about 2^226 operations before the next ice age. Assuming each is a brute-force check, we should probably be looking at symmetric ciphers with keys a minimum of 225 bits long right about now. Round up to the nearest handy power of 2 and make it 256 bit keys. Fortunately, the AES, and several other recent symmetric ciphers, have a use for a 256 bit key. Unless they find some radical flaw in AES Co, I don't see a real problem posed by molecular computing; we just need to start taking it into account when we decide what key length to use. Bear
