The strengths of various cryptographic primitives are often explained (though not defined) in terms of how long it would take to break under the current best known attacks. For example, apparently the best known attack against AES-128 reduces it to ~126 bits of security, and that is often explained as "good enough" because even if one were to use all the world's computers together it would still take hundreds of years to break a single key. Assuming (perhaps ridiculously) for the purpose of this question that the current best known attack against some algorithm is actually the best possible attack, this still doesn't seem like quite enough because what if we develop new technologies that let us try combinations faster?

Perhaps this is a ridiculous idea, but for peace of mind it would be nice to know that no one could ever break my ciphertexts (under current best known methods). As far as I can tell, there is only one fundamental limit to the ability to "just try combinations faster," and that's Landauer's principle. According to Wikipedia, Landauer argued that the minimum possible energy required to erase one bit is $kT ln(2)$ where $T$ is the temperature in Kelvin and $k$ is the Boltzman constant. I would like to compare this to the total entropy of the observable universe. According to the linked paper, this is estimated at $\sim 10^{105}k$, although the entropy of the cosmic event horizon is bigger, estimated at $\sim 10^{122} k$, and I don't know nearly enough physics to know what that means so I'm going to use the bigger one.

So it seems, naively, like we should be able to get the total number of possible bit erasures before the universe runs out of entropy, $N$, with the simple equation $NkT ln(2) \leq 10^{122}k$ and get $N \approx 10^{122}$ (assuming that $T \approx 2.7$ due to cosmic background radiation).

Now assume that we have some hash function $H$ that is assumed to have $n$ bits of security under either classical or quantum attack. As far as I understand, this means you have to do at least as much work as running the hash function $2^n$ times. It appears that such a hash function cannot be computed with reversible computing. As such, it seems safe to assume that you must use at least one bit of entropy (or equally erase one bit of information) per run of the hash function, for a total of at least $2^n$ bits. If we let $2^n \gt N \approx 10^{122}$, we get $n \gt \sim 405$, and seem to show that under the security assumption, it is impossible to break $H$ within the life of the universe if $n$ is greater than, for good measure, 410.

So, finally, my question is this: is this analysis correct? Can we really bound entropy consumed based on the "hardness" of the cryptographic problem? (Obviously, it would be off-topic here to talk about the details of the physics behind the problem.)

  • $\begingroup$ I apologize if this is off-topic here, and I totally understand if it needs to get reworked to be on-topic here, or if it ends up getting moved or closed. $\endgroup$ Mar 12, 2016 at 19:31
  • $\begingroup$ related answer $\endgroup$
    – SEJPM
    Mar 12, 2016 at 19:45
  • 1
    $\begingroup$ @SEJPM Thank you! In fact, it appears that basically answers my question. It seems that the only step left is between a supernova and the universe, and that's a physics question. $\endgroup$ Mar 12, 2016 at 19:52


Browse other questions tagged or ask your own question.