Ultimate limits to computation

[Jerry Leichter]

On Aug 11, 2009, at 2:47 PM, Hal Finney wrote:

> [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 at al-qaeda.net
> Date: Wed,  4 Aug 2004 11:04:15 -0700 (PDT)
> From: hal at 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  
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 at metzdowd.com