From: tcmay@got.net (Timothy C. May)
Date: Mon, 15 Apr 1996 11:18:15 +0800
To: Jack Mott <cypherpunks@toad.com
Subject: Re: key bit lengths
Message-ID: <ad96d54106021004da68@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


At 5:59 PM 4/14/96, Jack Mott wrote:
>In Applied Crypto, it talks about thermodynamic limitations of brute
>force attacks.  I did some calculations and it looks like it will take,
>given a perfectly effecient computer, the combined energy of 509,485,193
>average supernovas to brute force a 256 bit key. I was just wondering if
>there are any theoretical ways around this. I am just talking about
>plain brute force here, not attacking other weaknesses.

By "perfectly efficient" do you mean a computer which dissipates (uses) a
kT per logical operation? If so, then calculations are easy to do.

However, there are two theorized alternative approaches. First,
disssipationless or "reversible" computing, a la Landauer, Bennett,
Toffoli, Fredkin, Merkle, et. al. If actually feasible (and some of us are
skeptical), then computation could be done with much less energy per
logical operation than kT.

Second, quantum computation, a la Deutsch, Shor, Bennett, et. al. (Yes,
some of the same players.) See the work on quantum factoring.

As with reversible computing, the energy consumption may be vastly less
than the kT per logical operation usually considered to be the lower bound
on energy needed.

As I said, I am skeptical. Interested readers may want to track down
several references:

-- "Workshop on Physics and Computation," Proceedings, 1992, put out by the
IEEE.

-- a Santa Fe Institute publication, "Complexity, Entropy, and the Physics
of Information," ed. W. Zurek.

I have more references and discussion in my Cyphernomicon.

--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^756839 - 1  | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."