no possible brute force Was: Cruising the stacks and finding stuff

[Alexander Klimov]

On Tue, 22 Apr 2008, Leichter, Jerry wrote:
> Interestingly, if you add physics to the picture, you can convert
> "no practical brute force attack" into "no possible brute force
> attack given known physics".  Current physical theories all place a
> granularity on space and time:  There is a smallest unit of space
> beyond which you can't subdivide things, and a smallest unit of
> time.

I guess you are talking about Planck units, so let's make the
calculations:

 Planck length is L = \sqrt{hbar G / c^3} ~ 1.6E-35 m,

 Planck time T = L/c ~ 5.4E-44 s,

so a cubic-meter-computer can have

 N = (1/L)^3 ~ 2.4E104 elements

and thus

 N/T ~ 4.5E147 operations per second

that is approximately 2^{490} operations per second in a cubic meter
of "Planck computer". Given a year (3.15E7 s) on a Earth-size
(1.08E21 m^3) Planck computer we can make approximately 2^{585}
operations.

OK, it was amusing to do these calculations, but does it mean
anything? I think it is more like garbage-in-garbage-out process.

If I understand correctly, L and T are not non-divisible units of
space-time, but rather boundaries for which we understand that our
current theories do not work, because this scale requires unification
of general relativity and quantum mechanics.

Even more bizarre is to think about the above "processing element" as
representing a single bit: according to quantum mechanics, states of a
system are represented by unit vectors in associated Hilbert space of
the system and each observable is represented by a linear operator
acting on the state space. Even if we have only two qubits they are
not described by two complex numbers, but rather by 4:

 a_0|00> + a_1|01> + a_2|10> + a_3|11>

and thus description of the state of quantum registers requires
exponential number of complex numbers a_i and each operation
simultaneously process all those a_i. Since we cannot measure
them all, it is an open question whether quantum computations
provide exponential speed-up and all we know right now is that
they give at least quadratic one.

By the way, if you have a computer with the processing power larger
than that of all the cryptanalysts in the world, it makes sense to use
your computer to "think" to find a better attack than a brute-force
search :-)

> One place this shows up, as an example:  It turns out give a volume
> of space, the configuration with the maximum entropy for that volume
> of is exactly a black hole with that volume

[OT] This is a strange thesis because all black hole solutions in
general relativity can be completely characterized by only three
externally observable parameters: mass, electric charge, and angular
momentum (the no-hair theorem) and thus in some sense they have zero
entropy (it is not necessary a contradiction with something, because
it takes an infinite time for matter to reach the event horizon).

> and its entropy turns out to be the area of the black hole, in units
> of square Planck lengths.

[OT] Although Hawking showed that the total area of the event horizons
of a collection of black holes can never decrease, which is *similar*
to the second law of thermodynamics (with entropy replaced by area),
it is not clear that it allows to conclude that area *is* entropy.

-- 
Regards,
ASK

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com