CDR: Re: why should it be trusted? (NP-Completeness, cracking speed)

[Ryan McBride]

On Thu, 19 Oct 2000, Bill Stewart wrote:

> At Tue, 17 Oct 2000 17:39:13 -0700 Nathan Saper <natedog at well.com> wrote
> Unless I'm mistaken, there is no essential physical law that 
> determines computing power, exploits of algorithms, etc.  
> The same cannot be said for speed-of-light travel.
> 
> Data storage probably requires at least an atom, or at least one
> electron, or at least one quark. There are only so many spare ones of
> these in the universe. 

Yes, you do need at least one, but perhaps you _only_ need one. Check out
the story in EETimes at http://www.eet.com/story/OEG20000831S0019

> There have also been calculations on energy requirements for
> computation (don't remember the rationale; probably in Schneier 2nd
> Ed.)

<sigh> People seldom read the errata for books. 

>From http://www.counterpane.com/ac2errv30.html:

* Page 157: The section on "Thermodynamic Limitations" is not quite
correct. It requires kT energy to set or clear a single bit because these
are irreversible operations. However, complementing a bit is reversible
and hence has no minimum required energy. It turns out that it is
theoretically possible to do any computation in a reversible manner except
for copying out the answer. At this theoretical level, energy requirements
for exhaustive cryptanalysis are therefore linear in the key length, not
exponential.

-Ryan

--
Ryan McBride - mcbride at countersiege.com
Systems Security Consultant
Countersiege Systems Corporation - http://www.countersiege.com