Slashdot | 3D Microfluid Computers Used To Solve NP Problems
http://slashdot.org/articles/01/03/24/1840252.shtml -- ____________________________________________________________________ If the law is based on precedence, why is the Constitution not the final precedence since it's the primary authority? The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 24 Mar 2001, Jim Choate wrote:
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
At 09:58 PM 03/24/2001 -0800, Ray Dillinger wrote:
On Sat, 24 Mar 2001, Jim Choate wrote:
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.
participants (3)
-
Bill Stewart -
Jim Choate -
Ray Dillinger