Landauer's Principle vs. Classical Computability

In the quest for a more secure hash or encryption algorithm, the question naturally arises, how many key bits are enough? Is there a key which is physically impossible to crack?

The short answer is "it depends on whether P=NP". Even then, some algos will be weaker than others, meaning that they would require longer keys to achieve comparable security.

There is, however, a physical limitation here which is informative, namely, the number of bits which we could possibly flip on the way to discovering a solution. Landauer's Principle tells us that the minimum amount of energy required to flip a bit (at least, in a classical computer) is:

---

kT ln 2

---

where "where k is the Boltzmann constant (approximately 1.38×10−23 J/K), T is the temperature of the circuit in kelvins, and ln 2 is the natural logarithm of 2 (approximately 0.69315)", according to Wikipedia.

But what about this "circuit temperature"? Considering that the average temperature of the universe is not less than that of the microwave background, or about 3 kelvin, we already have a lower limit on the energy expenditure required, which is about 3x10^(-23) joules. (You could use a cryostat to achieve a lower temperature, but it wouldn't help you, because you would just heat up the universe elsewhere.)

And just how much energy is available to expend? Definitely not more than the total energy of the universe, which WolframAlpha puts at 2x10^69 J. (This value includes the energy equivalent of the mass of the universe, via Einstein's famous equation, E=mc^2. Nonetheless, it's obviously subject to considerable error, and probably fails to account for the vaccuum energy, dark energy, and who knows else. Still, this is a logarithmic analysis, so we can afford to be somewhat cavalier.)

The ratio of these energies is then about 7x10^91. The log to base of 2 of this value is about 305.

What this means, then, is that the longest key need only be 305 bits, because we couldn't count to a larger number, given all the energy in the universe. This upper bound is only valid, of course, if we assume that the fastest way to crack a given algo is to try every key. (We would likely need try only half the keys, so the key should be 306 bits long. Whatever.)

The other question is whether Landauer's Principle pertains to quantum computers, and more importantly whether a useful quantum computer can be constructed. I suspect that the answers are no (because quantum computations are required to be reversible, whereas the above analysis pertains to the opposite, and fundamentally because the Heisenberg Uncertainty Principle allows quantum systems to "borrow" energy) and yes (because it's "only" an engineering problem). So perhaps this upper bound of 306 bits is just a thermodynamic fantasy.

At best, it appears from the literature that a quantum computer can square root the complexity of a given algo (and sometimes cannot help at all). If this concept relates to energy expenditure as well, then perhaps the equivalent limit for quantum computation would be 612 bits. But I have no idea...