[Note subject line change] Jerry Leichter writes:

...

Since people do keep bringing up Moore's Law in an attempt to justify larger keys our systems "stronger than cryptography," it's worth keeping in mind that we are approaching fairly deep physical limits. I wrote about this on this list quite a while back. If current physical theories are even approximately correct, there are limits to how many "bit flips" (which would encompass all possible binary operations) can occur in a fixed volume of space-time....

Things may not be quite as favorable as this. Here is a posting I made to cypherpunks in 2004:

To: cypherpunks@al-qaeda.net Date: Wed, 4 Aug 2004 11:04:15 -0700 (PDT) From: hal@finney.org ("Hal Finney") Subject: Re: On what the NSA does with its tech

MV writes:

...

Yes. They can't break a 128 bit key. That's obvious. ("if all the atoms in the universe were computers..." goes the argument).

Not necessarily, if nanotechnology works. 128 bits is big but not that big.

Eric Drexler, in Nanosystems, section 12.9, predicts that a nanotech based CPU fitting in a 400 nm cube could run at 1000 MIPS and consume 60 nanowatts, performing 10^16 instructions per second per watt.

Let's design a system to break a 128 bit cipher. Let's suppose it has to do 2^10 instructions per test, so this is 2^138 instructions total, or about 10^41. Let's let it run for four months, which is 10^7 seconds, so our necessary processing rate is 10^34 instructions per second.... It must be the summer weather or something. I've received a whole bunch of messages - mainly privately - that say either "Here's another result that has a higher upper bound on computation" or "Here's a design for a machine that exceeds your bound". Both ignore (a) how bounds work: That fact that you have a weaker bound doesn't mean I don't have a stronger one; (b) that impossibility results can exist in

On Aug 11, 2009, at 2:47 PM, Hal Finney wrote: physics, not just in mathematics. True, the nature of such results are a bit different, since all our current physical theories might turn out to be wrong. But, hey, maybe our understanding of computation or even mathematics has some fundamental flaw, too. The estimate on the limits to brute-force search are mine, based on a *very* rough estimate that draws on the results in the following paper: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TVM-46X8Y6W-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=976695769&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d98e72ef5fe3301fead2dbc93c2885e4 (I haven't actually read the paper; my analysis was based on an article I can't find that discussed the implications of this one.) The basic summary of the author's result is: "[T]he total number of bits and number of operations for the universe does not exceed O(10^123)." I guessed about how this value scales (as the cube of the time - one factor for time, two for the size of the light sphere you can reach in that time; not 3 because the information content of space goes up as the area, *not* the volume - a very weird but by now standard result). Now, my scaling technique may be completely flawed, or my computations may be wrong. Or the paper could be wrong. (I wouldn't bet on it.) Or the physics may be wrong. (I *really* wouldn't bet on that.) But the fact that there are other bounds around that are not as tight, or that one can describe a machine that would do better if there were a way to realize it, aren't evidence for any of these. Bounds can be improved, and a description isn't a working machine. In fact, the whole point of the article that I *did* read is that this result should make use re-examine the whole notion of a "possible" computation. It's easy to describe a computation that would take more than 10^123 steps. Ackerman's function exceeds that for pretty small input values. We've traditionally said that a computation is "possible" if we can describe it fully. But if it couldn't be realized by the entire universe - is that really a *useful* notion of "possible"? -- Jerry --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE