On Wed, 23 Apr 2008, Alexander Klimov wrote:
| Date: Wed, 23 Apr 2008 12:53:56 +0300 (IDT) | From: Alexander Klimov <[EMAIL PROTECTED]> | To: Cryptography <cryptography@metzdowd.com> | Subject: no possible brute force Was: Cruising the stacks and finding stuff | | 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. Except that this doesn't quite work. You can't actually have anywhere near that many distinct states in that volume of space. The physics does indeed get bizarre here: The maximum number of bits you can store in a given volume of space is determined by that space's *surface area*, not its volume. So you actually "only" get around 1E70 elements and 4.5E112 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. Kind of. | 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. For simple search problems, where there are no shortcuts and you really can only do brute force, quadratic is the best you can do. | 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 :-) Of course. But the mice are already running that computation. | > 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). You're looking at this backwards. Suppose I want to store a large amount of data in a given volume of space. To be specific, I have a unit diameter sphere in which to build my memory device. Initially, I fill it with magnetic domains, and see how many distinct bits I can store. That gets me some huge number. I replace that with racetrack-style memory, with information on the edges of the domains. Then with single electrons, with bits stored in multiple quantum states. Can I keep going indefinitely? The answer is no: There is in fact a limit, and it turns out to be the number of bits equivalent to the entropy of a black hole with a unit diameter sphere. The entropy isn't given by the number of measurements I can make on my black hole - it's given by the number of possible precursor states that can produce the given black hole. In fact, if you try to shove that much information into your initial volume, you will inevitably produce a black hole - not a good idea if what you want is a storage device, since the data will be there in some sense, but will be inaccessible! | > 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. The actual computation requires using either string theory or loop quantum gravity or, presumably, some other theory that combines GR and QM. The entropy is proportional to the area by very general arguments, but to figure out the units, you have to make some more assumptions. According to the "Black Hole Thermodynamics" article in Wikipedia, string theory implies that the units are exactly the Planck length squared, while loop quantum gravity makes it proportional to the single free parameter in that theory. No one really understands what this means in any deep sense. It certainly doesn't say that a Planck-length x Planck-length square is "a minimal bit" in any physical sense. That's just a suggestive interpretation. If it were even approximately true ... that's a 2-d "object". Why can't I just stack a whole bunch of them in an arbitrary volume? What is important is the profound general principle that's emerged from 70 years or so of work on QM, which physicists now take for granted but hasn't really made it into the general conciousness: The universe is a fundamentally finite thing. The amount of information that can be "embedded" into any finite volume of space and time is bounded. (Note that in Newtonian mechanics, or in GR, the value of even the single gravitational field is given by a real number at every point in space and time, so an arbitrarily small volume of space-time can "hold" an arbitrary amount of information. This is not the case in QM; in fact, it's inherently incompatible with it. See the Bekenstein Bound.) Given this and a limit on the speed at which information can propagate, that there are fundamental physical limits on any computation follows. "All the rest is just detail." :-) -- Jerry --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]