[Cryptography] Low grade randomness for padding.

Jerry Leichter leichter at lrw.com
Fri Feb 12 21:51:34 EST 2021


> 
>> I made a back-of-the-envelope computation on this list a number of years
>> back that showed a physical limit on exhaustive search, based on a bound
>> one can get on the number of bit flips that physics allows in a given
>> volume of space-time....
> 
> Are you sure about this?...
> 
> The following page suggests that hardware is another factor of 1000 away
> from the Landauer limit:
> 
> https://www.lesswrong.com/posts/N7KYWJPmyzB6bJSYT/the-next-ai-winter-will-be-due-to-energy-costs-1
> 
> so it looks like, if we were to completely cover the planet in solar panels
> and use that energy for bitcoin mining at the Landauer limit, we'd be able
> to manage 10^30 hashes per second.
> 
> The (much higher) physical limit on computation is this one by Bremermann,
> which suggests that we're safe against 512-bit brute-force but not against
> 256-bit brute-force:
> 
> https://en.wikipedia.org/wiki/Bremermann%27s_limit
There are a whole bunch of limits one can place.  I'd have to go find my many-year-old-post, but it was based on a paper that looked at how many "state changes" could have occurred since the big bang, combined with some really rough approximations I made that I would not want to defend.  Again, details forgotten, but I believe this was a computation related to the number of distinct quantum states that can exist in a given volume, which (unexpectedly) is proportional to the area, not the volume.

In any case, the point is that physics in the universe in which we live places bounds on computational power, which while they may seem absurdly high, are not actually that high relative to some particular problems - like exhaustive search of quite realistic key spaces.  It's an interesting philosophical point whether a computation that cannot be achieved in our physical universe is "in principle" achievable.

                                                        -- Jerry



More information about the cryptography mailing list