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